自动完成系统是许多Web服务的关键功能。当您在浏览器中输入一些短语时，它会显示搜索建议列表。有时这些结果使用您的输入作为前缀，有时不使用。浏览器如何快速而准确地实现这一目标？以及如何在Python中设计一个简化的工作自动完成系统？由于正在设计Web服务的后端，因此需要考虑服务器与数据库之间的数据流方式以及服务器故障时的恢复机制。下面是从分布式系统基础结构角度来看的功能列表。

· 可以从数据库构建新的和恢复的应用程序服务器。

· 复制和分区数据库的选项。

· 应用程序服务器应该能够使用最新的使用情况数据更新数据库。

· 应用程序服务器能够从头开始构建数据库。

从服务器的角度来看，我们需要考虑如何优化性能。

· 我们如何更新最佳结果？如果我们每秒要处理数千个请求，则必须将延迟最小化。

· 我们多久执行一次更新？我们是否假设最终的一致性？

· 如有必要，我们如何从服务器删除短语？

　　数据结构与算法

为了处理大量数据，服务器应该能够快速搜索，插入和删除短语。另外，我们应该优化更新操作。

考虑以下基本情况：所有建议都具有与用户输入相同的前缀。然后，最节省时间的数据结构是前缀树，也称为Trie。我们不会详细介绍Trie的工作原理，因为为此目的有很多文章。基本上给出了最长长度为M的短语列表，在Trie中搜索任何短语都需要O(M)时间。search得益于Trie ，操作本来就快。

但是，我们仍然需要仔细设计体系结构以支持其他操作。Trie节点设计如下。TrieNode是具有前缀字符串和指向子/父节点的指针的节点。它使用Python计数器存储最重要的建议。我们可以使用most_common()内置方法有效地访问最常访问的结果。还要注意，它有一个标志，指示节点中的前缀是否是完整的单词，并且支持各种方法中的逻辑非常重要。

class TrieNode：

def __init __(self，前缀 = None，父 = None，is_word = False)：

“”“

：param前缀：该节点的前缀

：param父：trie中的父节点

：param is_word：如果节点存储，则为true一个节点

“”“

self.prefix = 前缀

self.children = dict()

self.parent = 父

self.count = 0

self.top_results = Counter()

如果is_word：

self.top_results [self.prefix] = 1

self.isWord = is_word

由于服务器的主要结构基于Trie，因此涉及的基本算法是图算法。当我们需要遍历整个图时，在代码中广泛使用了基本的遍历算法，例如深度优先搜索(DFS)和广度优先搜索(BFS)。当然，细节因功能而异，例如DFS功能签名。

作为BFS的一个简单示例，__delete_helper删除短语的方法会在子树中找到所有短语。

def __delete_helper(self，node)：

“”“

广度优先搜索以查找所有单词的子节点

：param node：TrieNode，subtree root

：return：set(str)

”“”

q = deque([ node ])

res =集()

，同时问：

CUR = q.popleft()

如果 cur.isWord：

res.add(cur.prefix)

为 _，孩子在 cur.children.items()：

q.append(孩子)

返回 RES

该__search_helper方法使用DFS搜索替换错误的拼写。它遍历一个word_list对象，它是一个嵌套的字符串列表，并返回所有单词组合。

高清 __search_helper(WORD_LIST，IDX，路径，RES)：

如果IDX == LEN(WORD_LIST)：

资源 .append(名单(路径))

回报

为字在WORD_LIST [ IDX ]：

路径 .append(字)

服务器.__ search_helper (word_list，idx +1，path，res)

path .pop()

　　数据库

我们想要构建一个连接数据库的自动完成服务器。数据库的选择是Neo4j，Neo4j是表达图形中复杂关系的绝佳选择。我们使用py2neo Python软件包，该软件包提供了与数据库通信的所有必需的API。这是插入4个单词{trying，tie，time，timing}后，Neo4j浏览器中数据的外观的可视化效果。

　　零件设计

对于更新操作，不是使用搜索子树中的所有节点，而是使用从叶子一直到根的遍历来更新顶部搜索结果。这种优化降低了从指数到多项式的时间复杂度。

但是，当服务器存储数百万个短语时，更新顶部搜索结果将花费很长时间。我们应该找到一个合理的更新频率，以便在一致性和延迟权衡之间取得平衡。可以通过class属性配置服务器更新频率。

有无数的挑战我遇到设计服务器类。我想分享解决其中一些问题的想法。

第一个设计挑战是如何更新数据库。术语的子集可能已经存储在数据库中，而其他的则是新术语。在遍历图形数据库时，我们必须区分节点是否存在。如果节点存在，则添加新计数;否则，添加新计数。如果不是，则会在正确的位置创建新节点。但是，如何更新数据库中每个短语的计数?这个想法是，每个节点应恒定地维护其自己短语的计数。更新数据库时，我们始终使用此值来保持一致性。

使用浏览器搜索时，请注意，即使您输入了一些乱码，系统也会自动更正您的输入并返回合理的搜索结果。我们想要实现类似的目标。从Peter Norvig扩展了经典的自动校正器，我们创建了Spell一个在拼写错误的情况下返回许多自动校正结果的类。这个想法是，如果输入的单词不在英语词汇表中，则搜索其替换单词并将其插入服务器。但是，这种设计带来了另一个问题。如果替换太多，则排序和排名将大大增加延迟。因此，在当前版本中，我们将每个拼写错误的单词的替换限制为小数。

序列化对于将对象转换为字节序列至关重要，以便存储在磁盘中或通过网络传输。序列化诸如Trie服务器之类的复杂对象并非易事。我们必须考虑压缩哪些是最重要的数据，以及在给定序列化表示形式的情况下如何重建应用服务器。为了尽可能准确地重建TrieNode，我们必须序列化prefix, number_children, top_results and is_word。序列化和反序列化应用程序服务器的顺序成对出现。我们决定使用深度优先搜索序列进行序列化。通过所有这些设计决策，我们能够序列化一台应用服务器，然后反序列化以创建一个新的服务器。下面是一个带有单词“时间”的服务器序列化示例。列表中的序列是DFS序列，每个项目都编码我们上面描述的数据。

[[“，'0'，'时间1'，'1']，

['t'，'0'，'时间1'，'1']，

['ti'，'0'，'时间1 '，'1']，

['tim'，'0'，'时间1'，'1']，

['时间'，'1'，'时间1'，'0']]

　　未来的工作

当前，用户通过运行app.py基于Python标准库中Tkinter软件包的服务器来访问服务器。未来的计划包括使用Flask提供REST API来访问服务。我们还可以添加功能来重定向用户选择。想了解更多关于Python的信息，请继续关注中培伟业。