字元串處理【字典樹】 - 原理 字典樹詳解

字典樹，又稱Trie樹、單詞查找樹，是一種樹形結構，也是哈希樹的一種變種，主要用于統計、排序和存儲大量的字元串（但不限于字元串），是以經常被搜尋引擎系統用于文本詞頻統計。

它的優點：利用字元串的公共字首來減少查詢時間，最大限度地減少無謂的字元串比較，查詢效率比哈希樹高。

字典樹是用于字元串快速檢索的多叉樹，每個節點都包含多個字元指針，将從根節點到某一節點路徑上經過的字元連接配接起來，為該節點對應的字元串。

例如，bee是一個單詞，beer也是一個單詞，此時可以在每個單詞結束的位置都加一個end[]标記，表示從根到這裡有一個單詞。

字典樹的基本操作： 建立、查找、插入和删除，極少出現删除操作。

【1】字典樹的建立

字典樹的建立指将所有字元串都插入字典樹中。插入操作指将一個字元串插入字典樹中。

字典樹可以采用數組或連結清單存儲，這裡采用數組存儲來實作靜态連結清單。

[舉個栗子]

字元串是由小寫字母組成的，每個節點都包含26個域（26個字母）。

① 插入一個單詞s（bike），首先将字元轉換為數字，s[0]-‘a’=1，判斷trie[1][1]為0，令trie[1][1]=2，相當于建立一個新的節點（下标為2）。

② s[1]-‘a’=8，判斷trie[2][8]為0，令trie[2][8]=3。

③ s[2]-‘a’=10，判斷trie[3][10]為0，令trie[3][10]=4。

④ s[3]-‘a’=4，判斷trie[4][4]為0，令trie[4][4]=5，end[5]=true，标記單詞結束。

⑤ 接着插入一個單詞s（bin），首先将字元轉換為數字，s[0]-‘a’=1，判斷trie[1][1]=2，不為0，令p =2，沿第2個節點繼續插入。

⑥ s[1]-‘a’=8，判斷trie[2][8]=3，令p =3，沿第3個節點繼續插入。

⑦ s[2]-‘a’=13，判斷trie[3][13]為0，令trie[3][13]=6，end[6]=true。

⑧ 接着插入一個單詞s（yes），首先将字元轉換為數字，s[0]-‘a’=24，判斷trie[1][24]為0，令trie[1][24]=7。

⑨ 繼續插入s（yes）的後兩個字元，end[9]=true，标記單詞結束。

[算法代碼]

void insert(string s){ // 将字元串s 插入字典樹中
	
	int len = s.length() , p = 1;
	for(int i = 0 ; i < len ; i ++){
		
		int ch = s[i] - 'a';  //轉換為數字
		if(!trie[p][ch]){
			trie[p][ch] = ++ tot;  //記錄下标
		}
		p = trie[p][ch];
	}
	
	end[p] = true;  // 标記單詞結束
}
           

[算法分析]

若單詞的總長度為N ，字元的種類為k ，插入的字元串長度為n ，則建立Trie的複雜度為O (N )，空間複雜度為O (Nk )，插入字元串的時間複雜度均為O (n )。

【2】字典樹的查找

若在字典樹中查找該字元串是否存在，則和插入操作一樣，首先将字元轉換為數字，在字典樹中查找，若查找的位置為0，則說明不存在，否則繼續向下查找；在字元串處理完畢後，判斷此處是否有單詞結束标記，若有，則說明該字元串存在。

[ 舉個栗子]

在字典樹中查找單詞s（bin）。

① 将字元轉換為數字，s[0]-‘a’=1，判斷trie[1][1]，若為0，則查找失敗；trie[1][1]=2，不為0，則令p =2，在第2個節點繼續查找。

② s[1]-‘a’=8，判斷trie[2][8]，若為0，則查找失敗；trie[2][8]=3，不為0，則令p =3，在第3個節點繼續查找。

③ s[2]-‘a’=13，判斷trie[3][13]，若為0，則查找失敗；trie[3][13]=6，不為0，則令p =6，在第6個節點繼續查找。

此時字元串處理完畢，看6号節點是否有單詞結束标記，若end[6]為真，則傳回查找成功，否則傳回查找失敗。

[算法代碼]

bool search(string s){  //在字典樹中查找該字元串是否存在
	int len = s.length() , p = 1;
	
	for(int i = 0 ; i < len ; i ++){
		p = trie[p][s[i] - 'a'];
		if(!p){
			return false;
		}
	}
	return end[p];
}
           

[算法分析]

在字典樹中查找一個關鍵字的時間與樹中包含的節點數無關，隻與關鍵字的字元數有關。若查找的字元串長度為n ，則查找的時間複雜度均為O (n )。

【3】字典樹的應用

① 字元串檢索。事先将已知的一些字元串（字典）的有關資訊存儲到Trie樹裡，查找一些字元串是否出現過、出現的頻率和搜尋引擎的熱門查詢。

② 字首統計。統計一個串所有字首單詞的個數，隻需統計從根到葉子路徑上單詞出現的個數，也可以判斷一個單詞是否為另一個單詞的字首。

③ 最長公共字首。Trie樹利用多個字元串的公共字首來節省存儲空間，反之，當把大量字元串都存儲到一棵Trie樹上時，可以快速得到某些字元串的公共字首。對所有字元串都建立字典樹，兩個串的最長公共字首的長度就是它們所在節點最近公共祖先的長度，于是轉變為最近公共祖先問題。

④ 排序。利用字典樹進行串排序。例如，給定N 個互不相同的僅由一個單詞構成的英文名，将它們按字典序從小到大輸出。采用數組方式建立字典樹，這棵樹每個節點的所有子節點都按照其字母大小排序。對字典樹進行先序周遊，輸出的相應字元串便是按字典序排序的結果。

⑤ 作為其他資料結構與算法的輔助結構，例如字尾樹、AC自動機等。