自動完成系統(tǒng)是許多Web服務(wù)的關(guān)鍵功能。當您在瀏覽器中輸入一些短語時，它會顯示搜索建議列表。有時這些結(jié)果使用您的輸入作為前綴，有時不使用。瀏覽器如何快速而準確地實現(xiàn)這一目標？以及如何在Python中設(shè)計一個簡化的工作自動完成系統(tǒng)？由于正在設(shè)計Web服務(wù)的后端，因此需要考慮服務(wù)器與數(shù)據(jù)庫之間的數(shù)據(jù)流方式以及服務(wù)器故障時的恢復機制。下面是從分布式系統(tǒng)基礎(chǔ)結(jié)構(gòu)角度來看的功能列表。

· 可以從數(shù)據(jù)庫構(gòu)建新的和恢復的應用程序服務(wù)器。

· 復制和分區(qū)數(shù)據(jù)庫的選項。

· 應用程序服務(wù)器應該能夠使用最新的使用情況數(shù)據(jù)更新數(shù)據(jù)庫。

· 應用程序服務(wù)器能夠從頭開始構(gòu)建數(shù)據(jù)庫。

從服務(wù)器的角度來看，我們需要考慮如何優(yōu)化性能。

· 我們?nèi)绾胃伦罴呀Y(jié)果？如果我們每秒要處理數(shù)千個請求，則必須將延遲最小化。

· 我們多久執(zhí)行一次更新？我們是否假設(shè)最終的一致性？

· 如有必要，我們?nèi)绾螐姆?wù)器刪除短語？

　　數(shù)據(jù)結(jié)構(gòu)與算法

為了處理大量數(shù)據(jù)，服務(wù)器應該能夠快速搜索，插入和刪除短語。另外，我們應該優(yōu)化更新操作。

考慮以下基本情況：所有建議都具有與用戶輸入相同的前綴。然后，最節(jié)省時間的數(shù)據(jù)結(jié)構(gòu)是前綴樹，也稱為Trie。我們不會詳細介紹Trie的工作原理，因為為此目的有很多文章。基本上給出了最長長度為M的短語列表，在Trie中搜索任何短語都需要O(M)時間。search得益于Trie ，操作本來就快。

但是，我們?nèi)匀恍枰屑氃O(shè)計體系結(jié)構(gòu)以支持其他操作。Trie節(jié)點設(shè)計如下。TrieNode是具有前綴字符串和指向子/父節(jié)點的指針的節(jié)點。它使用Python計數(shù)器存儲最重要的建議。我們可以使用most_common()內(nèi)置方法有效地訪問最常訪問的結(jié)果。還要注意，它有一個標志，指示節(jié)點中的前綴是否是完整的單詞，并且支持各種方法中的邏輯非常重要。

class TrieNode：

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

“”“

：param前綴：該節(jié)點的前綴

：param父：trie中的父節(jié)點

：param is_word：如果節(jié)點存儲，則為true一個節(jié)點

“”“

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

由于服務(wù)器的主要結(jié)構(gòu)基于Trie，因此涉及的基本算法是圖算法。當我們需要遍歷整個圖時，在代碼中廣泛使用了基本的遍歷算法，例如深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)。當然，細節(jié)因功能而異，例如DFS功能簽名。

作為BFS的一個簡單示例，__delete_helper刪除短語的方法會在子樹中找到所有短語。

def __delete_helper(self，node)：

“”“

廣度優(yōu)先搜索以查找所有單詞的子節(jié)點

：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(字)

服務(wù)器.__ search_helper (word_list，idx +1，path，res)

path .pop()

　　數(shù)據(jù)庫

我們想要構(gòu)建一個連接數(shù)據(jù)庫的自動完成服務(wù)器。數(shù)據(jù)庫的選擇是Neo4j，Neo4j是表達圖形中復雜關(guān)系的絕佳選擇。我們使用py2neo Python軟件包，該軟件包提供了與數(shù)據(jù)庫通信的所有必需的API。這是插入4個單詞{trying，tie，time，timing}后，Neo4j瀏覽器中數(shù)據(jù)的外觀的可視化效果。

