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

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

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

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

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

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

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

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

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

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

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

考慮以下基本情況：所有建議都具有與用戶輸入相同的前綴。然后，最節(jié)省時(shí)間的數(shù)據(jù)結(jié)構(gòu)是前綴樹，也稱為Trie。我們不會詳細(xì)介紹Trie的工作原理，因?yàn)闉榇四康挠泻芏辔恼隆；旧辖o出了最長長度為M的短語列表，在Trie中搜索任何短語都需要O(M)時(shí)間。search得益于Trie ，操作本來就快。

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

class TrieNode：

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

“”“

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

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

：param is_word：如果節(jié)點(diǎn)存儲，則為true一個(gè)節(jié)點(diǎn)

“”“

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，因此涉及的基本算法是圖算法。當(dāng)我們需要遍歷整個(gè)圖時(shí)，在代碼中廣泛使用了基本的遍歷算法，例如深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)。當(dāng)然，細(xì)節(jié)因功能而異，例如DFS功能簽名。

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

def __delete_helper(self，node)：

“”“

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

：param node：TrieNode，subtree root

：return：set(str)

”“”

q = deque([ node ])

res =集()

，同時(shí)問：

CUR = q.popleft()

如果 cur.isWord：

res.add(cur.prefix)

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

q.append(孩子)

返回 RES

該__search_helper方法使用DFS搜索替換錯(cuò)誤的拼寫。它遍歷一個(gè)word_list對象，它是一個(gè)嵌套的字符串列表，并返回所有單詞組合。

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

如果IDX == LEN(WORD_LIST)：

資源 .append(名單(路徑))

回報(bào)

為字在WORD_LIST [ IDX ]：

路徑 .append(字)

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

path .pop()

　　數(shù)據(jù)庫

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

　　零件設(shè)計(jì)

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

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

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

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

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

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

[[“，'0'，'時(shí)間1'，'1']，

['t'，'0'，'時(shí)間1'，'1']，

['ti'，'0'，'時(shí)間1 '，'1']，

['tim'，'0'，'時(shí)間1'，'1']，

['時(shí)間'，'1'，'時(shí)間1'，'0']]

　　未來的工作

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