自動完成系統是許多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的信息，請繼續關注中培偉業。