在《關鍵詞推薦工具中的使用者引導機制之一》 我們分析了使用者用到機制對搜尋引擎/關鍵詞工具的重要性，同時也提到按照使用者在搜尋引擎/或者關鍵詞工具上互動的階段，可以按互動前，互動中和互動後為使用者分别提供種子query，suggestion和相關搜尋詞對使用者進行引導。 種子query是比較經典的推薦問題， 對于‘相關搜尋’，後續會有博文專門介紹， 該文以下内容主要介紹如何構造高效的suggestion服務。包括架構及内部檢索邏輯。
suggestion到底有多大作用呢， 在很多搜尋引擎中， 一方面，從自然搜尋結果的角度，suggestion能夠引導客戶将輸入表現的更利于搜尋引擎了解使用者的意圖，得到更優質的搜尋結果； 另一方面， 從商業變現的角度看， 大的suggestion政策的上線， 往往能夠帶來搜尋引擎幾個點cpm的提升， 這可是非常了不起的貢獻。 是以對于搜尋引擎， 和關鍵詞推薦工具這樣的基于搜尋的系統， suggestion的作用就至關重要。
圖： 百度suggestion效果
圖：關鍵詞推薦系統suggestion
基本概念
要了解suggestion的設計細節，需要先定義以下名詞：
- Query片段：特指query的字首，例如使用者輸入的query為“鮮花快遞”，其全部query片段為‘鮮’，‘鮮花’，‘鮮花快’，‘鮮花快遞’。
- 拼音片段：本文中特指query片段對應的拼音片段，例如使用者輸入query為‘鮮花’，則全部拼音片段為‘x’，‘xi’，‘xia’，‘xian’，‘xianh’，‘xianhu’，‘xianhua’。
- 候選query：指挖掘出的候選種子query。
- wcode：建立suggestion 索引時，為每個候選query的編号，該編号值表示對應字面在數組結構中的下标位置，為無符号整型。
- 個性化suggestion：根據客戶帳戶資訊進行推薦的query suggestion。
- 通用suggestion:與個性化suggesion對應，所有客戶都适用的query suggestion。
解決方案的權衡
索引方式
suggestion可以做得比較簡單， 也可以比較複雜，例如在搜尋引擎搜尋框中， 可以輸入漢字， 拼音， 或者輸入幾個漢字後，又将輸入法切換為拼音進行輸入， 或是正好反過來。 這樣對于suggestion，就需要考慮是隻對漢字輸入query提供suggestion結果， 還是需要對混合輸入（拼音+漢字）query提供結果。 不同的功能會導緻實作不一樣。
圖：全拼音模式suggestion
圖：漢字+拼音混合模式suggestion
經過統計，候選query平均長度為13.9位元組（約7漢字），其對應的拼音平均22.1個字母。如果僅對漢字建立索引，則可假設每個候選query對應7個query片段索引片段，而如果要對漢字+拼音建立索引，則每個候選query需要對應約30個索引片段（7+22=29）。但建立拼音片段能夠支援使用者拼音輸入，或是中英文混合的情況，是以要達到較好的使用者體驗， 最好是實作： 索引結構支援拼音+漢字方式
性能
作為引導機制，suggestion的性能必須足夠快， 應該做到迅雷不及掩耳的速度，否則在使用者靈活的手指配上高效的輸入法下出現任何一頓一頓的感覺， 都會異常影響使用者體驗， 是以在記憶體允許的情況下， 所有資料常駐單機記憶體，是比較理想的情況， 如果單機記憶體存放不下， 那麼可能的選擇是使用資源定位系統，将資料進行水準拆分（最簡單的方式， 按照query簽名作為key，然後取模）
P.S. 對于如何對資料進行擴充， 推薦大家仔細揣摩《ebay網站架構原則》， 每一條原則都值得細心思考體會。
圖： 水準拆分，例如按照key簽名取模
使用該方式， 請求可輕松達到1w+/s
結果merge及rank
suggestion傳回結果由個性化suggestion(針對每個使用者單獨挖掘)與通用suggestion結果組成，個性化結果在前，通用結果在後的方式，當個性化結果不足時由通用結果補足。
其中，不管個性化結果，還是通用結果，由兩部分組成：原始query片段索引結果與拼音query片段索引結果。對于二者的merge方式存在兩種思路：
- 原始query片段索引結果與拼音query片段索引結果merge，按權重從高到低排序，傳回前N個結果。
- 優先傳回原始query片段索引結果，數量不足時由高權重的拼音query片段索引結果補充。
從使用者體驗與效率考慮，原始query片段索引結果與拼音query片段索引結果的merge方式采用思路2。
思路2還有一個問題需要考慮，原始query片段索引結果數量不足時，進行字音轉換成拼音串後，存在拼音串片段檢索結果與使用者輸入query的漢字串字首不一緻的情況。例如：query為“鮮花”，轉換成拼音串“xianhua”後的檢索結果可能有“鮮花”，“仙花”，“閑話”，這時候的檢索結果可能包含“仙花”，“閑話”同音但不同字的suggestion結果。從檢索邏輯複雜性、效率、數量量考慮，針對純漢字串片段索引結果數量不足時，不進行字音轉換後的拼音片段索引檢索。
針對非純漢字串，原始query片段索引結果數量不足時，通過字音轉換成拼音串片段進行檢索。在檢索過程中，考慮最大漢字字首比對的方式。例如：query為“鮮hua”，轉換成拼音串“xianhua”後的檢索結果可能有“鮮花”，“仙花”，“閑話”。在此例子中，會使用漢字字首“鮮”去與候選query進行比對，最終得到候選query“鮮花”。
使用上述方式， 可以在保證結果個性化（個性化結果需要在離線進行挖掘）的同時，保持suggestion應有的高效。
記憶體資料結構
在決定了使用全記憶體的存儲方式後， 就需要考慮内部資料結構的設計了。 要想讓效率最高，最快的方式就是直接使用hash進行query片段簽名查找。
圖： hash方式進行倒排查找。
索引中主要包括以下結構：
片段索引字典：存儲片段簽名到片段推薦詞倒排的偏移位址。使用bsl::hashmap存儲
片段至推薦詞反向索引：存儲每個片段到候選關鍵詞wcode的反向索引。使用hashmap存儲。通用拉鍊與個性化拉鍊倒排拉鍊合并存儲，差別在于個性化拉鍊不僅包含關鍵詞wcode，還包含關鍵詞的個性化weight。兩種結構根據标志位flag進行區分。為了提高線上服務時，合并字面傳回的效率，針對每個索引的拉鍊會有序(weight從大到小)存儲。
字面隊列：存儲具體wcode字面與字面權重，使用bsl::deque存儲，片段至推薦詞反向索引中的wcode值即為該隊列索引下标。
線上檢索流程
當使用者在搜尋框進行suggestion請求時，會經過對片段進行歸一化，查找漢字索引片段，查找拼音片段及merge結果階段，結果merge及rank主要的原則是漢字片段結果排在拼音結果前， 各類結果内部按照線下挖掘的權值進行rank。 線下挖掘在業界及學術界的方法參見後續博文。 附上一個流程圖， 類似的畫法是在工作中逐漸形成的習慣， 其中将function和data structure單獨分開表示， 虛線表示資料依賴， 實作表示處理邏輯依賴。 該方式自己覺得比較清晰， 特别是對照着文檔寫代碼的過程中：）
更多内容可參見：
《eBay網站的架構原則》 ： 網上都有，每一條擴充原則都值得細心揣摩及體會，各大搜尋引擎大資料的支援原則異曲同工
百度關鍵詞工具介紹參見：http://support.baidu.com/product/fc/4.html?castk=24b18bi7062c720d0d596
也可關注我的微網誌： weibo.com/dustinsea
或是直接通路： http://semocean.com