Il modo più efficace per trovare parole chiave K in una sequenza di parole grandi

Input: un intero positivo K e un testo grande. Il testo può essere effettivamente visto come una sequenza di parole. Quindi non dobbiamo preoccuparci di come suddividerlo in una sequenza di parole.
Output: le parole K più frequenti nel testo.

Il mio pensiero è così.

  1. usa una tabella hash per registrare la frequenza di tutte le parole mentre attraversi l’intera sequenza di parole. In questa fase, la chiave è “word” e il valore è “word-frequency”. Questo richiede O (n) tempo.

  2. ordina la coppia (parola, frequenza delle parole); e la chiave è “frequenza delle parole”. Questo richiede tempo O (n * lg (n)) con un normale algoritmo di ordinamento.

  3. Dopo l’ordinamento, prendiamo solo le prime parole K. Questo richiede O (K) tempo.

Per riassumere, il tempo totale è O (n + n lg (n) + K), poiché K è sicuramente più piccolo di N, quindi in realtà è O (n lg (n)).

Possiamo migliorare questo. In realtà, vogliamo solo parole chiave in alto. Le altre parole “la frequenza non ci riguarda. Quindi, possiamo usare “sort Heap parziale”. Per i passaggi 2) e 3), non eseguiamo solo l’ordinamento. Invece, lo cambiamo per essere

2 ‘) costruisce un cumulo di coppie (parola, frequenza delle parole) con “word-frequency” come chiave. Ci vuole O (n) tempo per build un mucchio;

3 ‘) estrae le parole K in cima all’heap. Ogni estrazione è O (lg (n)). Quindi, il tempo totale è O (k * lg (n)).

Per riassumere, questa soluzione ha un costo O (n + k * lg (n)).

Questo è solo il mio pensiero Non ho trovato il modo per migliorare il passaggio 1).
Spero che alcuni esperti di Information Retrieval possano far luce su questa domanda.

Questo può essere fatto nel tempo O (n)

Soluzione 1:

passi:

  1. Conta parole e cancellalo, che finirà nella struttura come questa

    var hash = { "I" : 13, "like" : 3, "meow" : 3, "geek" : 3, "burger" : 2, "cat" : 1, "foo" : 100, ... ... 
  2. Attraversa l’hash e trova la parola più utilizzata (in questo caso “pippo” 100), quindi crea l’array di quella dimensione

  3. Quindi possiamo attraversare di nuovo l’hash e utilizzare il numero di occorrenze di parole come indice di matrice, se non c’è nulla nell’indice, creare un array altrimenti aggiungerlo nell’array. Quindi finiamo con un array come:

      0 1 2 3 100 [[ ],[ ],[burger],[like, meow, geek],[]...[foo]] 
  4. Quindi attraversa la matrice dalla fine e raccogli le k parole.

Soluzione 2:

passi:

  1. Come sopra
  2. Usa l’heap min e mantieni la dimensione dell’heap min su k, e per ogni parola dell’hash confrontiamo le occorrenze delle parole con min, 1) se è maggiore del valore min, rimuovi il min (se la dimensione del min heap è uguale a k) e inserisci il numero nell’heap min. 2) condizioni semplici di rest.
  3. Dopo aver attraversato l’array, convertiamo l’heap minimo in array e restituiamo l’array.

Non otterrai in genere un tempo di esecuzione migliore della soluzione che hai descritto. Devi fare almeno O (n) lavoro per valutare tutte le parole, e poi O (k) lavoro extra per trovare i migliori termini k.

Se il tuo problema è molto grande, puoi usare una soluzione distribuita come map / reduce. Se gli operatori cartografici contano le frequenze al 1 / enimo del testo ciascuna, e per ogni parola, inviarla a uno dei lavoratori del riduttore calcolati in base all’hash della parola. I riduttori sumno quindi i conteggi. Unisci l’ordinamento sulle uscite dei riduttori ti darà le parole più popolari in ordine di popolarità.

Una piccola variazione sulla tua soluzione produce un algoritmo O (n) se non ci preoccupiamo di posizionare la top K e una soluzione O (n + k * lg (k)) se lo facciamo. Credo che entrambi questi limiti siano ottimali all’interno di un fattore costante.

