Swype is an awesome software which makes typing in mobile phones using the qwerty keyboard very easy. This is how it looks:
I was just thinking how this could be implemented. It boils down to a string sub-sequence problem. The path traced by the user consists of all the characters in a word. This is an ideal situation, but many a times, we do not take care of all the characters in between and miss many of them.
Some of the characteristics i have considered:
1. Filtering of words based on the first and last character.
2. Characters which are buried among other characters in the path traversed by the user.
3. The number of traversals between different rows of the keyboard gives us a fair idea about the length of the word.
We can use a number of such characteristics and increase the chances of suggesting the right word. One such hint i can think of is:
Split the words in sets of three characters:
Lets take the case of the word "English" here. The actual trace may be like "edfgbnbghjkliugfdsdfgh"
Groups like bnb, bgh, kli, dsd strongly suggest that there is a turn which signifies a character which has a higher probability of being present in the word.
I wrote a basic version of this using python and this wordlist. Some basic introduction to some of the functional programming used here is discussed in this link
The results for the same were pretty good.
['hello', 'hero', 'ho']
['wed', 'weird', 'weld', 'wild', 'wold', 'word', 'world', 'would']
['doctor', 'door', 'dour']
['adjure', 'agriculture', 'article', 'astute']
The basic version was working within an hour. I must say that the string split method in python is very well thought of. split( delimiter, 1) returns a the string before and after the first match.