谷歌的自動補全功能那么快，后臺是如何工作的？

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

使用自動補全

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

如何實現自動補全算法？

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

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

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

詞匯表實現

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

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

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

前綴樹實現

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

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

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