Bug Vanquisher

11 October 2007

How T9 Mode Works?

Filed under: Tips — Tanveer Badar @ 9:49 PM

I got this search string logged today ‘DRAW HEURISTICS FOR T9 DICTIONARY SEARCH’. Must be related to this post.

The algorithm to suggest words in T9 mode is very simple. All you need is a dictionary which stores the number sequence of keys pressed. For example, pressing 4663 can give you these six words: good, home. gone, hood, hoof, hone. The way it should work is to:
1- Store the currently typed number
2- Use it as the key to index the dictionary and get the list of all possible words that can be formed by that number sequence.
3- When the action key is pressed, cycle through that list. Start over.

Let’s say you want to simulate the functionality in a C++ application, here is now you would proceed.

// This code is utterly buggy, entirely untested, written out of the top of my head, in 10 minutes, using notepad, never seen a compiler in its life, some syntax may even be only valid in C# as my exposure to C++ these days is very limited. Use with your own responsibility.

#include <map>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

map< string , vector< string > > get_data( );

class T9
{
    vector< wstring > current_list;
    map< string , vector< wstring > > t9_dictionary;
    int index;

    void reset_list( )
    {
        if( t9_dictionary.size( ) )
            current_list = t9_dictionary.begin( ).first;
    }
public:
    T9( )
        : t9_dictionary( get_data( ) )
    {
        reset_list( );
    }

    void add_word( const wstring& word )
    {
        if( find( current_list.begin( ) , current_list.end( ) , word ) == current_list.end( ) )
            current_list.push_back( word );
    }

    void update_list( const string& current_number )
    {
        if( t9_dictionary.find( current_number ) == t9_dictionary.end( ) )
            t9_dictionary [ current_number ] = vector< wstring >( );
        current_list = t9_dictionary [ current_number ];
    }

    wstring& get_next_word( )
    {
        if( index < current_list.size( ) )
            return current_list [ size ];
        else
            index = 0;
        if( current_list.size( ) )
            return current_list [ index ];
        return L””;
    }
};

Advertisements

2 Comments »

  1. hello, i´m interested in programming something like that, but i´d like to use a trie. my idea is that every node in the trie should have a combination of numbers, and each combination would show a list of the possible words with that combination…

    could you give me a hand??

    thanks anyway

    Comment by gustavo — 18 November 2007 @ 12:30 AM

  2. It is quite an interesting idea. I definitely remember reading about suffix trees, google for suffix trees.
    When using trees for implementing T9 dictionary, one should replace the map with a tree that stores prefixes for each node. map, multi_map, set and multi_set are already implemented using AVL trees in Visual C++ implementation of C++ library, it is a nice optimization to roll your own tree.
    While searching for the words represented by a particular number combination, one should traverse the nodes. Each node would have 8 children because 1 and 0 are not used.
    I’ll work on this idea and will definitely finish it by the next weekend. Do visit again :).

    Comment by Tanveer Badar — 18 November 2007 @ 12:45 AM


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: