how to predict or trace words from gestures on android keyboard

Question

I am trying to develop a keyboard for Android and I don't understand the background theories / algorithms about how to implement prediction of words by swiping (tracing) them on the keyboard as they were implemented in Swype, SwiftKeys and Android Built-in Keyboard.

Any document or example is appreciated.

Answer 1

I have some suggestions.

Firstly, take a look at AnySoftKeyboard source code. This is basic but full-featured with text prediction and dictionaries. The code is clean and would make a good platform for extensions. Check out the Suggest, WordComposer and BinaryDictionary classes for functionality relating to word prediction. It has a dictionary with word frequency which tells you how frequently a word is found in 'real life'.

Secondly for the swipe algorithm. What you know for sure when a user swipes is what characters they started and finished on. This is a great start for prediction. I played with Swype a bit and it seems to always respect the start and end character.

In between the start and end characters, you have the ones the swipe passed over. These are possible characters to fill in the blanks. Now you can start taking guesses by making combinations of those chars and checking the dictionary for likely words. You'd always start your guess with the starting character, fill in some of the candidates from the swipe, and end with the finishing character. Show the user the best (highest frequency) matches from the dictionary.

That could be a lot of combinations to try, say 2^(n-2) where n is the number of characters under the swipe. So I'd suggest using a 'greedy' search and successively add characters from the start, keeping them if they match words in the dictionary otherwise discard them. Some refinements to this approach are probably necessary.

Another source of information you can use is when the swipe slows or changes direction on a particular character. You can detect this by calculating the speed (or acceleration) of the touch gesture. Points where the speed is low (or high deceleration) are likely to be characters the user wants.

So as an example, someone has swiped 'the'. They started on t, changed direction on h, and finished on e. These are your known points. Then you start guessing: the, tyhe, thge, thgfe, and so on and pick the words from the dictionary with the highest frequency count, which is obviously 'the' in this case.

Taking that algorithm and combining it with the prediction built into AnySoftKeyboard should yield something that works.

Hope that helps... tell us if you build it!

Answer 2

Prediction of words algo will go something like this.
you can provide your own static dictionary in the apk. when user installs it you can start with providing the word prediction after installation and first use.
To improve user experience you can have an algorithm to find the frequent words the user type.
and considering standard english(us) keyboard as an example you can see the proximity to the letter key which swipes user have done and show the suggestions accordingly.
ie. if user want to type(swipe) the word "SUN" , he starts swiping from the letter S and continues to Y instead of U and lastly to N. so you can use the PROXIMITY on the letter Y to find nearest set of letters. which are T, G, H, J, and U that suggest. words STN, SGN, SJN, SHN, SUN. so you can display SUN or TYPE - "SUN" in the textbox. OR if the user have used "SGN" or "SVN" more frequently you can have suggestion "SGN", "SUN" to the user and let the user to select the right word.
Going broad. Using sentences to Predict words
Continuing the same example of the word "SUN"
If the sentence user want to type is
I will commit on SVN tonight
so you can have the context of the sentence around the word (like the word commit etc..) SVN and correct the miss-typed(miss-swiped) S-Y-N to SVN directly.
or if the user wants to type a sentence
The SUN will rise in north today
you can apply the same thing according to the sentence context (like the word rise etc..) and let the S-Y-N mistake auto-correct to SUN.

Note :
This is my idea of designing the algorithm. If I have to implement the same thing I will use an Algorithm like this.

Answer 3

We can break down the input process into more manageable chunks.

1. User places their finger on/near a starting letter.
2. User drags finger over/near X more letters.
3. User releases finger on/near the final letter.

The result of this is some jumble of letters where the order and proximity are the most important indicators of the actual word they were trying to enter. So now, the task is to take this sorted list of letters and find the closest matches in our dictionary.

The simple, brute-force approach here would be to query the database for words by dropping letters. For example, "DSRTYUIOKNBVFRE" could legitimately contain "DRY", I", "DO", "RUN", "SUN", "SON", "STOVE", "DRIVE", "STOKE", and probably a few dozen or so others. Suddenly, we've already reduced the search space to a few dozen words from a dictionary of thousands.

But we can do better than that. We know the user probably started near the correct letter and ended near the correct letter, so words like "DRY", "I", "DO", "RUN" and "SON" are unlikely to be correct, as they miss out lots of letters at the start and/or end of the input. So we can refine the list to the final three that I found: "STOVE", "DRIVE" and "STOKE" (and maybe a dozen more)

Assuming we're also weighing letters based on how close the user's finger went to them, we could further refine this list and then present them to the user in order.

Obviously I've skipped over the tricky details here - like converting the jumble of "DSRTYUIOKNBVFRE" into a list of possible words, and performing matching based on the input and the found strings. But I hope I've given an overview of how such keyboards work (and I'm sure they're now much more advanced than my description).