L’ottimizzazione viene di nuovo dopo aver eseguito l’elenco, inserendo nella tabella hash. Possiamo usare l’algoritmo mediana di mediani per selezionare il Kesimo elemento più grande nell’elenco. Questo algoritmo è provabilmente O (n).

Dopo aver selezionato l’elemento Kth più piccolo, partizioniamo la lista attorno a quell’elemento proprio come in quicksort. Questo è ovviamente anche O (n). Qualunque cosa sul lato “sinistro” del pivot è nel nostro gruppo di elementi K, quindi abbiamo finito (possiamo semplicemente buttare via tutto il resto mentre procediamo).

Quindi questa strategia è:

  1. Passare attraverso ogni parola e inserirla in una tabella hash: O (n)
  2. Seleziona il più piccolo elemento K: O (n)
  3. Partizione attorno a quell’elemento: O (n)

Se si desidera classificare gli elementi K, basta ordinarli con un ordinamento di confronto efficiente in O (k * lg (k)), ottenendo un tempo di esecuzione totale di O (n + k * lg (k)).

Il tempo limite O (n) è ottimale all’interno di un fattore costante perché dobbiamo esaminare ogni parola almeno una volta.

Anche il limite di tempo O (n + k * lg (k)) è ottimale perché non esiste un metodo basato sul confronto per ordinare gli elementi k in meno di k * lg (k).

Se la tua “lista di parole importanti” è abbastanza grande, puoi semplicemente campionare e ottenere stime. In caso contrario, mi piace l’aggregazione di hash.

Modifica :

Per campione intendo scegliere un sottoinsieme di pagine e calcolare la parola più frequente in quelle pagine. Se si selezionano le pagine in modo ragionevole e si seleziona un campione statisticamente significativo, le stime delle parole più frequenti dovrebbero essere ragionevoli.

Questo approccio è davvero ragionevole solo se si dispone di così tanti dati che l’elaborazione di tutto ciò è solo un po ‘sciocco. Se hai solo pochi mega, dovresti essere in grado di strappare i dati e calcolare una risposta esatta senza rompere il sudore anziché preoccuparti di calcolare una stima.

Puoi ridurre il tempo ulteriormente partizionando usando la prima lettera di parole, quindi partizionare il più grande set di più parole usando il prossimo carattere finché non hai k set di parole singole. Dovresti usare una sorta di albero a 256 vie con elenchi di parole parziali / complete alle foglie. Dovresti stare molto attento a non causare copie di stringa ovunque.

Questo algoritmo è O (m), dove m è il numero di caratteri. Evita quella dipendenza da k, che è molto bella per k grande [dal modo in cui il tempo di esecuzione postato è sbagliato, dovrebbe essere O (n * lg (k)), e non sono sicuro di quello che è in termini di m].

Se si eseguono entrambi gli algoritmi fianco a fianco si otterrà quello che sono abbastanza sicuro è un algoritmo O (min (m, n * lg (k))) asintoticamente ottimale, ma il mio dovrebbe essere più veloce in media perché non comporta hashing o ordinamento.

Hai un bug nella tua descrizione: il conteggio richiede O (n) tempo, ma l’ordinamento richiede O (m * lg (m)), dove m è il numero di parole univoche . Questo di solito è molto più piccolo del numero totale di parole, quindi probabilmente dovrebbe solo ottimizzare come viene costruito l’hash.

Il tuo problema è lo stesso di questo- http://www.geeksforgeeks.org/find-the-k-most-frequent-words-from-a-file/

Usa Trie e min heap per risolverlo efficacemente.

Se quello che cerchi è l’elenco delle k più frequenti parole nel tuo testo per qualsiasi k pratico e per qualsiasi langage naturale, allora la complessità dell’algoritmo non è rilevante.

Basta campionare , ad esempio, qualche milione di parole dal testo, elaborarle con qualsiasi algoritmo in pochi secondi e i conteggi più frequenti saranno molto accurati.

