如何设计自动完成系统

自动完成是一个技术术语，用于描述您在搜索时看到的搜索建议。此功能可提高文本输入速度。事实上，它的目的是通过尝试预测您在键入时要搜索的内容来加速您的搜索交互。自动完成功能常见于搜索引擎和消息应用程序中。良好的自动完成功能必须快速，并在用户键入下一个字母后立即更新建议列表。自动完成功能只能建议它知道的单词。建议的单词来自预定义的词汇表，例如维基百科或英语词典中的所有不同单词。词汇表中的单词数量可能很大：维基百科包含数百万个不同的单词。如果需要自动完成来识别多词短语和实体名称，词汇量会变得更大。

该系统的核心是一个 API，它采用前缀并搜索以给定前缀开头的词汇。通常，仅返回k个可能的完成结果。有许多设计可以实现这样的系统。在本文中，我将介绍百万字系统的中层设计。在深入讨论之前，我将介绍基本概念及其用法，然后我将介绍设计部分。

Trie数据结构
Trie是一种数据检索数据结构。它降低了搜索复杂性并提高了优化性和速度。Trie 可以在 O(M) 时间内搜索键。然而，它需要数据存储。存储可以是内存缓存（Redis 或 Memcached）、数据库，甚至是文件。假设S是k 个字符串的集合。换句话说，  S = {s1, s2, ..., sk}。将S模型设置为一棵有根树T ，从T的根到其任何节​​点的每条路径都对应于S的至少一个字符串的前缀。展示这种结构的最好方法是考虑一个示例集。假设S = { het, hel, hi, car, cat } 且ε对应于空字符串。那么S的trie树如下所示：  

图片标题

考虑到内部节点到其子节点的每条边都由字母表中的一个字母标记，表示字符串所表示的字符串的扩展。此外，与S中的字符串对应的每个节点都用颜色标记。一个观察是，如果 he是S中另一个字符串的前缀，则与he对应的节点是T的内部节点，否则，它是叶子。有时，将与S中的字符串对应的所有节点作为叶子是很有用的，并且向S中的每个字符串附加一个保证不在Σ 中的字符是很常见的。 在我们的例子中，将$表示为这个特殊字符。那么这样修改后的trie就是这样的：  

图片标题

请注意，由于现在S中没有字符串（它是前缀），即S中的另一个字符串，因此T中与S中的字符串相对应的所有节点都是leaves。

为了创建trieT， 只需从一个节点作为代表空字符串ε的根开始。如果要将字符串e插入到T中，请从T的根开始并考虑e的第一个字符h。如果从当前节点到其任何子节点存在一条标有h的边，则您将消耗字符h并向下到达该子节点。如果在某个时刻不存在这样的边和子项，则必须创建它们，消耗h，并继续该过程，直到整个e完成。

现在，您可以简单地在T中搜索字符串e。您只需迭代e的字符，并从根开始沿着相应的边找到T中的这些字符。如果在某个时刻没有到子级的转换，或者如果您消耗了 e 的所有字母，但结束进程的节点不对应于S中的任何字符串，则e也不属于S。否则，您将在与e对应的节点中结束该进程，因此e属于S。

后缀树算法：
后缀树是给定字符串的所有后缀的压缩特里树。后缀树可用于解决许多与字符串相关的问题，例如模式匹配、查找给定字符串中的不同子字符串、查找最长回文等。后缀树T是对模式匹配问题中使用的trie数据结构的改进。在字符串s的一组子字符串上定义的。基本上就是这样一个trie可以有很长的路径而没有分支。更好的方法是将这些长路径减少为一条路径，这样做的好处是显着减小 trie 的大小。

让我们描述更多，首先考虑字符串s = 的后缀树T。单词 abakan 有 6 个后缀 {abakan, bakan, akan, kan, an, n}，它的后缀树如下所示：

图片标题

Ukkonen 设计了一种算法，用于根据s的长度在线性时间内为s制作后缀树。

