TP : Map-Reduce en Python

Auteurs

• Stéphane Derrode & Lamia Derrode, Centrale Lyon, Dpt Mathématiques & Informatique

Objectifs

Le TP est composé de 3 parties :

• D’abord, une partie tutoriel qui permet de prendre en main les fichiers nécessaires pour développer des programmes map-reduce en Python.
• Ensuite, la seconde partie permet de vérifier votre compréhension des principes de la programmation map-reduce sur un fichier de données réelles.
• Enfin, la troisième partie propose des exercices pour aller plus loin.

Dans ce TP, on considère que vous disposez de connaissances avancées en Python et d’une installation Python 3 sur votre ordinateur.

Organisation de la séance

Partie	Durée conseillée	Contenu
Partie 1	~1h	Prise en main du pipeline map-reduce sur Dracula
Partie 2	~1h30	Analyse d’un fichier de ventes réel (4 millions de lignes)
Partie 3	~1h30	Exercices avancés au choix

Table des matières

• Partie 1 : Tutoriel wordcount
  • Préparation
  • Wordcount improvement!
• Partie 2 : Fichier de ventes
  • Présentation du fichier
  • Questionner le fichier de ventes
• Partie 3 : Pour aller plus loin
  • Anagrammes
  • Aide au Scrabble
  • Parseur de fichier de logs
  • Multiplication de matrices

Partie 1 : Tutoriel 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 fichier 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 lancez-le. Observer, dans le répertoire de travail, la création de 3 fichiers texte :

  • resultmapper.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).

Le script met en œuvre le pipeline suivant, qui émule le comportement de Hadoop sur une seule machine :

fichier texte
     │
     ▼
 [ mapper ]  ──────►  resultmapper.txt
                              │
                              ▼
                         [ sort ]  ──────►  resultmappersorted.txt
                                                      │
                                                      ▼
                                               [ reducer ]  ──────►  resultreducer.txt

• Télécharger d’autres livres au format texte sur textfiles.com et adapter le script pour qu’il fonctionne sur ces fichiers.

Wordcount improvement!

En analysant le résultat du précédent algorithme, on constatera que le comptage de mots n’est pas très satisfaisant : les tirets, 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.

Piste

Le module string expose string.punctuation (liste de tous les signes de ponctuation). La méthode str.translate() combinée à str.maketrans() permet de les supprimer d’une chaîne sans boucle explicite.

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 modifier 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 : purchases10000.txt (511 Ko).

Conseil : commencez vos tests avec purchases10000.txt, puis validez votre solution sur le fichier complet.

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. Pour chacune, réfléchissez d’abord à quelles colonnes du fichier constitueront la clé et la valeur de votre mapper, avant d’écrire le code.

1. Quelle est la somme totale dépensée pour chaque catégorie d’achat ?
   Format de sortie attendu : une ligne par catégorie, triée, avec la somme totale.

2. Dans quelle ville la catégorie Women’s Clothing a-t-elle permis de générer le plus d’argent Cash ?
   Format de sortie attendu : le nom de la ville gagnante avec le montant correspondant.

   Indice

   Cette question nécessite deux passes map-reduce : la première calcule le total par ville (filtré sur la catégorie et le moyen de paiement), la seconde identifie la ville au montant maximum.

3. À quelle heure les clients dépensent-ils le plus ?
   Format de sortie attendu : une ligne par tranche horaire avec le montant total, e.g. “entre 16h et 17h : 2 345 678 €”.

Partie 3 : Pour aller plus loin

Voici plusieurs sujets à traiter, par ordre de difficulté croissante. Vous n’êtes pas obligés de tous les traiter : privilégiez la qualité d’un exercice bien compris à la quantité.

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.

Cadrage map-reduce : Quelle représentation d’un mot, indépendante de l’ordre de ses lettres, pourrait servir de clé dans le mapper ? (Il en existe plusieurs : certaines sont plus simples à calculer, d’autres plus efficaces.)

Dictionnaires de mots Pour vos tests intensifs, vous pourrez utiliser :

• le fichier (de langue anglaise) : words_alpha.txt
• ou le fichier (de langue française) : Liste-de-mots-francais-Gutenberg

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 ensemble.

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

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

Cadrage map-reduce : Cet exercice est une extension du précédent. La difficulté supplémentaire est de vérifier qu’un mot du dictionnaire est constructible à partir des lettres disponibles — sans forcément les utiliser toutes. Réfléchissez à comment encoder cette contrainte dans la clé ou la phase de filtrage du reducer.

Parseur de fichier de logs

Étant donné ce fichier de 100 000 logs provenant d’un serveur web, é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 chaque mois.

Format d’une ligne de log (format Apache Combined Log) :

192.168.1.42 - - [14/Apr/2023:08:32:11 -0700] "GET /index.html HTTP/1.0" 200 2326

Cadrage map-reduce : Quelle information extraire de chaque ligne pour constituer la clé du mapper ? Comment formuler deux questions différentes avec deux scripts map-reduce distincts ?

Multiplication de matrices

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

Pour générer des matrices de test, utiliser le script matrice.py. Celui-ci :

• crée 2 matrices avec des nombres entiers aléatoires : A de taille 20×10 et B de taille 10×15, et les stocke dans matriceA.txt et matriceB.txt ;
• affiche le résultat de leur multiplication A × B (taille attendue : 20×15).

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

Cadrage map-reduce : La multiplication matricielle C = A × B se définit par C[i,j] = Σₖ A[i,k] × B[k,j]. Réfléchissez à comment encoder les indices (i, j, k) dans la clé du mapper pour que le reducer reçoive, pour chaque case (i,j) de C, tous les termes du produit à sommer.