问题:

I am doing some research on string matching algorithms. One of the most usable I came across is the one my cellphone uses (android 2.3.4 on SE xPeria neo v).

As seen in the screenshot, I pressed the characters jiw which are near the ones I wanted and it suggested correctly.

It seems like the algorithm is similar to levenstein distance (distance between my input and the dictionary). Somehow the near characters have some value in the string-matching.

Any idea about the algorithm being used?

回答1:

I pulled the Android source code and looked for spell checking. I found this directory which seems to contain the sources you are looking for:

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

The file spellcheck/AndroidSpellCheckerService.java looks like the one doing all the heavy work, but Suggest.java also seems to be involved in some way.

回答2:

This excellent information retrieval book has a detailed section on Levenstein distance, including weighted variations. The weights could then be taken to be the distance between keys on your keypad.