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