|
之前說到了如何構(gòu)建赫夫曼樹，那么赫夫曼樹有什么用呢？赫夫曼樹經(jīng)典的應(yīng)用之一就是赫夫曼編碼。 1. 赫夫曼編碼是什么？ 它是一種編碼方式，可以用在電訊通信中，或者用于對(duì)數(shù)據(jù)文件進(jìn)行壓縮，壓縮率一般在20%到90%。 2. 為什么要有赫夫曼編碼？ 我們要在網(wǎng)絡(luò)中傳輸一句話，首先要將這句話的所有內(nèi)容轉(zhuǎn)成對(duì)應(yīng)的Ascii碼，然后再將Ascii轉(zhuǎn)成二進(jìn)制，這樣一來，可能這句話原本長(zhǎng)度是40，經(jīng)過轉(zhuǎn)換后會(huì)變得很長(zhǎng)。這種編碼方式叫定長(zhǎng)編碼，效率很低。其實(shí)我們可以統(tǒng)計(jì)這句話中各個(gè)字符出現(xiàn)的次數(shù)，然后用二進(jìn)制數(shù)字記錄這些字符出現(xiàn)的次數(shù)，對(duì)這句話進(jìn)行編碼時(shí)，將字符替換成對(duì)應(yīng)的二進(jìn)制就行了，這叫變長(zhǎng)編碼。但是這種編碼方式也會(huì)有問題，就是最后傳輸?shù)亩M(jìn)制串，對(duì)方在解碼的時(shí)候，不知道哪些是要組合起來的，比如最后二進(jìn)制串是101101……，到底第一位的1是單獨(dú)解碼呢還是要和第二位的0組合起來10才表示一個(gè)字符呢？這就造成了解碼的多異性。赫夫曼編碼就可以解決這個(gè)問題。 3. 赫夫曼編碼原理： 假如現(xiàn)在要對(duì)i like like like java do you like a java這句話(長(zhǎng)度是40)進(jìn)行編碼，過程如下： 統(tǒng)計(jì)各個(gè)字符出現(xiàn)的次數(shù)：d:1次 y:1次 u:1次 j:2次 v:2次 o:2次 i:4次 k:4次 e:4次 i:5次 a:5次 空格:9次 按照上面的字符出現(xiàn)的次數(shù)構(gòu)建赫夫曼樹，構(gòu)建方法和之前講的構(gòu)建赫夫曼樹一樣。 根據(jù)赫夫曼樹，給各個(gè)字符編碼。規(guī)定向左的路徑為0，向右路徑為1，然后路徑數(shù)字組合起來就是該字符的編碼。比如到a字符的路徑是先向右，再向左，再向左，那么a的編碼就是100。
o:1000 u:10010 d:100110 y:100111 i:101
a:100 k:1110 e:1111 j:0000 v:0001 l:001 空格:01
可以發(fā)現(xiàn)，每個(gè)字符的編碼，都不會(huì)是另一個(gè)字符編碼的前綴，比如空格的編碼是01，其他字符，沒有是以01開頭的，因?yàn)榈蕉鏄鋬蓚€(gè)不同的節(jié)點(diǎn)路徑不可能一樣，這樣解決了解碼多異性的問題。 根據(jù)各個(gè)字符的編碼，就可以得到要發(fā)送內(nèi)容編碼后的字符串，i是101，空格是01，l是001……要發(fā)送內(nèi)容編碼后就是10101001……，長(zhǎng)度為133。 可以發(fā)現(xiàn)，編碼后的二進(jìn)制字符串長(zhǎng)度(133)遠(yuǎn)遠(yuǎn)超過了原始內(nèi)容長(zhǎng)度(40)，所以還要壓縮一下。壓縮的方法就是將二進(jìn)制字符串每8位轉(zhuǎn)成一個(gè)數(shù)字再轉(zhuǎn)成字節(jié)，最終得到的字節(jié)數(shù)組就是：
-88，-65，-56，-65，-56，-65，-55，77，-57，6，-24，-14，-117，-4，-60，-90，28
長(zhǎng)度為17，原始長(zhǎng)度是40，壓縮率為57.5%。 4. 赫夫曼解碼： 本來是要發(fā)送i like like like java do you like a java這句話的，最終發(fā)送的是-88，-65，-56，-65，-56，-65，-55，77，-57，6，-24，-14，-117，-4，-60，-90，28，對(duì)方接收到后怎么還原成原始的那句話呢？其實(shí)這就是一個(gè)逆向操作了。 編碼的時(shí)候最后一步是壓縮，那么這里就先要將接收到的字節(jié)數(shù)組解壓成133位的字符串。即還原成10101001……這個(gè)字符串。 然后再根據(jù)各個(gè)字符的編碼，還原成原始發(fā)送的內(nèi)容，即用10101001……對(duì)照下表，將內(nèi)容還原即可。
o:1000 u:10010 d:100110 y:100111 i:101
a:100 k:1110 e:1111 j:0000 v:0001 l:001 空格:01
5. 赫夫曼編碼解碼注意事項(xiàng)： 如果文件本身就是經(jīng)過壓縮處理的，比如視頻文件、ppt等，壓縮率不會(huì)很高 赫夫曼編碼是按字節(jié)來處理的，因此可以處理所有的文件 如果文件重復(fù)的內(nèi)容不多，壓縮率也不高
|
