Analizando un terabyte de texto y contando eficientemente el número de ocurrencias de cada palabra

Recientemente me encontré con una pregunta de entrevista para crear un algoritmo en cualquier idioma que debería hacer lo siguiente

  1. Leer 1 terabyte de contenido
  2. Haz un recuento de cada palabra recurrente en ese contenido
  3. Enumera las 10 palabras más frecuentes

¿Podrías decirme la mejor manera posible de crear un algoritmo para esto?

Editar:

OK, digamos que el contenido está en inglés. ¿Cómo podemos encontrar las 10 palabras principales que ocurren con más frecuencia en ese contenido? Mi otra duda es que si intencionalmente están dando datos únicos, nuestro búfer caducará con el desbordamiento del tamaño del montón. Necesitamos manejar eso también.

Entrevista Respuesta

Esta tarea es interesante sin ser demasiado compleja, por lo que es una gran manera de comenzar una buena discusión técnica. Mi plan para hacer frente a esta tarea sería:

  1. Dividir los datos de entrada en palabras, usando el espacio en blanco y la puntuación como delimitadores
  2. Alimente cada palabra encontrada en una estructura Trie , con un contador actualizado en nodos que representa la última letra de una palabra
  3. Recorre el árbol completamente poblado para encontrar nodos con los recuentos más altos

En el contexto de una entrevista … demostraría la idea de Trie dibujando el árbol en una pizarra o papel. Comience desde el vacío, luego construya el árbol basado en una sola oración que contenga al menos una palabra recurrente. Diga “el gato puede atrapar el mouse” . Finalmente, muestre cómo se puede atravesar el árbol para encontrar los recuentos más altos. Entonces justificaría cómo este árbol proporciona un buen uso de la memoria, una buena velocidad de búsqueda de palabras (especialmente en el caso del lenguaje natural para el cual se derivan muchas palabras), y es adecuado para el procesamiento en paralelo.

Dibujar en el tablero

Dibuja el ejemplo trie

Manifestación

El progtwig C # a continuación pasa por 2 GB de texto en 75 segundos en un W2020 xeon de 4 núcleos, con un máximo de 8 hilos. El rendimiento es de alrededor de 4.3 millones de palabras por segundo con un código de análisis de entrada menos que óptimo. Con la estructura Trie para almacenar palabras, la memoria no es un problema al procesar el ingreso de lenguaje natural.

Notas:

  • texto de prueba obtenido del proyecto de Gutenberg
  • el código de análisis de entrada asume saltos de línea y es bastante subóptimo
  • la eliminación de la puntuación y otras palabras no correctas no se hace muy bien
  • manejar un archivo grande en lugar de uno más pequeño requeriría una pequeña cantidad de código para comenzar a leer los hilos entre el desplazamiento especificado dentro del archivo.

