Confronto veloce di una stringa con una raccolta in Java

Question

Sto cercando di calcolare le distanze di modifica di una stringa rispetto a una raccolta per trovare la corrispondenza più simile. Il mio problema attuale è che la collezione è molto grande (circa 25000 articoli), quindi ho dovuto restringere il set a stringhe di lunghezza simile ma che comunque lo restringerebbero solo a poche migliaia di stringhe e questo è ancora molto lento. Esiste una struttura dati che consente una rapida ricerca di stringhe simili o esiste un altro modo per risolvere questo problema?

Answer 1

Suoni come un BK-tree potrebbero essere ciò che desideri. Ecco un articolo che li discute: http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees. A quick Google produce alcune implementazioni Java.

Answer 2

Se i tuoi criteri per "simile" definiscono un ordinamento totale, dovresti essere in grado di definire un comparatore e utilizzare un set di alberi per trovare le corrispondenze più vicine (ad esempio utilizzando i metodi del soffitto e del pavimento).

Answer 3

Gli strumenti automatici di Levenshtein consentono di selezionare rapidamente un insieme di parole da un dizionario di grandi dimensioni in modo tale che si trovino all'interno della distanza Levenshtein specificata da una determinata parola.

Vedere: Schulz K, Mihov S. (2002) Fast String Correction with Levenshtein-Automata.