搜索手机通讯录

Question

假设手机只有一个数字键盘，我们需要以一种能使搜索速度更快的方式存储联系人。

用户将输入数字，我们必须显示地址簿中以与这些数字对应的字母开头的所有联系人。

我在一次面试中被问到这个问题，我建议创建一个trie。对于地址簿中的每个名字，我建议在trie中添加相应的数字。

因此，如果通讯簿包含以下联系人：

bob
boby
mat 
mav

我将使用相应的数字创建尝试。在这种情况下，trie将包含：

262     (At the 2nd node 2, keep a pointer to bob)
2629    (At the node 9, keep a pointer to boby)
628     (At the node 8, keep 2 pointers, one to each of mat & mav)

有没有更好的方法？

更新:此trie在Data structure behind T9 type of dictionary中描述的T9技术中使用

Answer 1

我怀疑大多数名字在前几个字符中都是不同的(例如，在你的列表中有"Theodore"，"Theodor"，"Theodora“会构成一个遥远的异常值)。

在此基础上，您可以使用比trie简单得多的东西，即将前缀映射到匹配条目列表的哈希表(一旦前缀唯一地确定了列表中的名称，您就不需要更进一步)。

例如，给定{bob, bobby, matt, mads, zed}，您将拥有哈希表

"b" --> [bob, bobby]
"bo" --> [bob, bobby]
"bob" --> [bob, bobby]
"bobb" --> [bobby]
"m" --> [matt, mads]
"ma" --> [matt, mads]
"mat" --> [matt]
"mad" --> [mads]
"z" --> [zed]

请注意，“非区分”前缀(例如，"b“、"bo”、"bob")可以共享它们的值列表。

如果平均公共前缀是k个字符，那么您的开销是k个哈希表条目的因子。如果k很小，就像我怀疑的那样，那么你最终会得到一个比trie更精简、更简单的数据结构。

Answer 2

您可以根据字母构建一个树，但它需要是三个值:左、右、电话号码列表

因此，在您的示例中：

                              root node

               b  (left node)                   m  (right node)
               o                                a
               b (number)             v                   t
               y (number) 

然后，您可以遍历节点以显示自动补全建议，因为在bob和boby的情况下，如果需要，您可以同时显示这两个名称。

更新

今天早上我考虑了一下，这篇文章可能会给出一些关于如何处理这个问题的新想法，因为它使用三叉树对字符串进行排序。

http://www.cs.tufts.edu/~nr/comp150fp/archive/bob-sedgewick/fast-strings.pdf

但是，如果我的示例中的节点有5个值，那么您将拥有：

1. 左节点
2. 右节点
3. 下行节点
4. current letter
5. 申请的电话号码列表

然后向左或向右搜索，直到在该位置找到正确的字母，然后向下搜索，然后向左或向右搜索，直到找到下一个字母。

这样，每个节点中的每个字母就不会有26个指针，所以这棵树将是稀疏的，但很可能是不平衡的。平衡它将是一个不同的问题。