using System; using System.Collections.Generic; using System.Collections.Concurrent; using System.IO; using System.Threading; namespace WordCount { class MainClass { public static void Main(string[] args) { Console.WriteLine("Counting words..."); DateTime start_at = DateTime.Now; TrieNode root = new TrieNode(null, '?'); Dictionary readers = new Dictionary(); if (args.Length == 0) { args = new string[] { "war-and-peace.txt", "ulysees.txt", "les-miserables.txt", "the-republic.txt", "war-and-peace.txt", "ulysees.txt", "les-miserables.txt", "the-republic.txt" }; } if (args.Length > 0) { foreach (string path in args) { DataReader new_reader = new DataReader(path, ref root); Thread new_thread = new Thread(new_reader.ThreadRun); readers.Add(new_reader, new_thread); new_thread.Start(); } } foreach (Thread t in readers.Values) t.Join(); DateTime stop_at = DateTime.Now; Console.WriteLine("Input data processed in {0} secs", new TimeSpan(stop_at.Ticks - start_at.Ticks).TotalSeconds); Console.WriteLine(); Console.WriteLine("Most commonly found words:"); List top10_nodes = new List { root, root, root, root, root, root, root, root, root, root }; int distinct_word_count = 0; int total_word_count = 0; root.GetTopCounts(ref top10_nodes, ref distinct_word_count, ref total_word_count); top10_nodes.Reverse(); foreach (TrieNode node in top10_nodes) { Console.WriteLine("{0} - {1} times", node.ToString(), node.m_word_count); } Console.WriteLine(); Console.WriteLine("{0} words counted", total_word_count); Console.WriteLine("{0} distinct words found", distinct_word_count); Console.WriteLine(); Console.WriteLine("done."); } } #region Input data reader public class DataReader { static int LOOP_COUNT = 1; private TrieNode m_root; private string m_path; public DataReader(string path, ref TrieNode root) { m_root = root; m_path = path; } public void ThreadRun() { for (int i = 0; i < LOOP_COUNT; i++) // fake large data set buy parsing smaller file multiple times { using (FileStream fstream = new FileStream(m_path, FileMode.Open, FileAccess.Read)) { using (StreamReader sreader = new StreamReader(fstream)) { string line; while ((line = sreader.ReadLine()) != null) { string[] chunks = line.Split(null); foreach (string chunk in chunks) { m_root.AddWord(chunk.Trim()); } } } } } } } #endregion #region TRIE implementation public class TrieNode : IComparable { private char m_char; public int m_word_count; private TrieNode m_parent = null; private ConcurrentDictionary m_children = null; public TrieNode(TrieNode parent, char c) { m_char = c; m_word_count = 0; m_parent = parent; m_children = new ConcurrentDictionary(); } public void AddWord(string word, int index = 0) { if (index < word.Length) { char key = word[index]; if (char.IsLetter(key)) // should do that during parsing but we're just playing here! right? { if (!m_children.ContainsKey(key)) { m_children.TryAdd(key, new TrieNode(this, key)); } m_children[key].AddWord(word, index + 1); } else { // not a letter! retry with next char AddWord(word, index + 1); } } else { if (m_parent != null) // empty words should never be counted { lock (this) { m_word_count++; } } } } public int GetCount(string word, int index = 0) { if (index < word.Length) { char key = word[index]; if (!m_children.ContainsKey(key)) { return -1; } return m_children[key].GetCount(word, index + 1); } else { return m_word_count; } } public void GetTopCounts(ref List most_counted, ref int distinct_word_count, ref int total_word_count) { if (m_word_count > 0) { distinct_word_count++; total_word_count += m_word_count; } if (m_word_count > most_counted[0].m_word_count) { most_counted[0] = this; most_counted.Sort(); } foreach (char key in m_children.Keys) { m_children[key].GetTopCounts(ref most_counted, ref distinct_word_count, ref total_word_count); } } public override string ToString() { if (m_parent == null) return ""; else return m_parent.ToString() + m_char; } public int CompareTo(TrieNode other) { return this.m_word_count.CompareTo(other.m_word_count); } } #endregion } 

Aquí el resultado de procesar los mismos 20 MB de texto 100 veces en 8 hilos.

 Counting words... Input data processed in 75.2879952 secs Most commonly found words: the - 19364400 times of - 10629600 times and - 10057400 times to - 8121200 times a - 6673600 times in - 5539000 times he - 4113600 times that - 3998000 times was - 3715400 times his - 3623200 times 323618000 words counted 60896 distinct words found 

Una gran oferta aquí depende de algunas cosas que no se han especificado. Por ejemplo, ¿estamos tratando de hacer esto una vez , o estamos tratando de construir un sistema que lo haga de forma regular y continua? ¿Tenemos algún control sobre la entrada? ¿Estamos lidiando con texto que está todo en un solo idioma (por ejemplo, inglés) o hay muchos idiomas representados (y si es así, cuántos)?

Estos importan porque:

  1. Si los datos comienzan en un solo disco duro, el conteo paralelo (por ejemplo, map-reduce) no servirá para nada; el cuello de botella será la velocidad de transferencia del disco. Hacer copias en más discos para que podamos contar más rápido será más lento que solo contar directamente desde un disco.
  2. Si estamos diseñando un sistema para hacer esto de manera regular, la mayor parte de nuestro énfasis está realmente en el hardware, específicamente, tenemos muchos discos en paralelo para boost nuestro ancho de banda y al menos estar un poco más cerca de estar al día con el UPC.
  3. No importa la cantidad de texto que esté leyendo, hay un límite en la cantidad de palabras discretas con las que debe lidiar: si tiene un terabyte de incluso un petabyte de texto en inglés, no verá nada como miles de millones de diferentes palabras en inglés. Al hacer una comprobación rápida, el Oxford English Dictionary enumera aproximadamente 600,000 palabras en inglés.
  4. Aunque las palabras reales son obviamente diferentes entre los idiomas, el número de palabras por idioma es más o menos constante, por lo que el tamaño del mapa que construyamos dependerá en gran medida del número de idiomas representados.

Eso deja en gran parte la pregunta de cuántos idiomas podrían representarse. Por el momento, supongamos el peor de los casos. ISO 639-2 tiene códigos para 485 idiomas humanos. Supongamos un promedio de 700,000 palabras por idioma y una longitud de palabra promedio de, por ejemplo, 10 bytes de UTF-8 por palabra.

Simplemente almacenado como una simple lista lineal, eso significa que podemos almacenar cada palabra en cada idioma en la tierra junto con un recuento de frecuencia de 8 bytes en un poco menos de 6 gigabytes. Si utilizamos algo así como Patricia trie en su lugar, probablemente podamos planificar esa reducción al menos un tanto, posiblemente a 3 gigabytes o menos, aunque no sé lo suficiente sobre todos esos idiomas para estar seguro.

Ahora, la realidad es que casi con seguridad hemos sobreestimado los números en varios lugares: bastantes idiomas comparten un número considerable de palabras, muchos (especialmente los antiguos) idiomas tienen probablemente menos palabras que inglés, y echan un vistazo a lista, parece que algunos están incluidos que probablemente no tienen formularios escritos.

Resumen: casi cualquier escritorio / servidor razonablemente nuevo tiene suficiente memoria para mantener el mapa completamente en RAM, y más datos no cambiarán eso. Para uno (o algunos) discos en paralelo, vamos a estar vinculados a E / S de todos modos, por lo que el conteo paralelo (y tal) probablemente sea una pérdida neta. Probablemente necesitemos decenas de discos en paralelo antes de que cualquier otra optimización signifique mucho.

Puede probar un enfoque de map-reduce para esta tarea. La ventaja de map-reduce es la escalabilidad, por lo que incluso para 1TB, o 10TB o 1PB: el mismo enfoque funcionará, y no necesitará hacer mucho trabajo para modificar su algoritmo para la nueva escala. El marco también se encargará de distribuir el trabajo entre todas las máquinas (y núcleos) que tenga en su clúster.

Primero: (word,occurances) pares (word,occurances) .
El pseudo código para esto será algo así:

 map(document): for each word w: EmitIntermediate(w,"1") reduce(word,list): Emit(word,size(list)) 

En segundo lugar, puede encontrar fácilmente los que tienen las mejores ocurrencias k superiores con una única iteración sobre los pares. Este hilo explica este concepto. La idea principal es mantener un montón mínimo de elementos K superiores, y mientras se itera, asegúrese de que el montón siempre contenga los elementos K principales hasta ahora. Cuando hayas terminado, el montón contiene los elementos K superiores.

Una alternativa más escalable (aunque más lenta si tiene pocas máquinas) es utilizar la funcionalidad de clasificación de reducción de mapa, y ordenar los datos de acuerdo con las ocurrencias, y simplemente grepizar la parte superior K.

Tres cosas importantes para esto

Específicamente: Archivo a grande para mantener en la memoria, lista de palabras (potencialmente) demasiado grande para mantener en la memoria, el conteo de palabras puede ser demasiado grande para una int de 32 bits.

Una vez que superas esas advertencias, debería ser sencillo. El juego está administrando la lista de palabras potencialmente grande.

Si es más fácil (evitar que la cabeza gire).

“Estás ejecutando una máquina Z-80 de 8 bits, con 65K de RAM y tienes un archivo de 1MB …”

Mismo problema exacto.

Depende de los requisitos, pero si puede permitirse algún error, los algoritmos de transmisión y las estructuras de datos probabilísticos pueden ser interesantes porque son muy eficientes en cuanto a tiempo y espacio, y bastante simples de implementar, por ejemplo:

  • Golpes fuertes (por ej., Ahorro de espacio), si solo estás interesado en las primeras n palabras más frecuentes
  • Esquema de cuenta-minuto, para obtener un conteo estimado de cualquier palabra

Esas estructuras de datos requieren muy poco espacio constante (la cantidad exacta depende del error que pueda tolerar).

Consulte http://alex.smola.org/teaching/berkeley2012/streams.html para obtener una descripción excelente de estos algoritmos.

Estaría bastante tentado de usar un DAWG ( wikipedia y un artículo de C # con más detalles ). Es lo suficientemente simple como para agregar un campo de conteo en los nodos hoja, eficiente en cuanto a la memoria y funciona muy bien para las búsquedas.

EDITAR: ¿Aunque has intentado simplemente usar un Dictionary ? Donde > representa palabra y cuenta? Tal vez estás tratando de optimizar demasiado temprano?

Nota del editor: esta publicación originalmente vinculada a este artículo de la wikipedia , que parece tratarse sobre otro significado del término DAWG: una forma de almacenar todas las subcadenas de una palabra, para una concordancia de cadenas aproximada eficiente.

Una solución diferente podría ser el uso de una tabla SQL y permitir que el sistema maneje los datos de la mejor manera posible. Primero crea la tabla con la word campo individual, para cada palabra en la colección.

A continuación, utilice la consulta (lo siento por el problema de syntax, mi SQL está oxidado, en realidad es un pseudo-código):

 SELECT DISTINCT word, COUNT(*) AS c FROM myTable GROUP BY word ORDER BY c DESC 

La idea general es generar primero una tabla (que se almacena en el disco) con todas las palabras, y luego usar una consulta para contar y ordenar (word,occurances) por usted. A continuación, puede simplemente tomar la parte superior K de la lista recuperada.


Para todos: si tengo alguna syntax u otros problemas en la statement de SQL: siéntete libre de editar

En primer lugar, hace poco que “descubrí” la estructura de datos de Trie y la respuesta de zeFrenchy fue excelente para ponerme al tanto de esto.

Vi en los comentarios que varias personas hicieron sugerencias sobre cómo mejorar su rendimiento, pero estos fueron solo pequeños ajustes, así que pensé en compartir con ustedes lo que descubrí que es el verdadero cuello de botella … el ConcurrentDictionary.

Quería jugar con el almacenamiento local de subprocesos y tu muestra me dio una gran oportunidad para hacer eso y después de algunos cambios menores para usar un diccionario por subproceso y luego combinar los diccionarios después de que Join () viera el rendimiento mejorar ~ 30% (procesando 20MB 100 veces en 8 hilos pasó de ~ 48 seg a ~ 33 seg en mi caja).

El código se pega a continuación y notará que no ha cambiado mucho de la respuesta aprobada.

PD. No tengo más de 50 puntos de reputación, así que no pude poner esto en un comentario.

 using System; using System.Collections.Generic; using System.IO; using System.Linq; using System.Text; using System.Threading; namespace WordCount { class MainClass { public static void Main(string[] args) { Console.WriteLine("Counting words..."); DateTime start_at = DateTime.Now; Dictionary readers = new Dictionary(); if (args.Length == 0) { args = new string[] { "war-and-peace.txt", "ulysees.txt", "les-miserables.txt", "the-republic.txt", "war-and-peace.txt", "ulysees.txt", "les-miserables.txt", "the-republic.txt" }; } List> roots; if (args.Length == 0) { roots = new List>(1); } else { roots = new List>(args.Length); foreach (string path in args) { ThreadLocal root = new ThreadLocal(() => { return new TrieNode(null, '?'); }); roots.Add(root); DataReader new_reader = new DataReader(path, root); Thread new_thread = new Thread(new_reader.ThreadRun); readers.Add(new_reader, new_thread); new_thread.Start(); } } foreach (Thread t in readers.Values) t.Join(); foreach(ThreadLocal root in roots.Skip(1)) { roots[0].Value.CombineNode(root.Value); root.Dispose(); } DateTime stop_at = DateTime.Now; Console.WriteLine("Input data processed in {0} secs", new TimeSpan(stop_at.Ticks - start_at.Ticks).TotalSeconds); Console.WriteLine(); Console.WriteLine("Most commonly found words:"); List top10_nodes = new List { roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value }; int distinct_word_count = 0; int total_word_count = 0; roots[0].Value.GetTopCounts(top10_nodes, ref distinct_word_count, ref total_word_count); top10_nodes.Reverse(); foreach (TrieNode node in top10_nodes) { Console.WriteLine("{0} - {1} times", node.ToString(), node.m_word_count); } roots[0].Dispose(); Console.WriteLine(); Console.WriteLine("{0} words counted", total_word_count); Console.WriteLine("{0} distinct words found", distinct_word_count); Console.WriteLine(); Console.WriteLine("done."); Console.ReadLine(); } } #region Input data reader public class DataReader { static int LOOP_COUNT = 100; private TrieNode m_root; private string m_path; public DataReader(string path, ThreadLocal root) { m_root = root.Value; m_path = path; } public void ThreadRun() { for (int i = 0; i < LOOP_COUNT; i++) // fake large data set buy parsing smaller file multiple times { using (FileStream fstream = new FileStream(m_path, FileMode.Open, FileAccess.Read)) using (StreamReader sreader = new StreamReader(fstream)) { string line; while ((line = sreader.ReadLine()) != null) { string[] chunks = line.Split(null); foreach (string chunk in chunks) { m_root.AddWord(chunk.Trim()); } } } } } } #endregion #region TRIE implementation public class TrieNode : IComparable { private char m_char; public int m_word_count; private TrieNode m_parent = null; private Dictionary m_children = null; public TrieNode(TrieNode parent, char c) { m_char = c; m_word_count = 0; m_parent = parent; m_children = new Dictionary(); } public void CombineNode(TrieNode from) { foreach(KeyValuePair fromChild in from.m_children) { char keyChar = fromChild.Key; if (!m_children.ContainsKey(keyChar)) { m_children.Add(keyChar, new TrieNode(this, keyChar)); } m_children[keyChar].m_word_count += fromChild.Value.m_word_count; m_children[keyChar].CombineNode(fromChild.Value); } } public void AddWord(string word, int index = 0) { if (index < word.Length) { char key = word[index]; if (char.IsLetter(key)) // should do that during parsing but we're just playing here! right? { if (!m_children.ContainsKey(key)) { m_children.Add(key, new TrieNode(this, key)); } m_children[key].AddWord(word, index + 1); } else { // not a letter! retry with next char AddWord(word, index + 1); } } else { if (m_parent != null) // empty words should never be counted { m_word_count++; } } } public int GetCount(string word, int index = 0) { if (index < word.Length) { char key = word[index]; if (!m_children.ContainsKey(key)) { return -1; } return m_children[key].GetCount(word, index + 1); } else { return m_word_count; } } public void GetTopCounts(List most_counted, ref int distinct_word_count, ref int total_word_count) { if (m_word_count > 0) { distinct_word_count++; total_word_count += m_word_count; } if (m_word_count > most_counted[0].m_word_count) { most_counted[0] = this; most_counted.Sort(); } foreach (char key in m_children.Keys) { m_children[key].GetTopCounts(most_counted, ref distinct_word_count, ref total_word_count); } } public override string ToString() { return BuildString(new StringBuilder()).ToString(); } private StringBuilder BuildString(StringBuilder builder) { if (m_parent == null) { return builder; } else { return m_parent.BuildString(builder).Append(m_char); } } public int CompareTo(TrieNode other) { return this.m_word_count.CompareTo(other.m_word_count); } } #endregion } 

Como algoritmo general rápido, haría esto.

 Create a map with entries being the count for a specific word and the key being the actual string. for each string in content: if string is a valid key for the map: increment the value associated with that key else add a new key/value pair to the map with the key being the word and the count being one done 

Entonces podrías encontrar el valor más grande en el mapa

 create an array size 10 with data pairs of (word, count) for each value in the map if current pair has a count larger than the smallest count in the array replace that pair with the current one print all pairs in array 

Bueno, personalmente, dividiría el archivo en diferentes tamaños, digamos 128mb, manteniendo dos en la memoria todo el tiempo mientras escaneo, cualquier palabra descubierta se agrega a una lista Hash, y el recuento de Lista de listas, luego iteraría en la lista de la lista al final para encontrar los 10 mejores …

Bueno, la primera idea es administrar una base de datos en forma de hashtable / Array o lo que sea para guardar cada aparición de palabras, pero de acuerdo con el tamaño de los datos, prefiero:

  • Obtenga las primeras 10 palabras encontradas donde ocurrencia> = 2
  • Obtenga cuántas veces aparecen estas palabras en toda la cadena y elimínelas mientras cuenta
  • Comienza de nuevo, una vez que tienes dos juegos de 10 palabras cada uno obtienes las 10 palabras más ocurridas de ambos conjuntos
  • Haga lo mismo para el rest de la cadena (que contiene ya estas palabras).

Incluso puede tratar de ser más eficiente y comenzar con las primeras 10 palabras encontradas donde ocurrencia> = 5 por ejemplo o más, si no se encuentra, reduzca este valor hasta que se encuentren 10 palabras. A través de esto, tienes una buena oportunidad de evitar el uso intensivo de la memoria al guardar todas las ocurrencias de palabras, que es una gran cantidad de datos, y puedes guardar las rondas de escaneo (en un buen caso)

Pero en el peor de los casos, puede tener más rondas que en un algoritmo convencional.

Por cierto, es un problema que trataría de resolver con un lenguaje de progtwigción funcional en lugar de OOP.

El siguiente método solo leerá sus datos una vez y se puede ajustar para tamaños de memoria.

  • Lea el archivo en trozos de digamos 1GB
  • Para cada fragmento, haga una lista de las 5000 palabras más frecuentes con su frecuencia
  • Fusiona las listas según la frecuencia (1000 listas con 5000 palabras cada una)
  • Devuelve los 10 primeros de la lista fusionada

En teoría, es posible que te pierdas las palabras, aunque creo que la posibilidad es muy pequeña.

Storm es la tecnología a la vista. Separa el rol de la entrada de datos (surtidores) de los procesadores (pernos). El capítulo 2 de la tormenta de libros resuelve su problema exacto y describe muy bien la architecture del sistema: http://www.amazon.com/Getting-Started-Storm-Jonathan-Leibiusky/dp/1449324010

Storm es un procesamiento en tiempo real más que un procesamiento por lotes con Hadoop. Si sus datos son por existencia, entonces puede distribuir cargas a diferentes surtidores y distribuirlos para su procesamiento a diferentes pernos.

Este algoritmo también permitirá el soporte para datos que crecen más allá de los terabytes ya que la fecha será analizada a medida que llegue en tiempo real.

Pregunta muy interesante. Se relaciona más con el análisis lógico que con la encoding. Con la asunción del idioma inglés y las oraciones válidas resulta más fácil.

No tiene que contar todas las palabras, solo las que tienen una longitud inferior o igual a la longitud promedio de la palabra del idioma dado (para el inglés es 5.1). Por lo tanto, no tendrás problemas con la memoria.

En cuanto a la lectura del archivo, debe elegir un modo paralelo, leyendo fragmentos (tamaño de su elección) manipulando las posiciones de archivos para espacios en blanco. Si decide leer fragmentos de 1 MB, por ejemplo, todos los fragmentos, excepto el primero, deben ser un poco más amplios (+22 bytes desde la izquierda y +22 bytes desde la derecha, donde 22 representa la palabra más larga en inglés, si estoy en lo cierto). Para el parallel processing, necesitará un diccionario simultáneo o colecciones locales que fusionará.

Tenga en cuenta que normalmente terminará entre los diez primeros como parte de una lista válida de palabras prohibidas (este es probablemente otro enfoque inverso, que también es válido siempre que el contenido del archivo sea normal).

Intenta pensar en una estructura de datos especial para abordar este tipo de problemas. En este caso, un tipo especial de árbol como trie para almacenar cadenas de manera específica, muy eficiente. O la segunda forma de construir su propia solución, como contar palabras. Supongo que esta TB de datos sería en inglés, entonces tenemos alrededor de 600,000 palabras en general, así que será posible almacenar solo esas palabras y contar qué cadenas se repetirán + esta solución necesitará expresiones regulares para eliminar algunos caracteres especiales. La primera solución será más rápida, estoy bastante seguro.

http://en.wikipedia.org/wiki/Trie

aquí está la implementación del neumático en java
http://algs4.cs.princeton.edu/52trie/TrieST.java.html

mapreduce
WordCount se puede alcanzar de manera eficiente a través de mapreduce usando hadoop. https://hadoop.apache.org/docs/r1.2.1/mapred_tutorial.html#Example%3A+WordCount+v1.0 Los archivos grandes se pueden analizar a través de él. Utiliza varios nodos en el clúster para realizar esta operación.

 public void map(LongWritable key, Text value, OutputCollector output, Reporter reporter) throws IOException { String line = value.toString(); StringTokenizer tokenizer = new StringTokenizer(line); while (tokenizer.hasMoreTokens()) { word.set(tokenizer.nextToken()); output.collect(word, one); } } public static class Reduce extends MapReduceBase implements Reducer { public void reduce(Text key, Iterator values, OutputCollector output, Reporter reporter) throws IOException { int sum = 0; while (values.hasNext()) { sum += values.next().get(); } output.collect(key, new IntWritable(sum)); } }