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。如果在數中找不到由前綴定義的路徑,則說明詞匯表中不包含以該前綴開頭的單詞。
有限狀態(tài)自動機(DFA)實現
前綴樹可以有效處理公共前綴,但是,對于其他共享詞部分,仍會分別存儲在每個分支中。比如,后綴 ed、ing、tion 在英文單詞中特別常見。在上一個例子中,e、d 分別存放在了每一個分支上。
有沒有一種方法可以更加節(jié)省存儲空間呢?有的,那就是 DFA。

在上面的例子中,單詞 need、nested、seed 和 speed 僅由 9 個節(jié)點組成,而上一張圖中的前綴樹包含了 17 個節(jié)點。
可以看出,最小化前綴樹 DFA 可以在很大程度上減少數據結構的大小。即使詞匯量很大,最小化 DFA 通常也適合在內存中存儲,避免昂貴的磁盤訪問是實現快速自動補全的關鍵。
一些擴展
上面介紹了如何利用合理的數據結構實現基本的自動補全功能。這些數據結構可以通過多種方式進行擴展,從而改善用戶體驗。
通常,滿足特定前綴的詞匯可能很多,而用戶界面上能夠顯示的卻不多,我們更希望能顯示最常搜索或者最有價值的詞匯。這通常可以通過為詞匯表中的每個單詞增加一個代表單詞值的權重 weight,并且按照權重高低來排序自動補全列表。
•對于排序后的詞匯表來說,在詞匯表每個元素上增加 weight 屬性并不難;
•對于前綴樹來說,將 weight 存儲在葉子節(jié)點中,也是很簡單的一個實現;
•對于 DFA 來說,則較為復雜。因為一個葉子節(jié)點可以通過多條路徑到達。一種解決方案是將權重關聯到路徑而不是葉子節(jié)點。
目前有不少開源庫都提供了這個功能,比如主流的搜索引擎框架 Elasticsearch[4]、Solr[5]等,基于此,我們可以實現高效而強大的自動補全功能。