algorithm - 在手机中搜索电话号码的算法？

Question

当前智能手​​机操作系统从联系人列表中搜索姓名的通用算法是什么？

联系人列表并不大，但是当我们输入“A”时，所有以“A”开头的名字都很容易出现。'A' 后跟 'B'，将带来 Abe、Abott 等名称，

Answer 1

快速执行此操作的一种方法是使用 trie ( http://en.wikipedia.org/wiki/Trie ) - 基本上，您会将所有键存储在树中，其中根节点表示一个空输入，并且每个您输入的字符会将您带到一个子树的分支，该子树包含所有以您迄今为止输入的字母集开头的名称。这里有一个使用这种技术进行自动完成的很好的例子：http: //igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/

在您的示例中，输入“A”将沿着标记为“A”的分支向下到包含所有以“A”开头的名称的子树。从那里输入“B”将沿着标记为“B”的分支向下到下一个子树，该子树将包含所有“AB”名称。将新名称添加到 trie 遵循相同的过程 - 按照名称中每个字母的正确分支（在它们不存在的地方添加新分支）直到到达名称的末尾，此时将其添加为叶子。

Answer 2

我不是 100% 确定，但如果我猜它会是Trie。

这个想法是您从树的根开始，然后跟踪到叶节点的路径。您向下的每个节点都会添加另一个字母作为后缀。

在您的示例中，树看起来像：这个（没有足够的代表嵌入图像）

双圈定义“接受”状态，并不总是叶节点。当您使用 Trie 时，它​​会缩小您的搜索范围：

• 在“A”之后选择“N”将拒绝“ABE”，因为它不在路径上。
• 在“ANN”之后选择“E”将拒绝“ANN”，因为它不在路径上。