T9字典背后的数据结构
T9字典是如何工作的？ 它背后的数据结构是什么？ 如果我们input“4663”，当我们按下button时，我们会变得“好”，我们会“走出去”，然后“回家”等等。
编辑：如果用户键入46，那么它应该显示“去”，当按下箭头应显示“走了”等…
它可以用几种方式来实现，其中之一就是Trie 。 路由由数字表示，节点指向单词的集合。
它也可以使用嵌套哈希表来实现，哈希表的键是一个字母，每个数字上的algorithm计算所有可能的路由（O（3 ^ n）路由）。
4663
翻译成
{G，H，I} {M，N，O} {M，N，O} {d，E，F}
T9从第一个可能的字母开始按顺序过滤可能性。 所以你的例子中的第一步就是将字典列表过滤为以G，H或I开始的所有单词。下一步，取出该列表，并用M，N，O过滤第二个字母。
我认为T9正在使用基于位图的Trie。 在第一级有一个32位（我认为他们扩大到32）字每个位代表一个字母。 所有有效的作为一个单词的开始字母的字母都设置了它们的位。
在下一级中，对于在前一级中设置的每个位，都有一个32位映射。 在这些映射中，如果相应的字母在单词中作为第二个字母是有效的，则起始字母由第一级决定。
结构然后继续。 每个字母使用一个位就可以创build一个非常高效的存储空间。 寻址scheme一定是有挑战性的。 使用上面的模式对短文进行优化也可能会有某种优化，而对长文本使用别的文件。
我想，就像之前那些T9使用一个trie，其中的链接是由一个位图（每个字母1位）表示。 这被称为简洁的数据结构，正如Steve Hanov所说的那样：
我可能会从字典开始，然后（对于每个单词）将单词推送到可以形成单词的数字所键入的列表中。
然后，你可能需要以某种方式对结果列表进行sorting，所以更可能的单词出现在不太可能的单词之前（如果有空间的话，我还可以包含一个小区域作为柜台，sorting这些或简单的mov ethe上次用于build议列表的前面，所以我们，随着时间的推移，倾向于给用户一个更好的答案）。
这样，当你有4663作为input，你可以很简单地检索相关的链表，哈哈大概O（1）哈希表查找。
使用Trie的C＃实现
public interface ICellT9 { void Add(string a_name); List<string> GetNames(string a_number); } public class Cell : ICellT9 { private Dictionary<int, Cell> m_nodeHolder; private List<string> m_nameList; public Cell() { m_nameList = new List<string>(); m_nodeHolder = new Dictionary<int, Cell>(); for (int i = 2; i < 10; i++) { m_nodeHolder.Add(i, null); } } public void Add(string a_name) { Add(a_name, a_name); } private void Add(string a_name, string a_originalName) { if (string.IsNullOrEmpty(a_name) && (string.IsNullOrEmpty(a_originalName) == false)) { m_nameList.Add(a_originalName); } else { int l_firstNumber = CharToNumber(a_name[0].ToString()); if (m_nodeHolder[l_firstNumber] == null) { m_nodeHolder[l_firstNumber] = new Cell(); } m_nodeHolder[l_firstNumber].Add(a_name.Remove(0, 1), a_originalName); } } public List<string> GetNames(string a_number) { List<string> l_result = null; if (string.IsNullOrEmpty(a_number)) { return l_result; } int l_firstNumber = a_number[0] - '0'; if (a_number.Length == 1) { l_result = m_nodeHolder[l_firstNumber].m_nameList; } else if(m_nodeHolder[l_firstNumber] != null) { l_result = m_nodeHolder[l_firstNumber].GetNames(a_number.Remove(0, 1)); } return l_result; } private int CharToNumber(string c) { int l_result = 0; if (c == "a" || c == "b" || c == "c") { l_result = 2; } else if (c == "d" || c == "e" || c == "f") { l_result = 3; } else if (c == "g" || c == "h" || c == "i") { l_result = 4; } else if (c == "j" || c == "k" || c == "l") { l_result = 5; } else if (c == "m" || c == "n" || c == "o") { l_result = 6; } else if (c == "p" || c == "q" || c == "r" || c == "s") { l_result = 7; } else if (c == "t" || c == "u" || c == "v") { l_result = 8; } else if (c == "w" || c == "x" || c == "y" || c == "z") { l_result = 9; } return l_result; } } 