Come nota a margine, la complessità dell’algoritmo fittizio (1. conta tutti 2. ordina i conteggi 3. prendi il meglio) è O (n + m * log (m)), dove m è il numero di parole diverse nel tuo testo. log (m) è molto più piccolo di (n / m), quindi rimane O (n).

In pratica, il lungo passo sta contando.

  1. Utilizzare una struttura di dati efficiente in memoria per memorizzare le parole
  2. Usa MaxHeap per trovare le parole K più frequenti.

Ecco il codice

 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 maxHeap; public TopKFrequentItems(int k) { this.maxSize = k; this.maxHeap = new PriorityQueue(k, maxHeapComparator()); } private Comparator maxHeapComparator() { return new Comparator() { @Override public int compare(TrieEntry o1, TrieEntry o2) { return o1.frequency - o2.frequency; } }; } public void add(String word) { this.trie.insert(word); } public List 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 result = new ArrayList(); 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; } } 

}

Ecco i test unitari

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

Per maggiori dettagli, fare riferimento a questo test case

  1. usa una tabella hash per registrare la frequenza di tutte le parole mentre attraversi l’intera sequenza di parole. In questa fase, la chiave è “word” e il valore è “word-frequency”. Questo richiede O (n) tempo. Questo è uguale a tutti quelli sopra descritti

  2. Durante l’inserimento stesso in hashmap, mantieni Treeset (specifico per java, ci sono implementazioni in ogni lingua) di dimensione 10 (k = 10) per mantenere le 10 parole frequenti più frequenti. Fino alla dimensione è inferiore a 10, continua ad aggiungerlo. Se la dimensione è uguale a 10, se l’elemento inserito è maggiore dell’elemento minimo, ovvero il primo elemento. Se sì rimuovilo e inserisci un nuovo elemento

Per limitare la dimensione del set di alberi, vedere questo link

Supponiamo di avere una sequenza di parole “annuncio” “annuncio” “ragazzo” “grande” “cattivo” “com” “vieni” “freddo”. E K = 2. come hai detto “partizionamento usando la prima lettera di parole”, abbiamo ottenuto (“annuncio”, “annuncio”) (“ragazzo”, “grande”, “cattivo”) (“com” “vieni” “freddo”) “quindi partizionare il più grande set di più parole utilizzando il carattere successivo fino a quando non si hanno k insiemi di parole singole. ” partirà (“ragazzo”, “grande”, “cattivo”) (“com” “vieni” “freddo”), la prima partizione (“annuncio”, “annuncio”) è mancante, mentre “annuncio” è in realtà il parola più frequente

Forse frainteso il tuo punto. Puoi per favore dettagliare il tuo processo sulla partizione?

Credo che questo problema possa essere risolto con un algoritmo O (n). Potremmo fare lo smistamento al volo. In altre parole, l’ordinamento in quel caso è un sotto-problema del problema di ordinamento tradizionale poiché solo un contatore viene incrementato di uno ogni volta che accediamo alla tabella hash. Inizialmente, l’elenco è ordinato poiché tutti i contatori sono zero. Man mano che continuiamo ad incrementare i contatori nella tabella hash, conserviamo un altro array di valori hash ordinati per frequenza come segue. Ogni volta che incrementiamo un contatore, controlliamo il suo indice nell’array classificato e controlliamo se il suo conteggio supera il suo predecessore nell’elenco. Se è così, scambiamo questi due elementi. Come tale otteniamo una soluzione che è al massimo O (n) dove n è il numero di parole nel testo originale.

Anch’io stavo lottando con questo e mi sono ispirato a @aly. Invece di ordinare in seguito, possiamo semplicemente mantenere un elenco di parole preselezionato ( List> ) e la parola sarà nell’insieme alla posizione X dove X è il conteggio corrente della parola. In generale, ecco come funziona:

  1. per ogni parola, memorizzarla come parte della mappa della sua occorrenza: Map .
  2. quindi, in base al conteggio, rimuoverlo dal set di conteggio precedente e aggiungerlo al nuovo set di conteggio.

