Structure de données derrière un dictionnaire de type T9

Question

Comment fonctionne un dictionnaire T9 ? Quelle est la structure de données qui le sous-tend ? Si nous tapons '4663', nous obtenons 'bon'. Si nous appuyons sur le bouton 'down', nous obtenons 'gone', puis 'home', etc...

EDIT : Si l'utilisateur tape 46, il doit afficher 'go' et quand il appuie sur la flèche vers le bas, il doit afficher 'gone' etc...

Answer 1

Il peut être mis en œuvre de plusieurs façons, l'une d'entre elles étant la suivante Trie . L'itinéraire est représenté par les chiffres et les nœuds pointent vers une collection de mots.

Il peut également être mis en œuvre à l'aide de tables de hachage imbriquées, la clé de la table de hachage de l'utilisateur. table de hachage est une lettre et pour chaque chiffre, l'algorithme calcule toutes les routes possibles (O(3^n) routes).

Answer 2

4663

se traduit par

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

T9 fonctionne en filtrant les possibilités de manière séquentielle en commençant par les premières lettres possibles. Ainsi, dans votre exemple, la première étape consistera à filtrer la liste du dictionnaire sur tous les mots commençant par G, H ou I. L'étape suivante consistera à prendre cette liste et à filtrer les secondes lettres par M, N, O. Et ainsi de suite...

Answer 3

Je suppose, comme ceux d'avant que T9 utilise un trie, où les liens sont représentés par un bitmap (1 bit par lettre). C'est ce qu'on appelle une structure de données succincte, comme l'explique très bien Steve Hanov :

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

Answer 4

Je pense que T9 utilise un Trie basé sur le bitmap. Au premier niveau, il y a un mot de 32 bits (je suppose qu'ils ont été étendus à 32) où chaque bit représente une lettre. Toutes les lettres qui sont valides comme lettres de départ pour un mot ont leur bit activé.

Au niveau suivant, il y a une carte de 32 bits pour chacun des bits qui ont été activés au niveau précédent. Dans ces cartes, chaque bit est activé si la lettre correspondante est valide comme deuxième lettre d'un mot, la lettre de départ étant déterminée par le premier niveau.

La structure se poursuit ensuite. L'utilisation d'un bit par lettre permet un stockage très efficace. Le schéma d'adressage doit cependant être un défi. Il pourrait également y avoir une sorte d'optimisation en utilisant le schéma ci-dessus pour les mots courts et en utilisant autre chose pour les mots plus longs.

Answer 5

Je commencerais probablement par un dictionnaire, puis (pour chaque mot) j'ajouterais le mot à une liste contenant les chiffres qui peuvent former le mot.

Ensuite, vous devrez probablement trier les listes résultantes d'une manière ou d'une autre, de façon à ce que les mots les plus probables apparaissent avant les mots les moins probables (si vous avez la place, j'inclurais également une petite zone pour un compteur, de façon à ce que nous puissions re-trier ces listes de manière incrémentale OU simplement déplacer le dernier mot utilisé vers le début de la liste de suggestions, de façon à ce que nous ayons tendance, au fil du temps, à donner une meilleure réponse à l'utilisateur).

De cette façon, lorsque vous avez 4663 comme entrée, vous pouvez tout simplement récupérer la liste liée pertinente avec une consultation de table de hachage d'environ O(1).