Naïve Swype Implementation (& How It Works)

How does Swype work? I don't know for sure, but I came up with a fairly simple approximation of Swype's behavior on Android phones. Which with a little bit of tweaking (maybe some more math and a better set of dictionaries) it could probably get a lot closer to approximating Swype.

This is implemented using Proce55ing which will export Proce55ing code to a Java applet (full source listing).

As for how the implementation works, I started with a word set which holds a collection of words and word prefixes.  The classify operation serves to tell me if the string I am holding is a complete word, a partial word, an incomplete word, or both.

A returned classification is also able to communicate it's frequency (ranking in frequency of usage in common english text).  These frequencies were acquired from Project Gutenburg.  The frequency list is a frequency count from Usenet postings, so it's a bit odd and doesn't include some common words (most notably some connecting words).  The other dictionary is a list of the 3000 most common English words.

Keep this in mind when you play with the sample, the dictionaries aren't perfect.  The naïve implementation along with the poor dictionaries give the demonstration some peculiarities.

Regargless, the populate operation of the word set loads these words, their frequencies, and all prefixes leading up to the word in a dictionary.  For example the word THEY is loaded in as T (stored as incomplete), TH (incomplete), THE (complete & incomplete) and THEY (complete) along with the corresponding word frequencies.


Next is all the connecting glue for Proce55ing. The SwypeState class maintains the keyboard hit collector, the word set, and the bits that draw the keyboard and the pen.  The keyboard logic and the keyboard hit collector are fairly boring, but suffice to say, they draw the keyboard and accurately collect what keys where hit when drawing over the keyboard.


Probably the most interesting part of the implementation is figuring out what words where Swyped.  The system passes an event to the key hit collector when a word is finished, this initiates a seach through the word set for potential words.  For a given word like "THEY" the actual keys swiped can vary widely.

Here are some examples (these all map to "THEY"):

  T, Y, H, G, F, E, R, T, Y

  T, G, H, N, C, D, S, E, R, F, C, X, S, W, T, G, V, C, S, E, Y

  T, Y, H, J, K, K, J, H, G, F, D, S, A, Q, W, E, R, T, Y

So, you have some things that don't really look like words at all.  However, the word set loaded with all the word prefixes sorts this out.  It does this using a simple search that slowly builds up a set of prefixes that map to partial words, or complete words (which get recorded), while throwing away things that map to nothing.  As a new letter is examined from the list of hit keys it is added to each of the previously collected prefixes.

In this manner words like OR, OUR, OUT that require one vertical swipe can be detected.  This word overlap presents another problem though: which word has priority?

The first strategy used to resolve overlapping words is a sort based on match length.  With the idea that the longest match is probably the word the user was trying to spell.  For example, a word like THERE will come up with THE as a complete prefix when THERE was then intended swipe because of the swipe length.

The second strategy is where the word frequencies come in to play, they attempt to sort the list of hit words by their frequency.  Words with a higher frequency in the English language should bubble to the top.

Improvements:

• Better dictionaries: Possibly one that lists all forms of a word with the same frequency (e.g. be, being, been).
• Fat finger search: extend and trim each swipe path so that less accuracy is needed.  That is, a what's around you operation could be added to each key to get many more paths to search that could lead to the desired word.
• Spell checking: for people that don't know how to spell, predictive text can be frustrating.  A misspelling dictionary could be really using to help with this.
• Markov chain: I don't know how effective this would be but since Markov Chains can be used to generate English text it seems like they could be used to select a more likely next word.

The full source code is available at github.com.