Algoritmo efficiente per trovare le frasi più comuni in un grande volume di testo

Question

Sto pensando di scrivere un programma per raccogliere per me le frasi più comuni in un grande volume del testo. Se il problema fosse stato ridotto alla sola ricerca di parole, sarebbe stato semplice archiviare ogni nuova parola in una mappa di hash e quindi aumentare il conteggio su ciascuna occorrenza. Ma con le frasi, memorizzare ogni permutazione di una frase come una chiave sembra impossibile.

Fondamentalmente il problema è ridotto a capire come estrarre ogni frase possibile da un testo sufficientemente grande. Il conteggio delle frasi e l'ordinamento in base al numero di occorrenze diventano banali.

Answer 1

Presumo che si stiano cercando modelli comuni di parole consecutive che compaiono nello stesso ordine (ad esempio "la cima del mondo" non sarebbe contata come la stessa frase "cima di un mondo" o "il mondo di cima" ").

Se è così allora mi sento di raccomandare il seguente approccio lineare-tempo:

1. dividere il testo in parole e rimuovere le cose che non si considera significativo (cioè rimuovere maiuscole, la punteggiatura, interruzioni di parola, ecc)
2. Converti il ​​tuo testo in un array di interi (un intero per parola unica) (ad esempio ogni istanza di "cat" diventa 1, ogni "cane" diventa 2) Questo può essere fatto in tempo lineare usando un dizionario basato su hash per memorizzare le conversioni da parole a numeri. Se la parola non è nel dizionario, allora assegna un nuovo id.
3. Costruire un suffisso-array per l'array di numeri interi (questo è un elenco ordinato di tutti i suffissi del vostro array e può essere costruito da tempo lineare - ad esempio utilizzando l'algoritmo e il codice C here)
4. Costruire la più lunga comuni matrice di prefissi per l'array di suffissi. (Questo può essere fatto anche in tempo lineare, ad esempio usando questo C code) Questo array LCP fornisce il numero di parole comuni all'inizio di ogni suffisso tra coppie consecutive nell'array di suffissi.

Ora sei in grado di raccogliere le tue frasi comuni.

Non è abbastanza chiaro come si desidera determinare la fine di una frase. Una possibilità è semplicemente raccogliere tutte le sequenze di 4 parole che si ripetono.
Questo può essere fatto in tempo lineare lavorando attraverso l'array di suffissi guardando i punti in cui l'array di prefissi più lungo è> = 4. Ogni sequenza di indici x nell'intervallo [start + 1 ... start + len] dove il LCP [x]> = 4 (per tutti tranne l'ultimo valore di x) corrisponde a una frase che viene ripetuta len volte. La frase stessa è data dalle prime 4 parole di, ad esempio, suffisso start + 1.

Si noti che questo approccio potrebbe individuare le frasi che attraversano la fine della frase. Potresti preferire di convertire alcuni segni di punteggiatura come gli arresti completi in numeri interi univoci per impedirlo.