作者：小傅哥
部落格：https://bugstack.cn
沉澱、分享、成長，讓自己和他人都能有所收獲！
一、前言
Trie 的曆史
字典樹 Trie 這個詞來自于 retrieval，于 1912 年，Axel Thue 首次抽象地描述了一組字元串資料結構的存放方式為 Trie 的想法。這個想法于 1960 年由 Edward Fredkin 獨立描述，并創造了 Trie 一詞。你看看，多少程式員為了一個詞、方法名、屬性名，想破腦袋！
二、字典樹資料結構
在計算機科學中，字典樹(Trie)也被稱為”單詞查找樹“或”數字樹“，有時候也被稱為基數樹或字首樹（因為可以通過字首的方式進行索引）。—— 它是一種搜尋樹，一種已排序的資料結構，通常用于存儲動态集或鍵為字元串的關聯數組。
與二叉查找樹不同，鍵不是直接儲存在節點中，而是由節點在樹中的位置決定。一個節點的所有子孫都有相同的字首，也就是這個節點對應的字元串，而根節點對應空字元串。一般情況下，不是所有的節點都有對應的值，隻有葉子節點和部分内部節點所對應的鍵才有相關的值。
- 這是一個把 battle 單詞字元串，按照字母拆分到字典樹進行存放的圖。
- 鍵标注在節點中，值标注在節點之下。每一個完整的英文單詞對應一個特定的整數。也就是26個字母對應的 ASCII 轉換後的值。
三、字典樹結構實作
字典樹字母的存放有26個，也就是說在實作的過程中，每一個節點的分支都有26個槽位用來存放可能出現的字母組合。同理如果是數字樹的話就是10個數字的組合，每個字典樹上的節點對應的分支則有10個操作存放可能出現組合的數字。
接下來我們就基于 Java 語言實作一個字典樹的存放和周遊索引的功能。
- 源碼位址：https://github.com/fuzhengwei/java-algorithms
- 本章源碼：https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/trie
1. 樹枝節點
public class TrieNode {
/** 形成一個鍊 */
public TrieNode[] slot = new TrieNode[26];
/** 字母 */
public char c;
/** 單詞：數量 > 0 表示一個單詞 */
public boolean isWord;
/** 字首 */
public int prefix;
/** 單詞：具體的一個單詞字元串 */
public String word;
/** 解釋：單詞的注釋說明 */
public String explain;
}
- 字典的樹的節點需要包括此節點内嵌的關聯節點，之後是節點的字母、到此字母是否為單詞、單詞的字首、單詞字元串和目前單詞的非必要注釋。
2. 插入元素
public void insert(String words, String explain) {
TrieNode root = wordsTree;
char[] chars = words.toCharArray();
for (char c : chars) {
int idx = c - 'a'; // - a 從 0 開始，參考 ASCII 碼表
if (root.slot[idx] == null) {
root.slot[idx] = new TrieNode();
}
root = root.slot[idx];
root.c = c;
root.prefix++;
}
root.explain = explain; // 單詞的注釋說明資訊
root.isWord = true; // 循環拆解單詞後标記
}
- insert 方法接收單詞和注釋資訊，并對一個單詞按照 char 進行拆分，拆分後則計算出索引位置并以此存放。存放完成後标記單詞和附屬上單詞的注釋資訊。
3. 索引元素
public List<String> searchPrefix(String prefix) {
TrieNode root = wordsTree;
char[] chars = prefix.toCharArray();
StringBuilder cache = new StringBuilder();
// 精準比對：根據前置精準查找
for (char c : chars) {
int idx = c - 'a';
// 比對為空
if (idx > root.slot.length || idx < 0 || root.slot[idx] == null) {
return Collections.emptyList();
}
cache.append(c);
root = root.slot[idx];
}
// 模糊比對：根據字首的最後一個單詞，遞歸周遊所有的單詞
ArrayList<String> list = new ArrayList<>();
if (root.prefix != 0) {
for (int i = 0; i < root.slot.length; i++) {
if (root.slot[i] != null) {
char c = (char) (i + 'a');
collect(root.slot[i], String.valueOf(cache) + c, list, 15);
if (list.size() >= 15) {
return list;
}
}
}
}
return list;
}
protected void collect(TrieNode trieNode, String pre, List<String> queue, int resultLimit) {
// 找到單詞
if (trieNode.isWord) {
trieNode.word = pre;
// 儲存檢索到的單詞到 queue
queue.add(trieNode.word + " -> " + trieNode.explain);
if (queue.size() >= resultLimit) {
return;
}
}
// 遞歸調用，查找單詞
for (int i = 0; i < trieNode.slot.length; i++) {
char c = (char) ('a' + i);
if (trieNode.slot[i] != null) {
collect(trieNode.slot[i], pre + c, queue, resultLimit);
}
}
}
- 從字典樹從檢索元素的過程分為2部分，第1部分是根據提供的索引字首精準比對到單詞資訊，第2部分是根據索引字首的最後一個單詞開始，循環遞歸周遊從目前位置所能關聯到的字母直至判斷為是單詞标記為結束，通過這樣的方式把所有比對動的單詞索引出來。
- list.size() >= 15 是判定索引的最大長度，超過這個數量就停止索引了，畢竟這是一種O(n)時間複雜度的操作，如果加載數十萬單詞進行比對，執行速度還是比較耗時的。
四、字典樹功能測試
@Test
public void test_trie() {
Trie trie = new Trie();
// 存入
trie.insert("bat","大廠");
trie.insert("batch", "批量");
trie.insert("bitch", "彪子");
trie.insert("battle", "戰鬥");
logger.info(trie.toString());
// 檢索
List<String> trieNodes = trie.searchPrefix("ba");
logger.info("測試結果：{}", JSON.toJSONString(trieNodes));
}
- 這裡提供一些有相近字母的單詞和名詞，用于測試。你也可以嘗試讀取txt檔案，檢索存入數十萬單詞進行檢索驗證。
測試結果
06:21:38.226 [main] INFO trie.__test__.TrieTest - 測試結果：["bat -> 大廠","batch -> 批量","battle -> 戰鬥"]
Process finished with exit code 0
- 通過測試結果可以看到，把所有以 ba 開頭的單詞全部檢索出來了。這也是字典樹最核心功能的展現。
- 讀者在學習的過程中，可以嘗試在檢索的方法體内打一些斷點看一下具體的執行過程，友善學習整個執行步驟。
五、常見面試題
- 簡述字典樹的資料結構
- 叙述你怎麼來實作一個字典樹
- 字典樹的實際業務場景舉例【排序、全文搜尋、網絡搜尋引擎、生物資訊】
- 字典樹的存入和檢索的時間複雜度
- 還有哪些字典樹的實作方式【字尾樹、哈希樹、帽子樹】