## 搜索關鍵詞智能提示suggestion ### 題目詳情 百度搜索框中，輸入“北京”，搜索框下面會以北京為前綴，展示“北京愛情故事”、“北京公交”、“北京醫院”等等搜索詞，輸入“[結構之](http://www.baidu.com/s?wd=結構之&rsv_bp=0&ch=&tn=baidu&bar=&rsv_spt=3&ie=utf-8&rsv_sug3=8&rsv_sug=0&rsv_sug4=1075&rsv_sug1=3&inputT=2559)”，會提示“結構之法”，“結構之法 算法之道”等搜索詞。 請問，如何設計此系統，使得空間和時間復雜度盡量低。  ### 分析與解法 本題來源于去年2012年百度的一套實習生筆試題中的系統設計題（*為尊重原題，本章主要使用百度搜索引擎展開論述，而不是google等其它搜索引擎，但原理不會差太多。然脫離本題，平時搜的時候，鼓勵用...*），題目比較開放，考察的目的在于看應聘者解決問題的思路是否清晰明確，其次便是看能考慮到多少細節。 我去年整理此題的時候，曾簡單解析過，提出的方法是： - 直接上**Trie樹**「Trie樹的介紹見：從Trie樹（字典樹）談到后綴樹」 + **TOP K**「hashmap+堆，hashmap+堆 統計出如10個近似的熱詞，也就是說，只存與關鍵詞近似的比如10個熱詞」 方法就是這樣子的：Trie樹+TOP K算法，但在實際中，真的只要Trie樹 + TOP K算法就夠了么，有什么需要考慮的細節？OK，請看下文娓娓道來。 #### 解法一、Trie樹 + TOP K ##### 步驟一、trie樹存儲前綴后綴 若看過博客內這篇[介紹Trie樹和后綴樹的文章](http://blog.csdn.net/v_july_v/article/details/6897097)的話，應該就能對trie樹有個大致的了解，為示本文完整性，引用下原文內容，如下： **1.1、什么是Trie樹** Trie樹，即字典樹，又稱單詞查找樹或鍵樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用于統計和排序大量的字符串（但不僅限于字符串），所以經常被搜索引擎系統用于文本詞頻統計。它的優點是：最大限度地減少無謂的字符串比較，查詢效率往往比哈希表高。 Trie的核心思想是空間換時間。利用字符串的公共前綴來降低查詢時間的開銷以達到提高效率的目的。 它有3個基本性質： 1. 根節點不包含字符，除根節點外每一個節點都只包含一個字符。 2. 從根節點到某一節點，路徑上經過的字符連接起來，為該節點對應的字符串。 3. 每個節點的所有子節點包含的字符都不相同。 **1.2、樹的構建** 舉個在網上流傳頗廣的例子，如下： 題目：給你100000個長度不超過10的單詞。對于每一個單詞，我們要判斷他出沒出現過，如果出現了，求第一次出現在第幾個位置。 分析：這題當然可以用hash來解決，但是本文重點介紹的是trie樹，因為在某些方面它的用途更大。比如說對于某一個單詞，我們要詢問它的前綴是否出現過。這樣hash就不好搞了，而用trie還是很簡單。 現在回到例子中，如果我們用最傻的方法，對于每一個單詞，我們都要去查找它前面的單詞中是否有它。那么這個算法的復雜度就是O(n^2)。（字符串比較的復雜度是否以strcmp次數計算更妥當，當此處為了討論簡化了細節）。顯然對于100000的范圍難以接受。現在我們換個思路想。假設我要查詢的單詞是abcd，那么在他前面的單詞中，以b，c，d，f之類開頭的我顯然不必考慮。而只要找以a開頭的中是否存在abcd就可以了。同樣的，在以a開頭中的單詞中，我們只要考慮以b作為第二個字母的，一次次縮小范圍和提高針對性，這樣一個樹的模型就漸漸清晰了。 好比假設有b，abc，abd，bcd，abcd，efg，hii 這6個單詞，我們構建的樹就是如下圖這樣的：  當時第一次看到這幅圖的時候，便立馬感到此樹之不凡構造了。單單從上幅圖便可窺知一二，好比大海搜人，立馬就能確定東南西北中的到底哪個方位，如此迅速縮小查找的范圍和提高查找的針對性，不失為一創舉。 ok，如上圖所示，對于每一個節點，從根遍歷到他的過程就是一個單詞，如果這個節點被標記為紅色，就表示這個單詞存在，否則不存在。 那么，對于一個單詞，我只要順著他從根走到對應的節點，再看這個節點是否被標記為紅色就可以知道它是否出現過了。把這個節點標記為紅色，就相當于插入了這個單詞。 借用上面的圖，當用戶輸入前綴a的時候，搜索框可能會展示以a為前綴的“abcd”，“abd”等關鍵詞，再當用戶輸入前綴b的時候，搜索框下面可能會提示以b為前綴的“bcd”等關鍵詞，如此，實現搜索引擎智能提示suggestion的第一個步驟便清晰了，即用trie樹存儲大量字符串，當前綴固定時，存儲相對來說比較熱的后綴。那又如何統計熱詞呢？請看下文步驟二、TOP K算法統計熱詞。 ##### 步驟二、TOP K算法統計熱詞 當每個搜索引擎輸入一個前綴時，下面它只會展示0~10個候選詞，但若是碰到那種候選詞很多的時候，如何取舍，哪些展示在前面，哪些展示在后面？這就是一個搜索熱度的問題。 如本題描述所說，在去年的這個時候，當我在搜索框內搜索“北京”時，它下面會提示以“北京”為前綴的諸如“北京愛情故事”，“北京公交”，“北京醫院”，且“ 北京愛情故事”展示在第一個：  為何輸入“北京”，會首先提示“北京愛情故事”呢？因為去年的這個時候，正是《北京愛情故事》這部電視劇上映正火的時候（其上映日期為2012年1月8日，火了至少一年），那個時候大家都一個勁的搜索這部電視劇的相關信息，當10個人中輸入“北京”后，其中有8個人會繼續敲入“愛情故事”（連起來就是“北京愛情故事”）的時候，搜索引擎對此當然不會無動于衷。 也就是說，搜索引擎知道了這個時間段，大家都在瘋狂查找北京愛情故事，故當用戶輸入以“北京”為前綴的時候，搜索引擎猜測用戶有80%的機率是要查找“北京愛情故事”，故把“北京愛情故事”在下面提示出來，并放在第一個位置上。 但為何今年這個時候再次搜索“北京”的時候，它展示出來的詞不同了呢？ 原因在于隨著時間變化，人們對《北京愛情故事》這部電視劇的關注度逐漸下降，與此同時，又出現了新的熱詞，或新的電影，故現在雖然同樣是輸入“北京”，后面提示的詞也相應跟著起了變化。那解決這個問題的辦法是什么呢？如開頭所說：定期分析某段時間內的人們搜索的關鍵詞，統計出搜索次數比較多的熱詞，繼而當用戶輸入某個前綴時，優先展示熱詞。 故說白了，這個問題的第二個步驟便是統計熱詞，我們把統計熱詞的方法稱為TOP K算法，此算法的應用場景便是[此文](http://blog.csdn.net/v_july_v/article/details/7382693)中的第2個問題，再次原文引用： **尋找熱門查詢，300萬個查詢字符串中統計最熱門的10個查詢** 原題：搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為1-255字節。假設目前有一千萬個記錄（這些查詢串的重復度比較高，雖然總數是1千萬，但如果除去重復后，不超過3百萬個。一個查詢串的重復度越高，說明查詢它的用戶越多，也就是越熱門），請你統計最熱門的10個查詢串，要求使用的內存不能超過1G。 解答：由上面第1題，我們知道，數據大則劃為小的，如一億個Ip求Top 10，可先將Ip地址使用Ip2long函數（各種語言或庫皆提供本函數）轉為長整型Ipld后，再按Ipld%1000將ip分到1000個小文件中去，并保證一種ip只出現在一個文件中，再對每個小文件中的ip進行hashmap計數統計并按數量排序，最后歸并或者最小堆依次處理每個小文件的top10以得到最后的結果。（小提示：常用的Ip hash還有一種基于bit的方法，聰明的你一定想到了吧^_^） 但如果數據規模本身就比較小，能一次性裝入內存呢？比如這第2題，雖然有一千萬個Query，但是由于重復度比較高，因此事實上只有300萬的Query，每個Query255Byte，因此我們可以考慮把他們都放進內存中去（300萬個字符串假設沒有重復，都是最大長度，那么最多占用內存3M\*1K/4=0.75G（實際占用會略大一點，因具體實現而異）。所以可以將所有字符串都存放在內存中進行處理），而現在只是需要一個合適的數據結構，在這里，HashTable絕對是我們優先的選擇。 所以對數據量較少（可以全部放入內存的時候）我們放棄分而治之+hash映射的步驟，直接上hash統計，然后排序。針對此類典型的TOP K問題，采取的對策往往是：hashmap + 堆。如下所示： 1. **hashmap統計：**先對這批海量數據預處理。具體方法是：維護一個Key為Query字串，Value為該Query出現次數的HashTable，即hash_map(Query，Value)，每次讀取一個Query，如果該字串不在Table中，那么加入該字串，并且將Value值設為1；如果該字串在Table中，那么將該字串的計數加一即可。最終我們在O(N)的時間復雜度內用Hash表完成了統計； 2. **堆排序：**第二步、借助堆這個數據結構，找出Top K，時間復雜度為N‘logK。即借助堆結構，我們可以在對數量級的時間內查找和調整。因此，維護一個K(該題目中是10)大小的小根堆，然后遍歷300萬的Query對應的計數，分別和根元素進行對比。所以，我們最終的時間復雜度是：O（N） + N' \* O（logK），（N為1000萬，N’為300萬）。 別忘了這篇文章中所述的堆排序思路：‘維護k個元素的最小堆，即用容量為k的最小堆存儲最先遍歷到的k個數，并假設它們即是最大的k個數，建堆費時O（k），并調整堆(費時O（logk）)后，有k1>k2>...kmin（kmin設為小頂堆中最小元素）。繼續遍歷數列，每次遍歷一個元素x，與堆頂元素比較，若x>kmin，則更新堆（x入堆，用時logk），否則不更新堆。這樣下來，總費時O（k\*logk+（n-k）\*logk）=O（n\*logk）。此方法得益于在堆中，查找等各項操作時間復雜度均為logk。’--第三章續、Top K算法問題的實現。 當然，你也可以采用trie樹，關鍵字域存該查詢串出現的次數，沒有出現為0。最后用10個元素的最小推來對出現頻率進行排序。 相信，如此，也就不難理解開頭所提出的方法了：Trie樹+ TOP K「hashmap+堆，hashmap+堆 統計出如10個近似的熱詞，也就是說，只存與關鍵詞近似的比如10個熱詞」。 而且你以后就可以告訴你身邊的伙伴們，為何輸入“結構之”，會提示出來一堆以“結構之”為前綴的詞了：  方法貌似成型了，但有哪些需要注意的細節呢？如@江申_Johnson所說：“實際工作里，比如當前綴很短的時候，候選詞很多的時候，查詢和排序性能可能有問題，也許可以加一層索引trie（這層索引可以只索引頻率高于某一個閾值的詞，很短的時候查這個就可以了。數量不夠的話再去查索引了全部詞的trie樹）；而且有時候不能根據query頻率來排，而要引導用戶輸入信息量更全面的query，或者或不僅僅是前綴匹配這么簡單。” 當然，在實際的工程中，排序的依據還有很多，例如對于突發的熱點問題，雖然之前用戶沒有輸入過，但是卻能排在最前面，是因為在系統內部有一些相應的模塊進行了所謂的“調權”。此外，上面我們談到trie的時候，都采取了簡化的模型，即trie通常只是針對英語單詞而言的，如果是中文，會有一個嚴重的問題：），你想到了嗎？（小提示：英語和中文的基本字符，差別是不是很大？）當然，如果考慮到我們喜歡用拼音來表述中文，這個問題不是沒有解決方法的^_^。 此外，在工程實現的時候，前端往往采用了ajax技術來保障速度上的優勢，不然等用戶輸入完畢了咱的推薦詞還在慢悠悠的傳輸中，那也就沒有多少意義了。由于前端討論和咱們這里的討論關系不大，感興趣的朋友可以參考相關資料。 ###擴展閱讀 除了上文提到的trie樹，三叉樹或許也是一個不錯的解決方案：[點擊此處](http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/)。此外，StackOverflow上也有兩個討論帖子，大家可以看看：[帖子1](http://stackoverflow.com/questions/2901831/algorithm-for-autocomplete)，[帖子2](http://stackoverflow.com/questions/1783652/what-is-the-best-autocomplete-suggest-algorithm-datastructure-c-c)。