La forma más eficiente de encontrar las K palabras más frecuentes en una secuencia de palabras grande

85

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í.

  1. 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.

  2. 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.

  3. 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.

Morgan Cheng
fuente
¿Usaría el ordenamiento combinado o el ordenamiento rápido para el ordenamiento O (n * logn)?
committedandroider
1
Para usos prácticos, la respuesta de Aaron Maenpaa de contar con una muestra es la mejor. No es que las palabras más frecuentes se escondan de su muestra. Para los fanáticos de la complejidad, es O (1) ya que el tamaño de la muestra es fijo. No obtiene los recuentos exactos, pero tampoco los está pidiendo.
Nikana Reklawyks
Si lo que desea es una revisión de su análisis de complejidad, entonces será mejor que mencione: si n es el número de palabras en su texto ym es el número de palabras diferentes (tipos, los llamamos), el paso 1 es O ( n ), pero el paso 2 es O ( m .lg ( m )) y m << n (puede tener miles de millones de palabras y no llegar a un millón de tipos, pruébelo). Entonces, incluso con un algoritmo ficticio, sigue siendo O ( n + m lg ( m )) = O ( n ).
Nikana Reklawyks
1
Agregue un supuesto a la pregunta de que tenemos suficiente memoria principal para contener todas las palabras del texto grande. Sería interesante ver enfoques para encontrar k = 100 palabras de un archivo de 10 GB (es decir, ¡todas las palabras no caben en 4 GB de RAM)!
KGhatak
@KGhatak ¿cómo lo haríamos si supera el tamaño de la RAM?
user7098526

Respuestas:

66

Esto se puede hacer en O (n) tiempo

Solución 1:

Pasos:

  1. Cuente palabras y hash, que terminará en la estructura como esta

    var hash = {
      "I" : 13,
      "like" : 3,
      "meow" : 3,
      "geek" : 3,
      "burger" : 2,
      "cat" : 1,
      "foo" : 100,
      ...
      ...
    
  2. Recorra el hash y busque la palabra más utilizada (en este caso "foo" 100), luego cree la matriz de ese tamaño

  3. 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:

      0   1      2            3                  100
    [[ ],[cat],[burger],[like, meow, geek],[]...[foo]]
    
  4. Luego simplemente recorra la matriz desde el final y recopile las k palabras.

Solución 2:

Pasos:

  1. Lo mismo que arriba
  2. Use min heap y mantenga el tamaño de min heap en k, y para cada palabra en el hash comparamos las apariciones de palabras con min, 1) si es mayor que el valor min, elimine min (si el tamaño de min montón es igual a k) e inserte el número en el montón mínimo. 2) Descanse en condiciones simples.
  3. Después de atravesar la matriz, simplemente convertimos el montón mínimo en matriz y devolvemos la matriz.
Chihung Yu
fuente
16
Su solución (1) es una clasificación de cubo O (n) que reemplaza una clasificación de comparación estándar O (n lg n). Su enfoque requiere espacio adicional para la estructura del cucharón, pero los tipos de comparación se pueden realizar en su lugar. Su solución (2) se ejecuta en el tiempo O (n lg k), es decir, O (n) para iterar sobre todas las palabras y O (lg k) para agregar cada una al montón.
stackoverflowuser2010
4
La primera solución requiere más espacio, pero es importante enfatizar que de hecho es O (n) en el tiempo. 1: Frecuencias hash codificadas por palabra, O (n); 2: Hash de frecuencia transversal, crea un segundo hash codificado por frecuencia. Esto es O (n) para atravesar el hash y O (1) para agregar una palabra a la lista de palabras en esa frecuencia. 3: Recorre el hash hacia abajo desde la frecuencia máxima hasta que llegues a k. A lo sumo, O (n). Total = 3 * O (n) = O (n).
BringMyCakeBack
3
Por lo general, al contar palabras, la cantidad de depósitos en la solución 1 se sobreestima ampliamente (porque la palabra número uno más frecuente es mucho más frecuente que la segunda y la tercera mejor), por lo que su matriz es escasa e ineficiente.
Nikana Reklawyks
Su solución n. ° 1 no funciona cuando k (el número de palabras frecuentes) es menor que el número de ocurrencias de la palabra más frecuente (es decir, 100 en este caso). Por supuesto, eso podría no suceder en la práctica, pero uno debería no asumir!
One Two Three
@OneTwoThree la solución propuesta es solo un ejemplo. El número se basará en la demanda.
Chihung Yu
22

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.

Nick Johnson
fuente
13

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:

  1. Revise cada palabra e insértela en una tabla hash: O (n)
  2. Seleccione el K-ésimo elemento más pequeño: O (n)
  3. Partición alrededor de ese elemento: O (n)

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
Cuando seleccionamos el K-ésimo elemento más pequeño, lo que se selecciona es la K-ésima clave hash más pequeña. No es necesario que haya exactamente K palabras en la partición izquierda del Paso 3.
Prakash Murali
2
No podrá ejecutar "medianas de medianas" en la tabla hash como lo hace con los intercambios. Tendría que copiar los datos de la tabla hash a una matriz temporal. Entonces, se requerirá almacenamiento O (n).
user674669
No entiendo cómo se puede seleccionar el K-ésimo elemento más pequeño en O (n).
Michael Ho Chum
Consulte esto para conocer el algoritmo para encontrar el K-ésimo elemento más pequeño en O (n) - wikiwand.com/en/Median_of_medians
Piyush
La complejidad es la misma incluso si usa una tabla hash + min heap. No veo ninguna optimización.
Vinay
8

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.

