android搜索框功能實現_巧用 Trie 樹，實現搜索引擎關鍵詞提示功能

來源 | 碼海責編 | Carol封圖 |?CSDN 付費下載于視覺中國我們幾乎每天都在用搜索引擎搜索信息，相信大家肯定有注意過這樣一個細節:當輸入某個字符的時候，搜索引框底下會出現多個推薦詞，如下，輸入「python」后，底下會出現挺多以python 為前綴的推薦搜索文本，它是如何實現的呢？

文章標題已經給出答案了，沒錯，用 Trie 樹。本文將會從以下幾個方面來簡述一下 Trie 樹的原理，以讓大家對 Trie 樹有一個比較全面的認識。

什么是 Trie 樹
Trie 樹的實現
如何實現搜索字符串自動提示
再談 Trie 樹

相信大家看了肯定有收獲

什么是 Trie 樹Trie 樹，又稱前綴樹，字典樹，或單詞查找樹，是一種樹形結構，也是哈希表的變種，它是一種專門處理字段串匹配的數據結構，用來解決在一組字符串集合中快速查找某個字符串的問題，主要被搜索引擎用來做文本詞頻的統計。畫重點：快速字符串匹配，詞頻統計。1、快速字符串匹配假設想要在一串字符串如 a, to, tea, ted, ten, i, in, inn 中多次查找某個字符串是否存在，該怎么做呢，很直觀的想法是用 hash，這種確實沒問題，如果 hash 函數設計得好的話，如果 hash 函數設計得不好，很容易產生沖突，進而退化成字符串間的比較，另外，在英文中其實有很多單詞有共同的前綴，比如中 tea, ted, ten 這三個單詞有共同的前綴 te, 如果用 hash 的話，無疑這些共同前綴相當于重復存了多次，比較費空間。如果用 Trie 樹的話，能解決以上兩個問題，先來看下 trie 樹是如何表示的，以以上的一組字符串 a, to, tea, ted, ten, i, in, inn 為例，它們組成的 Trie 樹如下：

如果要查找某個字符串的話，從根節點出發，每次取待查找字符串中的一個字符往下遍歷，即可找到，可以看到它的查找時間復雜度為 O(N) (N 為字符串長度)，還是很快的(英文單詞普遍比較短)。2、詞頻統計只要在每個結點上加一個計數器，遍歷單詞時，所有字符串的最后一個字符對應結點的計算器都加 1，如以 a，an，and 構造的 Trie 樹如下，每個結點計算器都為 1，代表以此結點存儲字符為終止字符的單詞分別為 1 個。

從前面 Trie 樹的圖解可以看到 Trie 樹的本質就是前綴樹，通過提取出字符串的公共前綴(如果有的話)，以達到快速匹配字符串的目的。通過前綴匹配，使用 Trie 樹查找字符串的效率大大提高！從以上 Trie 樹的圖解我們可以得出 Trie 樹的以下幾個特點

根節點不包含字符，除根節點外每個節點只包含一個字符
從根節點到某一節點，路徑上經過的字符連接起來，為該節點對應的字符串。如上圖中從根節點到結點 o，經過的字符為「t」和「o」,所以它表示單詞 to。
每個節點的所有子節點包含的字符都不相同，這一點也就保證了相同的前綴能夠得到復用。

那么 ?Trie 樹該怎么表示呢？

Trie 樹的實現從上文我們對 Trie 樹的剖析可以很明顯地看到 Trie 樹是一顆多叉樹，那么多叉樹該怎么表示呢，假設字符串都是由 26 個小寫字母組成，則顯然 Trie 樹應該是一顆 26 叉樹，每個節點包含 26 個子節點，如下

上圖可以看出，26 個子節點我們可以用大小為 26 的數組表示，所以 Trie 樹表示如下

/**
?*?26?個字母
?*/static?final?int?ALPHABET_SIZE?=?26;/**
?*?Trie?樹的節點表示
?*/static?class?TriedNode?{/**
?????*?根節點專用，存儲?"/"
?????*/public?char?val;/**
?????*?以此結點字符為終止字符的字符串的個數
?????*/public?int?frequency;/**
?????*?節點指向的子節點
?????*/
????TriedNode[]?children?=?new?TriedNode[ALPHABET_SIZE];public?TriedNode(char?val)?{this.val?=?val;
????}
}/**
?*?Trie?樹
?*/static?class?TrieTree?{private?TriedNode?root?=?new?TriedNode('/');?//?根節點
}

Trie 樹的表現有了，現在我們來看下 Trie 樹的兩個主要操作

根據一組字符串構造 Trie 樹
在 Trie 樹中查找字符串是否存在

先來看如何根據一組字符串構造 Trie 樹，首先如何根據一個單詞來構造 Trie 樹呢，假設我們以單詞「and」為例來看下 Trie 樹的表現形式

注：圖中的數字表示數組的元素位置可以看到構建 Trie 樹的主要步驟如下

