故事凌
今天刷算法題, 前綴樹, 字典樹, 真的是一個好東西啊, 在思想上又給自己打開了一個新的思路啊!
前綴樹被廣泛的運用在字典查找中, 也被稱為字典樹
舉例: 給定一系列字符串, 這些字符串構成了一種字典, 要求你在這個字典當中找出所有以"ABC"開頭的字符串
解法一: 暴利搜索
直接遍歷一遍字典, 然後逐個判斷每個字符串是否由"ABC"開頭, 假設字典很大, 有N個單詞, 要對比的不是"ABC", 而是任意的, 那不妨假設所要對比的開頭平均長度為M, 那麼時間複雜度是O(M x N)
解法二: 前綴樹
如果用前綴樹頭幫助對字典的存儲進行優化, 那麼可以把搜索的時間複雜度下降為O(M), 其中M表示字典裡最長的那個單詞的字符個數, 很多情況下, 字典裡的單詞個數N是遠遠大於M的, 因此, 前綴樹在各種場合中是非常高效的.
經典應用
- 網站的搜索框會羅列出以搜索文字作為開頭的相關搜索信息, 這裡運用了前綴樹進行後端的快速檢索
- 漢字拼音輸入法的聯想輸出功能也是運用了前綴樹
Trie (發音為 "try") 或前綴樹是一種樹數據結構，用於檢索字符串數據集中的鍵。這一高效的數據結構有多種應用：
1. 自動補全
2. 拼寫檢查
3. IP路由(最長前綴匹配)
4. T9(九宮格) 打字預測
5. 單詞遊戲
還有其他的數據結構，如平衡樹和哈希表，使我們能夠在字符串數據集中搜索單詞。為什麼我們還需要 Trie 樹呢？儘管哈希表可以在 O(1)O(1) 時間內尋找鍵值，卻無法高效的完成以下操作：
- 找到具有同一前綴的全部鍵值。
- 按詞典序枚舉字符串的數據集。
Trie 樹優於哈希表的另一個理由是，隨著哈希表大小增加，會出現大量的衝突，時間複雜度可能增加到 O(n)O(n)，其中 nn 是插入的鍵的數量。與哈希表相比，Trie 樹在存儲多個具有相同前綴的鍵時可以使用較少的空間。此時 Trie 樹只需要 O(m)O(m) 的時間複雜度，其中 mm 為鍵長。而在平衡樹中查找鍵值需要 O(m \\log n)O(mlogn) 時間複雜度。
Trie 樹的結點結構
Trie 樹是一個有根的樹，其結點具有以下字段：。
- 最多 RR 個指向子結點的鏈接，其中每個鏈接對應字母表數據集中的一個字母。本文中假定 RR 為 26，小寫拉丁字母的數量。
- 布爾字段，以指定節點是對應鍵的結尾還是隻是鍵前綴。
前綴樹的java代碼:
<code>class TrieNode {
// R links to node children
// 連接到 R 條子節點
private TrieNode[] links;
// 最初只有26個字符, 最多有26條子節點
private final int R = 26;
// 判斷是否是一個單詞是否結束
private boolean isEnd;
// 構造器, 初始化的時候, 都要創建26子節點
public TrieNode() {
links = new TrieNode[R];
}
// 判斷子節點是否存在, ch - 'a' 是0-25
public boolean containsKey(char ch) {
return links[ch -'a'] != null;
}
// 獲取到子節點
public TrieNode get(char ch) {
return links[ch -'a'];
}
// 往子節點中放元素
public void put(char ch, TrieNode node) {
links[ch -'a'] = node;
}
// 設置為單詞的結束符
public void setEnd() {
isEnd = true;
}
// 獲取單詞的結束符
public boolean isEnd() {
return isEnd;
}
}/<code>舉例: 假如有一個字典, 字典裡面有下面詞: "A", "to", "tea", "ted", "ten", "i", "in", "inn", 每個單詞還能有自己的一些權重值, 那麼用前綴樹來構建這個字典將會是如下的樣子:
性質
- 每個節點至少包含兩個基本屬性
- Childern: 數組或者集合, 羅列出每個分支當中包含的所有字符
- idEnd, 布爾值, 表示是該節點是否為某字符串的結尾
- 前綴樹的根節點是空的
所謂空, 即只利用這個節點的children屬性, 即只關心在這個字典裡, 有哪些打頭的字符
- 除了根節點, 其他所有節點都有可能是單詞的結尾, 葉子節點一定都是單詞的結尾
實現
前綴叔最基本的操作就是兩個: 創建和搜索
1. 創建
- 遍歷一遍輸入的字符串, 對每個字符串的字符進行遍歷
- 從前綴的根節點開始, 將每個字符加入到節點的children字符集當中.
- 如果字符集已經包含了這個字符, 則跳過
- 如果當前字符是字符串的最後一個, 則把當前節點的isEnd標記為真.
由上, 創建的方法很直觀
前綴樹真正強大的地方在於, 每個每個節點還能用來保存額外的信息, 比如可以用來記錄擁有相同前綴的所有字符串, 因此, 當用戶輸入某個前綴時, 就能在O(1)的時間內給出對應的推薦字符串
我們通過搜索 Trie 樹來插入一個鍵。我們從根開始搜索它對應於第一個鍵字符的鏈接。有兩種情況：
鏈接存在。沿著鏈接移動到樹的下一個子層。算法繼續搜索下一個鍵字符。鏈接不存在。創建一個新的節點，並將它與父節點的鏈接相連，該鏈接與當前的鍵字符相匹配。重複以上步驟，直到到達鍵的最後一個字符，然後將當前節點標記為結束節點，算法完成。
向前綴樹中插入元素:
<code>class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
TrieNode node = root;
for (int i = 0; i // 獲取到每個字符
char currentChar = word.charAt(i);
// 判斷是否存在, 不存在, 直接放入子節點
if (!node.containsKey(currentChar)) {
node.put(currentChar, new TrieNode());
}
// 子節點變成父節點, 進行下一次的循環
node = node.get(currentChar);
}
// 設置最後的字符為單詞的結束符
node.setEnd();
}
}/<code>2. 搜索
與創建方法類似, 從前綴的根節點出發, 逐個匹配輸入的前綴字符, 如果遇到了就繼續往下一層搜索, 如果沒遇到, 就立即返回.
在 Trie 樹中查找鍵每個鍵在 trie 中表示為從根到內部節點或葉的路徑。我們用第一個鍵字符從根開始，。檢查當前節點中與鍵字符對應的鏈接。有兩種情況：
存在鏈接。我們移動到該鏈接後面路徑中的下一個節點，並繼續搜索下一個鍵字符。不存在鏈接。若已無鍵字符，且當前結點標記為 isEnd，則返回 true。否則有兩種可能，均返回 false :還有鍵字符剩餘，但無法跟隨 Trie 樹的鍵路徑，找不到鍵。沒有鍵字符剩餘，但當前結點沒有標記為 isEnd。也就是說，待查找鍵只是Trie樹中另一個鍵的前綴。
在樹中查找元素
<code>class Trie {
...
// search a prefix or whole key in trie and
// returns the node where search ends
// 搜索前綴
private TrieNode searchPrefix(String word) {
TrieNode node = root;
for (int i = 0; i // 獲取到單詞的每一個字符
char curLetter = word.charAt(i);
// 如果子節點包含, 就把子節點當成新的父節點, 進入下一次循環
if (node.containsKey(curLetter)) {
node = node.get(curLetter);
} else {
// 否則, 就返回空
return null;
}
}
// 返回最終的子節點
return node;
}
// Returns if the word is in the trie.
// 判斷單詞是否存在於前綴樹中
public boolean search(String word) {
TrieNode node = searchPrefix(word);
// 最後的節點不能為空, 而且該節點上必須有單詞的結束符
return node != null && node.isEnd();
}
}/<code>查找 Trie 樹中的鍵前綴該方法與在 Trie 樹中搜索鍵時使用的方法非常相似。我們從根遍歷 Trie 樹，直到鍵前綴中沒有字符，或者無法用當前的鍵字符繼續 Trie 中的路徑。與上面提到的“搜索鍵”算法唯一的區別是，到達鍵前綴的末尾時，總是返回 true。我們不需要考慮當前 Trie 節點是否用 “isend” 標記，因為我們搜索的是鍵的前綴，而不是整個鍵。
<code>class Trie {
...
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
TrieNode node = searchPrefix(prefix);
return node != null;
}
}/<code>例題分析
- 單詞搜索 II](https://leetcode-cn.com/problems/word-search-ii/)
給定一個二維網格 board 和一個字典中的單詞列表 words，找出所有同時在二維網格和字典中出現的單詞。
單詞必須按照字母順序，通過相鄰的單元格內的字母構成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內的字母在一個單詞中不允許被重複使用。
示例:
<code>輸入:
words = ["oath","pea","eat","rain"] and board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
輸出: ["eat","oath"]/<code>
說明:你可以假設所有輸入都由小寫字母 a-z 組成。
提示:
你需要優化回溯算法以通過更大數據量的測試。你能否早點停止回溯？如果當前單詞不存在於所有單詞的前綴中，則可以立即停止回溯。什麼樣的數據結構可以有效地執行這樣的操作？散列表是否可行？為什麼？前綴樹如何？如果你想學習如何實現一個基本的前綴樹，請先查看這個問題：實現Trie（前綴樹）。
<code>import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
public class findWords_212 {
public List<string> findWords(char[][] board, String[] words) {
//構建字典樹
wordTrie myTrie=new wordTrie();
trieNode root=myTrie.root;
for(String s:words)
myTrie.insert(s);
//使用set防止重複
Set<string> result =new HashSet<>();
int m=board.length;
int n=board[0].length;
boolean[][] visited=new boolean[m][n];
//遍歷整個二維數組
for(int i=0;i<board.length> for (int j = 0; j find(board,visited,i,j,m,n,result,root);
}
}
System.out.print(result);
return new LinkedList<string>(result);
}
private void find(char [] [] board, boolean [][]visited,int i,int j,int m,int n,Set<string> result,trieNode cur){
//邊界以及是否已經訪問判斷
if(i<0||i>=m||j<0||j>=n||visited[i][j])
return;
cur=cur.child[board[i][j]-'a'];
visited[i][j]=true;
if(cur==null)
{
//如果單詞不匹配，回退
visited[i][j]=false;
return;
}
//找到單詞加入
if(cur.isLeaf)
{
result.add(cur.val);
//找到單詞後不能回退，因為可能是“ad” “addd”這樣的單詞得繼續回溯
// visited[i][j]=false;
// return;
}
//上下左右去遍歷, 通過遞歸的方法去實現
find(board,visited,i+1,j,m,n,result,cur);
find(board,visited,i,j+1,m,n,result,cur);
find(board,visited,i,j-1,m,n,result,cur);
find(board,visited,i-1,j,m,n,result,cur);
//最後要回退，因為下一個起點可能會用到上一個起點的字符
visited[i][j]=false;
}
}
//字典樹
class wordTrie{
public trieNode root=new trieNode();
public void insert(String s){
trieNode cur=root;
for(char c:s.toCharArray()){
if(cur.child[c-'a']==null){
cur.child [c-'a'] = new trieNode();
cur=cur.child[c-'a'];
}else
cur=cur.child [c-'a'];
}
cur.isLeaf=true;
cur.val=s;
}
}
//字典樹結點
class trieNode{
public String val;
public trieNode[] child=new trieNode[26];
public boolean isLeaf=false;
trieNode(){
}
}/<string>/<string>/<board.length>/<string>/<string>/<code>
閱讀更多 故事凌 的文章
