Entrada: un entero positivo K y un texto grande. En realidad, el texto puede verse como una secuencia de palabras. Así que no tenemos que preocuparnos por cómo dividirlo en una secuencia de palabras.
Resultado: Las palabras K más frecuentes en el texto.
Mi pensamiento es así.
use una tabla hash para registrar la frecuencia de todas las palabras mientras recorre toda la secuencia de palabras. En esta fase, la clave es "palabra" y el valor es "frecuencia de palabra". Esto lleva O (n) tiempo.
ordenar el par (palabra, palabra-frecuencia); y la clave es "frecuencia de palabras". Esto lleva O (n * lg (n)) tiempo con el algoritmo de clasificación normal.
Después de clasificar, solo tomamos las primeras K palabras. Esto lleva tiempo O (K).
Para resumir, el tiempo total es O (n + n lg (n) + K) , Dado que K es seguramente más pequeño que N, en realidad es O (n lg (n)).
Podemos mejorar esto. En realidad, solo queremos las K palabras más importantes. La frecuencia de otras palabras no nos preocupa. Por lo tanto, podemos usar "clasificación de montón parcial". Para los pasos 2) y 3), no solo clasificamos. En cambio, lo cambiamos para que sea
2 ') construye un montón de pares (palabra, frecuencia de palabra) con "frecuencia de palabra" como clave. Se necesita O (n) tiempo para construir un montón;
3 ') extrae las primeras K palabras del montón. Cada extracción es O (lg (n)). Entonces, el tiempo total es O (k * lg (n)).
En resumen, esta solución costó tiempo O (n + k * lg (n)).
Este es solo mi pensamiento. No he encontrado la forma de mejorar el paso 1).
Espero que algunos expertos en recuperación de información puedan arrojar más luz sobre esta pregunta.
fuente
Respuestas:
Esto se puede hacer en O (n) tiempo
Solución 1:
Pasos:
Cuente palabras y hash, que terminará en la estructura como esta
Recorra el hash y busque la palabra más utilizada (en este caso "foo" 100), luego cree la matriz de ese tamaño
Luego, podemos volver a recorrer el hash y usar el número de apariciones de palabras como índice de la matriz, si no hay nada en el índice, cree una matriz o añádala a la matriz. Luego terminamos con una matriz como:
Luego simplemente recorra la matriz desde el final y recopile las k palabras.
Solución 2:
Pasos:
fuente
En general, no obtendrá un tiempo de ejecución mejor que la solución que ha descrito. Tienes que hacer al menos O (n) trabajo para evaluar todas las palabras, y luego O (k) trabajo extra para encontrar los k términos principales.
Si su problema es realmente grande, puede usar una solución distribuida como map / reduce. Haga que n trabajadores del mapa cuenten frecuencias en 1 / enésimo del texto cada uno, y para cada palabra, envíelo a uno de los m trabajadores del reductor calculados en función del hash de la palabra. Luego, los reductores suman los recuentos. Combinar la clasificación sobre las salidas de los reductores le dará las palabras más populares en orden de popularidad.
fuente
Una pequeña variación en su solución produce un algoritmo O (n) si no nos importa clasificar el K superior, y un O (n + k * lg (k)) solución si lo hacemos. Creo que ambos límites son óptimos dentro de un factor constante.
La optimización aquí viene nuevamente después de que revisamos la lista, insertándola en la tabla hash. Podemos usar el algoritmo de la mediana de las medianas para seleccionar el K-ésimo elemento más grande de la lista. Este algoritmo es probablemente O (n).
Después de seleccionar el K-ésimo elemento más pequeño, dividimos la lista alrededor de ese elemento como en Quicksort. Obviamente, esto también es O (n). Todo lo que esté en el lado "izquierdo" del pivote está en nuestro grupo de elementos K, así que hemos terminado (simplemente podemos desechar todo lo demás a medida que avanzamos).
Entonces esta estrategia es:
Si desea clasificar los elementos K, simplemente ordénelos con cualquier clasificación de comparación eficiente en el tiempo O (k * lg (k)), lo que arroja un tiempo de ejecución total de O (n + k * lg (k)).
El límite de tiempo O (n) es óptimo dentro de un factor constante porque debemos examinar cada palabra al menos una vez.
El límite de tiempo O (n + k * lg (k)) también es óptimo porque no hay una forma basada en la comparación de ordenar k elementos en menos de k * lg (k) tiempo.
fuente
Si su "lista grande de palabras" es lo suficientemente grande, simplemente puede hacer una muestra y obtener estimaciones. De lo contrario, me gusta la agregación de hash.
Editar :
Por ejemplo me refiero a elegir un subconjunto de páginas y calcular la palabra más frecuente en esas páginas. Siempre que seleccione las páginas de forma razonable y seleccione una muestra estadísticamente significativa, sus estimaciones de las palabras más frecuentes deberían ser razonables.
Este enfoque solo es razonable si tiene tantos datos que procesarlos todos es un poco tonto. Si solo tiene unos pocos megas, debería poder analizar los datos y calcular una respuesta exacta sin sudar en lugar de molestarse en calcular una estimación.
fuente
Puede reducir aún más el tiempo dividiendo usando la primera letra de palabras, luego dividiendo el conjunto de palabras múltiples más grande usando el siguiente carácter hasta que tenga k conjuntos de palabras simples. Utilizaría una especie de árbol de 256 vías con listas de palabras parciales / completas en las hojas. Debería tener mucho cuidado de no generar copias de cadenas en todas partes.
Este algoritmo es O (m), donde m es el número de caracteres. Evita esa dependencia de k, lo cual es muy bueno para k grandes [por cierto, el tiempo de ejecución publicado es incorrecto, debería ser O (n * lg (k)), y no estoy seguro de qué es eso en términos de metro].
Si ejecuta ambos algoritmos uno al lado del otro, obtendrá lo que estoy bastante seguro de que es un algoritmo O (min (m, n * lg (k))) asintóticamente óptimo, pero el mío debería ser más rápido en promedio porque no implica hash o clasificación.
fuente
Tiene un error en su descripción: Contar toma O (n) tiempo, pero ordenar toma O (m * lg (m)), donde m es el número de palabras únicas . Esto suele ser mucho más pequeño que el número total de palabras, por lo que probablemente debería optimizar la forma en que se construye el hash.
fuente
Su problema es el mismo que este: http://www.geeksforgeeks.org/find-the-k-most-frequent-words-from-a-file/
Utilice Trie y min heap para resolverlo de manera eficiente.
fuente
Si lo que busca es la lista de k palabras más frecuentes en su texto para cualquier k práctica y para cualquier lenguaje natural, entonces la complejidad de su algoritmo no es relevante.
Solo muestre , digamos, algunos millones de palabras de su texto, procese eso con cualquier algoritmo en cuestión de segundos y los recuentos más frecuentes serán muy precisos.
Como nota al margen, la complejidad del algoritmo ficticio (1. contar todos 2. ordenar los conteos 3. tomar el mejor) es O (n + m * log (m)), donde m es el número de palabras diferentes en su texto. log (m) es mucho más pequeño que (n / m), por lo que sigue siendo O (n).
Prácticamente, el paso largo está contando.
fuente
Aqui esta el codigo
}
Aquí están las pruebas unitarias
Para obtener más detalles, consulte este caso de prueba
fuente
use una tabla hash para registrar la frecuencia de todas las palabras mientras recorre toda la secuencia de palabras. En esta fase, la clave es "palabra" y el valor es "frecuencia de palabra". Esto lleva O (n) tiempo. Esto es lo mismo que todos los explicados anteriormente.
Mientras se inserta en hashmap, mantenga el Treeset (específico de Java, hay implementaciones en todos los idiomas) de tamaño 10 (k = 10) para mantener las 10 palabras más frecuentes. Hasta que el tamaño sea inferior a 10, sigue agregándolo. Si el tamaño es igual a 10, si el elemento insertado es mayor que el elemento mínimo, es decir, el primer elemento. Si es así, elimínelo e inserte un nuevo elemento
Para restringir el tamaño del conjunto de árboles, consulte este enlace.
fuente
Supongamos que tenemos una secuencia de palabras "ad" "ad" "chico" "grande" "malo" "com" "ven" "frío". Y K = 2. como mencionaste "particionar usando la primera letra de las palabras", obtuvimos ("ad", "ad") ("boy", "big", "bad") ("com" "come" "cold") "luego particionando el conjunto de varias palabras más grande usando el siguiente carácter hasta que tenga k conjuntos de una sola palabra ". particionará ("chico", "grande", "malo") ("com" "ven" "frío"), la primera partición ("anuncio", "anuncio") se pierde, mientras que "anuncio" es en realidad el palabra más frecuente.
Quizás entiendo mal tu punto. ¿Puede detallar su proceso sobre la partición?
fuente
Creo que este problema se puede resolver con un algoritmo O (n). Podríamos hacer la clasificación sobre la marcha. En otras palabras, la clasificación en ese caso es un subproblema del problema de clasificación tradicional, ya que solo un contador se incrementa en uno cada vez que accedemos a la tabla hash. Inicialmente, la lista está ordenada ya que todos los contadores son cero. A medida que seguimos incrementando los contadores en la tabla hash, mantenemos otra matriz de valores hash ordenados por frecuencia de la siguiente manera. Cada vez que incrementamos un contador, verificamos su índice en la matriz clasificada y verificamos si su recuento excede a su predecesor en la lista. Si es así, intercambiamos estos dos elementos. Como tal, obtenemos una solución que es como máximo O (n) donde n es el número de palabras en el texto original.
fuente
Yo también estaba luchando con esto y me inspiré en @aly. En lugar de ordenar después, podemos simplemente mantener una lista de palabras clasificadas previamente (
List<Set<String>>
) y la palabra estará en el conjunto en la posición X donde X es el recuento actual de la palabra. En general, así es como funciona:Map<String, Integer>
.El inconveniente de esto es que la lista puede ser grande, se puede optimizar usando a
TreeMap<Integer, Set<String>>
, pero esto agregará algo de sobrecarga. En última instancia, podemos utilizar una combinación de HashMap o nuestra propia estructura de datos.El código
fuente
Acabo de descubrir la otra solución para este problema. Pero no estoy seguro de que sea correcto. Solución:
fuente
Intente pensar en una estructura de datos especial para abordar este tipo de problemas. En este caso un tipo especial de árbol como el intento de almacenar cadenas de forma específica, muy eficiente. O una segunda forma de construir su propia solución como contar palabras. Supongo que este TB de datos estaría en inglés, entonces tenemos alrededor de 600,000 palabras en general, por lo que será posible almacenar solo esas palabras y contar qué cadenas se repetirían + 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
fuente
Esta es una idea interesante para buscar y pude encontrar este documento relacionado con Top-K https://icmi.cs.ucsb.edu/research/tech_reports/reports/2005-23.pd f
También hay una implementación aquí .
fuente
El código más simple para obtener la aparición de la palabra más utilizada.
fuente
En estas situaciones, recomiendo utilizar las funciones integradas de Java. Dado que, ya están bien probados y son estables. En este problema, encuentro las repeticiones de las palabras usando la estructura de datos HashMap. Luego, envío los resultados a una serie de objetos. Ordeno el objeto por Arrays.sort () e imprimo las primeras k palabras y sus repeticiones.
Para obtener más información, visite https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TopKWordsTextFile.java . Espero que ayude.
fuente
I recommend to use Java built-in features
Como procesamiento de secuencias y bucles foreach ?)**
};
fuente