Java 數據結構與算法中的字典樹，你學會了嗎？
一、前言
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/stack
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開頭的單詞全部檢索出來了。這也是字典樹最核心功能的體現。
讀者在學習的過程中，可以嘗試在檢索的方法體內打一些斷點看一下具體的執行過程，方便學習整個執行步驟。
