在計算機科學中，字典樹(Trie)也被稱為”單詞查找樹“或”數(shù)字樹“，有時候也被稱為基數(shù)樹或前綴樹（因為可以通過前綴的方式進行索引）?！?它是一種搜索樹，一種已排序的數(shù)據結構，通常用于存儲動態(tài)集或鍵為字符串的關聯(lián)數(shù)組。
一、前言
Trie 的歷史
字典樹 Trie 這個詞來自于 retrieval，于 1912 年，Axel Thue 首次抽象地描述了一組字符串數(shù)據結構的存放方式為 Trie 的想法。這個想法于 1960 年由 Edward Fredkin 獨立描述，并創(chuàng)造了 Trie 一詞。你看看，多少程序員為了一個詞、方法名、屬性名，想破腦袋！
二、字典樹數(shù)據結構
在計算機科學中，字典樹(Trie)也被稱為”單詞查找樹“或”數(shù)字樹“，有時候也被稱為基數(shù)樹或前綴樹（因為可以通過前綴的方式進行索引）?！?它是一種搜索樹，一種已排序的數(shù)據結構，通常用于存儲動態(tài)集或鍵為字符串的關聯(lián)數(shù)組。
與二叉查找樹不同，鍵不是直接保存在節(jié)點中，而是由節(jié)點在樹中的位置決定。一個節(jié)點的所有子孫都有相同的前綴，也就是這個節(jié)點對應的字符串，而根節(jié)點對應空字符串。一般情況下，不是所有的節(jié)點都有對應的值，只有葉子節(jié)點和部分內部節(jié)點所對應的鍵才有相關的值。
- 這是一個把 battle 單詞字符串，按照字母拆分到字典樹進行存放的圖。
- 鍵標注在節(jié)點中，值標注在節(jié)點之下。每一個完整的英文單詞對應一個特定的整數(shù)。也就是26個字母對應的 ASCII 轉換后的值。
三、字典樹結構實現(xiàn)
字典樹字母的存放有26個，也就是說在實現(xiàn)的過程中，每一個節(jié)點的分支都有26個槽位用來存放可能出現(xiàn)的字母組合。同理如果是數(shù)字樹的話就是10個數(shù)字的組合，每個字典樹上的節(jié)點對應的分支則有10個操作存放可能出現(xiàn)組合的數(shù)字。
接下來我們就基于 Java 語言實現(xiàn)一個字典樹的存放和遍歷索引的功能。
- 源碼地址：https://github.com/fuzhengwei/java-algorithms
- 本章源碼：https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/trie
1. 樹枝節(jié)點
public class TrieNode {
/** 形成一個鏈 */
public TrieNode[] slot = new TrieNode[26];
/** 字母 */
public char c;
/** 單詞：數(shù)量 > 0 表示一個單詞 */
public boolean isWord;
/** 前綴 */
public int prefix;
/** 單詞：具體的一個單詞字符串 */
public String word;
/** 解釋：單詞的注釋說明 */
public String explain;
}- 字典的樹的節(jié)點需要包括此節(jié)點內嵌的關聯(lián)節(jié)點，之后是節(jié)點的字母、到此字母是否為單詞、單詞的前綴、單詞字符串和當前單詞的非必要注釋。
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; // 循環(huán)拆解單詞后標記
}- 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部分是根據索引前綴的最后一個單詞開始，循環(huán)遞歸遍歷從當前位置所能關聯(lián)到的字母直至判斷為是單詞標記為結束，通過這樣的方式把所有匹配動的單詞索引出來。
- list.size() >= 15 是判定索引的最大長度，超過這個數(shù)量就停止索引了，畢竟這是一種O(n)時間復雜度的操作，如果加載數(shù)十萬單詞進行匹配，執(zhí)行速度還是比較耗時的。
四、字典樹功能測試
@Test
public void test_trie() {
Trie trie = new Trie();
// 存入
trie.insert("bat","大廠");
trie.insert("batch", "批量");
trie.insert("bitch", "彪子");
trie.insert("battle", "戰(zhàn)斗");
logger.info(trie.toString());
// 檢索
List<String> trieNodes = trie.searchPrefix("ba");
logger.info("測試結果：{}", JSON.toJSONString(trieNodes));
}
- 這里提供一些有相近字母的單詞和名詞，用于測試。你也可以嘗試讀取txt文件，檢索存入數(shù)十萬單詞進行檢索驗證。
測試結果
06:21:38.226 [main] INFO trie.__test__.TrieTest - 測試結果：["bat -> 大廠","batch -> 批量","battle -> 戰(zhàn)斗"]
Process finished with exit code
- 通過測試結果可以看到，把所有以 ba開頭的單詞全部檢索出來了。這也是字典樹最核心功能的體現(xiàn)。
- 讀者在學習的過程中，可以嘗試在檢索的方法體內打一些斷點看一下具體的執(zhí)行過程，方便學習整個執(zhí)行步驟。
五、常見面試題
- 簡述字典樹的數(shù)據結構
- 敘述你怎么來實現(xiàn)一個字典樹
- 字典樹的實際業(yè)務場景舉例【排序、全文搜索、網絡搜索引擎、生物信息】
- 字典樹的存入和檢索的時間復雜度
- 還有哪些字典樹的實現(xiàn)方式【后綴樹、哈希樹、帽子樹】
