TP : Map-Reduce en python

Auteurs

Objectifs

Le TP est composé de 3 parties:

  • D’abord, une partie tutorial, qui permet d’installer l’ensemble des fichiers nécessaires pour développer les programmes avec python.
  • Ensuite, la seconde partie permet de vérifier votre compréhension des principes de la programmation map-reduce sur différents jeux de données.
  • Enfin, la dernière partie permet d’aller plus loin…

Dans ce TP, on considère que vous disposez de connaissances avancées en python, et d’une distribution de python sur votre ordinateur (à Centrale Lyon, on utilise Anaconda).

Table des matières


Partie 1 : Tutorial wordcount

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

Preparation

  • 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 (phase dite de shuffling and sorting, traduction: mélange et tri).
    • 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.

Worldcount 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 (e.g. ‘youth’ vs ‘Youth’).

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

Partie 2 : Fichier de ventes

Préambule: 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.

Presentation 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 : 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 à traiter :

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


Partie 3 : Pour aller plus loin

Voici plusieurs sujets à traiter.

Anagrammes

É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 cette liste:

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

La sortie ne devra afficher que les réponses avec au 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.

Dictionnaires de mots Pour vos tests intensifs, vous pourrez utiliser

mais faites attention aux voyelles accentuées de la langue française.

Aide au Scrabble

Étant donné un dictionnaire de mots, é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, avec les dictionnaire words_alpha, le programme doit renvoyer :

0.75 [painty]

0.625 [pinta, patin, paint, inapt]

…

Parseur de fichier de Logs

Étant donné ce fichier de 100000 logs provenant d’un serveur, écrire un script map-reduce qui génère des statistiques mensuelles, comme

  • le nombre d’accès par mois
  • l’adresse IP qui a fait le plus grand nombre d’accès durant le mois…

Multiplication de matrices

Écrivez un script map-reduce permettant de réaliser la multiplication de 2 (grosses) matrices, à partir de leur fichiers matriceA.txt et matriceB.txt.

Pour générer des matrices, vous pouvez utiliser ce script python. Celui-ci - crée 2 matrices avec des nombres entiers aléatoires et les stocke dans deux fichiers : matriceA.txt et matriceB.txt; - affiche le résultat de leur multiplication.

Contrôlez que le résultat obtenu par votre algorihtme est bien le même que celui affiché par le programme matrice.py.