MapReduce - Algorithme

L'algorithme MapReduce contient deux tâches importantes, à savoir Map et Reduce.

  • La tâche de carte est effectuée au moyen de la classe Mapper
  • La tâche de réduction est effectuée au moyen de la classe de réduction.

La classe Mapper prend l'entrée, la tokenise, la mappe et la trie. La sortie de la classe Mapper est utilisée comme entrée par la classe Reducer, qui à son tour recherche les paires correspondantes et les réduit.

MapReduce implémente divers algorithmes mathématiques pour diviser une tâche en petites parties et les affecter à plusieurs systèmes. En termes techniques, l'algorithme MapReduce aide à envoyer les tâches Map & Reduce aux serveurs appropriés dans un cluster.

Ces algorithmes mathématiques peuvent inclure les éléments suivants:

  • Sorting
  • Searching
  • Indexing
  • TF-IDF

Tri

Le tri est l'un des algorithmes de base de MapReduce pour traiter et analyser les données. MapReduce implémente un algorithme de tri pour trier automatiquement les paires clé-valeur en sortie du mappeur par leurs clés.

  • Les méthodes de tri sont implémentées dans la classe mapper elle-même.

  • Dans la phase de lecture aléatoire et de tri, après avoir tokenisé les valeurs dans la classe mapper, le Context class (classe définie par l'utilisateur) collecte les clés valuées correspondantes en tant que collection.

  • Pour collecter des paires clé-valeur similaires (clés intermédiaires), la classe Mapper prend l'aide de RawComparator class pour trier les paires clé-valeur.

  • L'ensemble des paires clé-valeur intermédiaires pour un Réducteur donné est automatiquement trié par Hadoop pour former des valeurs-clés (K2, {V2, V2,…}) avant qu'elles ne soient présentées au Réducteur.

Recherche

La recherche joue un rôle important dans l'algorithme MapReduce. Il aide dans la phase de combineur (facultatif) et dans la phase de réduction. Essayons de comprendre comment fonctionne la recherche à l'aide d'un exemple.

Exemple

L'exemple suivant montre comment MapReduce utilise l'algorithme de recherche pour trouver les détails de l'employé qui tire le salaire le plus élevé dans un ensemble de données d'employé donné.

  • Supposons que nous ayons des données d'employés dans quatre fichiers différents - A, B, C et D. Supposons également qu'il y ait des enregistrements d'employés en double dans les quatre fichiers en raison de l'importation répétée des données d'employés de toutes les tables de la base de données. Reportez-vous à l'illustration suivante.

  • The Map phasetraite chaque fichier d'entrée et fournit les données des employés par paires clé-valeur (<k, v>: <nom de l'emp, salaire>). Reportez-vous à l'illustration suivante.

  • The combiner phase(technique de recherche) acceptera l'entrée de la phase de carte comme une paire clé-valeur avec le nom et le salaire de l'employé. En utilisant la technique de recherche, le combineur vérifiera tous les salaires des employés pour trouver l'employé le plus élevé dans chaque fichier. Voir l'extrait suivant.

<k: employee name, v: salary>
Max= the salary of an first employee. Treated as max salary

if(v(second employee).salary > Max){
   Max = v(salary);
}

else{
   Continue checking;
}

Le résultat attendu est le suivant -

<satish, 26000>

<gopal, 50000>

<kiran, 45000>

<manisha, 45000>

  • Reducer phase- Formez chaque dossier, vous trouverez le salarié le plus élevé. Pour éviter la redondance, vérifiez toutes les paires <k, v> et éliminez les entrées en double, le cas échéant. Le même algorithme est utilisé entre les quatre paires <k, v>, qui proviennent de quatre fichiers d'entrée. Le résultat final devrait être comme suit -

<gopal, 50000>

Indexage

Normalement, l'indexation est utilisée pour pointer vers une donnée particulière et son adresse. Il effectue une indexation par lots sur les fichiers d'entrée pour un mappeur particulier.

La technique d'indexation qui est normalement utilisée dans MapReduce est connue sous le nom de inverted index.Les moteurs de recherche comme Google et Bing utilisent une technique d'indexation inversée. Essayons de comprendre le fonctionnement de l'indexation à l'aide d'un exemple simple.

Exemple

Le texte suivant est l'entrée pour l'indexation inversée. Ici T [0], T [1] et t [2] sont les noms de fichiers et leur contenu est entre guillemets.

T[0] = "it is what it is"
T[1] = "what is it"
T[2] = "it is a banana"

Après avoir appliqué l'algorithme d'indexation, nous obtenons la sortie suivante -

"a": {2}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": {0, 1}

Ici "a": {2} implique que le terme "a" apparaît dans le fichier T [2]. De même, "est": {0, 1, 2} implique que le terme "est" apparaît dans les fichiers T [0], T [1] et T [2].

TF-IDF

TF-IDF est un algorithme de traitement de texte qui est l'abréviation de Term Frequency - Inverse Document Frequency. C'est l'un des algorithmes d'analyse Web courants. Ici, le terme «fréquence» fait référence au nombre de fois qu'un terme apparaît dans un document.

Fréquence du terme (TF)

Il mesure la fréquence à laquelle un terme particulier apparaît dans un document. Il est calculé par le nombre de fois qu'un mot apparaît dans un document divisé par le nombre total de mots dans ce document.

TF(the) = (Number of times term the ‘the’ appears in a document) / (Total number of terms in the document)

Fréquence inverse des documents (IDF)

Il mesure l'importance d'un terme. Il est calculé par le nombre de documents dans la base de données texte divisé par le nombre de documents contenant un terme spécifique.

Lors du calcul de TF, tous les termes sont considérés comme également importants. Cela signifie que TF compte le terme fréquence pour des mots normaux tels que «est», «a», «quoi», etc. Ainsi, nous devons connaître les termes fréquents tout en augmentant les rares, en calculant ce qui suit -

IDF(the) = log_e(Total number of documents / Number of documents with term ‘the’ in it).

L'algorithme est expliqué ci-dessous à l'aide d'un petit exemple.

Exemple

Prenons un document contenant 1000 mots, dans lequel le mot hiveapparaît 50 fois. Le TF pourhive est alors (50/1000) = 0,05.

Maintenant, supposons que nous ayons 10 millions de documents et le mot hiveapparaît dans 1000 d'entre eux. Ensuite, l'IDF est calculé comme suit: log (10 000 000/1 000) = 4.

Le poids TF-IDF est le produit de ces quantités - 0,05 × 4 = 0,20.