十一假期大家過的還好嗎？時間過得真快，距離上一次跟大家聊技術已經過了快三周了。老王很開心今天又能跟大家一起扯淡了，用一句通俗的話講就是：老王想死你們了！今天準備跟大家聊的，乃是大名鼎鼎的文本檢索技術。也就是大家天天都在用的“百度一下”。

為了簡單，我們先從單詞搜索開始，也就是類似于百詞斬的查詞功能。

想必大家或多或少都用過類似的功能，就是我們在查詞框里輸入幾個字母或者中文，然后就能查找出我們想要的單詞。那這個算法是如何實現的呢？其實有很多中方法，我們接下來一一介紹。這里為了更方便描述，我們就只介紹搜索英文的情況，中文含義的搜索其實類似，就不混著講了~

在開始之前，我們先設定一個全局變量：假定有一個詞典DICT，含有的單詞：[good, bad, god, sad]。

方法一：暴力法

最容易讓人想到的方法，就是寫一個for循環，然后一個個的比較，看是否匹配，偽代碼大概就是這樣：

我們遍歷詞典中所有的單詞，讓每一個單詞和我們待搜索的單詞進行比較，看看他們之間的相似度，比較完了以后，就按照相似度排序，越像的排的越靠前。最后，我們將TOP-N的數據返回給用戶。

這里面最關鍵的一個函數，就是compare。我們怎么比較兩個單詞的相似度呢？一般采用LCS（Longest Common Subsequence，最長公共子序列）算法。這個算法用來比較兩個字符串含有的最多的相同字符，比如，same和some最長的公共子序列就是sme(same,some)。這個算法是一個動態規劃算法，挺有意思，以后有時間可以專門跟大家做一個分享。

上述的查找算法雖然很精確，但是卻有一個致命的問題，就是算法復雜度太高。如果我們有幾萬個單詞，那么每次用戶查詢都要做一個幾萬次的for循環，然后循環里面還要做一次相似度比較，效率實在太低。

那有沒有更好的方法呢？我們接著往下看。

方法二：Trie樹（字典樹）

想必好多朋友都聽說過這個大名鼎鼎的字典樹。老王模模糊糊的記得，當年去百度的時候，自己寫了一個反作弊的匹配算法就用到了這個數據結構。那這個東東是怎么工作的呢？

初始化的時候，我們構建一個根節點為空的樹，然后我們將字典DICT中的單詞，一個個的加入到這棵樹中，單詞的每一個字母掛接到對應的層次下，比如：good，就將g掛在root結點下，o掛接到g下…… 如此重復。便形成我們上面看到的這棵樹。從root結點延任意一條路勁走到葉結點，都能形成我們字典中的單詞。

那我們搜索的時候怎么做呢？

比如當用戶輸入go的時候，我們就從root結點開始，沿著這棵樹一直往下走。依次走過root->g->o這三個結點。接下來他有兩個子節點，我們就將這兩個子節點對應的單詞返回給用戶，即：god、good。

大家看看，這種算法的復雜度一下就下降了，不用再做遍歷。但是這個算法有一定的局限性：就是他只能做前綴匹配，也就是說他只能從開始做匹配，如果我們要匹配單詞中間的一部分或者是模糊匹配，就很難實現。

不過，這種算法也可以做一些簡單的改進，從而滿足我們更多的需求。

我們在建樹的時候，可以可以把每個單詞做一下拆分，將每一個字符都作為起始字符進行建樹。比如：good可以拆成4個單詞：good, ood, od, d。然后分別將這些所謂的單詞構建成Trie樹。這樣，我們即使搜索單詞中間一部分，也能出對應的結果，就不需要強制用戶從第一個字母開始輸入。

那有朋友一定會問，這個規模會膨脹多少??？我們只需要簡單計算一下就能得出。比方說，我們平均每個單詞的長度為10（老王大概統計了幾萬個單詞，平均長度大概是8.4左右），那么我們所有需要構建的單詞數就是DICT中單詞數的10倍。如果我們常用單詞約3萬個，那么就只需要構建一棵大約30萬個單詞的樹（這個數量級還是可以接受的）。

不過，即使通過上面的改進，我們還是比較難以實現模糊匹配的功能。比如，我們輸入gd，字典樹就不能檢索出good或者god。

那還有沒有其他的方法呢？

方法三：倒排索引

想必好多朋友對這個詞都耳熟能詳了吧。沒錯，這個算法就是我們現在檢索用的最多的工業界方法。這個算法用了一個很簡單的思想，解決了海量文本的索引問題。也就是百度、google做的事情。那具體怎么做的呢？跟著老王一起往下看吧。

我們之前講的第一種方法（暴力法），對于單詞沒有任何預處理，數據的組織完全是按照單詞本身去組織的，而沒有按照用戶的輸入去組織，所以每次查詢來了，都要重復的計算。而第二種方法（Trie樹），則是做了一定的預處理，將單詞拆分成字母，一定程度上按照用戶輸入的順序來組織。所以，每次用戶輸入請求的時候，只需要做很小一部分計算，就可以得到結果。

