【正文】 參考文獻(xiàn) [1]王增輝， 雷加 .一種變游程編碼的測(cè)試數(shù)據(jù)壓縮方法 .理論與方法 . [2]許川佩，董祥健 .一種交替游程編碼的 SOC 測(cè)試數(shù)據(jù)壓縮方法 .計(jì)算機(jī)工程與應(yīng)用 .2021， 46（ 25） [3]劉娟，詹文法，黃忠 .基于交替變游程編碼的測(cè)試數(shù)據(jù)壓縮方法 .安慶師范學(xué)院學(xué)報(bào) . [4]詹文法，梁華國(guó)，時(shí)峰，黃正峰，歐陽(yáng)一鳴 .一種共游程的測(cè)試數(shù)據(jù)壓縮方案 .計(jì)算機(jī)研究與發(fā)展 .2021 [5]彭喜元，俞洋 .基于變游程編碼的測(cè)試數(shù)據(jù)壓縮算法 .電子學(xué)報(bào) . [6]于翔。本次課設(shè)主要是編寫(xiě)一款 c程序來(lái)完成游程的數(shù)據(jù)壓縮。 總之，游 程編碼壓縮數(shù)據(jù)的方法就是通過(guò)對(duì)連續(xù)出現(xiàn)的“ 0”、“ 1”進(jìn)行進(jìn)行相應(yīng)的壓縮來(lái)減小信源大小，以實(shí)現(xiàn)數(shù)據(jù)壓縮。 目前已提出的比較有效的測(cè)試壓縮編碼算法主要有 3大類(lèi)：（ 1）基于統(tǒng)計(jì)的編碼壓縮算法，如哈夫曼（ Huffman）編碼、 VIHC 編碼；（ 2）基于游程（ runlength coding）的編碼壓縮算法，如 Golomb 編碼、 FDR（ Frequencydirected runlength）編碼算法、 VariableTail 算法、交替游程算法（ alternating runlength）；（ 3）基于字典的編碼算法，如FixedLengthIndexDictionary 算法、 CDCR（ bining dictionary coding and LFSR reseeding）。青海大學(xué)學(xué)報(bào) . [7]祝本明，劉桂華。本文中我才用游程編碼和哈夫曼編碼混合使用。哈夫曼變長(zhǎng)碼的效率是相當(dāng)高的，它可以單個(gè)信源符號(hào)編碼或用 L較小的信源序列編碼，對(duì)編碼器的設(shè)計(jì)來(lái)說(shuō)也簡(jiǎn)單的符號(hào)碼元 /4pi K iK 9 1i ?? ??碼元/)(HR bi tKX ???燕山大學(xué)本科生畢業(yè)設(shè)計(jì)（論文） 30 多。即總的壓縮效率為 59%，而游程壓縮效率為 80%。開(kāi)始對(duì)密文的字符串進(jìn)行解碼，樹(shù)索引從根節(jié)點(diǎn)開(kāi)始走，當(dāng)密文中的當(dāng)前字符是‘ 0’的時(shí)候，則索引走向左子節(jié)點(diǎn)；當(dāng)是‘ 1’的時(shí)候，則走向右子節(jié)點(diǎn)。以此類(lèi)推進(jìn)行編碼直到根節(jié)點(diǎn)為止。先在所有可能出現(xiàn)的字符中篩選出當(dāng)前權(quán)重最小的兩個(gè)字符，將這兩個(gè)字符分別作為新節(jié)點(diǎn)的左子和右子建立一個(gè)小的二叉樹(shù)，并將兩個(gè)字符的權(quán)重之和賦值給新節(jié)點(diǎn)，將新二叉樹(shù)放入篩選字符中，再將篩選過(guò)的兩個(gè)字符從篩選列表中淘汰掉。 游程編碼數(shù)據(jù)壓縮算法流程圖如圖 31： 數(shù)據(jù)解碼算法流程如下： 1) 打開(kāi)壓縮數(shù)據(jù)文件和恢復(fù)文件； 2) 從壓縮文件中循環(huán)讀出字符和該字符連續(xù)的個(gè)數(shù) , 在恢復(fù)文件中連續(xù)寫(xiě)入從壓縮文件中讀出的字符 , 寫(xiě)的次數(shù)等于該字符連續(xù)的個(gè)數(shù) :。如果規(guī)定二元序列是以“ 0”開(kāi)始，第一個(gè)游程是“ 0”游程，第二個(gè)必為“ 1”游程，第三個(gè)又是“ 0”游程等等。由于初始測(cè)試數(shù)據(jù)集中存 在大量的無(wú)關(guān)位，可以適當(dāng)?shù)膶?duì)這些無(wú)關(guān)位進(jìn)行賦值填充，增加 0 游程的長(zhǎng)度，這些游程長(zhǎng)度在同組的概率很高。顯然該編碼方案的數(shù)據(jù)壓縮率比共前綴碼高一些，不考慮相鄰游程的長(zhǎng)度相同的前提下，編碼方法與共前綴碼相同。同組共前綴碼的前綴和后綴的位數(shù)相同，前綴和后綴相加對(duì)應(yīng)的十進(jìn)制數(shù)比對(duì)應(yīng)的游程長(zhǎng)度多 2，也就是說(shuō)跟 FDR 碼相比，相同的碼字所表示的 游程長(zhǎng)度少 2，使壓縮效果受到一些影響，因此對(duì)初始測(cè)試數(shù)據(jù)進(jìn)行無(wú)關(guān)位 (don’t cares bit)填充時(shí)，要盡量時(shí)這種影響降到最低。 將任何 (二元 )序列變換成一一對(duì)應(yīng)的游程長(zhǎng)度序列，再按哈夫曼編碼或其他方法處理以達(dá)到壓縮碼率的目的 [9]。如果給出了形成串的字符，串的長(zhǎng)度以及串的位置，就能恢復(fù)出原來(lái)的數(shù)據(jù)流，游程長(zhǎng)度編碼 (RLC)就是用二進(jìn)制碼字給出這些信息的一類(lèi)方法。 比如上面的例子，哈弗曼樹(shù) 建立的過(guò)程如下 : 1) 列出原始的節(jié)點(diǎn)數(shù)據(jù)： 圖 24原始節(jié)點(diǎn) 第 2章 信源編碼分類(lèi) 13 2) 將最小的兩個(gè)節(jié)點(diǎn) C和 E結(jié)合起來(lái)： 圖 25C和 E結(jié)合 3) 再將新的節(jié)點(diǎn)和 A組合起來(lái) 圖 26新節(jié)點(diǎn)結(jié)合圖 4) 再將 D節(jié)點(diǎn)加入 圖 27新節(jié)點(diǎn)結(jié)合圖 燕山大學(xué)本科生畢業(yè)設(shè)計(jì)（論文） 14 5) 如此循環(huán)，最終得到一個(gè)最優(yōu)二叉樹(shù) 圖 28最優(yōu)二叉樹(shù)圖 生成的數(shù)據(jù)文件長(zhǎng)度為： 3*6 + 1*15 + 4*2 + 2*9 + 4*1 = 63 下面我們用逆推法來(lái)證明對(duì)于各種不同的節(jié)點(diǎn)序列，用哈弗曼算法建立起來(lái)的樹(shù)總是一棵最優(yōu)二叉樹(shù)： 當(dāng)這個(gè)過(guò)程中的節(jié)點(diǎn)序列只有兩個(gè)節(jié)點(diǎn)時(shí)（比如前例中的 15和 18），肯定是一棵最優(yōu)二叉樹(shù)，一個(gè)編碼為 0，另一個(gè)編碼為 1，無(wú)法再進(jìn)一步優(yōu)化。 哈弗曼編碼幾乎是所有壓縮算法的基礎(chǔ)，其實(shí)這個(gè)算法并不復(fù)雜，簡(jiǎn)單的理解就是，如何用更短的 bit 來(lái)編碼數(shù)據(jù)。 （ 2） 每一次選出頻率最小的兩個(gè)值，作為二叉樹(shù)的兩個(gè)葉子節(jié)點(diǎn)，將和作為它們的根節(jié)點(diǎn)，這兩個(gè)葉子節(jié) 點(diǎn)不再參與比較，新的根節(jié)點(diǎn)參與比較。 （ 3）將每一大組的信源符號(hào)再分為兩組，使劃分后的兩個(gè)組的概率之和近似相同，并對(duì)各組賦予一個(gè)二進(jìn)制符號(hào)“ 0”和“ 1”。這種編碼方法就是香農(nóng)編碼。但現(xiàn)代通信應(yīng)用中常見(jiàn)的信源編碼方式有： Huffman 編碼、算術(shù)編碼、 LZ 編碼，這三種都是無(wú)損編碼，另外還有一些有損的編碼方式。采用的一般方法是壓縮每個(gè)信源符號(hào)的平均比特?cái)?shù)或信源的碼率。然后主要描述了哈夫曼編碼方法以及如何構(gòu)造哈夫曼樹(shù)。 飛速發(fā)展的數(shù)據(jù)壓縮和圖像編碼技術(shù)，給多媒體數(shù)據(jù)傳輸和數(shù)據(jù)存儲(chǔ)帶來(lái)極大的快捷和便利。這樣，對(duì)多媒體信息的存儲(chǔ)和傳輸造成了很大困難，成為阻礙人們有效獲取和利用信息的一個(gè) 瓶頸問(wèn)題。哈夫曼編碼使用 變長(zhǎng)編碼表 對(duì)源符號(hào)進(jìn)行編碼，其中 變長(zhǎng)編碼表 是通過(guò)一種評(píng)估來(lái)源符號(hào)出現(xiàn)機(jī)率的方法得到的，出現(xiàn)機(jī)率高的字母使用較短的編碼，反之出現(xiàn)機(jī)率低的則使用較長(zhǎng)的編碼，這便使編碼之后的字符串的平均長(zhǎng)度、 期望值 降低，從而達(dá)到 無(wú)損壓縮 數(shù)據(jù)的目的。游程編碼是一種簡(jiǎn)單的 非破壞性資料壓縮法，其好處是加壓縮和解壓縮都非?？?。 結(jié)論 ......................................................................................................................31 參考文獻(xiàn) ..............................................................................................................32 致謝 ......................................................................................................................34 附錄 1 ...................................................................................................................35 Abstract 附錄 2 ................................................................................................................... 40 附錄 3 ................................................................................................................... 44 附錄 4 ................................................................................................................... 49 緒論 20 第 1章 緒論 課題背景 信息時(shí)代人們對(duì)使用計(jì)算機(jī)獲取信息、處理信息的依賴(lài)性越來(lái)越高。無(wú)損壓縮雖然壓縮比不是很高，但還原后的文件與原數(shù)據(jù)文件完全相同，從而保證了信息細(xì)節(jié)的不失真，常用的方法有統(tǒng)計(jì)式壓縮法和字典式壓縮法，統(tǒng)計(jì)式壓縮法的編碼方案主要是霍夫曼 (Hufman)編碼、算術(shù)編碼 (AC)和游程長(zhǎng)度編碼(RLC)[2]。但在某些數(shù)據(jù)安全性要求比較苛刻的領(lǐng)域，現(xiàn)在比較流行和壓縮效果好的壓縮算法幾乎都屬于有損范疇，對(duì)原始數(shù)據(jù)壓縮處理后有不同程度的損傷，無(wú)法完全恢復(fù)，以至于不能滿(mǎn)足技術(shù)要求 ，現(xiàn)有的無(wú)損壓縮方法，如 Huffman、 LZ 系列、算術(shù)編碼等壓縮方法盡管在某些方面各有優(yōu)點(diǎn)，但壓縮效果比較差或者算法實(shí)現(xiàn)比較困難， 而 游程編碼卻是一種是一種非常簡(jiǎn)單，且編碼、解碼速度很快編碼方法。由于信源符號(hào)之間存在分布不均勻和相關(guān)性，使得信源存在冗余度，信源編碼的主要任務(wù)就是減少冗余，提高編碼效率。 信源編碼的分類(lèi)及作用 信源編碼的分類(lèi)： 離散信源編碼：獨(dú)立信源編碼 ,可做到無(wú)失真編碼； 連續(xù)信源編碼：獨(dú)立信源編碼 ,只能做到限失真信源編碼； 相關(guān)信源編碼：非獨(dú)立信源編碼。能獲得最佳編碼的方法主要有：香農(nóng)（ Shannon）、費(fèi)諾（ Fano）、哈夫曼（ Huffman）編碼等。 所以信源符號(hào)的平均碼長(zhǎng)為： （ 25） 平均信息傳輸率即編碼效率為： ? ? 碼元\b i ??? （ 26） 符號(hào)碼元 /)(pK 7 1i ?? ?? Kai燕山大學(xué)本科生畢業(yè)設(shè)計(jì)（論文） 6 表 21 香農(nóng)編碼過(guò)程 信源消息符號(hào) Ai 符號(hào)概率 P(Ai） 累加概率Pi logp(Ai) 碼字長(zhǎng)度Ki 碼字 A1 A2 A3 A4 A5 A6 A7 0 3 3 3 3 3 4 7 000 001 011 100 101 1110 1111110 費(fèi)諾編碼方法 費(fèi)諾編碼，它編碼后的費(fèi)諾碼要比香農(nóng)碼的平均碼長(zhǎng)小，消息傳輸速率大，編碼效率高，但它屬于概率匹配編碼它不是最佳的編碼方法。 哈夫曼編碼方法 哈夫曼編碼是一種常見(jiàn)的壓縮方法。 表 23 哈夫曼編碼過(guò)程 信源符號(hào)Ai 概率p(Ai) 編碼過(guò)程 碼字Wi 碼長(zhǎng)Ki A1 0 1 10 2 A2 0 1 11 2 A3 0 1 000 3 A4 0 1 001 3 A5 0 1 010 3 A6 0 1 0110 4 A7 1 0111 4 該哈夫曼碼的平均碼長(zhǎng)為 （ 29） 信息傳輸速率 ? ? 碼元/bi ??? （ 210） ? ? 符號(hào)碼元 /2 . 7 2KiaipK 7 1i ?? ??第 2章 信源編碼分類(lèi) 9 由此可見(jiàn)，哈夫曼編碼的平均碼長(zhǎng)最小，消息傳輸速率最大，編碼效率最高。然后從節(jié)點(diǎn)序列中去除這兩個(gè)節(jié)點(diǎn)，加入它們的父節(jié)點(diǎn)到序列中。它們的父節(jié)點(diǎn)小于其他節(jié)點(diǎn)的父節(jié)點(diǎn)，它們又小于其他所有節(jié)點(diǎn)，只要前一步符合最優(yōu)二叉樹(shù)的第二個(gè)條件，到這一步仍將符合?！?0”游程和“ l”游程總是交替出現(xiàn)的。再按哈夫曼編碼或其他方法處 理以達(dá)到壓縮碼率的目的。 可見(jiàn)數(shù)據(jù)串 00000000000001 和 0000000000000001 的游程長(zhǎng)度分別為 13 和 15，都在第三組，前綴都為 1110，所以后一游程的碼字前綴用標(biāo)志位 0 表示，其碼字為 0 0011。例如數(shù)據(jù)串 00000000000x 000000000001，其中的 x 是無(wú)關(guān)位，如果把它填充為 0 則該數(shù)據(jù)