目錄
哈夫曼樹
樹的帶權(quán)路徑長度(wpl)
哈夫曼編碼
代碼實現(xiàn)哈夫曼樹
封裝哈夫曼樹的節(jié)點(diǎn)
構(gòu)建哈夫曼樹
字典樹
執(zhí)行流程
代碼實現(xiàn)字典樹
封裝字典樹的節(jié)點(diǎn)
構(gòu)建字典樹
哈夫曼樹
??????? 哈夫曼樹（Huffman Tree）是一種帶權(quán)路徑長度最短的二叉樹。哈夫曼樹常常用于數(shù)據(jù)壓縮，其壓縮效率比較高。
哈夫曼樹的構(gòu)建過程主要有兩個步驟：（1）選取權(quán)值最小的兩個節(jié)點(diǎn)構(gòu)造新的二叉樹，其權(quán)值為兩個節(jié)點(diǎn)權(quán)值之和；（2）將新生成的節(jié)點(diǎn)加入到原來的節(jié)點(diǎn)集合中，重復(fù)執(zhí)行步驟一和步驟二，直到只剩下一個節(jié)點(diǎn)，這個節(jié)點(diǎn)就是哈夫曼樹的根節(jié)點(diǎn)。哈夫曼樹的構(gòu)建過程可以用貪心算法實現(xiàn)，構(gòu)建出的哈夫曼樹可以保證帶權(quán)路徑長度最短。
樹的帶權(quán)路徑長度(wpl)
????????樹的帶權(quán)路徑長度（weighted path length）是指樹中所有葉子節(jié)點(diǎn)深度乘以它們對應(yīng)的權(quán)值之和。對于一棵有n個葉子節(jié)點(diǎn)的樹，其帶權(quán)路徑長度為：
權(quán)路徑長度是一種衡量樹結(jié)構(gòu)緊密程度的指標(biāo)，一棵緊密結(jié)構(gòu)的樹的帶權(quán)路徑長度通常比較小，相對來說能夠更好地利用樹的結(jié)構(gòu)進(jìn)行數(shù)據(jù)壓縮等操作。在哈夫曼編碼中，帶權(quán)路徑長度是一個重要的概念，因為哈夫曼編碼的目的就是要最小化樹的帶權(quán)路徑長度，以達(dá)到最優(yōu)編碼的效果。
(a) wpl : 7 * 2 + 5 * 2 + 2 * 2 + 4 * 2 = 36
(b) wpl : 7 * 3 + 5 * 3 + 2 * 1 + 4 * 2 = 46
(c) wpl : 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3 = 35
哈夫曼編碼
????????哈夫曼編碼（Huffman coding）是一種可變長度編碼（variable-length encoding）方法，是一種最優(yōu)編碼，用于無損數(shù)據(jù)壓縮。該方法的核心思想是，將出現(xiàn)頻率較高的字符用較短的編碼表示，出現(xiàn)頻率較低的字符用較長的編碼表示，以達(dá)到壓縮數(shù)據(jù)的目的。
哈夫曼編碼的實現(xiàn)過程可以分為兩個階段：
（1）建立哈夫曼樹。將輸入字符串中每個字符出現(xiàn)的頻率作為權(quán)重，構(gòu)建一個哈夫曼樹，使得出現(xiàn)頻率較高的字符對應(yīng)的節(jié)點(diǎn)在哈夫曼樹的深度較淺，出現(xiàn)頻率較低的字符對應(yīng)的節(jié)點(diǎn)在哈夫曼樹的深度較深。哈夫曼樹的葉子節(jié)點(diǎn)對應(yīng)輸入字符串中的每個字符，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑上的邊表示該字符的編碼。
（2）對輸入字符串進(jìn)行編碼。根據(jù)哈夫曼樹的構(gòu)建結(jié)果，生成每個字符的編碼，并將輸入字符串中每個字符替換為其對應(yīng)的編碼，得到壓縮后的字符串。
由于哈夫曼編碼是一種最優(yōu)編碼方法，因此它具有以下優(yōu)點(diǎn)：
（1）壓縮率高。使用哈夫曼編碼進(jìn)行壓縮可以達(dá)到很高的壓縮率，特別是對于包含大量重復(fù)字符的文本文件，哈夫曼編碼的效果更加明顯。
（2）無損壓縮。哈夫曼編碼是一種無損壓縮方法，壓縮后的數(shù)據(jù)可以完全恢復(fù)為原始數(shù)據(jù)。
（3）可逆性好。哈夫曼編碼的編碼和解碼過程都可以通過哈夫曼樹實現(xiàn)，因此哈夫曼編碼具有很好的可逆性。
例如我們給定原文 A B A C C D A，使其變成二進(jìn)制存儲，我們就可以使用等長的編碼方式，A:00 B:01 C:10 D:11，那么我們的原文就可以轉(zhuǎn)換成00010010101100，len=14.所以我們想要縮短長度的話就需要用另一種編碼方式，那就是讓出現(xiàn)次數(shù)多的字母對應(yīng)更短的二進(jìn)制數(shù)，如A出現(xiàn)了三次，所以A:0 C出現(xiàn)了兩次，所以C:1，那么B:00，D:01，這樣原文就可以轉(zhuǎn)換成000011010，len=9，但這樣的缺點(diǎn)就是0000可以是AAAA，也可以是BB等多種情況。
所以我們就可以使用哈夫曼編碼，也就是最優(yōu)無前綴編碼。
通過這個哈夫曼樹得到A:0 B:10 C:110 D:111，原文也就轉(zhuǎn)換成了01001101101110，len= 14。
代碼實現(xiàn)哈夫曼樹
封裝哈夫曼樹的節(jié)點(diǎn)
class HuffmanNode implements Comparable<HuffmanNode> {
public int value; // 節(jié)點(diǎn)的值
public int frequency; // 節(jié)點(diǎn)出現(xiàn)的次數(shù)
public HuffmanNode left; // 左子節(jié)點(diǎn)
public HuffmanNode right; // 右子節(jié)點(diǎn)
public HuffmanNode(int value, int frequency) {
this.value = value;
this.frequency = frequency;
}
// 按照頻率從小到大排序
@Override
public int compareTo(HuffmanNode o) {
return this.frequency - o.frequency;
}
}構(gòu)建哈夫曼樹
import java.util.PriorityQueue;
public class HuffmanTree {
// 構(gòu)建哈夫曼樹
public static HuffmanNode buildHuffmanTree(int[] frequencies) {
PriorityQueue<HuffmanNode> queue = new PriorityQueue<>();
// 將所有出現(xiàn)的數(shù)字及其頻率作為葉子節(jié)點(diǎn)加入到優(yōu)先隊列中
for (int i = 0; i < frequencies.length; i++) {
if (frequencies[i] > 0) {
queue.offer(new HuffmanNode(i, frequencies[i]));
}
}
// 構(gòu)建哈夫曼樹
while (queue.size() > 1) {
HuffmanNode left = queue.poll();
HuffmanNode right = queue.poll();
HuffmanNode parent = new HuffmanNode(-1, left.frequency + right.frequency);
parent.left = left;
parent.right = right;
queue.offer(parent);
}
// 返回哈夫曼樹的根節(jié)點(diǎn)
return queue.poll();
}
public static void main(String[] args) {
int[] frequencies = new int[]{3, 2, 1, 4, 5, 6};
HuffmanNode root = buildHuffmanTree(frequencies);
// do something with the root node of the Huffman tree
}
}字典樹
????????字典樹（Trie樹），也稱為前綴樹（Prefix Tree），是一種用于高效存儲和檢索字符串的樹形數(shù)據(jù)結(jié)構(gòu)。它的基本思想是利用字符串的公共前綴，將具有相同前綴的字符串存儲在一起，從而達(dá)到節(jié)省空間、提高查詢效率的目的。
字典樹的每個節(jié)點(diǎn)都表示一個字符，從根節(jié)點(diǎn)開始到某個節(jié)點(diǎn)路徑上的所有字符連接起來，就構(gòu)成了從根節(jié)點(diǎn)到該節(jié)點(diǎn)所表示的字符串。每個節(jié)點(diǎn)還包含一個計數(shù)器，用于記錄以該節(jié)點(diǎn)結(jié)尾的字符串的個數(shù)。
在字典樹中，每個節(jié)點(diǎn)最多有26個子節(jié)點(diǎn)，對應(yīng)著26個小寫字母。為了實現(xiàn)高效的字符串檢索，字典樹通常是按照字典序排序的，即每個節(jié)點(diǎn)的子節(jié)點(diǎn)按照字母順序排列。
字典樹的主要優(yōu)點(diǎn)是可以在O(m)的時間復(fù)雜度內(nèi)（m為待查字符串的長度），完成字符串的檢索操作，比其他數(shù)據(jù)結(jié)構(gòu)如哈希表等具有更高的效率。同時，字典樹還可以支持前綴匹配查詢和自動補(bǔ)全功能，因此在搜索引擎、輸入法、單詞拼寫檢查等應(yīng)用中廣泛使用。
執(zhí)行流程
????????字典樹（Trie 樹）是一種特殊的樹型數(shù)據(jù)結(jié)構(gòu)，用于快速檢索和查找字符串集合中的單詞或前綴。它的執(zhí)行流程如下：
（1）初始化字典樹，創(chuàng)建一個根節(jié)點(diǎn)，根節(jié)點(diǎn)不包含任何值。
（2）將所有的字符串依次插入到字典樹中。對于每個字符串，從根節(jié)點(diǎn)開始，依次遍歷字符串中的每個字符。如果該字符對應(yīng)的節(jié)點(diǎn)已經(jīng)存在，則直接向下遍歷；否則，創(chuàng)建一個新節(jié)點(diǎn)，并將該節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)。重復(fù)該過程，直到遍歷完整個字符串。
（3）在字典樹中查找指定的單詞或前綴。從根節(jié)點(diǎn)開始，依次遍歷待查找的單詞或前綴中的每個字符，如果存在當(dāng)前字符對應(yīng)的節(jié)點(diǎn)，則向下遍歷；否則，直接返回空。
（4）如果是查找單詞，則需要判斷查找到的最后一個節(jié)點(diǎn)是否為一個單詞的結(jié)束節(jié)點(diǎn)。如果是，則說明該單詞存在于字典樹中；否則，不存在。
（5）如果是查找前綴，則不需要判斷最后一個節(jié)點(diǎn)是否為一個單詞的結(jié)束節(jié)點(diǎn)，只需要返回查找到的最后一個節(jié)點(diǎn)的子樹中所有單詞即可。
字典樹的優(yōu)點(diǎn)是可以快速的插入、查找和刪除字符串集合中的單詞，時間復(fù)雜度為 O(m)，其中 m 為單詞的長度。但是它的缺點(diǎn)是會消耗大量的存儲空間，因為每個節(jié)點(diǎn)都需要存儲一個字符和若干個指針，如果字符串集合中的單詞數(shù)量較多，則會占用大量的存儲空間。
例如下圖中已經(jīng)出現(xiàn)過一遍的字母就會被存到字典樹中，在下次遇到時就不會從新創(chuàng)建，加快了存儲時間，但會占用較大的空間。
代碼實現(xiàn)字典樹
封裝字典樹的節(jié)點(diǎn)
public class TrieNode {
char value;//當(dāng)前節(jié)點(diǎn)存儲的字符
int num;//有多少個單詞經(jīng)過了當(dāng)前這個字符，從當(dāng)前到根就是這num個單詞的前綴
TrieNode[] son;//所有葉子存放在一個對象數(shù)組里，默認(rèn)為26叉，因為只有26個英文字母
boolean isword;//是否構(gòu)成一個完整的單詞，如acm acmer
public TrieNode() {
num = 1;//至少有一個字符是經(jīng)過本身的
isword = false;//默認(rèn)為false
son = new TrieNode[26];//26個英文單詞
}
}構(gòu)建字典樹
public class TrieTree {
public static void main(String[] args) {
TrieTree trieNode = new TrieTree();
String[] strs = {"banana","band","bee","absolute","acm","acmer"};
String[] prefix = {"ba","b","band","abc","acm"};
for (String str : strs) trieNode.insertTrieTree(str);
System.out.println(trieNode.isContains("abc"));
System.out.println(trieNode.isContains("acm"));
for (String str : prefix) System.out.printf("%s前綴%d\n",str,trieNode.getPreFixNum(str));
}
TrieNode root = new TrieNode();//字典樹的根
//建樹的過程就是不斷的往字典樹里插入單詞
public void insertTrieTree(String s) {
if (s == null || s.length() == 0) return;//空串直接返回
TrieNode node = root;//獲取根節(jié)點(diǎn)，因為在插入的時候根節(jié)點(diǎn)是變化的
char[] words = s.toCharArray();//得到字符數(shù)組給words
for (int i = 0; i < words.length; i++) {
int distance = words[i] - 'a';//計算當(dāng)前字符是當(dāng)前根的第多少個孩子，所以要-'a'
if (node.son[distance] == null) {//當(dāng)當(dāng)前字符不存在時候
node.son[distance] = new TrieNode();
node.son[distance].value = words[i];
} else {
node.son[distance].num++;//經(jīng)過當(dāng)前字符的次數(shù)++
}
node = node.son[distance];//已經(jīng)存儲了，那么根就要做變化
}
node.isword = true;//當(dāng)最后一個字符存儲完畢后，這個字符就變成了一個完整的字符了
}
//給定單詞，查找是否在字典樹中
public boolean isContains(String s) {
if (s == null ||s.length() == 0) return false;//空串直接返回false
TrieNode node = root;//獲取根節(jié)點(diǎn)，因為在插入的時候根節(jié)點(diǎn)是變化的
char[] words = s.toCharArray();//得到字符數(shù)組給words
for (int i = 0; i < words.length; i++) {
int distance = words[i] - 'a';//計算當(dāng)前字符是當(dāng)前根的第多少個孩子，所以要-'a'
if (node.son[distance] != null) node = node.son[distance];//繼續(xù)往下再找
else return false;
}
return node.isword;//返回是否構(gòu)成完整的單詞
}
//給定前綴返回有多少個單詞以它作為前綴
public int getPreFixNum(String prefix) {
if (prefix == null ||prefix.length() == 0) return 0;//空串直接返回false
TrieNode node = root;//獲取根節(jié)點(diǎn)，因為在插入的時候根節(jié)點(diǎn)是變化的
char[] words = prefix.toCharArray();//得到字符數(shù)組給words
for (int i = 0; i < words.length; i++) {
int distance = words[i] - 'a';//計算當(dāng)前字符是當(dāng)前根的第多少個孩子，所以要-'a'
if (node.son[distance] != null) node = node.son[distance];//繼續(xù)往下再找
else return 0;
}
return node.num;//返回多少個單詞經(jīng)過當(dāng)前這個字符的個數(shù)
}
}得到abc不在字典樹中，acm在字典樹中。以及以ba、b、band、abc、acm做前綴的單詞個數(shù)
文章來源：http://www.zghlxwxcb.cn/news/detail-407879.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-407879.html
到了這里，關(guān)于哈夫曼樹、哈夫曼編碼和字典樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
