Algoritmo desiderato: trova tutte le parole di un dizionario simili alle parole in un testo libero

Question

Abbiamo un elenco di circa 150.000 parole e quando l'utente immette un testo libero, il sistema dovrebbe presentare un elenco di parole dal dizionario , che sono molto vicini alle parole nel testo libero.

Ad esempio, l'utente inserisce: "Vorrei acquistare giocattoli legoe in Walmart". Se il dizionario contiene "Lego", "Car" e "Walmart", il sistema dovrebbe presentare "Lego" e "Walmart" nell'elenco. "Walmart" è ovvio perché è identico a una parola nella frase, ma "Lego" è abbastanza simile a "Legoe" da menzionare anche. Tuttavia, nulla è simile a "Car", quindi la parola non viene mostrata.

La visualizzazione dell'elenco deve essere in tempo reale, ovvero quando l'utente ha inserito la frase, l'elenco di parole deve essere presente sullo schermo. Qualcuno conosce un buon algoritmo per questo?

Il dizionario contiene effettivamente concetti che possono includere uno spazio. Ad esempio, "Lego navicella spaziale". La soluzione perfetta riconosce anche questi concetti multi-parola.

Qualsiasi suggerimento è gradito.

Answer 1

Dai un'occhiata a http://norvig.com/spell-correct.html per un semplice algoritmo. L'articolo usa Python, ma alla fine ci sono collegamenti alle implementazioni in altre lingue.

Answer 2

Potrebbe essere interessante osservare alcuni algoritmi come lo Levenshtein distance, che può calcolare la quantità di differenza tra 2 stringhe.

Non sono sicuro di quale lingua si sta pensando di utilizzare, ma PHP ha una funzione chiamata levenshtein che esegue questo calcolo e restituisce la distanza. C'è anche una funzione chiamata similar_text che fa una cosa simile. C'è una code example here per la funzione levenshtein che controlla una parola contro un dizionario di possibili parole e restituisce le parole più vicine.

Spero che questo ti dia un po 'di informazioni su come una soluzione potrebbe funzionare!

Answer 3

È probabile che si desideri utilizzare un algoritmo che calcola lo Levenshtein distance.

Tuttavia, dal momento che il set di dati è abbastanza grande e si confrontano molte parole contro di esso, un'implementazione diretta di typical algorithms non è pratica.

Per trovare le parole in un ragionevole lasso di tempo, è necessario indicizzare il set di parole in un modo che faciliti fuzzy string matching.

Uno di questi metodi di indicizzazione consisterebbe nell'utilizzare uno suffix tree. Un altro approccio sarebbe quello di utilizzare n-grams.

Mi piacerebbe utilizzare un albero di suffisso poiché trovo più facile avvolgerlo intorno alla testa e lo trovo più adatto al problema.

Answer 4

Farai parecchie ricerche di parole su un dizionario fisso. Pertanto è necessario preparare il dizionario. Logicamente, puoi eliminare rapidamente candidati "troppo diversi".

Per esempio, le parole e le cardissimilar può condividere un suffisso, ma sono ovviamente non errori di ortografia di ogni altro. Ora, perché è così ovvio per noi umani? Per i principianti, la lunghezza è completamente diversa.Questa è una squalifica immediata (ma con una eccezione - sotto). Quindi, il tuo dizionario dovrebbe essere ordinato in base alla lunghezza della parola. Abbina la tua parola in ingresso con parole di lunghezza simile. Per parole brevi significa +/- 1 carattere; le parole più lunghe dovrebbero avere un margine più elevato (esattamente quanto può essere buono il tuo incantesimo demografico?)

Una volta che ti sei limitato a parole candidate di lunghezza simile, vorrai togliere le parole che sono completamente dissimili. Con questo intendo che usano lettere completamente diverse. Questo è più facile da confrontare se si ordinano le lettere in una parola in ordine alfabetico. Per esempio. car diventa "acr"; rack diventa "ackr". Lo farai in pre-elaborazione per il tuo dizionario e per ogni parola in ingresso. Il motivo è che è economico determinare la (dimensione di una) differenza di due serie ordinate. (Aggiungi un commento se hai bisogno di una spiegazione). car e rack hanno una differenza di dimensione 1, car e hat hanno una differenza di dimensione 2. Questo restringe ulteriormente il vostro gruppo di candidati. Nota che per parole più lunghe, puoi uscire presto quando hai trovato troppe differenze. Per esempio. dissimilar e biography hanno una differenza totale di 13, ma considerando la lunghezza (8/9) si può probabilmente uscire di emergenza una volta trovate 5 differenze.

Questo ti lascia con una serie di parole candidate che usano quasi le stesse lettere, e sono anche quasi della stessa lunghezza. A questo punto puoi iniziare ad usare algoritmi più raffinati; non è più necessario eseguire 150.000 confronti per parola di input.

Ora, per l'eccezione di lunghezza menzionata in precedenza: il problema è in "parole" come greencar. In realtà non corrisponde a una parola di lunghezza 8, eppure per gli umani è abbastanza ovvio cosa si intendesse. In questo caso, non è possibile interrompere realmente la parola di input su un qualsiasi limite casuale ed eseguire una coppia addizionale N-1 su entrambe le metà. Tuttavia, è possibile verificare solo uno spazio mancante. Basta fare una ricerca per tutti i possibili prefissi. Questo è efficiente perché utilizzerai più volte la stessa parte del dizionario, ad es. ggr, gre, gree, ecc. Per ogni prefisso che hai trovato, controlla se il suffisso rimanente si trova anche nella dizione, ad es. reencar, eencar. Se entrambe le metà della parola di input sono nel dizionario, ma la parola stessa non lo è, puoi assumere uno spazio mancante.