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

Question

T9 词典如何工作？其背后的数据结构是怎样的。如果我们输入“4663”，当我们按下按钮时，我们会得到“gone”，然后是“home”等...

编辑：如果用户输入46，那么它应该显示“go”，当按下向下箭头时应该显示“go”显示“消失”等...

Answer 1

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

它也可以使用嵌套哈希表来实现，哈希表的键是一个字母和对于每个数字，算法都会计算所有可能的路线（O(3^n) 路线）。

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 很好地解释的那样：

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

Answer 4

我认为 T9 使用的是基于位图的 Trie。第一层有一个 32 位（我假设它们扩展为 32）字，其中每个位代表一个字母。所有有效作为单词起始字母的字母都已设置其位。

在下一个级别中，对于上一个级别中设置的每个位都有一个 32 位映射。在这些映射中，如果相应的字母作为单词中的第二个字母有效，则设置每个位，而起始字母由第一级决定。

然后该结构继续。使用每个字母一位可以实现非常高效的存储。然而，寻址方案必定具有挑战性。还可能存在对短单词使用上述模式而对较长单词使用其他模式的某种优化。

Answer 5

使用 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;
            }
        }

Answer 6

我可能会从一本字典开始，然后（对于每个单词）将单词推到一个列表中，该列表由可以形成该单词的数字键入。

然后，您可能需要以某种方式对结果列表进行排序，以便更可能的单词出现在不太可能的单词之前（如果您有空间，我还会为计数器添加一个小区域，这样我们就可以逐步重新排序）对这些进行排序或简单地将最后使用的内容移至建议列表的前面，因此随着时间的推移，我们倾向于为用户提供更好的答案）。

这样，当您有 4663 作为输入时，您可以通过大约 O(1) 的哈希表查找来非常简单地检索相关链表。