huffman的壓縮原理和壓縮過程-創(chuàng)新互聯(lián)

壓縮原因
1.文件太大，節(jié)省空間
2.提高數(shù)據(jù)在網(wǎng)絡(luò)上傳輸?shù)男?br/>3.對數(shù)據(jù)起到保護(hù)作用---加密
文件壓縮類型
無損壓縮：源文件被壓縮之后，可以通過解壓縮還原成與源文件相同的格式
有損壓縮：源文件被壓縮之后，解壓縮無法還原成與源文件相同，但識別其內(nèi)容沒有影響，多用于語音，圖片，視頻壓縮
基于Huffman樹的壓縮如何實(shí)現(xiàn)
通過Huffman編碼實(shí)現(xiàn)，字符一般都是以字節(jié)存儲的，通過編碼轉(zhuǎn)換為二進(jìn)制編碼（1字節(jié)=8比特位）
首先，什么是Huffman樹
給定N個(gè)權(quán)值作為N個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹，若該樹的帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹。哈夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點(diǎn)離根較近。
例如：給定權(quán)值為1（A）,3（B）,5（C）,7（D）四個(gè)節(jié)點(diǎn)，構(gòu)建Huffman樹
huffman的壓縮原理和壓縮過程
Huffman壓縮原理--基于Huffman編碼
以字符串中每個(gè)字符出現(xiàn)的次數(shù)為權(quán)值構(gòu)建Huffman樹
從根節(jié)點(diǎn)開始，左分支為0，右分支為1，如上圖
所有權(quán)值節(jié)點(diǎn)都在葉子節(jié)點(diǎn)位置，遍歷每條到葉子節(jié)點(diǎn)的路徑獲取字符的編碼

創(chuàng)新互聯(lián)建站10多年企業(yè)網(wǎng)站制作服務(wù);為您提供網(wǎng)站建設(shè),網(wǎng)站制作,網(wǎng)頁設(shè)計(jì)及高端網(wǎng)站定制服務(wù),企業(yè)網(wǎng)站制作及推廣,對成都辦公空間設(shè)計(jì)等多個(gè)方面擁有豐富的網(wǎng)站運(yùn)維經(jīng)驗(yàn)的網(wǎng)站建設(shè)公司。

舉個(gè)栗子：ABBBCCCCCDDDDDDD
Huffman編碼：
A:100
B:101
C:11
D:0

原理就是這么簡單，一個(gè)字符占一個(gè)字節(jié)，現(xiàn)在用二進(jìn)制編碼代替之后，一個(gè)字符只占三位，也就是說一個(gè)字節(jié)可以表示兩三個(gè)字符，所以說一次壓縮，就會節(jié)省很多字節(jié)，也就起到了壓縮的作用。
項(xiàng)目中最重要的是三點(diǎn)
創(chuàng)建Huffman樹

1 先用權(quán)值創(chuàng)建n棵只有根節(jié)點(diǎn)的二叉樹森林【意思是先創(chuàng)建n個(gè)節(jié)點(diǎn)】
2 選取根節(jié)點(diǎn)權(quán)值最小的二叉樹構(gòu)建新的二叉樹【建小堆，新二叉樹根節(jié)點(diǎn)權(quán)值為左右子樹的根節(jié)點(diǎn)權(quán)值之和】【用到了priority_queue優(yōu)先級隊(duì)列】
3 刪除使用的兩棵根節(jié)點(diǎn)權(quán)值較小的二叉樹
4 將新創(chuàng)建的二叉樹添加到二叉樹森林中
接下來2-4循環(huán)繼續(xù)，直到二叉樹森林中只有一棵二叉樹則Huffman樹創(chuàng)建成

文件壓縮過程：

1讀取源文件，讀取源文件中每個(gè)字符出現(xiàn)的次數(shù)
2 以每個(gè)字符出現(xiàn)的次數(shù)作為權(quán)值，創(chuàng)建huffman樹：小堆--優(yōu)先級隊(duì)列
3 通過huffman樹找每個(gè)字符對應(yīng)的編碼
4 用每個(gè)字符的新編碼重新對源文件進(jìn)行改寫【翻譯的過程】

文件解壓縮的過程：

從壓縮文件中獲取源文件的后綴
從壓縮文件中獲取字符次數(shù)的總行數(shù)
獲取每個(gè)字符出現(xiàn)的次數(shù)
重建huffman樹
解壓壓縮數(shù)據(jù)
  a. 從壓縮文件中讀取一個(gè)字節(jié)的獲取壓縮數(shù)據(jù)ch
  b. 從根節(jié)點(diǎn)開始，按照ch的8個(gè)比特位信息從高到低遍歷huffman樹：該比特位是0，取當(dāng)前節(jié)點(diǎn)的左孩子，否則取右孩子，直到遍歷到葉子節(jié)點(diǎn)位置，該字符就被解析成功，將解壓出的字符寫入文件，如果在遍歷huffman過程中，8個(gè)比特位已經(jīng)比較完畢還沒有到達(dá)葉子節(jié)點(diǎn)，從a開始執(zhí)行
   c. 重復(fù)以上過程，直到所有的數(shù)據(jù)解析完畢。

寫代碼當(dāng)中碰到的一些主要的問題，我將這些總結(jié)起來：

1.編譯的時(shí)候：
剛開始寫的時(shí)候測試發(fā)現(xiàn)如果壓縮文件中出現(xiàn)了中文，程序就會崩潰，最后發(fā)現(xiàn)是數(shù)組越界的錯(cuò)誤，因?yàn)槿绻皇亲址?，它的范圍?128~127，程序中使用char類型為數(shù)組下標(biāo)(0~127)，所以字符沒有問題. 但是漢字的編碼是兩個(gè)字節(jié)，所以可能會出現(xiàn)越界，

解決方法：就是將char類型強(qiáng)轉(zhuǎn)為unsigned char，下標(biāo)可表示范圍為0~255.

2.解壓縮的時(shí)候
有些特殊字符在處理需要注意一下，比如'\n'，我的程序中Getline()函數(shù)就是讀取一行字符，但是若是該字符本身就是一個(gè)'\n'呢？這就非常的棘手了. 因?yàn)榻鈮嚎s之后出現(xiàn)了亂碼

解決方法：讀取壓縮文件時(shí)若讀到了'\n',則說明該字符就是'\n'，應(yīng)該繼續(xù)讀取它的次數(shù)

3.運(yùn)行的時(shí)候：
發(fā)現(xiàn)文件篇幅很長的時(shí)候，只能壓縮和解壓縮一部分，是因?yàn)樽址L度的設(shè)定太小

解決方法：_count長度設(shè)為unsigned long long類型

4.還有許多大大小小的問題等等
壓縮率

文件類型	源文件大小	壓縮后大小	壓縮率
word文檔	31.5KB	32.1KB	1.02
音頻文件	29.8 MB	29.8MB	0.99
視頻文件	20.7MB	20.7MB	0.99

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)cdcxhl.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

名稱欄目：huffman的壓縮原理和壓縮過程-創(chuàng)新互聯(lián)
標(biāo)題來源：http://muchs.cn/article6/eipig.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供響應(yīng)式網(wǎng)站、電子商務(wù)、微信小程序、用戶體驗(yàn)、小程序開發(fā)、網(wǎng)站營銷

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容