portella.com.br

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"

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

WORDS = open('wordlist.txt').read().split()
KEYBRD_LAYOUT = ['qwertyuiop', 'asdfghjkl', 'zxcvbnm']

def match(path, word):
    """ Checks if a word is present in a path or not. """

    try:
        for char in word:
            path = path.split(char, 1)[1]
        return True
    except : return False

def get_keyboard_row( char ):
    """ Returns the row number of the character """

    for row_no, row in enumerate(KEYBRD_LAYOUT):
        if char in row:
            return row_no

def compress(sequence):
    """ Removes redundant sequential characters. ex : 11123311 => 1231 """
    ret_val = [ sequence[0] ]
    for element in sequence:
        if ret_val[-1] != element:
            ret_val.append(element)
    return ret_val

def get_minimum_wordlength(path):
    """ 
    Returns the minimum possible word length from the path.
    Uses the number of transitions from different rows in 
    the keyboard layout to determin the minimum length
    """
    row_numbers = map(get_keyboard_row, path)
    compressed_row_numbers = compress(row_numbers)
    return len(compressed_row_numbers) - 3

def get_suggestion(path):
    """ Returns suggestions for a given path. """

    suggestions = filter(lambda x: x[0] == path[0] and x[-1] == path[-1], WORDS)
    suggestions = filter(lambda x: match(path, x), suggestions)

    min_length = get_minimum_wordlength(path)
    suggestions = filter(lambda x: len(x) > min_length, suggestions)

    return suggestions

if __name__ == '__main__':
    test_cases = ['heqerqllo',                   # hello
        'qwertyuihgfcvbnjk',                     # quick
        'wertyuioiuytrtghjklkjhgfd',             # world
        'dfghjioijhgvcftyuioiuytr',              # doctor
        'aserfcvghjiuytedcftyuytre',             # architecture
        'asdfgrtyuijhvcvghuiklkjuytyuytre',      # agriculture
        'mjuytfdsdftyuiuhgvc',                   # music
        'vghjioiuhgvcxsasdvbhuiklkjhgfdsaserty', # vocabulary 
        ]

    for test in test_cases:
        print get_suggestion(test)

The results for the same were pretty good.

 ['hello', 'hero', 'ho']
 ['quick']
 ['wed', 'weird', 'weld', 'wild', 'wold', 'word', 'world', 'would']
 ['doctor', 'door', 'dour']
 ['architecture']
 ['adjure', 'agriculture', 'article', 'astute']
 ['music', 'mystic']
 ['vocabulary']

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.

oplocks = yes 

level2 oplocks = yes 

kernel oplocks = no