　　零件設(shè)計

對于更新操作，不是使用搜索子樹中的所有節(jié)點，而是使用從葉子一直到根的遍歷來更新頂部搜索結(jié)果。這種優(yōu)化降低了從指數(shù)到多項式的時間復雜度。

但是，當服務(wù)器存儲數(shù)百萬個短語時，更新頂部搜索結(jié)果將花費很長時間。我們應該找到一個合理的更新頻率，以便在一致性和延遲權(quán)衡之間取得平衡。可以通過class屬性配置服務(wù)器更新頻率。

有無數(shù)的挑戰(zhàn)我遇到設(shè)計服務(wù)器類。我想分享解決其中一些問題的想法。

第一個設(shè)計挑戰(zhàn)是如何更新數(shù)據(jù)庫。術(shù)語的子集可能已經(jīng)存儲在數(shù)據(jù)庫中，而其他的則是新術(shù)語。在遍歷圖形數(shù)據(jù)庫時，我們必須區(qū)分節(jié)點是否存在。如果節(jié)點存在，則添加新計數(shù);否則，添加新計數(shù)。如果不是，則會在正確的位置創(chuàng)建新節(jié)點。但是，如何更新數(shù)據(jù)庫中每個短語的計數(shù)?這個想法是，每個節(jié)點應恒定地維護其自己短語的計數(shù)。更新數(shù)據(jù)庫時，我們始終使用此值來保持一致性。

使用瀏覽器搜索時，請注意，即使您輸入了一些亂碼，系統(tǒng)也會自動更正您的輸入并返回合理的搜索結(jié)果。我們想要實現(xiàn)類似的目標。從Peter Norvig擴展了經(jīng)典的自動校正器，我們創(chuàng)建了Spell一個在拼寫錯誤的情況下返回許多自動校正結(jié)果的類。這個想法是，如果輸入的單詞不在英語詞匯表中，則搜索其替換單詞并將其插入服務(wù)器。但是，這種設(shè)計帶來了另一個問題。如果替換太多，則排序和排名將大大增加延遲。因此，在當前版本中，我們將每個拼寫錯誤的單詞的替換限制為小數(shù)。

序列化對于將對象轉(zhuǎn)換為字節(jié)序列至關(guān)重要，以便存儲在磁盤中或通過網(wǎng)絡(luò)傳輸。序列化諸如Trie服務(wù)器之類的復雜對象并非易事。我們必須考慮壓縮哪些是最重要的數(shù)據(jù)，以及在給定序列化表示形式的情況下如何重建應用服務(wù)器。為了盡可能準確地重建TrieNode，我們必須序列化prefix, number_children, top_results and is_word。序列化和反序列化應用程序服務(wù)器的順序成對出現(xiàn)。我們決定使用深度優(yōu)先搜索序列進行序列化。通過所有這些設(shè)計決策，我們能夠序列化一臺應用服務(wù)器，然后反序列化以創(chuàng)建一個新的服務(wù)器。下面是一個帶有單詞“時間”的服務(wù)器序列化示例。列表中的序列是DFS序列，每個項目都編碼我們上面描述的數(shù)據(jù)。

[[“，'0'，'時間1'，'1']，

['t'，'0'，'時間1'，'1']，

['ti'，'0'，'時間1 '，'1']，

['tim'，'0'，'時間1'，'1']，

['時間'，'1'，'時間1'，'0']]

　　未來的工作

當前，用戶通過運行app.py基于Python標準庫中Tkinter軟件包的服務(wù)器來訪問服務(wù)器。未來的計劃包括使用Flask提供REST API來訪問服務(wù)。我們還可以添加功能來重定向用戶選擇。想了解更多關(guān)于Python的信息，請繼續(xù)關(guān)注中培偉業(yè)。