Which algorithm is being used in Android's spell checker?

algorithm, string-matching

Solution

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.

Problem

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?

Original source