algorithm - varias - La forma más eficiente de encontrar palabras frecuentes de K superior en una secuencia de Word grande
como cambiar una palabra que se repite varias veces en word (19)
- Utilice una estructura de datos eficiente en memoria para almacenar las palabras
- Use MaxHeap, para encontrar las palabras frecuentes principales de K.
Aquí está el código
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import com.nadeem.app.dsa.adt.Trie;
import com.nadeem.app.dsa.adt.Trie.TrieEntry;
import com.nadeem.app.dsa.adt.impl.TrieImpl;
public class TopKFrequentItems {
private int maxSize;
private Trie trie = new TrieImpl();
private PriorityQueue<TrieEntry> maxHeap;
public TopKFrequentItems(int k) {
this.maxSize = k;
this.maxHeap = new PriorityQueue<TrieEntry>(k, maxHeapComparator());
}
private Comparator<TrieEntry> maxHeapComparator() {
return new Comparator<TrieEntry>() {
@Override
public int compare(TrieEntry o1, TrieEntry o2) {
return o1.frequency - o2.frequency;
}
};
}
public void add(String word) {
this.trie.insert(word);
}
public List<TopK> getItems() {
for (TrieEntry trieEntry : this.trie.getAll()) {
if (this.maxHeap.size() < this.maxSize) {
this.maxHeap.add(trieEntry);
} else if (this.maxHeap.peek().frequency < trieEntry.frequency) {
this.maxHeap.remove();
this.maxHeap.add(trieEntry);
}
}
List<TopK> result = new ArrayList<TopK>();
for (TrieEntry entry : this.maxHeap) {
result.add(new TopK(entry));
}
return result;
}
public static class TopK {
public String item;
public int frequency;
public TopK(String item, int frequency) {
this.item = item;
this.frequency = frequency;
}
public TopK(TrieEntry entry) {
this(entry.word, entry.frequency);
}
@Override
public String toString() {
return String.format("TopK [item=%s, frequency=%s]", item, frequency);
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + frequency;
result = prime * result + ((item == null) ? 0 : item.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
TopK other = (TopK) obj;
if (frequency != other.frequency)
return false;
if (item == null) {
if (other.item != null)
return false;
} else if (!item.equals(other.item))
return false;
return true;
}
}
}
Aquí está la unidad de pruebas
@Test
public void test() {
TopKFrequentItems stream = new TopKFrequentItems(2);
stream.add("hell");
stream.add("hello");
stream.add("hello");
stream.add("hello");
stream.add("hello");
stream.add("hello");
stream.add("hero");
stream.add("hero");
stream.add("hero");
stream.add("hello");
stream.add("hello");
stream.add("hello");
stream.add("home");
stream.add("go");
stream.add("go");
assertThat(stream.getItems()).hasSize(2).contains(new TopK("hero", 3), new TopK("hello", 8));
}
Para más detalles refiera este caso de prueba
Entrada: Un entero positivo K y un texto grande. El texto en realidad se puede ver como una secuencia de palabras. Entonces no tenemos que preocuparnos de cómo dividirlo en una secuencia de palabras.
Salida: 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 "palabra-frecuencia". Esto toma O (n) tiempo.
ordenar el par (palabra, palabra-frecuencia); y la clave es "palabra-frecuencia". Esto toma el tiempo O (n * lg (n)) con el algoritmo de clasificación normal.
Después de ordenar, tomamos las primeras K palabras. Esto toma el tiempo O (K).
En resumen, el tiempo total es O (n + n lg (n) + K), ya que K es seguramente más pequeño que N, por lo que en realidad es O (n lg (n)).
Podemos mejorar esto. En realidad, solo queremos las mejores palabras de K. La frecuencia de otras palabras no nos preocupa. Por lo tanto, podemos usar "clasificación parcial de Heap". Para el paso 2) y 3), no solo hacemos la clasificación. En cambio, lo cambiamos para ser
2 '') construye un montón de par (palabra, palabra-frecuencia) con "palabra-frecuencia" como clave. Toma O (n) tiempo para construir un montón;
3 '') extraer las palabras K superiores del montón. Cada extracción es O (lg (n)). Entonces, el tiempo total es O (k * lg (n)).
Para resumir, esta solución cuesta tiempo O (n + k * lg (n)).
Esto 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 cuestión.
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 "palabra-frecuencia". Esto toma el tiempo de O (n). 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) del tamaño 10 (k = 10) para mantener las 10 palabras frecuentes 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. En caso afirmativo, quítelo e inserte un nuevo elemento
Para restringir el tamaño de treeset ver este enlace
Acabo de descubrir la otra solución para este problema. Pero no estoy seguro de que sea correcto. Solución:
- Use una tabla Hash para registrar todas las palabras ''frecuencia T (n) = O (n)
- Elija los primeros k elementos de la tabla hash y restáurelos en un búfer (cuyo espacio = k). T (n) = O (k)
- Cada vez, primero necesitamos encontrar el elemento mínimo actual del buffer, y simplemente comparar el elemento mínimo del buffer con los elementos (n - k) de la tabla hash uno por uno. Si el elemento de la tabla hash es mayor que este elemento mínimo del búfer, a continuación, suelte el mínimo del búfer en uso y agregue el elemento de la tabla hash. Entonces, cada vez que encontramos que el mínimo en el buffer necesita T (n) = O (k), y atraviesa toda la tabla hash, necesita T (n) = O (n - k). Entonces, la complejidad del tiempo total para este proceso es T (n) = O ((nk) * k).
- Después de recorrer toda la tabla hash, el resultado está en este búfer.
- La complejidad del tiempo completo: T (n) = O (n) + O (k) + O (kn - k ^ 2) = O (kn + n - k ^ 2 + k). Dado que, k es realmente más pequeño que n en general. Entonces para esta solución, la complejidad del tiempo es T (n) = O (kn) . Ese es el tiempo lineal, cuando k es realmente pequeño. ¿Es correcto? Realmente no estoy seguro.
Código más simple para obtener la ocurrencia de la palabra más utilizada.
function strOccurence(str){
var arr = str.split(" ");
var length = arr.length,temp = {},max;
while(length--){
if(temp[arr[length]] == undefined && arr[length].trim().length > 0)
{
temp[arr[length]] = 1;
}
else if(arr[length].trim().length > 0)
{
temp[arr[length]] = temp[arr[length]] + 1;
}
}
console.log(temp);
var max = [];
for(i in temp)
{
max[temp[i]] = i;
}
console.log(max[max.length])
//if you want second highest
console.log(max[max.length - 2])
}
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 sub-problema 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 aumentamos los contadores en la tabla hash, reservamos 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 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.
En estas situaciones, recomiendo usar funciones incorporadas de Java. Desde entonces, ya están bien probados y estables. En este problema, encuentro las repeticiones de las palabras mediante el uso de la estructura de datos HashMap. Luego, envío los resultados a una matriz de objetos. Clasifico el objeto por Arrays.sort () e imprimo las primeras k palabras y sus repeticiones.
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
public class TopKWordsTextFile {
static class SortObject implements Comparable<SortObject>{
private String key;
private int value;
public SortObject(String key, int value) {
super();
this.key = key;
this.value = value;
}
@Override
public int compareTo(SortObject o) {
//descending order
return o.value - this.value;
}
}
public static void main(String[] args) {
HashMap<String,Integer> hm = new HashMap<>();
int k = 1;
try {
BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("words.in")));
String line;
while ((line = br.readLine()) != null) {
// process the line.
//System.out.println(line);
String[] tokens = line.split(" ");
for(int i=0; i<tokens.length; i++){
if(hm.containsKey(tokens[i])){
//If the key already exists
Integer prev = hm.get(tokens[i]);
hm.put(tokens[i],prev+1);
}else{
//If the key doesn''t exist
hm.put(tokens[i],1);
}
}
}
//Close the input
br.close();
//Print all words with their repetitions. You can use 3 for printing top 3 words.
k = hm.size();
// Get a set of the entries
Set set = hm.entrySet();
// Get an iterator
Iterator i = set.iterator();
int index = 0;
// Display elements
SortObject[] objects = new SortObject[hm.size()];
while(i.hasNext()) {
Map.Entry e = (Map.Entry)i.next();
//System.out.print("Key: "+e.getKey() + ": ");
//System.out.println(" Value: "+e.getValue());
String tempS = (String) e.getKey();
int tempI = (int) e.getValue();
objects[index] = new SortObject(tempS,tempI);
index++;
}
System.out.println();
//Sort the array
Arrays.sort(objects);
//Print top k
for(int j=0; j<k; j++){
System.out.println(objects[j].key+":"+objects[j].value);
}
} catch (IOException e) {
e.printStackTrace();
}
}
}
Para obtener más información, visite https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TopKWordsTextFile.java . Espero que ayude.
En general, no obtendrás mejor tiempo de ejecución que la solución que describes. Tienes que hacer al menos O (n) trabajo para evaluar todas las palabras, y luego O (k) trabajo adicional para encontrar los mejores k términos.
Si su conjunto de problemas es realmente grande, puede usar una solución distribuida como map / reduce. Haga que los trabajadores del mapa cuenten las frecuencias en 1 / nth del texto cada una, y para cada palabra, envíela a uno de los m trabajadores del reductor calculados en base al hash de la palabra. Los reductores suman los conteos. Merge sort over the reducrs ''outputs le dará las palabras más populares en orden de popularidad.
Esta es una idea interesante para buscar y podría 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 de esto here .
Estaba luchando con esto también y me inspiré en @aly. En lugar de ordenar después, podemos simplemente mantener una lista de palabras previamente listadas ( List<Set<String>> ) y la palabra estará en el conjunto en la posición X, donde X es el conteo actual de la palabra. En general, así es como funciona:
- para cada palabra, guárdela como parte del mapa de su ocurrencia:
Map<String, Integer>. - luego, según el conteo, elimínelo del conjunto de conteos anterior y agréguelo al nuevo conjunto de conteos.
El inconveniente de esto es que la lista puede ser grande, se puede optimizar utilizando TreeMap<Integer, Set<String>> , pero esto agregará algo de sobrecarga. En última instancia, podemos usar una combinación de HashMap o nuestra propia estructura de datos.
El código
public class WordFrequencyCounter {
private static final int WORD_SEPARATOR_MAX = 32; // UNICODE 0000-001F: control chars
Map<String, MutableCounter> counters = new HashMap<String, MutableCounter>();
List<Set<String>> reverseCounters = new ArrayList<Set<String>>();
private static class MutableCounter {
int i = 1;
}
public List<String> countMostFrequentWords(String text, int max) {
int lastPosition = 0;
int length = text.length();
for (int i = 0; i < length; i++) {
char c = text.charAt(i);
if (c <= WORD_SEPARATOR_MAX) {
if (i != lastPosition) {
String word = text.substring(lastPosition, i);
MutableCounter counter = counters.get(word);
if (counter == null) {
counter = new MutableCounter();
counters.put(word, counter);
} else {
Set<String> strings = reverseCounters.get(counter.i);
strings.remove(word);
counter.i ++;
}
addToReverseLookup(counter.i, word);
}
lastPosition = i + 1;
}
}
List<String> ret = new ArrayList<String>();
int count = 0;
for (int i = reverseCounters.size() - 1; i >= 0; i--) {
Set<String> strings = reverseCounters.get(i);
for (String s : strings) {
ret.add(s);
System.out.print(s + ":" + i);
count++;
if (count == max) break;
}
if (count == max) break;
}
return ret;
}
private void addToReverseLookup(int count, String word) {
while (count >= reverseCounters.size()) {
reverseCounters.add(new HashSet<String>());
}
Set<String> strings = reverseCounters.get(count);
strings.add(word);
}
}
Esto se puede hacer en el tiempo O (n)
Solución 1:
Pasos:
Contar palabras y hash it, que terminará en la estructura de esta manera
var hash = { "I" : 13, "like" : 3, "meow" : 3, "geek" : 3, "burger" : 2, "cat" : 1, "foo" : 100, ... ...Atraviese el hash y encuentre la palabra más utilizada (en este caso, "foo" 100), luego cree la matriz de ese tamaño
Entonces podemos atravesar el hash nuevamente y usar el número de ocurrencias de palabras como índice de matriz, si no hay nada en el índice, crear una matriz o agregarla en la matriz. Luego terminamos con una matriz como:
0 1 2 3 100 [[ ],[ ],[burger],[like, meow, geek],[]...[foo]]Luego, simplemente atraviesa la matriz desde el final y recoge las k palabras.
Solución 2:
Pasos:
- Lo mismo que arriba
- Use min heap y mantenga el tamaño de min heap en k, y para cada palabra en el hash comparamos las ocurrencias de palabras con min, 1) si es mayor que el valor min, elimine el min (si el tamaño de min) el montón es igual a k) e inserte el número en el montón mínimo. 2) descansar en condiciones simples.
- Después de atravesar la matriz, simplemente convertimos el montón mínimo en una matriz y devolvemos la matriz.
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.
Puede reducir aún más el tiempo mediante la creación de particiones utilizando la primera letra de las palabras, y luego particionar el conjunto de palabras múltiples más grande con el siguiente carácter hasta que tenga k conjuntos de una sola palabra. Utilizaría un tipo de árbol de 256 vías con listas de palabras parciales / completas en las hojas. Debería tener mucho cuidado de no causar 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 lo que es en términos de metro].
Si ejecuta ambos algoritmos uno al lado del otro obtendrá lo que estoy seguro es un algoritmo asintóticamente óptimo O (min (m, n * lg (k))), pero el mío debería ser más rápido en promedio porque no involucra hash o clasificación.
Si lo que busca es la lista de k palabras más frecuentes en su texto para cualquier k práctica y para cualquier idioma natural, entonces la complejidad de su algoritmo no es relevante.
Simplemente muestree , digamos, unos pocos 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 recuentos 3. tomar lo 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 es contar.
Si su "gran lista de palabras" es lo suficientemente grande, simplemente puede probar y obtener estimaciones. De lo contrario, me gusta la agregación de hash.
Editar :
Por muestra quiero decir elegir un subconjunto de páginas y calcular la palabra más frecuente en esas páginas. Siempre que seleccione las páginas de manera razonable y seleccione una muestra estadísticamente significativa, sus estimaciones de las palabras más frecuentes deben ser razonables.
Este enfoque es realmente razonable solo si tienes tantos datos que procesarlos es simplemente una tontería. Si solo tiene unos pocos megas, debería poder analizar los datos y calcular una respuesta exacta sin perder el tiempo en lugar de molestarse en calcular un presupuesto.
Su problema es el mismo que este- http://www.geeksforgeeks.org/find-the-k-most-frequent-words-from-a-file/
Usa Trie y min heap para resolverlo de manera eficiente.
Supongamos que tenemos una secuencia de palabras "ad" "ad" "chico" "grande" "malo" "com" "ven" "frío". Y K = 2. como mencionaste "particionando usando la primera letra de las palabras", obtuvimos ("anuncio", "anuncio") ("chico", "grande", "malo") ("com" "venir" "frío") "entonces particionar el conjunto de palabras múltiples más grande usando el siguiente carácter hasta que tengas k conjuntos de una sola palabra ". se dividirá ("chico", "grande", "malo") ("com" "venir" "frío"), la primera partición ("anuncio", "anuncio") se perderá, mientras que "anuncio" es en realidad el palabra más frecuente.
Tal vez no entiendo tu punto. ¿Puedes por favor detallar tu proceso sobre la partición?
Tiene un error en su descripción: el conteo toma O (n) tiempo, pero la clasificación 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 genera el hash.
Una pequeña variación en su solución arroja un algoritmo O (n) si no nos importa clasificar el K superior, y una solución O (n + k * lg (k)) si lo hacemos. Creo que ambos límites son óptimos dentro de un factor constante.
La optimización aquí viene de nuevo después de ejecutar la lista, insertando en la tabla hash. Podemos usar el algoritmo de la mediana de las medianas para seleccionar el K-ésimo elemento más grande en la lista. Este algoritmo es probablemente O (n).
Después de seleccionar el elemento más pequeño Kth, dividimos la lista alrededor de ese elemento como en quicksort. Esto es obviamente también O (n). Cualquier cosa en el lado "izquierdo" del pivote está en nuestro grupo de elementos K, así que terminamos (podemos simplemente tirar todo lo demás a medida que avanzamos).
Entonces esta estrategia es:
- Repase cada palabra e insértela en una tabla hash: O (n)
- Seleccione el K-ésimo elemento más pequeño: O (n)
- Partición alrededor de ese elemento: O (n)
Si desea clasificar los elementos K, simplemente ordénelos con cualquier orden de comparación eficiente en el tiempo O (k * lg (k)), produciendo un tiempo de ejecución total de O (n + k * lg (k)).
El límite de tiempo de O (n) es óptimo dentro de un factor constante porque debemos examinar cada palabra al menos una vez.
El límite de tiempo de O (n + k * lg (k)) también es óptimo porque no hay una forma basada en la comparación para clasificar elementos k en menos de k * lg (k) tiempo.
**
C ++ 11 Implementación del pensamiento anterior
**
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> map;
for(int num : nums){
map[num]++;
}
vector<int> res;
// we use the priority queue, like the max-heap , we will keep (size-k) smallest elements in the queue
// pair<first, second>: first is frequency, second is number
priority_queue<pair<int,int>> pq;
for(auto it = map.begin(); it != map.end(); it++){
pq.push(make_pair(it->second, it->first));
// onece the size bigger than size-k, we will pop the value, which is the top k frequent element value
if(pq.size() > (int)map.size() - k){
res.push_back(pq.top().second);
pq.pop();
}
}
return res;
}
};