構建根節點，此時根節點存有一個元素大小為 26 的數組
遍歷字符串「and」
遍歷第一個字符 a 時，將上述數組的第一個元素賦值為一個 TriedNode 實例(假設其名為 A)
當遍歷第二個字符 n 時，將 A 結點 TriedNode 數組下標為 n-a = 13 (a 的 ascii 為 97，n 的 ascii 碼為 110) 的元素賦值為一個 TriedNode 實例(假設其名為 N)
同理，當遍歷第三個字符 d 時，將 N 結點 TriedNode 數組的第 4 個元素(下標為 3)賦值為一個 TriedNode 實例(假設其名為 D)，同時也將其結點的 frequency 加一，代表以此字符為終止字符的字符串多了一個。

由以上分析不難寫出根據字符串構建 Trie 樹的代碼，如下

/**
?*?Trie?樹
?*/static?class?TrieTree?{private?TriedNode?root?=?new?TriedNode('/');?//?根節點/**
?????*?以?String?為條件構建?Trie?樹
?????*?@param?s
?????*/public?void?insertString(String?s)?{
????????TriedNode?p?=?root;for?(int?i?=?0;?i?????????????char?c?=?s.charAt(i);int?index??=?c-'a';if?(p.children[index]?==?null)?{
????????????????p.children[index]?=?new?TriedNode(c);
????????????}
????????????p?=?p.children[index];//Process?char
????????}
????????p.frequency++;
????}
}

Trie 樹構造好了，再在 Trie 樹中查找某字符串是否存在就簡單很多了，遍歷字符串，查看每個字符在相應層級的數組位置的元素是否為空即可，如果是，說明不存在，如果不是，則繼續遍歷字符查找，直到遍歷完成，代碼如下

/**
?*?查找字符串是否在原字符串集合中
?*?@param?s
?*?@return?boolean
?*/public?boolean?findStr(String?s)?{
????TriedNode?p?=?root;for?(int?i?=?0;?i?????????//?當前被遍歷的字符char?c?=?s.charAt(i);int?index??=?c-'a';if?(p.children[index]?==?null)?{//?如果字符對應位置的數組元素為空，說明肯定不存在此字符，終止之后的字符遍歷return?false;
????????}//?如果存在，則繼續往后遍歷字符串
????????p?=?p.children[index];
????}return?true;
}

由于在節點中也用 frequency 保存了單詞數，所以如果在 Trie 樹中最終發現字符串存在，也可以隨便查找出此字符串的個數。

如何實現搜索字符串自動提示功能

有了 Trie 樹，相信大家不難解決開篇的這個問題，首先搜索引擎根據用戶的搜索詞構建一顆 Trie 樹，假設這個搜索詞庫是 a, to, tea, ted, ten, i, in, inn，則構建的 Trie 樹為：

那么當用戶在搜索框輸入「te」的時候，根據 Trie 樹的特性得知以 ?te 為前綴的字符串有 tea，ted，ten，則應該在搜索框提示詞中展示這三個字符串。這里有一個小問題，一般搜索框只會展示 10 個搜索詞，但以用戶輸入字符串為前綴的字符串可能遠超 10 次，到底該展示哪 10 個呢，最簡單的規則是展示搜索次數最多的 10 個字符串，于是問題就轉化為了 TopK 問題，維護一個有 10 個元素的小頂堆，步驟如下

先根據用戶輸入的前綴在樹中找出含有此前綴的所有字符串
我們知道在節點中保存了字符串的被搜索次數，所以利用小頂堆即可算出被搜索次數最多的 10 個字符串，即可得最終展示給用戶的提示詞。

注意：這里的求 TopK 要用是小頂堆，不是大頂堆哦，在之前一篇文章中有讀者提出了疑問，不要搞混了，小頂堆是求最大的 Top K 值，大頂堆是求最小的 TopK 值，由于我們要求最多的前 10 個搜索詞，所以應該是用小頂堆)。

這樣就解決了，考慮以下現象：我們在輸入搜索詞的時候，搜索引擎給出的提示詞可能并不是以用戶輸入的字符串為前綴的。

如圖示：搜索引擎給出的搜索關鍵字并不包含有「brekfa」前綴。

這種又是怎么實現的呢，它實際上用到了字符串編輯距離的思想，所謂字符串編輯距離是說一個字符串可以通過增刪改查字符來變成另外一個字符串。

如圖示: brekfa 添加 a 之后變成了 ?breakfa顯然所作的增刪改查次數越少，效率越高，經過最少的字符中編輯變成另一個合法的字符串后，就以此字符串為前綴去 Trie 樹中查找提示詞。當然了，像 Google 這樣的搜索引擎要實時顯示這些結果，背后肯定經過了很多改造。不過原理都大同小異。

再談 Trie 樹

從前面的介紹中我們可以看到使用 Trie 樹確實在能在快速查找字符串與詞頻統計上發揮重要作用，但天下沒有免費的午餐，如果字符集比較大的話，用 Trie 樹可能會造成空間的浪費，以上文中構建的 Trie 樹為例

每個結點維護一個 26 個元素大小的數組，共有 4 個數組，也就是分配了 26 x 4 = 104 ?個元素的空間，但實際上只有三個元素空間(a，n，d)被分配了，浪費了 101 個空間，空間利率率很低，所以一般更適用于字符串前綴重復比較多的情況，當然也可以考慮對 Trie 樹進行如下縮點優化，能節省一些空間