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

使用自動(dòng)補(bǔ)全

Google 搜索的自動(dòng)補(bǔ)全功能可以在 Google 搜索應(yīng)用的大多數(shù)位置使用，包括 Google^[1] 主頁(yè)、適用于 IOS 和 Android 的 Google 應(yīng)用，我們只需要在 Google 搜索框上開(kāi)始鍵入關(guān)鍵字，就可以看到聯(lián)想詞了。

在上圖示例中，我們可以看到，輸入關(guān)鍵字 juej，Google 搜索會(huì)聯(lián)想到“掘金”、“掘金小冊(cè)”、“絕句”等等，好處就是，我們無(wú)須輸入完整的關(guān)鍵字即可輕松完成針對(duì)這些 topics 的搜索。

谷歌搜索的自動(dòng)補(bǔ)全功能對(duì)于使用移動(dòng)設(shè)備的用戶(hù)來(lái)說(shuō)特別有用，用戶(hù)可以輕松在難以鍵入的小屏幕上完成搜索。當(dāng)然，對(duì)于移動(dòng)設(shè)備用戶(hù)和臺(tái)式機(jī)用戶(hù)而言，這都節(jié)省了大量的時(shí)間。根據(jù) Google 官方報(bào)告，自動(dòng)補(bǔ)全功能可以減少大約 25% 的打字，累積起來(lái)，預(yù)計(jì)每天可以節(jié)省 200 多年的打字時(shí)間。是的，每天！

注意，本文所提到的“聯(lián)想詞”與“預(yù)測(cè)”，是同一個(gè)意思。

基于“預(yù)測(cè)”而非“建議”

Google 官方將自動(dòng)補(bǔ)全功能稱(chēng)之為“預(yù)測(cè)”，而不是“建議”，為什么呢？其實(shí)是有充分理由的。自動(dòng)補(bǔ)全功能是為了幫助用戶(hù)完成他們打算進(jìn)行的搜索，而不是建議用戶(hù)要執(zhí)行什么搜索。

那么，Google 是如何確定這些“預(yù)測(cè)”的？其實(shí)，Google 會(huì)根據(jù)趨勢(shì)搜索 trends^[2] 給到我們這些“預(yù)測(cè)”。簡(jiǎn)單來(lái)說(shuō)，哪個(gè)熱門(mén)、哪個(gè)搜索頻率高，就更可能推給我們。當(dāng)然，這也與我們當(dāng)前所處的位置以及我們的搜索歷史相關(guān)。

另外，這些“預(yù)測(cè)”也會(huì)隨著我們鍵入的關(guān)鍵字的變更而更改。例如，當(dāng)我們把鍵入的關(guān)鍵字從 juej 更改為 juex 時(shí)，與“掘金”相關(guān)的預(yù)測(cè)會(huì)“消失”，同時(shí)，與“覺(jué)醒”、“決心”相關(guān)聯(lián)的詞會(huì)出現(xiàn)。

為什么我們看不到某些聯(lián)想詞？

如果我們?cè)谳斎肽硞€(gè)關(guān)鍵字時(shí)看不到聯(lián)想詞，那么表明 Google 的算法可能檢測(cè)到：

•這個(gè)關(guān)鍵字不是熱門(mén)字詞；

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

•這是一個(gè)侮辱性或敏感字詞，這個(gè)搜索字詞違反了 Google 的相關(guān)政策。更加詳細(xì)的情況，可以了解 Google 搜索自動(dòng)補(bǔ)全政策^[3]。

為什么我們會(huì)看到某些不當(dāng)?shù)穆?lián)想詞？

Google 擁有專(zhuān)門(mén)設(shè)計(jì)的系統(tǒng)，可以自動(dòng)捕獲不適當(dāng)?shù)念A(yù)測(cè)結(jié)果而不顯示出來(lái)。然而，Google 每天需要處理數(shù)十億次搜索，這意味著 Google 每天會(huì)顯示數(shù)十億甚至上百億條預(yù)測(cè)。再好的系統(tǒng)，也可能存在缺陷，不正確的預(yù)測(cè)也可能隨時(shí)會(huì)出現(xiàn)。

我們作為 Google 搜索的用戶(hù)，如果認(rèn)定某條預(yù)測(cè)違反了相關(guān)的搜索自動(dòng)補(bǔ)全政策，可以進(jìn)行舉報(bào)反饋，點(diǎn)擊右下角“舉報(bào)不當(dāng)?shù)穆?lián)想查詢(xún)”并勾選相關(guān)選項(xiàng)即可。

如何實(shí)現(xiàn)自動(dòng)補(bǔ)全算法？

目前，Google 官方似乎并沒(méi)有公開(kāi)搜索自動(dòng)補(bǔ)全的算法實(shí)現(xiàn)，但是業(yè)界在這方面已經(jīng)有了不少研究。

一個(gè)好的自動(dòng)補(bǔ)全器必須是快速的，并且在用戶(hù)鍵入下一個(gè)字符后立即更新聯(lián)想詞列表。自動(dòng)補(bǔ)全器的核心是一個(gè)函數(shù)，它接受輸入的前綴，并搜索以給定前綴開(kāi)頭的詞匯或語(yǔ)句列表。通常來(lái)說(shuō)，只需要返回少量的數(shù)目即可。

