前綴樹
字典樹也叫前綴樹、Trie。它本身就是一個樹型結(jié)構(gòu)，也就是一顆多叉樹，學過樹的朋友應(yīng)該非常容易理解，它的核心操作是插入，查找。刪除很少使用，因此這個講義不包含刪除操作。
截止目前（2020-02-04） 前綴樹（字典樹） 在 LeetCode 一共有 17 道題目。其中 2 道簡單，8 個中等，7 個困難。
簡介
我們想一下用百度搜索時候，打個“一語”，搜索欄中會給出“一語道破”，“一語成讖(四聲的 chen)”等推薦文本，這種叫模糊匹配，也就是給出一個模糊的 query，希望給出一個相關(guān)推薦列表，很明顯，hashmap 并不容易做到模糊匹配，而 Trie 可以實現(xiàn)基于前綴的模糊搜索。
注意這里的模糊搜索也僅僅是基于前綴的。比如還是上面的例子，搜索“道破”就不會匹配到“一語道破”，而只能匹配“道破 xx”
基本概念
假想一個場景：給你若干單詞 words 和一系列關(guān)鍵字 keywords，讓你判斷 keywords 是否在 words 中存在，或者判斷 keywords 中的單詞是否有 words 中的單詞的前綴。比如 pre 就是 pres 的前綴之一。
樸素的想法是遍歷 keywords，對于 keywords 中的每一項都遍歷 words 列表判斷二者是否相等，或者是否是其前綴。這種算法的時間復雜度是 O ( m ? n ) O(m * n) O(m?n)，其中 m 為 words 的平均長度，n 為 keywords 的平均長度。那么是否有可能對其進行優(yōu)化呢？答案就是本文要講的前綴樹。
我們可以將 words 存儲到一個樹上，這棵樹叫做前綴樹。 一個前綴樹大概是這個樣子：
如圖每一個節(jié)點存儲一個字符，然后外加一個控制信息表示是否是單詞結(jié)尾，實際使用過程可能會有細微差別，不過變化不大。
為了搞明白前綴樹是如何優(yōu)化暴力算法的。我們需要了解一下前綴樹的基本概念和操作。
節(jié)點：
- 根結(jié)點無實際意義
- 每一個節(jié)點數(shù)據(jù)域存儲一個字符
- 每個節(jié)點中的控制域可以自定義，如 isWord(是否是單詞)，count(該前綴出現(xiàn)的次數(shù))等，需實際問題實際分析需要什么。
一個可能的前綴樹節(jié)點結(jié)構(gòu)：
private class TrieNode {
int count; //表示以該處節(jié)點構(gòu)成的串的個數(shù)
int preCount; //表示以該處節(jié)點構(gòu)成的前綴的字串的個數(shù)
TrieNode[] children;
TrieNode() {
children = new TrieNode[26];
count = 0;
preCount = 0;
}
}
可以看出 TriNode 是一個遞歸的數(shù)據(jù)結(jié)構(gòu)，其結(jié)構(gòu)類似多叉樹，只是多了幾個屬性記錄額外信息罷了。 比如 count 可以用來判斷以當前節(jié)點結(jié)束的單詞個數(shù)， preCount 可以用來判斷以當前節(jié)點結(jié)束的前綴個數(shù)。舉個例子：比如前綴樹中存了兩個單詞 lu 和 lucifer，那么單詞 lu 有一個，lu 前綴有兩個。
前綴樹大概如下圖：
l(count = 0, preCount=2)
u(count = 1, preCount=2)
c(count = 0, preCount=1)
i(count = 0, preCount=1)
f(count = 0, preCount=1)
e(count = 0, preCount=1)
f(count = 1, preCount=1)
Trie 的插入
構(gòu)建 Trie 的核心就是插入。而插入指的就是將單詞（words）全部依次插入到前綴樹中。假定給出幾個單詞 words [she,he,her,good,god]構(gòu)造出一個 Trie 如下圖：
也就是說從根結(jié)點出發(fā)到某一粉色節(jié)點所經(jīng)過的字符組成的單詞，在單詞列表中出現(xiàn)過，當然我們也可以給樹的每個節(jié)點加個 count 屬性，代表根結(jié)點到該節(jié)點所構(gòu)成的字符串前綴出現(xiàn)的次數(shù)。
可以看出樹的構(gòu)造非常簡單：插入新單詞的時候就從根結(jié)點出發(fā)一個字符一個字符插入，有對應(yīng)的字符節(jié)點就更新對應(yīng)的屬性，沒有就創(chuàng)建一個！
Trie 的查詢
查詢更簡單了，給定一個 Trie 和一個單詞，和插入的過程類似，一個字符一個字符找
- 若中途有個字符沒有對應(yīng)節(jié)點 →Trie 不含該單詞
- 若字符串遍歷完了，都有對應(yīng)節(jié)點，但最后一個字符對應(yīng)的節(jié)點并不是粉色的，也就不是一個單詞 →Trie 不含該單詞
Trie 模版
了解了 Trie 的使用場景以及基本的 API， 那么最后就是用代碼來實現(xiàn)了。這里我提供了 Python 和 Java 兩種語言的代碼。
Java Code:
class Trie {
TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
if (node.children[word.charAt(i) - 'a'] == null)
node.children[word.charAt(i) - 'a'] = new TrieNode();
node = node.children[word.charAt(i) - 'a'];
node.preCount++;
}
node.count++;
}
public boolean search(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
if (node.children[word.charAt(i) - 'a'] == null)
return false;
node = node.children[word.charAt(i) - 'a'];
}
return node.count > 0;
}
public boolean startsWith(String prefix) {
TrieNode node = root;
for (int i = 0; i < prefix.length(); i++) {
if (node.children[prefix.charAt(i) - 'a'] == null)
return false;
node = node.children[prefix.charAt(i) - 'a'];
}
return node.preCount > 0;
}
private class TrieNode {
int count; //表示以該處節(jié)點構(gòu)成的串的個數(shù)
int preCount; //表示以該處節(jié)點構(gòu)成的前綴的字串的個數(shù)
TrieNode[] children;
TrieNode() {
children = new TrieNode[26];
count = 0;
preCount = 0;
}
}
}
Python Code:
class TrieNode:
def __init__(self):
self.count = 0 # 表示以該處節(jié)點構(gòu)成的串的個數(shù)
self.preCount = 0 # 表示以該處節(jié)點構(gòu)成的前綴的字串的個數(shù)
self.children = {}
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.preCount += 1
node.count += 1
def search(self, word):
node = self.root
for ch in word:
if ch not in node.children:
return False
node = node.children[ch]
return node.count > 0
def startsWith(self, prefix):
node = self.root
for ch in prefix:
if ch not in node.children:
return False
node = node.children[ch]
return node.preCount > 0
復雜度分析
- 插入和查詢的時間復雜度自然是 O ( l e n ( k e y ) ) O(len(key)) O(len(key))，key 是待插入(查找)的字串.
- 建樹的最壞空間復雜度是 O ( m n ) O(m^{n}) O(mn), m 是字符集中字符個數(shù)，n 是字符串長度。
回答開頭的問題
前面我們拋出了一個問題：給你若干單詞 words 和一系列關(guān)鍵字 keywords，讓你判斷 keywords 是否在 words 中存在，或者判斷 keywords 中的單詞是否有 words 中的單詞的前綴。比如 pre 就是 pres 的前綴之一。
如果使用 Trie 來解，會怎么樣呢？首先我們需要建立 Trie，這部分的時間復雜度是 O ( t ) O(t) O(t)，其中 t 為 words 的總字符。預處理完畢之后就是查詢了。對于查詢，由于樹的高度是 O ( m ) O(m) O(m)，其中 m 為 words 的平均長度，因此查詢基本操作的次數(shù)不會大于 m m m。當然查詢的基本操作次數(shù)也不會大于 k k k，其中 k 為被查詢單詞 keyword 的長度，因此對于查詢來說，時間復雜度為 O ( m i n ( m , k ) ) O(min(m, k)) O(min(m,k))。時間上優(yōu)化的代價是空間上的消耗，對于空間來說則是預處理的消耗，空間復雜度為 O ( t ) O(t) O(t)。
前綴樹的特點
簡單來說， 前綴樹就是一個樹。前綴樹一般是將一系列的單詞記錄到樹上， 如果這些單詞沒有公共前綴，則和直接用數(shù)組存沒有任何區(qū)別。而如果有公共前綴， 則公共前綴僅會被存儲一次?？梢韵胂?，如果一系列單詞的公共前綴很多， 則會有效減少空間消耗。
而前綴樹的意義實際上是空間換時間，這和哈希表，動態(tài)規(guī)劃等的初衷是一樣的。
其原理也很簡單，正如我前面所言，其公共前綴僅會被存儲一次，因此如果我想在一堆單詞中找某個單詞或者某個前綴是否出現(xiàn)，我無需進行完整遍歷，而是遍歷前綴樹即可。本質(zhì)上，使用前綴樹和不使用前綴樹減少的時間就是公共前綴的數(shù)目。也就是說，一堆單詞沒有公共前綴，使用前綴樹沒有任何意義。
知道了前綴樹的特點，接下來我們自己實現(xiàn)一個前綴樹。關(guān)于實現(xiàn)可以參考 0208.implement-trie-prefix-tree
應(yīng)用場景及分析
正如上面所說，前綴樹的核心思想是用空間換時間，利用字符串的公共前綴來降低查詢的時間開銷。
比如給你一個字符串 query，問你這個字符串是否在字符串集合中出現(xiàn)過，這樣我們就可以將字符串集合建樹，建好之后來匹配 query 是否出現(xiàn)，那有的朋友肯定會問，之前講過的 hashmap 豈不是更好？
因此，這里我的理解是：上述精確查找只是模糊查找一個特例，模糊查找 hashmap 顯然做不到，并且如果在精確查找問題中，hashmap 出現(xiàn)過多沖突，效率還不一定比 Trie 高，有興趣的朋友可以做一下測試，看看哪個快。
再比如給你一個長句和一堆敏感詞，找出長句中所有敏感詞出現(xiàn)的所有位置（想下，有時候我們口吐芬芳，結(jié)果發(fā)送出去卻變成了****，懂了吧）
小提示：實際上 AC 自動機就利用了 trie 的性質(zhì)來實現(xiàn)敏感詞的匹配，性能非常好。以至于很多編輯器都是用的 AC 自動機的算法。
可以參考：https://blog.csdn.net/bestsort/article/details/82947639
ac自動機,就是在tire樹的基礎(chǔ)上,增加一個fail指針,如果當前點匹配失敗,則將指針轉(zhuǎn)移到fail指針指向的地方,這樣就不用回溯,而可以路匹配下去了.(當前模式串后綴和fail指針指向的模式串部分前綴相同,如abce和bcd,我們找到c發(fā)現(xiàn)下一個要找的不是e,就跳到bcd中的c處,看看此處的下一個字符(d)是不是應(yīng)該找的那一個)
還有些其他場景，這里不過多討論，有興趣的可以 google 一下。
總結(jié)
前綴樹的核心思想是用空間換時間，利用字符串的公共前綴來降低查詢的時間開銷。因此如果題目中公共前綴比較多，就可以考慮使用前綴樹來優(yōu)化。
前綴樹的基本操作就是插入和查詢，其中查詢可以完整查詢，也可以前綴查詢，其中基于前綴查詢才是前綴樹的靈魂，也是其名字的來源。
最后給大家提供了兩種語言的前綴樹模板，大家如果需要用，直接將其封裝成標準 API 調(diào)用即可。文章來源：http://www.zghlxwxcb.cn/news/detail-432451.html
基于前綴樹的題目變化通常不大， 使用模板就可以解決。如何知道該使用前綴樹優(yōu)化是一個難點，不過大家只要牢牢記一點即可，那就是算法的復雜度瓶頸在字符串查找，并且字符串有很多公共前綴，就可以用前綴樹優(yōu)化。文章來源地址http://www.zghlxwxcb.cn/news/detail-432451.html
到了這里，關(guān)于每天一道算法練習題--Day18 && 第一章 --算法專題 --- ----------前綴樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
