Algoritmo per Confrontando le parole (non in ordine alfabetico)

Question

Ho bisogno di codificare una soluzione per un determinato requisito, e volevo sapere se qualcuno è o familiarità con una libreria di off-the-shelf che può raggiungere, o mi può indirizzare al meglio la pratica. Descrizione:

L'utente immette una parola che si suppone essere una delle diverse opzioni fisse (tengo le opzioni in una lista). So che l'ingresso deve essere in un membro della lista, ma dal momento che è l'input dell'utente, lui / lei può avere commesso un errore. Sto cercando un algoritmo che mi dirà qual è la parola più probabile che l'utente voleva dire. Non ho nessun contesto e non posso forzare l'utente può scegliere una lista (cioè deve essere possibile inserire la parola liberamente e manualmente).

Ad esempio, dire che la lista contiene le parole "acqua", “quartiere”, "birra", “barbabietola”, “inferno”, “ciao” e "aardvark".

La soluzione deve tenere conto di diversi tipi di "normali" errori:

• errori di battitura di velocità (per esempio raddoppiando personaggi, lasciando cadere caratteri ecc)
• errori di battitura tastiera adiacente caratteri (ad esempio "Qater" per “acqua”)
• Non nativi errori di battitura in inglese (ad esempio "quater" per “quarto”)
• E così via ...

La soluzione più ovvia è quella di confrontare lettera per lettera e dare "pesi" di penalità per ogni lettera diversa, lettera in più e lettera mancante. Ma questa soluzione ignora migliaia di errori "standard" Sono sicuro che sono elencati da qualche parte. Sono sicuro che ci sono là fuori euristiche che si occupano di tutti i casi, sia specifici e generali, probabilmente utilizzando un ampio database di disallineamenti standard, (io sono aperto a soluzioni di dati-pesante).

Sono la codifica in Python, ma prendere in considerazione questa domanda indipendente dal linguaggio.

Tutti i consigli / pensieri?

Answer 1

Si vuole leggere come Google fa questo: http://norvig.com/spell-correct. html

Edit: Alcune persone hanno detto algoritmi che definiscono una metrica tra un utente data parola e una parola candidato (levenshtein, soundex). Questa non è però una soluzione completa al problema, dal momento che si potrebbe anche bisogno di un datastructure per eseguire in modo efficiente una ricerca vicino di casa non euclideo più vicino. Questo può essere fatto per esempio con l'Albero di copertina: http://hunch.net/~jl/projects/cover_tree /cover_tree.html

Answer 2

Una soluzione comune è quello di calcolare il Levenshtein distanza tra l'ingresso e vostri testi fissi. La distanza Levenshtein di due stringhe è solo il numero di semplici operazioni - inserzioni, delezioni e sostituzioni di un singolo carattere -. Necessaria per trasformare uno della stringa nell'altra

Answer 3

Avete considerato algoritmi che mettono a confronto con i suoni fonetici, come soundex ? Non dovrebbe essere troppo difficile per produrre rappresentazioni soundex del vostro elenco di parole, memorizzarli, e quindi ottenere un soundex di input dell'utente e di trovare la corrispondenza più vicina lì.

Answer 4

Cercare l'algoritmo Bitap. Si qualifica bene per quello che si vuole fare, e anche dotato di un esempio di codice sorgente in Wikipedia.

Answer 5

Se il set di dati è davvero piccolo, semplicemente confrontando la distanza Levenshtein su tutti gli articoli dovrebbero indipendentemente bastare. Se è più grande, però, è necessario utilizzare un BK-Tree o simile sistema di indicizzazione. L'articolo ho collegato a descrive come trovare le partite all'interno di una data distanza Levenshtein, ma è abbastanza semplice per adattarsi a fare ricerche più vicino-vicino di casa (e lasciato come esercizio al lettore;).

Answer 6

Anche se non può risolvere l'intero problema, si può prendere in considerazione utilizzando l'algoritmo soundex come parte della soluzione. Una rapida ricerca google di "soundex" e "python" ha mostrato alcune implementazioni pitone dell'algoritmo.

Answer 7

Prova a cercare "Levenshtein distanza" o "edit distance". Conta il numero di operazioni di modifica (eliminare, inserire, modificare lettera) è necessario per trasformare una parola in un altro. Si tratta di un algoritmo comune, ma a seconda del problema che si potrebbe avere bisogno di qualcosa di speciale con pesi diversi per i diversi tipi di errori di battitura.