數(shù)據(jù)壓縮大作業(yè)

《數(shù)據(jù)壓縮大作業(yè)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、數(shù)據(jù)壓縮大作業(yè)——算數(shù)編碼壓縮與解壓縮程序目錄一、試驗(yàn)背景及目的3二、試驗(yàn)內(nèi)容32.1試驗(yàn)步驟32.2試驗(yàn)原理3三、算法流程63.1編碼器算法63.2解碼器算法四、程序設(shè)計(jì)說明7五、程序壓縮性能評(píng)價(jià)85.1data,txt文件的測(cè)試結(jié)果85.2textdata,txt文件的測(cè)試結(jié)果115.3程序壓縮性能評(píng)價(jià)13六、程序源代碼14七、測(cè)試數(shù)據(jù)文件22試驗(yàn)背景及目的霍夫曼方法比香農(nóng)-費(fèi)諾方法更有效，但這兩種方法都很少能產(chǎn)生最佳變長(zhǎng)編碼，僅當(dāng)符號(hào)概率等于2的負(fù)整數(shù)次幕時(shí)，這些方法才能產(chǎn)生最佳結(jié)果（碼字的平均長(zhǎng)度等于嫡）

2、。算數(shù)編碼克服了這個(gè)問題，它是把一個(gè)碼字（通常較長(zhǎng)）分配給整個(gè)輸入流，而不是給各符號(hào)分別分配碼字。它可以為特定序列指定碼字,而又不需要為所有同一長(zhǎng)度的序列生成代碼。算術(shù)編碼逐個(gè)符號(hào)讀輸入流，每輸入和處理一個(gè)符號(hào)，就在碼字后面加上幾位，因此，在算數(shù)編碼中，當(dāng)前區(qū)間的下限和上限隨著碼流長(zhǎng)度的增大，將變得無限長(zhǎng)。而實(shí)際上，雙精度的實(shí)數(shù)也只有16位有效數(shù)字，更長(zhǎng)精度的數(shù)無法表示，除此Z外，即使有一種方法能夠表示足夠長(zhǎng)的數(shù)據(jù)精度，兩個(gè)很長(zhǎng)的數(shù)進(jìn)行運(yùn)算，花費(fèi)的時(shí)間也無法承受。因此，一個(gè)實(shí)用的方案應(yīng)當(dāng)采用有限長(zhǎng)度的整數(shù)運(yùn)算，利

3、用有限字長(zhǎng)寄存器來實(shí)現(xiàn)算數(shù)編碼，該方法即為整數(shù)算數(shù)編碼。本實(shí)驗(yàn)的目的即根據(jù)算數(shù)編碼的原理，利用二進(jìn)制定點(diǎn)數(shù)法編寫算數(shù)編碼壓縮及解壓縮程序，實(shí)現(xiàn)對(duì)*?txt文件的壓縮及解壓縮，并對(duì)程序壓縮性能進(jìn)行評(píng)價(jià)，從而加深對(duì)算數(shù)編碼原理的理解，掌握相關(guān)算法的設(shè)計(jì)方法以及進(jìn)一步提高程序編寫的能力。二、試驗(yàn)內(nèi)容2.1試驗(yàn)步驟根據(jù)試驗(yàn)?zāi)康?，本次試?yàn)的具體步驟如下：①參考相關(guān)資料對(duì)算數(shù)編碼的原理進(jìn)行分析與理解，②根據(jù)其原理，利用二進(jìn)制定點(diǎn)數(shù)法設(shè)計(jì)符合要求的算法，③根據(jù)所設(shè)計(jì)的算法，利用C語言編寫相關(guān)程序，④利用測(cè)試數(shù)據(jù)文件對(duì)程序進(jìn)行測(cè)

4、試，并對(duì)程序的壓縮性能進(jìn)行評(píng)價(jià)。2.2試驗(yàn)原理2.2.1編碼器的實(shí)現(xiàn)給定一個(gè)字長(zhǎng)加，將［0,1）區(qū)間中的重要值映射到2〃個(gè)二進(jìn)制字的范圍。點(diǎn)0被映射為:加次00---0點(diǎn)1被映射為：加次r八111??1點(diǎn)0.5被映射為：〃山次100^6以耳表示符號(hào)i出現(xiàn)的次數(shù)，定義CumCount(k)=,編碼下限/和上限u/=!可以用下式迭代：(%-/+1)*CumCountx-TotalCount1—1+("一/+1)*CumCountx)TotalCountu—/+具體編碼規(guī)則如下：?如果/和M的最咼位都是弘①將方輸出

5、到碼流，②將Z左移1位，最低位補(bǔ)0,③將u左移1位，最低位補(bǔ)1④如果Scale>0,輸出b的補(bǔ)，scale減1?如果Scale條件成立:①將I左移1位，最低位補(bǔ)0②將u左移1位，最低位補(bǔ)1③Z和m最高位取反，scale加1上述規(guī)則用表格表示如下：LOW.HIGHp輸出"OXqox「輸岀sX1X^輸岀仆OOP10^正常區(qū)間卩01p正常區(qū)間卩00.11^正常區(qū)間卩01p10^Scale區(qū)卩2.2.2解碼器的實(shí)現(xiàn)解碼過程與編碼過程相反，有了編碼器的實(shí)現(xiàn)，解碼器實(shí)現(xiàn)就很好描述了。解碼過程一旦啟動(dòng)，剩下的就是模擬編碼器算法

6、了。其原理如下：初始化/和腺從壓縮碼流讀入加個(gè)比特作為人以Index解碼符號(hào)x,其表達(dá)式如下：Index=(f一/+1)*TotalCount-1(w—/+1)MM解碼下限/和上限u可以用下式迭代:(%-/+1)*CumCountx-}TotalCount?“(w-/+l)(兀)]TotalCount具體解碼規(guī)則如下：?如果/和m的最咼位都是慶①將r左移1位，最低位從壓縮碼流補(bǔ)1個(gè)比特，②將/左移1位，最低位補(bǔ)0,③將m左移1位，最低位補(bǔ)1。?如果Scale條件成立:①將/左移1位，最低位從壓縮碼流補(bǔ)1個(gè)比特

7、，②將/左移1位，最三、低位補(bǔ)0,③將m左移1位，最低位補(bǔ)1,CD將厶碼/最高位取反。算法流程根據(jù)上述編碼器與解碼器的原理，設(shè)計(jì)相關(guān)的算法。2.1編碼器算法初始化/和U取得符號(hào)Total_Count(w-/+l)xCum_Count(x-I)(w-/+l)xCum_Count(x)1TotalCountWhile（u和l的最高位都等于b或滿足Scale條件）If（u和/的最高位都等于b）{發(fā)送b將/左移一個(gè)比特，并將0移入最低位將u左移一個(gè)比特，并將1移入最低位While（ScaIe>0）{發(fā)送b的補(bǔ)碼遞減Sca

8、le}}（滿足Scale條件）{將/左移一個(gè)比特，并將0移入最低位將u左移一個(gè)比特，并將1移入最低位對(duì)/和況的（新）最高位求反遞增Scale}2.2解碼器算法初始化Z和u將接收到的比特流中的前加個(gè)比特讀入標(biāo)簽rk=Owhile[t-l+)xTotal_Count-w—+1>Cum_Count(Z:)丿k?k+對(duì)符號(hào)兀進(jìn)行解碼(w-/+l)xCum_Count(x-