Confrontando distanza stringa sulla base di hash precalcolate

Question

Ho un elenco di grandi dimensioni (oltre 200.000) di stringhe che mi piacerebbe confrontare ad una data stringa. La proposta stringa viene inserita da un utente, quindi potrebbe essere leggermente corretto.

Quello che speravo di fare era creare una sorta di hash precalcolate su ogni stringa su aggiungerlo alla lista. Questo hash dovrebbe contenere informazioni quali la lunghezza della stringa, l'aggiunta di tutti i personaggi, ecc

La mia domanda è, fa qualcosa di simile già esiste? Sicuramente ci sarebbe qualcosa che mi permette di evitare l'esecuzione Levenshtein distanza su ogni stringa nella lista?

O forse c'è una terza opzione che non ho ancora pensato?

Answer 1

Sembra che si desidera utilizzare un hash sfocata di qualche tipo. Ci sono un sacco di funzioni hash disponibili che possono fare cose come questa. L'algoritmo vecchio classico " SOUNDEX " potrebbe anche lavoro.

Un altro pensiero - se si stima che la probabilità di una voce non corretta è basso, allora si potrebbe effettivamente andare bene avere un colpo diretto il 99,9% del tempo, ricadendo a SOUNDEX che potrebbe prendere il 90% dei rimanenti casi e poi la ricerca l'intera lista per il restante 0,01% del tempo.

Anche la pena di verificare questa discussione: Come cercare corrispondenza fuzzy per una stringa in un grande database di stringa