1. 首頁 > 生活 > >

數據結構與算法【Java】08---樹結構的實際應用( 四 )

生活百科

結果：

數據結構與算法【Java】08---樹結構的實際應用

文章插圖
3、赫夫曼編碼3.1、簡介
  • 赫夫曼編碼也翻譯為 哈夫曼編碼(Huffman Coding)，又稱霍夫曼編碼，是一種編碼方式, 屬于一種程序算法
  • 赫夫曼編碼是赫哈夫曼樹在電訊通信中的經典的應用之一 。
  • 赫夫曼編碼廣泛地用于數據文件壓縮 。其壓縮率通常在 20%～90%之間
  • 赫夫曼碼是可變字長編碼(VLC)的一種 。Huffman 于 1952 年提出一種編碼方法，稱之為最佳編碼
3.2、原理剖析
  • 通信領域中信息的處理方式 1-定長編碼
【數據結構與算法【Java】08---樹結構的實際應用】
數據結構與算法【Java】08---樹結構的實際應用

文章插圖
  • 通信領域中信息的處理方式 2-變長編碼

數據結構與算法【Java】08---樹結構的實際應用

文章插圖
  • 通信領域中信息的處理方式 3-赫夫曼編碼
1、傳輸的 字符串i like like like java do you like a java
2、d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各個字符對應的個數
3、按照上面字符出現的次數構建一顆赫夫曼樹, 次數作為權值構成赫夫曼樹的步驟：
  • 從小到大進行排序, 將每一個數據，每個數據都是一個節點 ，每個節點可以看成是一顆最簡單的二叉樹
  • 取出根節點權值最小的兩顆二叉樹
  • 組成一顆新的二叉樹, 該新的二叉樹的根節點的權值是前面兩顆二叉樹根節點權值的和
  • 再將這顆新的二叉樹，以根節點的權值大小 再次排序，不斷重復 1-2-3-4 的步驟，直到數列中，所有的數據都被處理，就得到一顆赫夫曼樹

數據結構與算法【Java】08---樹結構的實際應用

文章插圖
4、根據赫夫曼樹，給各個字符,規定編碼 (前綴編碼)，向左的路徑為 0 向右的路徑為 1 ，編碼如下:
o: 1000
u: 10010
d: 100110
y: 100111
i: 101
a : 110
k: 1110
e: 1111
j: 0000
v: 0001
l: 001
: 01(空格)
5、按照上面的赫夫曼編碼，我們的"i like like like java do you like a java" 字符串對應的編碼為 (注意這里我們使用的無損壓縮)
1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110
通過赫夫曼編碼處理 長度為 133,且不會有多義性
6、長度為 ： 133說明:原來長度是359 , 壓縮了 (359-133) / 359 = 62.9%
此編碼滿足前綴編碼, 即字符的編碼都不能是其他字符編碼的前綴 。不會造成匹配的多義性赫夫曼編碼是無損處理方案（可以完全恢復）
注：這個赫夫曼樹根據 排序方法不同，也可能不太一樣，這樣對應的 赫夫曼編碼也不完全一樣，但是 wpl 是一樣的，都是最小的, 最后生成的赫夫曼編碼的長度是一樣，比如: 如果我們讓每次生成的新的二叉樹總是排在權值相同的二叉樹的最后一個，則生成的二叉樹如下圖，但是編碼長度是不會變的，還是133
數據結構與算法【Java】08---樹結構的實際應用

文章插圖
3.3、創建赫夫曼樹（數據壓縮）將給出的一段文本，比如"i like like like java do you like a java"，根據前面的講的赫夫曼編碼原理，對其進行數據 壓 縮 處 理 ，形 式 如"1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100 110111101111011100100001100001110"

經驗總結擴展閱讀