那根據以上兩種方式的啟發，我們如果要很好的滿足用戶的需求，就應該將我們已有的數據按照用戶的輸入來組織，經過這樣的預處理以后，等用戶查詢來的時候，我們就不會重復的去做計算了，對吧~

那倒排索引的思想也基本是這樣：我們將每個單詞都拆解成字母，然后根據用戶輸入的字母，將含有這些字母的單詞都列舉出來，然后看誰更符合用戶的輸入，就將誰返回。來看下圖：

我們將每一個單詞都拆解成單個單個的字母，然后將含有相同字母的單詞掛接到對應的字母鏈上。如上圖：bad就可以拆解成b、a、d三個字母，然后我們將bad這個單詞分別掛接到字母b、a、d所在的鏈上。同理，對于其他單詞也是。

這樣，當用戶輸入b的時候，我們一下就能找到bad。如果用戶輸入bd，我們就可以將b鏈和d鏈的數據進行合并，將最符合條件的bad先輸出，然后再輸出其他幾個有可能是結果的備選單詞。

怎么樣，是不是很簡單啊。是的，這就是傳說中的倒排索引。之所以稱做倒排，是相對于bad->b-a-d這樣的正排索引而言。

有了上述這個基本的邏輯以后，我們剩下的工作就是需要做結果優化。

1、多路歸并計數。

比如，我們輸入bd，那對于用戶預期而言，結果bad肯定要比god要好，因為bad含有b和d兩個關鍵字母，而god只有一個d。所以，我們要將檢索的結果進行合并，看誰含有的關鍵字母更多，就應該往前面排。

這里用到了一個關鍵技術，就是多路歸并。在算法和數據結構的課上，大家應該至少聽說過這個算法。老王就不詳細的來講了。（記得當年剛到百度的時候，就參加了一個內部搞的一個算法優化大賽，做的就是多路歸并算法優化，老王還得了前幾名，哈哈哈~）

2、增加偏序關系。

上面講了多路歸并，那是不是出現字母越多，就應該排在越前面呢？我們看一個例子：當我們字典里有[god, dog, dot]這三個單詞的時候，如果用戶輸入dog這三個字母的時候，根據上面多路歸并的結果，god匹配3次，dog3次，dot2次，按道理說，我們就應該按照字典里的順序輸出god-dog-dot。但是，實際上比較好的一個結果可能是：dog-dot-god。為什么呢？因為用戶輸入的順序很！重！要！

因此，我們除了要檢查字母個數，還需要增加偏序關系，用于記錄字母出現在單詞中的位置。匹配結果的時候，要根據用戶的輸入順序進行排序。具體實現的時候，我們可以在倒排拉鏈的時候，記錄一下位置，最后歸并的時候，對位置做一個打分，排序的時候，加入位置因素。

好了，以上講了兩種優化結果的方法。其實，還有很多地方要根據實際業務去優化，我們這里就不細講了（不然這篇文章的字數真的就要過萬了）。

那上面這個倒排索引的方法，是不是真的就很好了呢？如果你真的去寫寫代碼，就會發現，還有一個巨大的坑兒在等著你！

對于a,e,i,o,u這幾個元音字母而言，因為絕大多數單詞都含有他們，所以他們的拉鏈會非常的長。如果有用戶搜索a，那可能你的程序在很長時間內都沒辦法出結果。那怎么辦呢？

這個時候，我們就需要用到分布式了。我們可以將所有單詞，隨機的拆分成多個組。比如我們有1萬個單詞，拆分成10組。這樣每一組單詞，就只有大概1000個。比方說，原來含有字母a的單詞大概有7000個，這樣拆分以后，每個組里面就只有700個左右的單詞含有字母a。因此每個組里面，字母a的拉鏈就只有700個左右的元素。

接下來，我們將每個組的單詞放到一臺服務器上，搜索的時候，每臺服務器都進行檢索。完成后，將TOP_N的結果上報給一個合并服務器，由他再做一次合并。這樣，我們是不是就可以規避元音字母拉鏈過長的問題了呢。

好了，以上就是我們關于單詞檢索的算法。大家覺得怎么樣呢？

除了單詞搜索，我們在現實中還經常用到搜索好友、搜索文本內容等東東，對應的就是微信的好友搜索和百度的文本搜索。那這些東東在基礎方法上都是上述的一個思想：元素拆分 + 倒排索引 + 合并優化。只不過，在每一個維度上都做了很多優化。比如：文本搜索中，整篇文章就像是一個單詞，而文章中的詞組就像是單詞的字母，用詞組作為倒排拉鏈的基礎元素。那最難的就是分詞，特別是中文分詞，就是一個專門的課題。如果分詞分的不好，那么檢索的結果就會很差。以后找機會，老王也可以跟大家一起聊聊分詞這個話題。

而倒排索引和結果合并，也是有很多地方需要優化的。比如，實時性強的文本（比如新聞），就需要按時間順序來建立排序的索引。對于廣告而言，可能價格就更重要。

好了，今天的內容大家都看懂了嘛？如果對老王的文章感興趣，就請繼續聽老王扯淡吧。老王將文章做了分類，放到了自己搭的網站上，大家可以去上面看看www.virginiabusinesslawupdate.com