Lo svantaggio di questa è la lista forse grande – può essere ottimizzato usando una TreeMap> – ma questo aggiungerà un sovraccarico. In definitiva possiamo usare un mix di HashMap o la nostra struttura dati.

Il codice

 public class WordFrequencyCounter { private static final int WORD_SEPARATOR_MAX = 32; // UNICODE 0000-001F: control chars Map counters = new HashMap(); List> reverseCounters = new ArrayList>(); private static class MutableCounter { int i = 1; } public List 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 strings = reverseCounters.get(counter.i); strings.remove(word); counter.i ++; } addToReverseLookup(counter.i, word); } lastPosition = i + 1; } } List ret = new ArrayList(); int count = 0; for (int i = reverseCounters.size() - 1; i >= 0; i--) { Set 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()); } Set strings = reverseCounters.get(count); strings.add(word); } } 

Ho appena trovato l’altra soluzione per questo problema. Ma non sono sicuro che sia giusto. Soluzione:

  1. Usa una tabella hash per registrare tutte le parole ‘frequency T (n) = O (n)
  2. Scegli i primi k elementi della tabella hash e ripristinali in un buffer (il cui spazio = k). T (n) = O (k)
  3. Ogni volta, in primo luogo, è necessario trovare l’elemento min corrente del buffer e confrontare l’elemento min del buffer con gli elementi (n – k) della tabella hash uno per uno. Se l’elemento della tabella hash è maggiore di questo elemento min del buffer, rilascia il valore min del buffer corrente e aggiungi l’elemento della tabella hash. Quindi ogni volta che troviamo il min nel buffer bisogno di T (n) = O (k), e attraversare l’intera tabella hash bisogno di T (n) = O (n – k). Quindi l’intera complessità temporale per questo processo è T (n) = O ((nk) * k).
  4. Dopo aver attraversato l’intera tabella hash, il risultato è in questo buffer.
  5. La complessità di tutto il tempo: T (n) = O (n) + O (k) + O (kn – k ^ 2) = O (kn + n – k ^ 2 + k). Poiché, k è molto più piccolo di n in generale. Quindi per questa soluzione, la complessità temporale è T (n) = O (kn) . Questo è il tempo lineare, quando k è veramente piccolo. È giusto? Non sono davvero sicuro.

Prova a pensare a una struttura dati speciale per affrontare questo tipo di problemi. In questo caso un tipo speciale di albero come trie per memorizzare le stringhe in modo specifico, molto efficiente. O il secondo modo di build la tua soluzione come contare le parole. Immagino che questa TB di dati sia in inglese, quindi abbiamo circa 600.000 parole in generale, quindi sarà ansible memorizzare solo quelle parole e contare quali stringhe sarebbero ripetute + questa soluzione avrà bisogno di regex per eliminare alcuni caratteri speciali. La prima soluzione sarà più veloce, ne sono abbastanza sicuro.

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

Questa è un’idea interessante da cercare e potrei trovare questo documento relativo a Top-K https://icmi.cs.ucsb.edu/research/tech_reports/reports/2005-23.pd f

Inoltre c’è un’implementazione di questo qui .

Il codice più semplice per ottenere l’occorrenza della parola più utilizzata.

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

In queste situazioni, consiglio di utilizzare le funzionalità integrate di Java. Dal momento che sono già ben testati e stabili. In questo problema, trovo le ripetizioni delle parole usando la struttura dati HashMap. Quindi, spingo i risultati su una serie di oggetti. Ordino l’object con Arrays.sort () e stampo le prime k parole e le loro ripetizioni.

 import java.io.*; import java.lang.reflect.Array; import java.util.*; public class TopKWordsTextFile { static class SortObject implements Comparable{ 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 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 

Per ulteriori informazioni, visitare https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TopKWordsTextFile.java . Spero possa essere d'aiuto.

 ** 

C ++ 11 Implementazione del pensiero sopra

**

 class Solution { public: vector topKFrequent(vector& nums, int k) { unordered_map map; for(int num : nums){ map[num]++; } vector res; // we use the priority queue, like the max-heap , we will keep (size-k) smallest elements in the queue // pair: first is frequency, second is number priority_queue> 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; } 

};