原文連結
一、前言
我們幾乎每天都在用搜尋引擎搜尋資訊，相信大家肯定有注意過這樣一個細節:當輸入某個字元的時候，搜尋引框底下會出現多個推薦詞，如下，輸入「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 < s.length(); 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 < s.length(); 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 樹進行如下縮點優化，能節省一些空間
當然這麼優化後也增加了代碼的編碼難度，是以要視情況而定。
另外如果用 Trie 樹的話，一般需要我們自己編碼，對工程師的編碼能力要求較高，是以是否用 Trie 樹我們一般建議如下：
- 如果是字元串的精确比對查找，我們一般建議使用散清單或紅黑樹來解決，畢竟很多語言的類庫都有現成的，不需要自己實作，拿來即用
- 如果需要進行字首比對查找，則用 Trie 樹更合适一些
六、總結
本文通過搜尋引擎字元串提示簡要地概述了其實作原理，相信大家應該了解了，需要注意的是其使用場景，更推薦在需要字首比對查找的時候用 Trie 樹，否則像一般的精确比對查找等更推薦用散清單和紅黑樹這些很成熟的資料結構，畢竟這兩資料結構實作一般在類庫中都是實作了的，不需要自己實作，盡量不要重複造輪子。
作者 | 碼海
來源 | 碼海