后缀树可以解决许多复杂的问题，因为它包含了很多关于字符串本身的数据。例如，为了知道模式P在s中出现了多少次，只需在T中找到P并返回与其节点对应的子树的大小即可。另一个众所周知的应用是查找s的不同子串的数量，并且可以使用后缀树轻松解决。

前缀的完成是通过首先遵循前缀字母定义的路径来找到的。这将最终出现在某个内部节点中。例如，在图中的前缀树中，前缀对应于从根节点取左边缘和从子节点取唯一边缘的路径。然后可以通过继续遍历从内部节点可以到达的所有叶节点来生成完成。

在前缀树中搜索速度非常快。查找前缀所需的比较步骤数与前缀中的字母数相同。特别是，这意味着搜索时间与词汇量大小无关。因此，前缀树甚至适用于大词汇表。前缀树为超序列表提供了显着的速度改进。之所以能够实现这种改进，是因为每次比较都能够修剪更大一部分的搜索空间。

最小 DFA：
前缀树有效地处理公共前缀，但其他共享单词部分仍然单独存储在每个分支中。例如，后缀（例如-ing和-ion）在英语中很常见。幸运的是，有一种方法可以更有效地保存共享单词部分。前缀树是一类更通用的数据结构的实例，称为非循环确定性有限自动机 (DFA)。有一些算法可以将 DFA 转换为具有更少节点的等效 DFA。最小化前缀树 DFA 可减小数据结构的大小。即使词汇量很大，最小的 DFA 也适合记忆。避免昂贵的磁盘访问是快速自动完成的关键。

Myhill-Nerode 定理为我们提供了字符串等价类的最小 DFA 的理论表示。说两个状态无法区分意味着它们都运行到最终状态或所有字符串都运行到非最终状态。显然，我们并没有测试所有的字符串。这个想法是增量计算不可区分的等价类。我们说：

如果p和q可通过长度 ≤ k的字符串区分，则它们是k可区分的

很容易理解这个关系的归纳性质：

如果p和q是( k -1)可区分的，则它们是k可区分的，或者对于某些符号σ ∈ Σ δ ( p,σ ) 和δ ( q,σ ) 是 ( k -1) 可区分的

等价类的构造是这样开始的：

p和q是0 -如果它们都是最终的或都是非最终的，则无法区分。因此，我们开始算法时将状态分为两个部分：最终状态和非最终状态。

在这两个分区的每一个中， 如果存在符号σ使得δ ( p,σ )和δ ( q , σ )是 0 可区分的，则 p和q是 1 可区分的。例如，一个是最终的，另一个不是。通过这样做，我们进一步将每个组划分为 1-不可区分状态的集合。

然后的想法是继续分割这些分区集，如下所示：

如果存在符号σ使得δ ( p , σ ) 和δ ( q,σ ) 是 ( k -1) 可区分，则划分集中的 p 和 q 是k可区分的。

在某些时候，我们无法进一步细分分区。此时，终止算法，因为没有进一步的步骤可以产生任何新的细分。当我们终止时，我们得到了不可区分的等价类，它们形成了最小 DFA 的状态。从一个等价类到另一个等价类的转换是通过在源类中选择任意状态，应用转换，然后取整个来获得的：

图片标题

首先区分最终和非最终：{q1,q3}, {q2,q4,q5,q6}

区分组内的状态，得到下一个分区：{q1,q3}, {q4,q6}, {q5}, {q2}

b 区分 q2, q4: δ(q2,b) ∈ {q1,q3}, δ(q4,b) ∈ {q2,q4,q5,q6}

b 区分 q2、q5： δ(q2,b) ∈ {q1,q3}, δ(q5,b) ∈ {q2,q4,q5,q6}

a 区分 q4, q5: δ(q4,a) ∈ {q1,q3}, δ(q5,a) ∈ {q2,q4,q5,q6}

a 和 b 都无法区分 (q4,q6)