Quale algoritmo viene utilizzato nel correttore ortografico di Android?

Question

Sto facendo qualche ricerca sugli algoritmi di corrispondenza delle stringhe. Uno dei più utilizzabili che ho trovato è quello che usa il mio cellulare (Android 2.3.4 su SE xPeria neo v).

Come si vede nello screenshot, ho premuto i personaggi jiw che sono vicino quelli che volevo e che ha suggerito in modo corretto.

Sembra che l'algoritmo sia simile a levenstein distance (distanza tra il mio input e il dizionario). In qualche modo i personaggi vicini hanno un valore di pari a nella corrispondenza delle stringhe.

Qualche idea sull'algoritmo in uso?

Answer 1

Ho tirato il Android source code e ho cercato il controllo ortografico. Ho trovato questo elenco che sembra contenere le fonti che stai cercando:

packages/inputmethods/LatinIME/java/src/com/android/inputmethod/latin/ 

Il file spellcheck/AndroidSpellCheckerService.java sembra quello di fare tutto il lavoro pesante, ma Suggest.java sembra anche essere coinvolta in qualche modo.

Answer 2

Questo excellent information retrieval book ha una sezione dettagliata su Levenstein distance, comprese le variazioni ponderate. I pesi potrebbero quindi essere considerati come la distanza tra i tasti sulla tastiera.