內(nèi)容來自尚硅谷Java數(shù)據(jù)結(jié)構(gòu)與java算法（Java數(shù)據(jù)結(jié)構(gòu)與算法）_嗶哩嗶哩_bilibili

寫在前面:本文內(nèi)容大致和原視頻內(nèi)老師的筆記內(nèi)容相同，會(huì)偶爾插入自己的注釋和理解，盡量會(huì)完成作業(yè)

本次沒有作業(yè)，輕松一課，內(nèi)容也不難

11.3赫夫曼編碼

11.3.1基本介紹

1.????? 赫夫曼編碼也翻譯為哈夫曼編碼(Huffman Coding)，又稱霍夫曼編碼，是一種編碼方式。屬于一種程序算法

2.????? 赫夫曼編碼是赫夫曼樹在電訊通信中的經(jīng)典的應(yīng)用之一。

3.????? 赫夫曼編碼廣泛地用于數(shù)據(jù)文件壓縮。其壓縮率通常在20%～90%之間

4.????? 赫夫曼碼是可變字長(zhǎng)編碼(VLC)的一種。Huffman于1952年提出一種編碼方法，稱之為最佳編碼

11.3.2原理剖析

通信領(lǐng)域中信息的處理方式1-定長(zhǎng)編碼

通信領(lǐng)域中信息的處理方式2-變長(zhǎng)編碼

通信領(lǐng)域中信息的處理方式3-赫夫曼編碼

步驟如下

?

傳輸?shù)淖址?/p>

1) i like like like java do you like a java

2) d:1y:1 u:1 j:2 v:2 o:2l:4 k:4 e:4 i:5 a:5 ?:9//各個(gè)字符對(duì)應(yīng)的個(gè)數(shù),9個(gè)空格

3)按照上面字符出現(xiàn)的次數(shù)構(gòu)建一顆赫夫曼樹,次數(shù)作為權(quán)值

步驟:

構(gòu)成赫夫曼樹的步驟:

1)從小到大進(jìn)行排序,將每一個(gè)數(shù)據(jù)，每個(gè)數(shù)據(jù)都是一個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)可以看成是一顆最簡(jiǎn)單的二叉樹2)取出根節(jié)點(diǎn)權(quán)值最小的兩顆二叉樹

3)組成一穎新的二叉樹,該新的二叉樹的根節(jié)點(diǎn)的權(quán)值是前面兩顆二叉樹根節(jié)點(diǎn)權(quán)值的和

4)再將這顆新的二叉樹，以根節(jié)點(diǎn)的權(quán)值大小再次排序，不斷重復(fù)1-2-3-4的步驟，直到數(shù)列中，所有的數(shù)據(jù)都被處理，就得到一顆赫夫曼樹

4)根據(jù)赫夫曼樹，給各個(gè)字符,規(guī)定編碼(前綴編碼)，向左的路徑為0向右的路徑為1，編碼如下:o: 1000 u: 10010 d: 100110 y: 100111 i: 101

a : 110k:1110 e: 1111j: 0000v : 0001l:001:01

5)按照上面的赫夫曼編碼，我們的"ilike like like java do you like a java”字符串對(duì)應(yīng)的編碼為(注意這里我們使用的無損壓縮)

1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110通過赫夫曼編碼處理長(zhǎng)度為133

6）長(zhǎng)度為:133

說明:

原來長(zhǎng)度是359,壓縮了(359-133)/359=62.9%

此編碼滿足前綴編碼,即字符的編碼都不能是其他字符編碼的前綴。不會(huì)造成匹配的多義性赫夫曼編碼是無損處理方案

?

注意事項(xiàng)

注意，這個(gè)赫夫曼樹根據(jù)排序方法不同，也可能不太一樣，這樣對(duì)應(yīng)的赫夫曼編碼也不完全一樣，但是wpl是一樣的，都是最小的，最后生成的赫夫曼編碼的長(zhǎng)度是一樣的，比如:如果我們讓每次生成的新的二叉樹總是排在權(quán)值相同的二叉樹的最后一個(gè)，則生成的二叉樹為: