搜索時的動態提示

上周跟大家聊了文本檢索的算法和原理。然后有朋友就跟老王提了個問題，如何實現搜索時的提示？比如輸入“老王”，怎么出現“老王很帥”、“老王很酷”的？

那借著上周的內容，我們這周就聊聊這個算法的實現吧。

這個提示一般被叫做 suggestion ，為的是減少用戶在查詢時的輸入。那我們為了保證有足夠好 & 多的 suggestion ，一般需要解決以下兩個問題。

第一個問題： suggestion 數據來源問題

這個問題要解決的就是你在輸入的時候，我給的提示的數據源從哪里來？一般情況下有多種途徑：

1 、根據所有用戶的歷史查詢輸入，對用戶的檢索內容做統計和排序，生成大量用作 suggestion 的字符串；

比如：用戶 A 搜索了：老王好帥；用戶 B 搜索了：老王很酷；用戶 C 搜索了：老王很帥。這個時候，當用戶 D 來搜索：“老王”的時候，檢索系統就會把之前熱搜的“老王很帥”、“老王很酷”展示出來當做搜索提示，方便 D 用戶來輸入。

2 、根據文本內的高頻詞匯、句子和短語建立 suggestion 字符串。

我們的文本搜索引擎會收錄大量的文本，并且會對這些文本進行分段落、劃句、切詞等等操作。其中有些句子或者短語是非常高頻的，這一部分的句子或者短語也可以用做檢索時的提示。

以上列出了兩種 suggestion 內容的來源。其實根據不同的業務，還可以有其他不同的來源。比如，如果是做好友系統，那么在添加好友的時候， suggestion 里面就可以優先出現好友的好友等等。

好了，解決了數據源的問題，接下來要解決的就是如何做索引，達到高效的檢索提示的性能。

第二個問題：高效的檢索

在用戶檢索的時候，一般都是前綴匹配提示。比如：你輸入“老”，會提示“老王 XXX ”。但是如果輸入“王”，就一般不會再出現“老王 XXX ”這樣的提示了，而是出現“王者歸來”這樣以“王”開頭的提示。所以，這樣的業務模式就大大簡化了我們做 suggestion 的難度。

那具體怎么做呢？

上周我們講了文本檢索的幾種方法，大家還記得嘛？

第一種： Trie （字典）樹

字典樹的特點就是前綴匹配。那根據我們上面對的 suggestion 的分析，他是非常適合用這樣的方法來建立索引的。

所以，我們只需要將我們所有的 suggestion 條目建立成對應的字典樹即可。如果內容過多，就考慮拆分成多機，然后由一個結點來做合并即可。

第二種：倒排索引（改進型）

還是上周講到的老方法。不過在建立索引的時候，有一點不一樣。上周我們講的時候，是將文本進行單詞或者中文詞組分詞，然后建立倒排索引。當檢索的時候，進行合并。

做 suggestion 就沒有那么麻煩，因為提示一般會是一個詞組、短句等等，字數都很少。不會有那種長篇的文章，所以再按原來的方法，效率會比較低。

那怎么樣改進呢？其實可以這樣來實現。我們只需要將熱搜或者高頻詞組進行前綴拆分，然后分別建立索引，即可達到效果。如下圖：

我們將“老王很帥”拆分成“老”、“老王”、“老王很”、“老王很帥”四個 term ，然后將他們作為倒排索引的 key ， value 都指向實體的內容（ id=100 ， content= 老王很帥）。當用戶輸入“老”或者“老王”，被檢索的 key 都能被索引到，而指向真正的數據。

當然，每個 key 后面掛的都是一個按權重排序好的實體數據指針鏈。這樣，我們檢索的時候，只需要查一次索引，便可以方便的得到想要的結果。

但是這種方法也有一個問題，就是數據膨脹。如果按照平均每一個提示內容的長度為 5 個字符的話，我們索引的空間需要增加 5 倍。不過按照空間換時間的原則，這一部分的開銷，其實還是比較劃算的。

如果確實不愿意增加空間開銷，也可以用上周我們講到的方案，分詞 + 歸并的方法。只是查詢效率上會降低一些。

額外的需求

如果用戶的輸入中含有拼音，怎么辦？比如：“老 wang ”……

作為技術人員，不得不感嘆：用戶的需求怎么這么多？（其實更直接的反饋是：產品經理真是變態）。

wang 可能有很多漢字與之對應，比如：“王、網、旺……”他們其實都有相同的拼音 wang 。所以，當用戶輸入“老 wang ”的時候，他有可能表達的是“老王”、“老網”或者是“老旺”。這個時候，我們就要將這幾個詞放到我們的倒排索引系統中，去找找，看看到底有哪些是通過索引能匹配的。如果遇到那種拼音對飲漢字再多一點的，比如“ a ”，這個時候程序員要瘋了……

不過作為有追求的程序員，我們還是有辦法去解決這樣的問題。大家還記得一個詞叫做“歸一化”嗎？就是將表象不同的 N 個東西，通過一定的分析和處理，找到他們相同的本質，從而用另外一個東西去代替這一堆的東西。

拼音，即是漢字做歸一化的一個途徑。既然正著做不行，那我們就反著做。比如“老王很帥”，我們是否可以將漢字轉化成拼音“ lao-wang-hen-shuai ” , 將這個拼音詞組也按之前的方式，拆成四個倒排索引，指向 id=100 的那個實體內容。當用戶查詢“老 wang ”的時候，我們檢測到有拼音，即可將他們轉換成“ laowang ”，再去倒排系統中查詢。

對于多音字，比如“了”，我們在建立倒排索引的時候，注意做一下這個字在句子或者短語中的發音處理即可。

對于 suggestion ，根據不同的業務，有很多不同的實現方案，好不好關鍵看是否適合相關的業務。所謂的沒有最好的架構，只有更適合的方案。如果本身的業務規模并不大，或者是產品要求沒那么高，或許，只需要一條 sql ： select * from simplemain where word like ' 老王 %' 就可以解決了。所以，大家不用迷信所謂的各種高級架構。更適合的才是最好的！

好了，今天扯了這么多，大家都看懂了嘛？

 

 

來自：http://mp.weixin.qq.com/s?__biz=MzA3MDExNzcyNA==&mid=2650392332&idx=1&sn=afde4f7887059800681b9a5d05d9fee2&chksm=86ccd73fb1bb5e290617155d27de64fa5b1dd333a186b47ab15e14761abd37622f7c100b67c5&scene=0