google 搜索自動補全功能的強大，相信不少朋友都能感受到，它幫助我們更快地“補全”我們所要輸入的搜索關鍵字。那么，它怎么知道我們要輸入什么內容？它又是如何工作的？在這篇文章里，我帶你一起看看。

使用自動補全

Google 搜索的自動補全功能可以在 Google 搜索應用的大多數位置使用，包括 Google^[1] 主頁、適用于 IOS 和 Android 的 Google 應用，我們只需要在 Google 搜索框上開始鍵入關鍵字，就可以看到聯想詞了。

在上圖示例中，我們可以看到，輸入關鍵字 juej，Google 搜索會聯想到“掘金”、“掘金小冊”、“絕句”等等，好處就是，我們無須輸入完整的關鍵字即可輕松完成針對這些 topics 的搜索。

谷歌搜索的自動補全功能對于使用移動設備的用戶來說特別有用，用戶可以輕松在難以鍵入的小屏幕上完成搜索。當然，對于移動設備用戶和臺式機用戶而言，這都節省了大量的時間。根據 Google 官方報告，自動補全功能可以減少大約 25% 的打字，累積起來，預計每天可以節省 200 多年的打字時間。是的，每天！

注意，本文所提到的“聯想詞”與“預測”，是同一個意思。

基于“預測”而非“建議”

Google 官方將自動補全功能稱之為“預測”，而不是“建議”，為什么呢？其實是有充分理由的。自動補全功能是為了幫助用戶完成他們打算進行的搜索，而不是建議用戶要執行什么搜索。

那么，Google 是如何確定這些“預測”的？其實，Google 會根據趨勢搜索 trends^[2] 給到我們這些“預測”。簡單來說，哪個熱門、哪個搜索頻率高，就更可能推給我們。當然，這也與我們當前所處的位置以及我們的搜索歷史相關。

另外，這些“預測”也會隨著我們鍵入的關鍵字的變更而更改。例如，當我們把鍵入的關鍵字從 juej 更改為 juex 時，與“掘金”相關的預測會“消失”，同時，與“覺醒”、“決心”相關聯的詞會出現。

為什么我們看不到某些聯想詞？

如果我們在輸入某個關鍵字時看不到聯想詞，那么表明 Google 的算法可能檢測到：

•這個關鍵字不是熱門字詞；

•搜索的字詞太新了，我們可能需要等待幾天或幾周才能看到聯想詞；

•這是一個侮辱性或敏感字詞，這個搜索字詞違反了 Google 的相關政策。更加詳細的情況，可以了解 Google 搜索自動補全政策^[3]。

為什么我們會看到某些不當的聯想詞？

Google 擁有專門設計的系統，可以自動捕獲不適當的預測結果而不顯示出來。然而，Google 每天需要處理數十億次搜索，這意味著 Google 每天會顯示數十億甚至上百億條預測。再好的系統，也可能存在缺陷，不正確的預測也可能隨時會出現。

我們作為 Google 搜索的用戶，如果認定某條預測違反了相關的搜索自動補全政策，可以進行舉報反饋，點擊右下角“舉報不當的聯想查詢”并勾選相關選項即可。

如何實現自動補全算法？

目前，Google 官方似乎并沒有公開搜索自動補全的算法實現，但是業界在這方面已經有了不少研究。

一個好的自動補全器必須是快速的，并且在用戶鍵入下一個字符后立即更新聯想詞列表。自動補全器的核心是一個函數，它接受輸入的前綴，并搜索以給定前綴開頭的詞匯或語句列表。通常來說，只需要返回少量的數目即可。

接下來，我們先從一個簡單且低效的實現開始，并在此基礎上逐步構建更高效的方法。

詞匯表實現

一個簡單粗暴的實現方式是：順序查找詞匯表，依次檢查每個詞匯，看它是否以給定的前綴開頭。

但是，此方法需要將前綴與每個詞匯進行匹配檢查，若詞匯量較少，這種方式可能勉強行得通。但是，如果詞匯量規模較大，效率就太低了。

一個更好的實現方式是：讓詞匯按字典順序排序。借助二分搜索算法，可以快速搜索有序詞匯表中的前綴。由于二分搜索的每一步都會將搜索的范圍減半，因此，總的搜索時間與詞匯表中單詞數量的對數成正比，即時間復雜度是 O(log N)。二分搜索的性能很好，但有沒有更好的實現呢？當然有，往下看。

前綴樹實現

通常來說，許多詞匯都以相同的前綴開頭，比如 need、nested 都以 ne 開頭，seed、speed 都以 s 開頭。要是為每個單詞分別存儲公共前綴似乎很浪費。

前綴樹是一種利用公共前綴來加速補全速度的數據結構。前綴樹在節點樹中排列一組單詞，單詞沿著從根節點到葉子節點的路徑存儲，樹的層次對應于前綴的字母位置。

前綴的補全是順著前綴定義的路徑來查找的。例如，在上圖的前綴樹中，前綴 ne 對應于從子節點取左邊緣 N 和唯一邊緣 E 的路徑。然后可以通過繼續遍歷從 E 節點可以達到的所有葉節點來生成補全列表。在圖中，ne 的補全可以是兩個分支：-ed 和 -sted。如果在數中找不到由前綴定義的路徑，則說明詞匯表中不包含以該前綴開頭的單詞。

有限狀態自動機(DFA)實現

前綴樹可以有效處理公共前綴，但是，對于其他共享詞部分，仍會分別存儲在每個分支中。比如，后綴 ed、ing、tion 在英文單詞中特別常見。在上一個例子中，e、d 分別存放在了每一個分支上。

有沒有一種方法可以更加節省存儲空間呢？有的，那就是 DFA。

在上面的例子中，單詞 need、nested、seed 和 speed 僅由 9 個節點組成，而上一張圖中的前綴樹包含了 17 個節點。

可以看出，最小化前綴樹 DFA 可以在很大程度上減少數據結構的大小。即使詞匯量很大，最小化 DFA 通常也適合在內存中存儲，避免昂貴的磁盤訪問是實現快速自動補全的關鍵。

一些擴展

上面介紹了如何利用合理的數據結構實現基本的自動補全功能。這些數據結構可以通過多種方式進行擴展，從而改善用戶體驗。

通常，滿足特定前綴的詞匯可能很多，而用戶界面上能夠顯示的卻不多，我們更希望能顯示最常搜索或者最有價值的詞匯。這通?？梢酝ㄟ^為詞匯表中的每個單詞增加一個代表單詞值的權重 weight，并且按照權重高低來排序自動補全列表。

•對于排序后的詞匯表來說，在詞匯表每個元素上增加 weight 屬性并不難；

•對于前綴樹來說，將 weight 存儲在葉子節點中，也是很簡單的一個實現；

•對于 DFA 來說，則較為復雜。因為一個葉子節點可以通過多條路徑到達。一種解決方案是將權重關聯到路徑而不是葉子節點。

目前有不少開源庫都提供了這個功能，比如主流的搜索引擎框架 Elasticsearch^[4]、Solr^[5]等，基于此，我們可以實現高效而強大的自動補全功能。