Algoritmo automatico corretto

Question

Voglio implementare quanto segue in C++:

1) Verificare se la parola data esiste in un dizionario. Il file del dizionario è un file enorme; considera 100 MB o 3-4 milioni di parole.

2) Suggerisci correzioni per la parola errata.

3) Funzione di completamento automatico.

mio approccio

1) Ho intenzione di costruire un albero in modo da cercare volontà efficiente.

2) Non riesco a capire come implementare la funzione di correzione automatica.

3) Posso implementare automatico caratteristica completo utilizzando alberi

Qual è la migliore struttura dei dati e l'algoritmo per implementare tutte le caratteristiche di cui sopra?

Answer 1

È possibile eseguire il completamento automatico esaminando tutte le stringhe in una determinata sottostruttura. Alcuni punteggi per aiutarti a scegliere potrebbero aiutarti. Funziona in questo modo se hai "te" che percorri quel sentiero nel trie e attraversi tutto il sottoalbero per ottenere tutti i possibili finali.

Per le correzioni è necessario implementare qualcosa come http://en.wikipedia.org/wiki/Levenshtein_distance sull'albero. Puoi usare il fatto che se hai elaborato un determinato percorso nel trie, puoi riutilizzare il risultato per tutte le stringhe nel sottoalbero radicato alla fine del tuo percorso.

Answer 2

1) Oltre alberi, un altro metodo interessante è BWT
http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform
BWT matrice suffisso può essere facilmente utilizzato per monitorare parole con prefisso specificato.

2) Per la correzione degli errori, approccio moderno è LHS:
http://en.wikipedia.org/wiki/Locality-sensitive_hashing#LSH_algorithm_for_nearest_neighbor_search

Alcuni collegamenti forniti in modo casuale da Google Search:
https://cs.stackexchange.com/questions/2093/efficient-map-data-structure-supporting-approximate-lookup
https://code.google.com/p/likelike/
http://aspguy.wordpress.com/2012/02/18/the-magic-behind-the-google-search/

Answer 3

ho lavorato sulla stesso problema. Finora la soluzione migliore che ho incontrato è l'utilizzo di un albero di ricerca ternario per il completamento automatico. Gli alberi di ricerca ternari sono più efficienti rispetto ai tentativi. Se non riesco a trovare la stringa cercata nella mia struttura di ricerca ternaria, utilizzo un albero BK già costruito per trovare la corrispondenza più simile. BK Tree utilizza internamente la distanza di Levenshtein.

I metafoni sono anche qualcosa che potresti voler esplorare, ma non sono entrato nella profondità delle metafonie.

Ho una soluzione in Java per BK TREE + TERNARY SEARCH TREE se ti piace.