接下來(lái)，我們先從一個(gè)簡(jiǎn)單且低效的實(shí)現(xiàn)開(kāi)始，并在此基礎(chǔ)上逐步構(gòu)建更高效的方法。

詞匯表實(shí)現(xiàn)

一個(gè)簡(jiǎn)單粗暴的實(shí)現(xiàn)方式是：順序查找詞匯表，依次檢查每個(gè)詞匯，看它是否以給定的前綴開(kāi)頭。

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

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

前綴樹(shù)實(shí)現(xiàn)

通常來(lái)說(shuō)，許多詞匯都以相同的前綴開(kāi)頭，比如 need、nested 都以 ne 開(kāi)頭，seed、speed 都以 s 開(kāi)頭。要是為每個(gè)單詞分別存儲(chǔ)公共前綴似乎很浪費(fèi)。

前綴樹(shù)是一種利用公共前綴來(lái)加速補(bǔ)全速度的數(shù)據(jù)結(jié)構(gòu)。前綴樹(shù)在節(jié)點(diǎn)樹(shù)中排列一組單詞，單詞沿著從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑存儲(chǔ)，樹(shù)的層次對(duì)應(yīng)于前綴的字母位置。

前綴的補(bǔ)全是順著前綴定義的路徑來(lái)查找的。例如，在上圖的前綴樹(shù)中，前綴 ne 對(duì)應(yīng)于從子節(jié)點(diǎn)取左邊緣 N 和唯一邊緣 E 的路徑。然后可以通過(guò)繼續(xù)遍歷從 E 節(jié)點(diǎn)可以達(dá)到的所有葉節(jié)點(diǎn)來(lái)生成補(bǔ)全列表。在圖中，ne 的補(bǔ)全可以是兩個(gè)分支：-ed 和 -sted。如果在數(shù)中找不到由前綴定義的路徑，則說(shuō)明詞匯表中不包含以該前綴開(kāi)頭的單詞。

有限狀態(tài)自動(dòng)機(jī)(DFA)實(shí)現(xiàn)

前綴樹(shù)可以有效處理公共前綴，但是，對(duì)于其他共享詞部分，仍會(huì)分別存儲(chǔ)在每個(gè)分支中。比如，后綴 ed、ing、tion 在英文單詞中特別常見(jiàn)。在上一個(gè)例子中，e、d 分別存放在了每一個(gè)分支上。

有沒(méi)有一種方法可以更加節(jié)省存儲(chǔ)空間呢？有的，那就是 DFA。

在上面的例子中，單詞 need、nested、seed 和 speed 僅由 9 個(gè)節(jié)點(diǎn)組成，而上一張圖中的前綴樹(shù)包含了 17 個(gè)節(jié)點(diǎn)。

可以看出，最小化前綴樹(shù) DFA 可以在很大程度上減少數(shù)據(jù)結(jié)構(gòu)的大小。即使詞匯量很大，最小化 DFA 通常也適合在內(nèi)存中存儲(chǔ)，避免昂貴的磁盤(pán)訪(fǎng)問(wèn)是實(shí)現(xiàn)快速自動(dòng)補(bǔ)全的關(guān)鍵。

一些擴(kuò)展

上面介紹了如何利用合理的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)基本的自動(dòng)補(bǔ)全功能。這些數(shù)據(jù)結(jié)構(gòu)可以通過(guò)多種方式進(jìn)行擴(kuò)展，從而改善用戶(hù)體驗(yàn)。

通常，滿(mǎn)足特定前綴的詞匯可能很多，而用戶(hù)界面上能夠顯示的卻不多，我們更希望能顯示最常搜索或者最有價(jià)值的詞匯。這通常可以通過(guò)為詞匯表中的每個(gè)單詞增加一個(gè)代表單詞值的權(quán)重 weight，并且按照權(quán)重高低來(lái)排序自動(dòng)補(bǔ)全列表。

•對(duì)于排序后的詞匯表來(lái)說(shuō)，在詞匯表每個(gè)元素上增加 weight 屬性并不難；

•對(duì)于前綴樹(shù)來(lái)說(shuō)，將 weight 存儲(chǔ)在葉子節(jié)點(diǎn)中，也是很簡(jiǎn)單的一個(gè)實(shí)現(xiàn)；

•對(duì)于 DFA 來(lái)說(shuō)，則較為復(fù)雜。因?yàn)橐粋€(gè)葉子節(jié)點(diǎn)可以通過(guò)多條路徑到達(dá)。一種解決方案是將權(quán)重關(guān)聯(lián)到路徑而不是葉子節(jié)點(diǎn)。

目前有不少開(kāi)源庫(kù)都提供了這個(gè)功能，比如主流的搜索引擎框架 Elasticsearch^[4]、Solr^[5]等，基于此，我們可以實(shí)現(xiàn)高效而強(qiáng)大的自動(dòng)補(bǔ)全功能。