Data structure behind T9 type of dictionary

Question

How does a T9 dictionary work? What is the data structure behind it. If we type '4663' we get 'good' when we press down button we get 'gone' then 'home' etc...

EDIT: If the user types in 46 then it should show 'go' and when pressed down arrow should show 'gone' etc...

Answer 1

It can be implemented in several ways, one of them is Trie. The route is represented by the digits and the nodes point to collection of words.

It can be implemented using nested hash tables as well, the key of the hash table is a letter and on every digit the algorithm calculates all possible routes (O(3^n) routes).

Answer 2

4663

translates to

{G,H,I}{M,N,O}{M,N,O}{D,E,F}

T9 works by filtering the possibilities down sequentially starting with the first possible letters. So the first step in your example will be to filter the dictionary list to all words beginning with G, H, or I. Next step, take that list and filter the second letters by M, N, O. And so on...

Answer 3

I guess, as those before that T9 uses a trie, where the links are represented by a bitmap (1 bit per letter). This is called a succinct data structure, as Steve Hanov explains very nicely:

http://stevehanov.ca/blog/index.php?id=120