Aller au contenu

TP : Map-Reduce en Python

Auteurs

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

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.

Auto-évaluation — résultat attendu sur Dracula

Après nettoyage (passage en minuscules + suppression de la ponctuation), votre programme doit produire 9 719 mots distincts pour 161 057 occurrences au total.

Les 20 mots les plus fréquents :

Rang Mot Occurrences
1 the 7 882
2 and 5 902
3 i 4 796
4 to 4 462
5 of 3 610
6 a 2 914
7 he 2 569
8 in 2 498
9 that 2 470
10 it 2 152
11 was 1 878
12 as 1 589
13 we 1 542
14 for 1 532
15 is 1 499
16 his 1 473
17 me 1 452
18 not 1 398
19 you 1 392
20 with 1 285

Si vous obtenez Youth et youth séparément, ou si the, apparaît, votre nettoyage est incomplet.

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.

    Auto-évaluation (sur purchases.txt complet, 4 138 476 lignes)

    18 catégories, totaux remarquablement homogènes (~57 millions chacune — le fichier est manifestement synthétique). Les 5 plus grosses :

    Catégorie Total dépensé
    DVDs 57 649 212,14 €
    Children’s Clothing 57 624 820,94 €
    Men’s Clothing 57 621 279,04 €
    Sporting Goods 57 599 085,89 €
    Garden 57 539 833,11 €

    Et les 3 plus petites :

    Catégorie Total dépensé
    Computers 57 315 406,32 €
    Cameras 57 299 046,64 €
    Pet Supplies 57 197 250,24 €

    Sur purchases10000.txt, l’ordre sera différent (effet d’échantillonnage) mais les sommes par catégorie doivent être proportionnelles.

  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.

    Auto-évaluation (sur purchases.txt complet)

    Ville gagnante : Fresno — 132 743,03 €

    Top 5 :

    Ville Women’s Clothing payé Cash
    Fresno 132 743,03 €
    Las Vegas 124 790,58 €
    Colorado Springs 123 911,43 €
    Greensboro 123 411,60 €
    Richmond 123 302,50 €

  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 €”.

    Auto-évaluation (sur purchases.txt complet)

    Le fichier ne contient que des achats entre 9h et 17h59. L’heure 16h-17h gagne avec 115 228 708,28 €, mais l’écart entre les tranches est faible (~1 % entre la plus haute et la plus basse).

    Tranche Total dépensé
    09h-10h 114 767 312,45 €
    10h-11h 114 997 301,67 €
    11h-12h 114 799 964,72 €
    12h-13h 114 909 978,09 €
    13h-14h 115 061 758,15 €
    14h-15h 114 886 427,44 €
    15h-16h 114 916 347,74 €
    16h-17h 115 228 708,28 €
    17h-18h 114 890 154,72 €

    Si votre top affiche une tranche comme “9h-10h” ou si tous vos totaux sont du même ordre de grandeur que ceux ci-dessus, c’est bon.


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 :

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

Auto-évaluation — quelques anagrammes vérifiables

Sur l’exemple melon barre deviner lemon arbre fiable fable vendre devenir faible barbe, vous devez obtenir exactement 4 groupes :

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

Sur words_alpha.txt (~370 000 mots anglais), votre script doit retrouver des classes connues comme :

  • algin, align, liang, ligan, linga, gnail, naiglg — variantes autour des lettres a-g-i-l-n
  • caret, cater, crate, react, recta, trace — variantes autour de a-c-e-r-t
  • aster, rates, stare, tares, tears, reast, resat, … — variantes autour de a-e-r-s-t

Astuce de validation : trier les lettres d’un mot pour en faire la clé est l’approche la plus simple. sorted("react") == sorted("crate") doit être vrai.

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.

Auto-évaluation — patterns attendus

Pour la suite bnaitypi avec words_alpha.txt, l’extrait de l’énoncé donne déjà :

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

À score plus bas, on s’attend à voir notamment :

0.5 [pita, naib, tapi, pian, pain, anti, pita, pina, …]
0.5 [bait, pyin, …]
0.375 [bin, nip, pin, tin, ait, pat, …]

Astuce : un mot du dictionnaire est constructible si chaque lettre y apparaît au plus autant de fois que dans la suite donnée. Un compteur (collections.Counter) avec l’opérateur <= fait l’affaire en une ligne — mais difficile à transposer tel quel en map-reduce ; il faut souvent en passer par une comparaison de signatures triées + filtrage côté 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 ?

Auto-évaluation — sortie attendue sur web_access.log (100 000 lignes, année 2023)

Question 1 — nombre d’accès par mois :

Mois Accès
2023-01 8 558
2023-02 7 666
2023-03 8 519
2023-04 8 224
2023-05 8 450
2023-06 8 162
2023-07 8 489
2023-08 8 481
2023-09 8 091
2023-10 8 587
2023-11 8 222
2023-12 8 551

Total : 100 000 accès ; Février est le mois le moins chargé (cohérent avec un mois plus court).

Question 2 — IP la plus active de chaque mois (résultats vérifiables, IPs toutes en 192.168.1.x) :

Mois IP gagnante Hits
2023-01 192.168.1.206 55
2023-02 192.168.1.216 49
2023-03 192.168.1.148 50
2023-04 192.168.1.79 45
2023-05 192.168.1.189 46
2023-06 192.168.1.250 50
2023-07 192.168.1.146 48
2023-08 192.168.1.204 47
2023-09 192.168.1.98 48
2023-10 192.168.1.3 51
2023-11 192.168.1.109 47
2023-12 192.168.1.134 48

Si vous trouvez les bons totaux mais des IPs différentes, vérifiez la regex d’extraction de l’IP source (premier champ de la ligne).

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.

Auto-évaluation

Cet exercice est auto-vérifiant : matrice.py affiche déjà le résultat de A × B calculé par numpy. Votre script map-reduce doit produire la même matrice 20×15.

Pour comparer rapidement, sauvegardez votre sortie au format i\tj\tvaleur (une case par ligne), puis :

import numpy as np
expected = np.loadtxt("matriceA.txt") @ np.loadtxt("matriceB.txt")
yours = np.zeros_like(expected)
with open("votre_sortie.txt") as f:
    for line in f:
        i, j, v = line.split()
        yours[int(i), int(j)] = float(v)
print(np.allclose(yours, expected))   # doit afficher True

Piège classique : oublier de croiser correctement les éléments de A et B. Pour la case C[i,j], le mapper doit émettre, pour chaque A[i,k], une paire ((i,j), A[i,k] * B[k,j]) — il doit donc connaître l’autre matrice. Une astuce : faire passer A par le mapper et charger B en mémoire (utilisable si B est petite), ou émettre des paires intermédiaires depuis chaque matrice avec des clés bien choisies.