Aaron Maenpaa
fuente
A veces tienes que hacer esto muchas veces, por ejemplo, si estás tratando de obtener la lista de palabras frecuentes por sitio web o por tema. En ese caso, "sin sudar" realmente no es suficiente. Aún necesita encontrar la manera de hacerlo de la manera más eficiente posible.
itsadok
1
+1 para obtener una respuesta práctica que no aborde los problemas de complejidad irrelevantes. @itsadok: Para cada ejecución: si es lo suficientemente grande, muestrelo; si no es así, la obtención de un factor logarítmico es irrelevante.
Nikana Reklawyks
2

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
7
Lo que estás describiendo se llama "trie".
Nick Johnson
Hola Strilanc. ¿Puede explicar el proceso de partición en detalle?
Morgan Cheng
1
¿Cómo esto no implica ordenar? Una vez que tenga el intento, ¿cómo extraer las k palabras con las frecuencias más grandes? no tiene ningún sentido
ordinario
2

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.

martinus
fuente
2

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.

Nikana Reklawyks
fuente
2
  1. Utilice una estructura de datos eficiente en la memoria para almacenar las palabras
  2. Utilice MaxHeap para encontrar las K palabras más frecuentes.

Aqui esta el codigo

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án las pruebas unitarias

@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 obtener más detalles, consulte este caso de prueba

artesano
fuente
1
  1. 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.

  2. 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.

M Sach
fuente
0

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?

Morgan Cheng
fuente
0

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.

Aly Farahat
fuente
En general, esta es una buena dirección, pero tiene un defecto. cuando se aumenta el recuento, no solo verificaremos "su predecesor", sino que tendremos que verificar los "predecesores". por ejemplo, existe una gran posibilidad de que la matriz sea [4,3,1,1,1,1,1,1,1,1,1] - los 1 pueden ser tantos - lo que la hará menos eficiente ya que tendremos que mirar hacia atrás a través de todos los predecesores para encontrar el adecuado para intercambiar.
Shawn
¿No sería esto mucho peor que O (n)? ¿Más como O (n ^ 2) ya que es esencialmente un tipo bastante ineficiente?
dcarr622
Hola Shawn. Sí estoy de acuerdo con usted. Pero sospecho que el problema que mencionaste es fundamental para el problema. De hecho, si en lugar de mantener solo una matriz ordenada de valores, podríamos seguir adelante y mantener una matriz de pares (valor, índice), donde el índice apunta a la primera aparición del elemento repetido, el problema debería poder resolverse en O (n) tiempo. Por ejemplo, [4,3,1,1,1,1,1,1,1,1,1] se verá como [(4,0), (3,1), (1,2), (1 , 2), (1,2, ..., (1,2)]; los índices comienzan desde 0.
Aly Farahat
0

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:

  1. para cada palabra, almacenarla como parte del mapa de ocurrencia de que: Map<String, Integer>.
  2. luego, según el recuento, elimínelo del conjunto de recuento anterior y agréguelo al nuevo conjunto de recuento.

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

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);
    }

}
Shawn
fuente
0

Acabo de descubrir la otra solución para este problema. Pero no estoy seguro de que sea correcto. Solución:

  1. Use una tabla hash para registrar la frecuencia de todas las palabras T (n) = O (n)
  2. Elija los primeros k elementos de la tabla hash y restáurelos en un búfer (cuyo espacio = k). T (n) = O (k)
  3. Cada vez, primero necesitamos encontrar el elemento mínimo actual del búfer, y simplemente comparar el elemento mínimo del búfer con los (n - k) elementos de la tabla hash uno por uno. Si el elemento de la tabla hash es mayor que este elemento mínimo del búfer, elimine el mínimo del búfer actual y agregue el elemento de la tabla hash. Entonces, cada vez que encontramos el mínimo en el búfer necesitamos T (n) = O (k), y recorremos toda la tabla hash necesitamos T (n) = O (n - k). Entonces, la complejidad de tiempo total para este proceso es T (n) = O ((nk) * k).
  4. Después de recorrer toda la tabla hash, el resultado está en este búfer.
  5. Toda la complejidad del tiempo: T (n) = O (n) + O (k) + O (kn - k ^ 2) = O (kn + n - k ^ 2 + k). Dado que, k es realmente menor 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.
zproject89
fuente
0

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

blueberry0xff
fuente
0

El código más simple para obtener la aparición 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])
}
ngLover
fuente
0

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.

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.

Mohammad
fuente
¿De qué manera esto mejora el enfoque esbozado en la pregunta? (Por favor, no omita comentarios del código presentado en SE.) (¿ I recommend to use Java built-in featuresComo procesamiento de secuencias y bucles foreach ?)
greybeard
Como sabe, uno de los factores más importantes en el diseño de un algoritmo eficiente es elegir la estructura de datos correcta. Entonces, es importante cómo aborda el problema. Por ejemplo, necesita atacar un problema dividiendo y conquistando. Necesitas atacar a otro codicioso. Como saben, la empresa Oracle está trabajando en Java. Son una de las mejores empresas tecnológicas del mundo. Hay algunos de los ingenieros más brillantes que trabajan allí en las funciones integradas de Java. Por lo tanto, estas características están bien probadas y a prueba de balas. Si podemos utilizarlos, en mi opinión, es mejor utilizarlos.
Mohammad
0
**

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;

}

};

asad_nitp
fuente