T9类型字典背后的数据结构

Question

T9词典如何运作？它背后的数据结构是什么.如果我们输入'4663',当我们按下按钮时我们会'好',然后'去'然后'回家'等...

编辑:如果用户键入46然后它应显示'go',按下箭头时应显示'去'等...

Answer 1

它可以通过多种方式实现,其中一种是Trie.路由由数字表示,节点指向单词集合.

它可以使用嵌套哈希表,以及被实现,所述的关键哈希表是一个字母和每个数字算法计算所有可能的路由(O(3 ^ n)的路由).

你能详细说明一下嵌套哈希表的解决方案吗？我不明白为什么嵌套哈希表比整个单词上的简单哈希表更好（例如使用 [multimap](http://www.sgi.com/tech/stl/Multimap.html)），其中仍然是 O(3^n) 平均情况。 (2认同)

Answer 2

4663

翻译成

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

T9通过从第一个可能的字母开始按顺序过滤可能性来工作.因此,您的示例中的第一步是将字典列表过滤为以G,H或I开头的所有单词.下一步,取出该列表并按M,N,O过滤第二个字母.依此类推......

Answer 3

我猜想，就像之前的 T9 使用 trie 一样，其中链接由位图表示（每个字母 1 位）。这被称为简洁的数据结构，正如 Steve Hanov 很好地解释的那样：