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

Huffman壓縮原理--基于Huffman編碼
以字符串中每個(gè)字符出現(xiàn)的次數(shù)為權(quán)值構(gòu)建Huffman樹(shù)
從根節(jié)點(diǎn)開(kāi)始，左分支為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)頁(yè)設(shè)計(jì)及高端網(wǎng)站定制服務(wù),企業(yè)網(wǎng)站制作及推廣,對(duì)成都辦公空間設(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

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

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

文件壓縮過(guò)程：

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

文件解壓縮的過(guò)程：

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

寫(xiě)代碼當(dāng)中碰到的一些主要的問(wèn)題，我將這些總結(jié)起來(lái)：

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

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

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

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

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

解決方法：_count長(zhǎng)度設(shè)為unsigned long long類(lèi)型

4.還有許多大大小小的問(wèn)題等等
壓縮率

文件類(lèi)型	源文件大小	壓縮后大小	壓縮率
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元起步，三天無(wú)理由+7*72小時(shí)售后在線(xiàn)，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性?xún)r(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專(zhuān)為企業(yè)上云打造定制，能夠滿(mǎn)足用戶(hù)豐富、多元化的應(yīng)用場(chǎng)景需求。

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

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

廣告

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