Sommaire

TP MapReduce en Python

Le TP est composé de 3 parties:

  • D’abord, une partie tutorial, qui vous permet d’installer l’ensemble des fichiers nécessaires pour développer les programmes Python.
  • Ensuite, la seconde partie vous permet de vérifier votre compréhension des principes de la programmation map-reduce sur différents jeux de données.
  • Puis, la troisième partie consiste à trouver tous les anagrammes d’un dictionnaire de mots ! Par exttension, on proposera ensuite un système de triche au Scrabble !

A noter que ce TP considère que vous disposez de connaissances avancées en Python, et que vous avez installé sur votre ordinateur une distribution de Python. La distribution utilisée à l’École Centrale de Lyon est Anaconda.

Créer un répertoire de travail sur votre machine, dans lequel vous stockerez les fichiers nécessaires au TP.

Partie 1 : Tutorial wordcount

Nous allons ici faire fonctionner l’algorithme map-reduce qui compte les mots d’un fichier texte (vu en cours).

Préparation

  • Sauvegarder le fichiers dracula dans votre espace de travail. Ce fichier contient le livre dracula, libre de droits.
  • Sauvegarder également le fichier wordcount_mapreduce.py dans votre espace de travail.
  • Analyser le script et lancer-le.
  • Observer, dans le répertoire de travail, la création de 3 fichiers texte :
    • resultmapperer.txt : le résultat du mapper.
    • resultmappersorted.txt : le résultat du mapper après tri par ordre alphabétique selon les clés.
    • resultreducer.txt : le résultat du reducer (et donc le résultat final).
  • Télécharger d’autres livres au format texte sur textfiles.com et adapter le script pour qu’il fonctionne sur ces fichiers.

wordcount improvment!

En analysant le résultat du précédent algorithme, on constatera que le comptage de mots n’est pas très satisfaisant : les côtes, les points de terminaison, les guillemets ou les virgules viennent corrompre le résultat ! Notez également que le programme précédent distingue les mots en majuscule des mots en minuscule (eg. ‘youth’ vs ‘Youth’).

A faire : Modifier le programme précédent pour qu’il corrige ces comportements inappropriés (consultez Internet pour trouver un moyen de supprimer les signes de ponctuation d’une chaîne de caractères représentant un mot).

Partie 2 : Fichier de ventes

Pour répondre à cet exercice, pensez à sauvegarder le script original wordcount_mapreduce.py sous un nouveau nom (ventes.py par exemple) : il vous suffira alors de changer uniquement la partie algorithmique et les noms des fichiers d’entrée et de sortie.

Présentation du fichier

Télécharger le fichier purchases.txt (211 MO !) dans votre espace de travail. Il contient 4 138 476 lignes ! Une version réduite à 10 000 lignes est téléchargeable ici pour vos essais : purchases10000.txt (511 KO).

Le fichier est organisé en 6 colonnes :

  • date (format YYYY-MM-DD);
  • heure (format hh:mm);
  • ville d’achat;
  • catégorie de l’achat (parmi Book, Men’s Clothing, DVDs…);
  • somme dépensée par le client;
  • moyen de paiement (parmi Amex, Cash, MasterCard…).

Les colonnes sont séparées par une tabulation. Ce caractère est codé par \t en Python.

Questionner le fichier de ventes

Voici une liste de questions que vous pouvez aborder dans l’ordre (ou non !) :

  1. Quel est le nombre d’achats effectués pour chaque catégorie d’achat ?
  2. Quelle est la somme totale dépensée pour chaque catégorie d’achat ?
  3. Quelle somme est dépensée dans la ville de San Francisco dans chaque moyen de paiement ?
  4. Dans quelle ville la catégorie Women’s Clothing a permis de générer le plus d’argent Cash ?
  5. À quelle heure les clients dépensent-ils le plus ? Type de réponse attendue : “entre 16h et 17h” par exemple.

Partie 3 : Anagrammes et jeu du Scrabble

Annagramme

Étant donné un fichier de mots, écrire un script map-reduce qui détecte les mots ayant EXACTEMENT les mêmes lettres (mais dans un ordre différent), et le même nombre de lettres (le mot ‘a’ est donc différent du mot ‘aa’).

Ainsi, par exemple, le fichier de mots suivant

melon barre deviner lemon
arbre fiable fable vendre
devenir faible barbe

donnera en sortie ce résultat :

faible, fiable
arbre, barre
devenir, deviner
lemon, melon

La sortie ne devra afficher que les réponses avec aux moins 2 mots. Dans cet exemple, les mots fable ou barbe n’apparaissent pas car ce sont les seuls mots de la liste avec ces lettres.

L’algorithme ne devra pas tenir compte de la présence éventuelle de majuscules dans les mots.

Pour vos tests, vous pourrez utiliser le fichier de mots words_alpha.txt.

Tricher au jeu de Scrabble

Étant donné un dictionnaire de mots (p. ex words_alpha.txt), écrire un script map-reduce qui donne tous les mots du dictionnaire que l’on peut construire avec une suite de 8 lettres donnée. La liste de mots devra être triée par ordre décroissant du nombre de lettres utilisées (un score entre 0 et 1 pourra être utilisé à cet effet), et les mots anagrammes listés ensembles.

Par exemple, si la suite de 8 lettres est bnaitypi, le programme doit renvoyer :

0.75 [painty] 0.625 [pinta, patin, paint, inapt]
0.625 binit
0.625 taipi
…