本科畢業(yè)設(shè)計(jì)（論文）基于游程編碼數(shù)據(jù)壓縮算法的設(shè)計(jì)與實(shí)現(xiàn)2013年6月摘要本次畢業(yè)設(shè)計(jì)主要是針對(duì)于游程編碼數(shù)據(jù)壓縮算法的設(shè)計(jì)與實(shí)現(xiàn)，游程編碼非常簡(jiǎn)單，編碼、解碼速度快，應(yīng)用廣泛。游程編碼是針對(duì)于二元序列的一種編碼方法，對(duì)于二值圖像而言是一種編碼方法，對(duì)連續(xù)的黑、白像素?cái)?shù)游程以不同的碼字進(jìn)行編碼。游程編碼是一種簡(jiǎn)單的非破壞性資料壓縮法，其好處是加壓縮和解壓縮都非常快。其方法是計(jì)算連續(xù)出現(xiàn)的資料長(zhǎng)度壓縮之，其缺點(diǎn)是對(duì)于不重復(fù)的資料反而加大容量。游程編碼即需大量的緩沖和優(yōu)質(zhì)信道，所以對(duì)數(shù)據(jù)游程編碼后在進(jìn)一步的進(jìn)行哈夫曼編碼已達(dá)到更完善的數(shù)據(jù)壓縮。哈夫曼編碼使用變長(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ù)的目的。本文主要介紹了信源編碼的分類、獲得最佳編碼的方法、哈夫曼樹(shù)的構(gòu)建方法以及游程編碼的原理和實(shí)現(xiàn)技術(shù)，對(duì)游程長(zhǎng)度編碼技術(shù)做了較為全面地研究。包括游程數(shù)據(jù)壓縮、解壓縮過(guò)程，并給出了流程圖；哈夫曼數(shù)據(jù)壓縮、解壓縮過(guò)程，并給出流程圖和結(jié)果圖。關(guān)鍵詞游程編碼哈夫曼編碼壓縮ABSTRACTTHISGRADUATIONDESIGNISMAINLYBASEDONRUNLENGTHCODINGDATACOMPRESSIONALGORITHMDESIGNANDIMPLEMENTATIONOFRUNLENGTHCODINGISVERYSIMPLE,ENCODINGANDDECODINGSPEED,WIDEAPPLICATIONRUNLENGTHCODINGISACODINGMETHODFORBINARYSEQUENCE,ISAKINDOFCODINGMETHODFORBINARYIMAGE,THEBLACKANDWHITEPIXELSOFCONTINUOUSRUNINDIFFERENTCODECODEWORDRUNLENGTHCODINGISAKINDOFSIMPLENONDESTRUCTIVEDATACOMPRESSIONMETHOD,THEADVANTAGEISTHATOFCOMPRESSIONANDDECOMPRESSIONAREVERYFASTITSMETHODISTOCALCULATEACONTINUOUSLENGTHOFDATACOMPRESSION,THEDOWNSIDEISTONOTREPEATDATAINSTEADOFINCREASINGCAPACITYRUNLENGTHCODINGISNEEDALOTOFBUFFERANDCHANNEL,SOTHEDATAAFTERTHERUNLENGTHCODINGINFURTHERHUFFMANENCODINGHASREACHEDMORESOURCECODINGISMAINLYINTRODUCEDINTHISPAPERTHECLASSIFICATION,THEOPTIMALMETHODOFCODING,HUFFMANTREE,CONSTRUCTIONMETHODS,ANDTHERUNLENGTHCODINGPRINCIPLEANDIMPLEMENTATIONTECHNOLOGY,THELENGTHOFTHERUNLENGTHENCODINGTECHNOLOGYISDONEMORECOMPREHENSIVERESEARCHINCLUDINGTHERUNLENGTHDATACOMPRESSIONANDDECOMPRESSIONPROCESS,ANDGIVESTHEFLOWCHARTHUFFMANDATACOMPRESSIONANDDECOMPRESSIONPROCESS,CHARTANDFLOWCHARTISGIVENANDTHERESULTSKEYWORDSRUNLENGTHCODINGHUFFMANENCODINGTHECOMPRESSION目錄摘要IABSTRACTII第1章緒論111課題背景112選題目的、意義213主要內(nèi)容2第2章信源編碼分類321信源編碼3211信源編碼簡(jiǎn)介3212信源編碼的理論基礎(chǔ)3213信源編碼的分類及作用422最佳變長(zhǎng)編碼4221香農(nóng)編碼方法5222費(fèi)諾編碼方法6223哈夫曼編碼方法723游程編碼15231游程長(zhǎng)度15232游程編碼算法15233游程編碼特點(diǎn)16234幾種基于游程相關(guān)性的數(shù)據(jù)壓縮方案1624本章小結(jié)19第3章游程編碼以及哈夫曼編2031游程編碼2032哈夫曼編碼過(guò)程2333運(yùn)行結(jié)果2834本章小結(jié)30結(jié)論31參考文獻(xiàn)33致謝35附錄136附錄241附錄345附錄450第1章緒論11課題背景信息時(shí)代人們對(duì)使用計(jì)算機(jī)獲取信息、處理信息的依賴性越來(lái)越高。多媒體計(jì)算機(jī)系統(tǒng)面臨的是數(shù)值、文字、語(yǔ)言、音樂(lè)、圖形、動(dòng)畫、靜圖像、電視視頻圖像等多種媒體承載的由模擬量轉(zhuǎn)化成數(shù)字量信息的吞吐、存儲(chǔ)和傳輸?shù)膯?wèn)題。數(shù)字化了的視頻和音頻信號(hào)的數(shù)量之大是驚人的，與硬件技術(shù)所能提供的計(jì)算機(jī)存儲(chǔ)資源和網(wǎng)絡(luò)帶寬之間有很大差距1。這樣，對(duì)多媒體信息的存儲(chǔ)和傳輸造成了很大困難，成為阻礙人們有效獲取和利用信息的一個(gè)瓶頸問(wèn)題。多媒體信息使用的前提是進(jìn)行有效的壓縮。例如一段時(shí)間長(zhǎng)度為1MIN，圖像尺寸為640480PIXETE，每秒播放30幀的非壓縮彩色24位真彩色視頻的信息量為640480330601658880000BYTES，約為16GB未含音頻信息的容量，如果用650MB的CDR來(lái)存放，需要3張。由此可見(jiàn)，在視頻信息的處理及應(yīng)用過(guò)程中壓縮及解壓縮技術(shù)是十分必要的2。數(shù)據(jù)壓縮技術(shù)主要采用兩種方法一種是“保真率”較高的無(wú)損壓縮法；另一種是以損失信息細(xì)節(jié)而換取較高壓縮比的有損壓縮法。無(wú)損壓縮雖然壓縮比不是很高，但還原后的文件與原數(shù)據(jù)文件完全相同，從而保證了信息細(xì)節(jié)的不失真，常用的方法有統(tǒng)計(jì)式壓縮法和字典式壓縮法，統(tǒng)計(jì)式壓縮法的編碼方案主要是霍夫曼HUFMAN編碼、算術(shù)編碼AC和游程長(zhǎng)度編碼RLC2。其中，游程長(zhǎng)度編碼是一種十分簡(jiǎn)單的壓縮方法，編碼解碼的速度也非?？?，因此得到了廣泛的應(yīng)用。許多圖形和視頻文件，如BMP，TIF及AVI等，都采用了這種壓縮方法，尤其適用于文本文件數(shù)據(jù)壓縮，它主要是去除文本中的冗余字符或字節(jié)中的冗余位以達(dá)到減少數(shù)據(jù)文件所占的存儲(chǔ)空間的目的6。飛速發(fā)展的數(shù)據(jù)壓縮和圖像編碼技術(shù)，給多媒體數(shù)據(jù)傳輸和數(shù)據(jù)存儲(chǔ)帶來(lái)極大的快捷和便利。但在某些數(shù)據(jù)安全性要求比較苛刻的領(lǐng)域，現(xiàn)在比較流行和壓縮效果好的壓縮算法幾乎都屬于有損范疇，對(duì)原始數(shù)據(jù)壓縮處理后有不同程度的損傷，無(wú)法完全恢復(fù)，以至于不能滿足技術(shù)要求，現(xiàn)有的無(wú)損壓縮方法，如HUFFMAN、LZ系列、算術(shù)編碼等壓縮方法盡管在某些方面各有優(yōu)點(diǎn)，但壓縮效果比較差或者算法實(shí)現(xiàn)比較困難，因此十分有必要對(duì)無(wú)損壓縮算法進(jìn)行研究4。通過(guò)對(duì)游程編碼RUNLENGTHENCODING,RLE進(jìn)行研究,結(jié)合哈夫曼編碼。最后找到一種實(shí)現(xiàn)相對(duì)簡(jiǎn)單、壓縮效果比較好的方法，即對(duì)游程編碼后的數(shù)據(jù)在進(jìn)一步的進(jìn)行哈夫曼編碼，采用該方法可以收到比較理想的效果。12選題目的、意義飛速發(fā)展的數(shù)據(jù)壓縮和圖像編碼技術(shù)，給多媒體數(shù)據(jù)傳輸和數(shù)據(jù)存儲(chǔ)帶來(lái)極大的快捷和便利。但在某些數(shù)據(jù)安全性要求比較苛刻的領(lǐng)域，現(xiàn)在比較流行和壓縮效果好的壓縮算法幾乎都屬于有損范疇，對(duì)原始數(shù)據(jù)壓縮處理后有不同程度的損傷，無(wú)法完全恢復(fù)，以至于不能滿足技術(shù)要求，現(xiàn)有的無(wú)損壓縮方法，如HUFFMAN、LZ系列、算術(shù)編碼等壓縮方法盡管在某些方面各有優(yōu)點(diǎn)，但壓縮效果比較差或者算法實(shí)現(xiàn)比較困難，而游程編碼卻是一種是一種非常簡(jiǎn)單，且編碼、解碼速度很快編碼方法。所以通過(guò)對(duì)于游程編碼的研究能夠比較快捷語(yǔ)簡(jiǎn)單的實(shí)現(xiàn)對(duì)于數(shù)據(jù)的無(wú)損壓縮。13主要內(nèi)容本文主要介紹了信源編碼中的幾種最佳變長(zhǎng)編碼方法香農(nóng)（SHANNON）、費(fèi)諾（FANO）、哈夫曼（HUFFMAN）編碼，以及這幾種編碼的編碼過(guò)程。然后主要描述了哈夫曼編碼方法以及如何構(gòu)造哈夫曼樹(shù)。然后詳細(xì)的介紹了游程編碼的編碼算法以及游程編碼的特點(diǎn)。畫出游程編碼哈夫曼編碼的流程圖，以及得出的結(jié)果圖，最后做出總結(jié)。第2章信源編碼分類21信源編碼211信源編碼簡(jiǎn)介編碼實(shí)質(zhì)上就是對(duì)信源的原始符號(hào)按一定規(guī)則進(jìn)行的一種變換。編碼可分為信源編碼和信道編碼。由于信源符號(hào)之間存在分布不均勻和相關(guān)性，使得信源存在冗余度，信源編碼的主要任務(wù)就是減少冗余，提高編碼效率。具體的說(shuō)就是針對(duì)信源輸出符號(hào)序列的統(tǒng)計(jì)特性，尋找一定的方法把信源輸出符號(hào)序列變換為最短碼字序列的方法。信源編碼的基本途徑有兩個(gè)使序列中的各個(gè)符號(hào)盡可能地相互獨(dú)立，即解除相關(guān)性；使編碼中各個(gè)符號(hào)出現(xiàn)的概率盡可能地相等，即概率均勻化。采用的一般方法是壓縮每個(gè)信源符號(hào)的平均比特?cái)?shù)或信源的碼率。即同樣多的信息用較少的碼率傳送,使單位時(shí)間內(nèi)傳送的平均信息量增加,從而提高通信的有效性3。212信源編碼的理論基礎(chǔ)信源編碼就是從信源符號(hào)到碼符號(hào)的一種映射F，它把信源輸出的符號(hào)UI變換成碼元序列WI。信源編碼定義如圖21信源編碼器UU1，U2ULWW1,W2WKXX1，X2XR圖21信源編碼定義圖信源編碼理論是信息論的一個(gè)重要分支,其理論基礎(chǔ)是信源編碼的兩個(gè)定理。無(wú)失真信源編碼定理是離散信源/數(shù)字信號(hào)編碼的基礎(chǔ)；限失真信源編碼定理是連續(xù)信源/模擬信號(hào)編碼的基礎(chǔ)。213信源編碼的分類及作用信源編碼的分類離散信源編碼獨(dú)立信源編碼,可做到無(wú)失真編碼；連續(xù)信源編碼獨(dú)立信源編碼,只能做到限失真信源編碼；相關(guān)信源編碼非獨(dú)立信源編碼。編碼的作用信源編碼的作用之一是設(shè)法減少碼元數(shù)目和降低碼元速率，即通常所說(shuō)的數(shù)據(jù)壓縮作用之二是將信源的模擬信號(hào)轉(zhuǎn)化成數(shù)字信號(hào)，以實(shí)現(xiàn)模擬信號(hào)的數(shù)字化傳輸。214信源編碼的歷史最原始的信源編碼就是莫爾斯電碼，另外還有ASCII碼和電報(bào)碼都是信源編碼。但現(xiàn)代通信應(yīng)用中常見(jiàn)的信源編碼方式有HUFFMAN編碼、算術(shù)編碼、LZ編碼，這三種都是無(wú)損編碼，另外還有一些有損的編碼方式。信源編碼的目標(biāo)就是使信源減少冗余，更加有效、經(jīng)濟(jì)地傳輸，最常見(jiàn)的應(yīng)用形式就是壓縮。另外，在數(shù)字電視領(lǐng)域，信源編碼包括通用的MPEG2編碼和H264（MPEGPART10AVC）編碼等相應(yīng)地，信道編碼是為了對(duì)抗信道中的噪音和衰減，通過(guò)增加冗余，如校驗(yàn)碼等，來(lái)提高抗干擾能力以及糾錯(cuò)能力4。22最佳變長(zhǎng)編碼凡是能載荷一定的信息量，且碼字的平均長(zhǎng)度最短，可分離的變長(zhǎng)碼的碼字稱為最佳變長(zhǎng)碼。為此必須將概率大的信息符號(hào)編以短的碼字，概率小的符號(hào)編以長(zhǎng)的碼字，使得平均碼字長(zhǎng)度最短。能獲得最佳編碼的方法主要有香農(nóng)（SHANNON）、費(fèi)諾（FANO）、哈夫曼（HUFFMAN）編碼等。221香農(nóng)編碼方法香農(nóng)第一定理指出了平均碼長(zhǎng)與信源之間的關(guān)系，同時(shí)也指出了可以通過(guò)編碼使平均碼長(zhǎng)達(dá)到極限值，這是一個(gè)很重要的極限定理。如何構(gòu)造這種碼香農(nóng)第一定理指出，選擇每個(gè)碼字的長(zhǎng)度KI滿足下式IXIKIXI1,（2I1）就可以得到這種碼。這種編碼方法就是香農(nóng)編碼。香農(nóng)編碼法冗余度稍大，實(shí)用性不大，但有重要的理論意義。編碼步驟如下1）將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列P（X1）P（X2）P（XN）（22）2）確定滿足下列不等式整數(shù)碼長(zhǎng)KILOG2PXIKILOG2PXI1（23）3為了編成唯一可譯碼，計(jì)算第I個(gè)消息的累加概率PIPXK（21K4）4將累加概率PI變成二進(jìn)制數(shù)。5取PI二進(jìn)制數(shù)的小數(shù)點(diǎn)后KI位即為該消息符號(hào)的二進(jìn)制碼字。設(shè)信源共7個(gè)符號(hào)消息，其概率和累加概率如表21，則其香農(nóng)編碼過(guò)程如表21。所以信源符號(hào)的平均碼長(zhǎng)為（25）符號(hào)碼元/143IPK71IA平均信息傳輸率即編碼效率為碼元BIT8310462KXHR（26）表21香農(nóng)編碼過(guò)程信源消息符號(hào)AI符號(hào)概率PAI）累加概率PILOGPAI碼字長(zhǎng)度KI碼字A1A2A3A4A5A6A7020019018017015010001002039057074089099234241248256274334666333334700000101110010111101111110222費(fèi)諾編碼方法費(fèi)諾編碼，它編碼后的費(fèi)諾碼要比香農(nóng)碼的平均碼長(zhǎng)小，消息傳輸速率大，編碼效率高，但它屬于概率匹配編碼它不是最佳的編碼方法。費(fèi)諾編碼步驟（1）將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列。NPP21（2）將依次排列的信源符號(hào)按概率值分為兩大組，使兩個(gè)組的概率之和近似相同，并對(duì)各組賦予一個(gè)二進(jìn)制碼元“0”和“1”。（3）將每一大組的信源符號(hào)再分為兩組，使劃分后的兩個(gè)組的概率之和近似相同，并對(duì)各組賦予一個(gè)二進(jìn)制符號(hào)“0”和“1”。（4）如此重復(fù)，直至每個(gè)組只剩下一個(gè)信源符號(hào)為止。5信源符號(hào)所對(duì)應(yīng)的碼字即為費(fèi)諾碼。對(duì)表21中信源消息進(jìn)行費(fèi)諾編碼，則編碼過(guò)程如表22。則該費(fèi)諾編碼的平均碼長(zhǎng)（27）信息傳輸速率（28）表22費(fèi)諾編碼過(guò)程消息符號(hào)AI消息概率P（AI）第一次分組第二次分組第三次分組第四次分組二元碼字碼長(zhǎng)KIA10200002A201900103A30180110113A40170102A501501103A6010011104A7001111111114顯然費(fèi)諾碼要比上述香農(nóng)碼的平均碼長(zhǎng)小，消息傳輸速率大，說(shuō)明編碼效率高。223哈夫曼編碼方法碼元BIT953074261KXHR符號(hào)碼元/742IAP71I哈夫曼編碼是一種常見(jiàn)的壓縮方法。它的基本原理是按照信號(hào)出現(xiàn)概率大小順序排列信源信號(hào)，并設(shè)法按逆序分配碼字字長(zhǎng)，使編碼的碼字是可辨識(shí)的。哈夫曼編碼步驟（1）首先把信源中的消息出現(xiàn)的頻率從小到大排列。（2）每一次選出頻率最小的兩個(gè)值，作為二叉樹(shù)的兩個(gè)葉子節(jié)點(diǎn)，將和作為它們的根節(jié)點(diǎn)，這兩個(gè)葉子節(jié)點(diǎn)不再參與比較，新的根節(jié)點(diǎn)參與比較。（3）重復(fù)2，直到最后得到和為1的根節(jié)點(diǎn)。（4）將形成的二叉樹(shù)的左節(jié)點(diǎn)標(biāo)0，右節(jié)點(diǎn)標(biāo)1。把從最上面的根節(jié)點(diǎn)到最下面的葉子節(jié)點(diǎn)途中遇到的0，1序列串起來(lái)，就得到了各個(gè)符號(hào)的編碼。對(duì)表21中的信源數(shù)據(jù)進(jìn)行哈夫曼編碼，編碼過(guò)程如表23。表23哈夫曼編碼過(guò)程信源符號(hào)AI概率PAI編碼過(guò)程碼字WI碼長(zhǎng)KIA102002603503906101102A201902002603500391112A3018019020002610003A4017018001910013A5015001710103A60100101104A7001101114該哈夫曼碼的平均碼長(zhǎng)為（29）符號(hào)碼元/27KIAP71I信息傳輸速率（210）碼元/BIT960721KXHR由此可見(jiàn)，哈夫曼編碼的平均碼長(zhǎng)最小，消息傳輸速率最大，編碼效率最高。哈夫曼編碼是用概率匹配方法進(jìn)行信源編碼。他有兩個(gè)明顯的特點(diǎn)一是哈夫曼碼的編碼方法保證了概率大的符號(hào)對(duì)應(yīng)于短碼，概率小的符號(hào)對(duì)應(yīng)于長(zhǎng)嗎，充分利用了短碼；二是縮減信源的最后兩個(gè)碼字總是最后一位不同，從而保證哈夫曼編碼是即時(shí)碼6。哈弗曼編碼幾乎是所有壓縮算法的基礎(chǔ)，其實(shí)這個(gè)算法并不復(fù)雜，簡(jiǎn)單的理解就是，如何用更短的BIT來(lái)編碼數(shù)據(jù)。我們知道普通的編碼都是定長(zhǎng)的，比如常用的ASCII編碼,每個(gè)字符都是8個(gè)BIT字符編碼A00101001B00101010C00101011這樣，計(jì)算機(jī)就能很方便的把由0和1組成的數(shù)據(jù)流解析成原始信息，但我們知道，在很多情況下，數(shù)據(jù)文件中的字符出現(xiàn)的概率是不均勻的，比如在一篇英語(yǔ)文章中，字母“E”出現(xiàn)的頻率最高，“Z”最低，如果我們使用不定長(zhǎng)的BIT編碼，頻率高的字母用比較短的編碼表示，頻率低的字母用長(zhǎng)的編碼表示，豈不是可以大大縮小文件的空間嗎但這就要求編碼要符合“前綴編碼”的要求，即較短的編碼不能是任何較長(zhǎng)的編碼的前綴，這樣解析的時(shí)候才不會(huì)混淆，比如下面的編碼方法就符合前綴原則字符編碼A0B10C110D1110E11110根據(jù)這個(gè)碼表，下面一段數(shù)據(jù)就可以唯一解析成原始信息了1110010101110110111100010DABBDCEAAB要生成這種編碼，最方便的就是用二叉樹(shù)，考察一下下面這個(gè)樹(shù)圖22二叉樹(shù)圖把要編碼的字符放在二叉樹(shù)的葉子上，所有的左節(jié)點(diǎn)是0，右節(jié)點(diǎn)是1，從根瀏覽到葉子上，因?yàn)樽址荒艹霈F(xiàn)在樹(shù)葉上，任何一個(gè)字符的路徑都不會(huì)是另一字符路徑的前綴路徑，符合前綴原則編碼就可以得到字符編碼A00B010C011D10E11現(xiàn)在我們可以開(kāi)始考慮壓縮的問(wèn)題，如果有一篇只包含這五個(gè)字符的文章，而這幾個(gè)字符的出現(xiàn)的次數(shù)如下A6次B15次C2次D9次E1次用過(guò)用定長(zhǎng)的編碼，每個(gè)字符3BIT，這篇文章總長(zhǎng)度為3631532393199（211）而用上面用二叉樹(shù)生成的編碼，總長(zhǎng)度為2631522292180（212）顯然，這顆樹(shù)還可以進(jìn)一步優(yōu)化，使得編碼更短，比如下面的編碼圖23二叉樹(shù)圖生成的數(shù)據(jù)長(zhǎng)度為3611542294163213可以看出，構(gòu)造更優(yōu)的二叉樹(shù)，原則就是權(quán)重越大的葉子，距離根應(yīng)該越近，而我們的終級(jí)目標(biāo)是生成“最優(yōu)”的二叉樹(shù)，最優(yōu)二叉樹(shù)必須符合下面兩個(gè)條件所有上層節(jié)點(diǎn)都大于等于下層節(jié)點(diǎn)。某節(jié)點(diǎn)，設(shè)其較大的子節(jié)點(diǎn)為，較小的子節(jié)點(diǎn)為，下的任一層的所有節(jié)點(diǎn)都應(yīng)大于等于下的該層的所有節(jié)點(diǎn)。上面這個(gè)例子是比較簡(jiǎn)單的，實(shí)際的文件中，一個(gè)字節(jié)有256種可能的取值，所以二叉樹(shù)的葉子節(jié)點(diǎn)多達(dá)256個(gè)，最終的樹(shù)形可能非常復(fù)雜，但有一種非常精巧的算法可以快速地建起一棵最優(yōu)二叉樹(shù)，這種算法由DHUFFMAN（戴哈夫曼）提出，下面我們先來(lái)介紹哈弗曼算法的步驟，然后再來(lái)證明通過(guò)這么簡(jiǎn)單的步驟得出的樹(shù)形確實(shí)是一棵最優(yōu)二叉樹(shù)。哈夫曼算法的步驟是這樣的從各個(gè)節(jié)點(diǎn)中找出最小的兩個(gè)節(jié)點(diǎn)，給它們建一個(gè)父節(jié)點(diǎn)，值為這兩個(gè)節(jié)點(diǎn)之和。然后從節(jié)點(diǎn)序列中去除這兩個(gè)節(jié)點(diǎn)，加入它們的父節(jié)點(diǎn)到序列中。重復(fù)上面兩個(gè)步驟，直到節(jié)點(diǎn)序列中只剩下唯一一個(gè)節(jié)點(diǎn)。這時(shí)一棵最優(yōu)二叉樹(shù)就已經(jīng)建成了，它的根就是剩下的這個(gè)節(jié)點(diǎn)。比如上面的例子，哈弗曼樹(shù)建立的過(guò)程如下1列出原始的節(jié)點(diǎn)數(shù)據(jù)圖24原始節(jié)點(diǎn)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é)合圖5如此循環(huán)，最終得到一個(gè)最優(yōu)二叉樹(shù)圖28最優(yōu)二叉樹(shù)圖生成的數(shù)據(jù)文件長(zhǎng)度為3611542294163下面我們用逆推法來(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)化。然后往前步進(jìn)，節(jié)點(diǎn)序列中不斷地減少一個(gè)節(jié)點(diǎn)，增加兩個(gè)節(jié)點(diǎn)，在步進(jìn)過(guò)程中將始終保持是一棵最優(yōu)二叉樹(shù)，這是因?yàn)榘凑展ヂ鼧?shù)的建立過(guò)程，新增的兩個(gè)節(jié)點(diǎn)是當(dāng)前節(jié)點(diǎn)序列中最小的兩個(gè)，其他的任何兩個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)都大于（或等于）這兩個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)，只要前一步是最優(yōu)二叉樹(shù)，其他的任何兩個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)就一定都處在它們的父節(jié)點(diǎn)的上層或同層，所以這兩個(gè)節(jié)點(diǎn)一定處在當(dāng)前二叉樹(shù)的最低一層。這兩個(gè)新增的節(jié)點(diǎn)是最小的，所以無(wú)法和其他上層節(jié)點(diǎn)對(duì)換。符合我們前面說(shuō)的最優(yōu)二叉樹(shù)的第一個(gè)條件。只要前一步是最優(yōu)二叉樹(shù)，由于這兩個(gè)新增的節(jié)點(diǎn)是最小的，即使同層有其他節(jié)點(diǎn)，也無(wú)法和同層其他節(jié)點(diǎn)重新結(jié)合，產(chǎn)生比它們的父節(jié)點(diǎn)更小的上層節(jié)點(diǎn)來(lái)和同層的其他節(jié)點(diǎn)對(duì)換。它們的父節(jié)點(diǎn)小于其他節(jié)點(diǎn)的父節(jié)點(diǎn)，它們又小于其他所有節(jié)點(diǎn)，只要前一步符合最優(yōu)二叉樹(shù)的第二個(gè)條件，到這一步仍將符合。這樣一步步逆推下去，在這個(gè)過(guò)程中哈弗曼樹(shù)每一步都始終保持著是一棵最優(yōu)二叉樹(shù)。23游程編碼231游程長(zhǎng)度游程長(zhǎng)度RLRUNLENGTH，簡(jiǎn)稱游程或游長(zhǎng)，指的是由字符或信號(hào)取樣值構(gòu)成的數(shù)據(jù)流中各個(gè)字符重復(fù)出現(xiàn)而形成的字符的長(zhǎng)度。如果給出了形成串的字符，串的長(zhǎng)度以及串的位置，就能恢復(fù)出原來(lái)的數(shù)據(jù)流，游程長(zhǎng)度編碼RLC就是用二進(jìn)制碼字給出這些信息的一類方法。232游程編碼算法游程編碼的基本原理是用一個(gè)符號(hào)值或串長(zhǎng)代替具有相同值的連續(xù)符號(hào)（連續(xù)符號(hào)構(gòu)成了一段連續(xù)的“游程”，游程編碼因此而得名），使符號(hào)長(zhǎng)度少于原始數(shù)據(jù)的長(zhǎng)度。只在各行或者各列數(shù)據(jù)的代碼發(fā)生變化時(shí)，一次記錄該代碼及相同代碼重復(fù)的個(gè)數(shù)，從而實(shí)現(xiàn)數(shù)據(jù)的壓縮。在二元序列中，只有兩種符號(hào)，即“0”和“1”，這些符號(hào)可連續(xù)出現(xiàn)，連“0”這一段稱為“0”游程，連“1”這一段稱為“1”游程。它們的長(zhǎng)度分別稱為游程長(zhǎng)度L0和LL?！?”游程和“L”游程總是交替出現(xiàn)的。如果規(guī)定二元序列是以“0”開(kāi)始，第一個(gè)游程是“0”游程，第二個(gè)必為“1”游程，第三個(gè)又是“0”游程等等。對(duì)于隨機(jī)的二元序列，各游程長(zhǎng)度將是隨機(jī)變量，其取值可為1，2，3，直到無(wú)限。將任何二元序列變換成一一對(duì)應(yīng)的游程長(zhǎng)度序列，再按哈夫曼編碼或其他方法處理以達(dá)到壓縮碼率的目的9。233游程編碼特點(diǎn)游程編碼仍是變長(zhǎng)碼，有其固有的缺點(diǎn)，及需要大量的緩沖和優(yōu)質(zhì)的信道。此外，編程長(zhǎng)度可以從一直到無(wú)限，這在碼字的選擇和碼表的建立方面都有困難，實(shí)際應(yīng)用是尚需采用某些措施來(lái)改進(jìn)。一般情況下游程長(zhǎng)度越長(zhǎng)，其概率越小，這在以前的計(jì)算中也可以看見(jiàn)，而且將隨著長(zhǎng)度的增大漸進(jìn)向零。對(duì)于小概率的碼字，其長(zhǎng)度為達(dá)到概率匹配或較長(zhǎng)，損失不會(huì)太大，也就是對(duì)平均碼字長(zhǎng)度影響較小。再按哈夫曼編碼或其他方法處理以達(dá)到壓縮碼率的目的。234幾種基于游程相關(guān)性的數(shù)據(jù)壓縮方案1）共前綴碼共前綴碼編碼時(shí)也是按照一定規(guī)律用盡量短的碼字來(lái)表示游程形式的初始測(cè)試數(shù)據(jù)，但該編碼壓縮方案進(jìn)一步考慮了相鄰游程之間存在的聯(lián)系。如果相鄰游程的長(zhǎng)度在同一組，則它們對(duì)應(yīng)碼字的前綴是相同的即共前綴，可以用一個(gè)標(biāo)志位來(lái)表示這些相鄰游程除第一個(gè)游程以外的其他游程的前綴，這樣數(shù)據(jù)壓縮率得以進(jìn)一步提高。同組共前綴碼的前綴和后綴的位數(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)位DONTCARESBIT填充時(shí)，要盡量時(shí)這種影響降到最低。所謂無(wú)關(guān)位是指無(wú)論它們的取值是0還是1都不會(huì)影響測(cè)試結(jié)果。不過(guò)由此也可看出待測(cè)試數(shù)據(jù)的游程長(zhǎng)度加上2所對(duì)應(yīng)的FDR碼就是相應(yīng)的共前綴碼，若這兩個(gè)相差為2的游程長(zhǎng)度在同一組內(nèi)，則碼字長(zhǎng)度并沒(méi)有增加，不會(huì)影響壓縮效果。共前綴碼的前綴都是以1開(kāi)始，以0結(jié)束的數(shù)字串，所以當(dāng)相鄰游程長(zhǎng)度在同一組時(shí)，可以用數(shù)字0來(lái)表示后面游程的碼字前綴，后綴則不變，這樣碼字的長(zhǎng)度進(jìn)一步縮短。下面給出一個(gè)共前綴編碼的實(shí)例編碼前的初始測(cè)試數(shù)據(jù)00000000110000001000000000000010000000000000001（47位）；編碼后的碼字11010010001100101110000100011（29位）?？梢?jiàn)數(shù)據(jù)串00000000000001和0000000000000001的游程長(zhǎng)度分別為13和15，都在第三組，前綴都為1110，所以后一游程的碼字前綴用標(biāo)志位0表示，其碼字為00011。2）共游程碼前面介紹的共前綴碼是利用游程長(zhǎng)度同組的前綴相同，用標(biāo)志位0加碼字后綴來(lái)表示后面的游程，從而進(jìn)一步壓縮初始測(cè)試數(shù)據(jù)。共游程碼（SHARINGRUNLENGTHCODE，SRLC）與共前綴碼的編碼方案類似，該方案注意到初始測(cè)試數(shù)據(jù)中有的相鄰游程是相同的，于是就用一個(gè)標(biāo)志位來(lái)表示后面的相同游程，所以該方案被稱為共游程碼。顯然該編碼方案的數(shù)據(jù)壓縮率比共前綴碼高一些，不考慮相鄰游程的長(zhǎng)度相同的前提下，編碼方法與共前綴碼相同。對(duì)共游程碼編碼方案，如果有若干相鄰游程相同，則后面的一個(gè)或多個(gè)相同游程都可以用唯一的標(biāo)志位來(lái)代替，從而大大減少了編碼碼字的長(zhǎng)度，即進(jìn)一步提高了測(cè)試數(shù)據(jù)壓縮率。共游程碼的前綴都是以“1”開(kāi)頭以“0”結(jié)尾的數(shù)字串，沒(méi)有以“0”開(kāi)頭的前綴，所以可以用數(shù)字0來(lái)作為相鄰相同游程的標(biāo)志位，即后面相鄰相同游程的碼字只有1位。顯然相鄰相同游程的長(zhǎng)度越長(zhǎng)，測(cè)試數(shù)據(jù)壓縮率就越高。由于初始測(cè)試數(shù)據(jù)中存在著大量的無(wú)關(guān)位，可以有意識(shí)的對(duì)它們進(jìn)行賦值填充，以增加長(zhǎng)度相同的相鄰游程的數(shù)量，從而降低碼字的長(zhǎng)度。例如數(shù)據(jù)串00000000000X000000000001，其中的X是無(wú)關(guān)位，如果把它填充為0則該數(shù)據(jù)串是一個(gè)長(zhǎng)度為23的0游程，由編碼碼表可知其對(duì)應(yīng)的碼字為11101011（8位）；如果把無(wú)關(guān)位賦值為1，則數(shù)據(jù)串變成了兩個(gè)長(zhǎng)度都為11的相鄰0游程，其對(duì)應(yīng)的碼字為1101110（7位），使碼字的長(zhǎng)度減少了1位，提高了數(shù)據(jù)壓縮效果。3）共前綴連續(xù)長(zhǎng)度碼共前綴連續(xù)長(zhǎng)度碼（COPREFIXALRUNLENGTHCODES，CPRL）也考慮了相鄰游程的相關(guān)性。如果相鄰游程的長(zhǎng)度在同一組內(nèi)，則同組的后面的相鄰游程的前綴可以省略，則編碼后碼字的前綴越長(zhǎng)，則壓縮效果越明顯。由于初始測(cè)試數(shù)據(jù)集中存在大量的無(wú)關(guān)位，可以適當(dāng)?shù)膶?duì)這些無(wú)關(guān)位進(jìn)行賦值填充，增加0游程的長(zhǎng)度，這些游程長(zhǎng)度在同組的概率很高。該編碼方案為了增加0游程的長(zhǎng)度，對(duì)填充后的測(cè)試數(shù)據(jù)采取了差分處理，即把測(cè)試數(shù)據(jù)等長(zhǎng)劃分并進(jìn)行異或邏輯運(yùn)算。通過(guò)對(duì)ISCAS89基準(zhǔn)電路硬故障測(cè)試集的分析對(duì)不同的電路各組共前綴次數(shù)的分布不均勻，因此CPRL碼引入了一個(gè)參變量M,M表示確定的組號(hào)，M取值不同，編碼結(jié)果就不同。但對(duì)于具體的編碼，M是事先確定好的常數(shù)，顯然M的取值范圍在1和最大組號(hào)之間。CPRL碼的具體編碼方法如下若待編碼的0游程長(zhǎng)度所在的組號(hào)M,則直接用FDR碼字表示CPRL碼字，原因是組號(hào)小的碼字前綴位數(shù)也短；若待編碼的0游程長(zhǎng)度所在的組號(hào)M，且相鄰游程長(zhǎng)度在同一組內(nèi)，則后面的游程CPRL碼字由該游程長(zhǎng)度對(duì)應(yīng)的FDR碼字省略前綴，并在剩下的碼字后綴后面加上一個(gè)標(biāo)志位0組成，同組相鄰的第一個(gè)游程的CPRL碼字由對(duì)應(yīng)的FDR碼字加上標(biāo)志位1組成；若待編碼的0游程長(zhǎng)度所在的組號(hào)M，且相鄰游程長(zhǎng)度不在同一組內(nèi)，則各游程的CPRL碼字由對(duì)應(yīng)的FDR碼字加一位標(biāo)志位組成。下面給出一個(gè)CPRL碼的編碼實(shí)例（參變量M1）編碼前的初始測(cè)試數(shù)據(jù)00000010000001000011100101111010010；對(duì)應(yīng)的差分測(cè)試數(shù)據(jù)00000010000000000011000100001000101（35位）；差分后的測(cè)試數(shù)據(jù)對(duì)應(yīng)的FDR碼1100001101010010011010100101（28位）；對(duì)應(yīng)的CPRL碼字11000011010001001110101001（26位）。24本章小結(jié)本章主要介紹了信源編碼中的幾種最佳信源變長(zhǎng)編碼香農(nóng)（SHANNON）、費(fèi)諾（FANO）、哈夫曼（HUFFMAN）編碼，以及這幾種編碼的編碼過(guò)程,然后主要介紹了哈夫曼樹(shù)的構(gòu)成步驟，以及游程編碼的算法和編碼特點(diǎn)。第3章游程編碼以及哈夫曼編31游程編碼游程編碼是針對(duì)于二元序列的壓縮編碼方法，在二元序列中，只有兩種符號(hào)，即“0”游程和“1”游程，“0”游程和“L”游程總是交替出現(xiàn)的。如果規(guī)定二元序列是以“0”開(kāi)始，第一個(gè)游程是“0”游程，第二個(gè)必為“1”游程，第三個(gè)又是“0”游程等等。而對(duì)二元序列游程編碼主要是針對(duì)于每個(gè)游程長(zhǎng)度以及總共有多少個(gè)游程。我在C語(yǔ)言編碼過(guò)程中主要針對(duì)這兩方面進(jìn)行編碼，即通過(guò)對(duì)“0”、“1”的變換次數(shù)來(lái)確定二元序列中總共有多少個(gè)游程；然后在確定每一個(gè)游程中游程的長(zhǎng)度。兩者綜合即實(shí)現(xiàn)對(duì)于二元序列的游程編碼。用游程編碼壓縮數(shù)據(jù)時(shí)，首先要計(jì)算每次連續(xù)相同字符的個(gè)數(shù)，然后將每次連續(xù)相同的字符及個(gè)數(shù)保存起來(lái)。這種壓縮數(shù)據(jù)的方法,連續(xù)相同的字符及出現(xiàn)連續(xù)相同的次數(shù)越多，壓縮比就越大，反之，壓縮比就越小。數(shù)據(jù)壓縮算法流程如下1打開(kāi)源數(shù)據(jù)文件和壓縮后的數(shù)據(jù)文件；2從源數(shù)據(jù)文件中讀取字符,并把它放入一個(gè)寄存器中，然后再循環(huán)讀取后面的字符，并與寄存器中的字符相比較。如果相等，則計(jì)數(shù)器加1，否則，把寄存器中的字符和計(jì)數(shù)器中數(shù)寫入壓縮數(shù)據(jù)文件中，然后再把寄存器中字符不相等的字符放入寄存器中，并把計(jì)數(shù)器置1。游程編碼數(shù)據(jù)壓縮算法流程圖如圖31數(shù)據(jù)解碼算法流程如下1打開(kāi)壓縮數(shù)據(jù)文件和恢復(fù)文件；2從壓縮文件中循環(huán)讀出字符和該字符連續(xù)的個(gè)數(shù),在恢復(fù)文件中連續(xù)寫入從壓縮文件中讀出的字符,寫的次數(shù)等于該字符連續(xù)的個(gè)數(shù)。游程編碼數(shù)據(jù)解壓縮算法流程圖32圖31游程編碼數(shù)據(jù)壓縮算法游程圖打開(kāi)源數(shù)據(jù)文件與壓縮后的數(shù)據(jù)文件從元數(shù)據(jù)文件中讀取一個(gè)字符將字符放入寄存器計(jì)數(shù)器COUNT1是否讀到文件尾在源數(shù)據(jù)文件中讀下一個(gè)字符讀取的字符與寄存器中的字符是否相等計(jì)數(shù)器加1COUNTCOUNT1關(guān)閉源數(shù)據(jù)文件和壓縮文件將寄存器字符和計(jì)數(shù)器中的數(shù)寫入數(shù)據(jù)壓縮文件將最后讀取的字符放入寄存器計(jì)數(shù)器置1COUNT1YESNOYES圖32游程編碼數(shù)據(jù)解碼流程圖打開(kāi)源數(shù)據(jù)文件與恢復(fù)后的數(shù)據(jù)文件判斷是否為文件尾從壓縮文件中讀取字符以及該字符的連續(xù)的個(gè)數(shù)讀取的字符及連續(xù)個(gè)數(shù)是否寫完在恢復(fù)文件中寫入從壓縮文件中讀取的字符關(guān)閉恢復(fù)數(shù)據(jù)文件和數(shù)據(jù)壓縮文件YESNONOYES32哈夫曼編碼過(guò)程哈夫曼編碼是一種常見(jiàn)的壓縮方法。它的基本原理是按照信號(hào)出現(xiàn)概率大小順序排列信源信號(hào)，并設(shè)法按逆序分配碼字字長(zhǎng)，使編碼的碼字是可辨識(shí)的。要完成哈夫曼的編碼需要首先建立哈夫曼樹(shù)，之后對(duì)所有字符根據(jù)權(quán)重進(jìn)行編碼，最后再對(duì)文件內(nèi)容進(jìn)行編碼。建立哈夫曼樹(shù)的思想。首先定義適合哈夫曼樹(shù)的節(jié)點(diǎn)類型，需要定義的有當(dāng)前節(jié)點(diǎn)的字符，當(dāng)前節(jié)點(diǎn)的左子、右子和父親指針。在建立哈夫曼樹(shù)之前還需要對(duì)出現(xiàn)的字符和權(quán)重進(jìn)行統(tǒng)計(jì)和記錄，并且定義一個(gè)可以篩選出最小權(quán)重的函數(shù)。初始化樹(shù)節(jié)點(diǎn)之后開(kāi)始建立哈夫曼樹(shù)。先在所有可能出現(xiàn)的字符中篩選出當(dāng)前權(quán)重最小的兩個(gè)字符，將這兩個(gè)字符分別作為新節(jié)點(diǎn)的左子和右子建立一個(gè)小的二叉樹(shù)，并將兩個(gè)字符的權(quán)重之和賦值給新節(jié)點(diǎn)，將新二叉樹(shù)放入篩選字符中，再將篩選過(guò)的兩個(gè)字符從篩選列表中淘汰掉。依次對(duì)列表中剩下的字符進(jìn)行權(quán)重最小的篩選，直到根節(jié)點(diǎn)（如果編碼表共有N個(gè)字符，則2N1就為最終根節(jié)點(diǎn)）為止，也就是當(dāng)篩選列表為空的時(shí)候，哈夫曼樹(shù)即建立完成。對(duì)于哈夫曼編碼樹(shù)來(lái)說(shuō)，由于哈夫曼編碼是前綴碼，所以所有要編碼的字符最終都將是這顆樹(shù)的葉子節(jié)點(diǎn)，而其它節(jié)點(diǎn)并沒(méi)有真正的字符意義。即當(dāng)哈夫曼編碼樹(shù)建立之后，對(duì)樹(shù)的所有葉子節(jié)點(diǎn)進(jìn)行打印可知道是否有字符遺漏或多余。建立哈夫曼樹(shù)的流程圖如圖33圖33構(gòu)建哈夫曼樹(shù)流程圖構(gòu)建完哈夫曼樹(shù)后，根據(jù)建立哈夫曼樹(shù)建立哈夫曼碼表。建立編碼表時(shí)要根據(jù)每個(gè)出現(xiàn)的字符的權(quán)重對(duì)建立的哈夫曼樹(shù)的每個(gè)葉子節(jié)點(diǎn)進(jìn)行編碼。編碼時(shí)要從葉子節(jié)點(diǎn)出發(fā)向根節(jié)點(diǎn)進(jìn)行逆向編碼。判斷如果當(dāng)前節(jié)點(diǎn)為左子則對(duì)其編碼0，如果當(dāng)前節(jié)點(diǎn)為右子則對(duì)其編碼1。以此類推進(jìn)行編碼直到根節(jié)點(diǎn)為止。此時(shí)的編碼是逆向的，所以需要將碼值逆向存儲(chǔ)。依次對(duì)每一個(gè)葉子節(jié)點(diǎn)進(jìn)行編碼操作，即可得到當(dāng)前哈夫曼樹(shù)的編碼表。構(gòu)建哈夫曼編碼表的算法流程圖如圖34圖33構(gòu)建哈夫曼編碼表的算法流程圖有了碼表就可以進(jìn)行編碼了。首先需要建立一個(gè)原始文件，在文件中輸入需要編碼的內(nèi)容。之后將文件打開(kāi)，將其中的內(nèi)容存儲(chǔ)到字符串中以便程序編碼調(diào)用。開(kāi)始對(duì)需要編碼的字符進(jìn)行編碼，將字符逐一讀取與剛剛建立的編碼表中的每個(gè)葉子節(jié)點(diǎn)代表的字符進(jìn)行比較，找出相同的對(duì)象，并將當(dāng)前節(jié)點(diǎn)的編碼打印到屏幕，并將編碼存入到新建的密碼文件當(dāng)中。編碼流程圖如圖34圖34編碼算法流程圖在解碼時(shí)先打開(kāi)密碼文件，將之前編碼后得到的密文內(nèi)容存儲(chǔ)到字符串中以便解碼調(diào)用。開(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)。以此類推，一直走到葉子節(jié)點(diǎn)為止，則當(dāng)前葉子節(jié)點(diǎn)所代表的字符即為前一段密文的解碼結(jié)果，。再對(duì)下一個(gè)字符依次從根節(jié)點(diǎn)開(kāi)始解碼，如此循環(huán)對(duì)每一段密文進(jìn)行解碼直到解碼結(jié)束。將解碼打印到屏幕，并將解碼結(jié)果存入到新的解碼文件當(dāng)中。在解碼之前，還應(yīng)該先確認(rèn)之前是否建立了哈夫曼樹(shù)并且是否構(gòu)建了編碼表。不過(guò)由于本次將A到Z都進(jìn)行了編碼，所以此步省略了，因?yàn)榫幋a表是唯一的。需要的時(shí)候可以在ENCODER函數(shù)中先進(jìn)行判定。圖35解碼算法流程圖33運(yùn)行結(jié)果對(duì)于二元序列00011100001111100011111111110000000000000111110000000000000即（3,0）（3,1（4,0）（5,1）3,010,113,05,113,0編碼圖解碼圖進(jìn)行完編碼后的平均碼長(zhǎng)為（31信息傳輸速率（32）壓縮前二元序列長(zhǎng)度為49，進(jìn)行游程編碼后序列長(zhǎng)度為36，再進(jìn)行哈夫曼編碼后序列長(zhǎng)度為29。即總的壓縮效率為59，而游程壓縮效率為80。所以進(jìn)行兩次編碼后的壓縮效率比單一一次的游程編碼的壓縮效率高很多。這次的仿真只是對(duì)于一段很短的二元序列，而且各游程長(zhǎng)度也很短，所以還不能過(guò)很好的體現(xiàn)出游程編碼的壓縮效率。但對(duì)于二值圖像序列的就能夠很好的體現(xiàn)出游程編碼的壓縮效率，然后在進(jìn)行哈夫曼編碼就能夠很好的體現(xiàn)出這種方法的壓縮效率。34本章小結(jié)游程編碼是一種簡(jiǎn)單的快捷的編碼方法，能夠有效的對(duì)二元序列進(jìn)行無(wú)損壓縮，一般情況下，游程長(zhǎng)度越大，其概率越小，而且隨著長(zhǎng)度的增大逐漸趨向零。對(duì)于小概率的碼字，其長(zhǎng)度未達(dá)到概率匹配或較長(zhǎng)，損失不會(huì)太大，也就對(duì)平均碼字長(zhǎng)度影響較小，這樣就可以對(duì)長(zhǎng)游程不嚴(yán)格按哈夫曼碼步驟進(jìn)行。哈夫曼碼是用概率匹配方法進(jìn)行信源編碼。它有兩明顯的個(gè)特點(diǎn)一是哈夫曼編碼方法保證了概率大的符號(hào)對(duì)應(yīng)于短碼，概率小的符號(hào)對(duì)應(yīng)于長(zhǎng)碼，充分利用了短碼；一是縮減信源的最后兩個(gè)碼字總是最后一位不同，從而保證哈夫曼編碼是即時(shí)碼。哈夫曼變長(zhǎng)碼的效率是相當(dāng)高的，它可以單個(gè)信源符號(hào)編碼或用L較小的信源序列編碼，對(duì)編碼器的設(shè)計(jì)來(lái)說(shuō)符號(hào)碼元/4PIK91碼元/14HRBITKX也簡(jiǎn)單的多。但應(yīng)當(dāng)注意要達(dá)到很高的效率仍然需要按長(zhǎng)序列來(lái)計(jì)算，這樣才能使平均碼字長(zhǎng)度降低。結(jié)論游程編碼是圖像壓縮的基本算法，因此對(duì)于二元相關(guān)信源數(shù)據(jù)編碼研究變得尤為重要。為此，本人對(duì)游程編碼壓縮原理做了深入的學(xué)習(xí)，并結(jié)合哈夫曼編碼把其應(yīng)用到二元相關(guān)信源數(shù)據(jù)的壓縮。經(jīng)過(guò)這段時(shí)間的學(xué)習(xí)與實(shí)踐，我對(duì)二元相關(guān)信源游程編碼與信號(hào)編碼的發(fā)展及現(xiàn)狀有了更深刻的認(rèn)識(shí)，意識(shí)到數(shù)據(jù)壓縮與解壓對(duì)于信息時(shí)代的巨大影響及其潛在的經(jīng)濟(jì)效益，并對(duì)MICROCSOFTVISUALC軟件有了進(jìn)一步的了解。經(jīng)過(guò)這一段的學(xué)習(xí)，我想我對(duì)于知識(shí)的獵取是有限的，關(guān)鍵是我學(xué)會(huì)了如何用認(rèn)真、嚴(yán)謹(jǐn)?shù)膶W(xué)習(xí)態(tài)度去面對(duì)工作，如何用自學(xué)的方法來(lái)處理問(wèn)題，如何把書籍和網(wǎng)上查找到的信息運(yùn)用到實(shí)踐中去。二元相關(guān)游程編碼一般不直接應(yīng)用與多灰度圖像，但比較適于二值圖像的編碼，例如傳真圖像的編碼等。為了達(dá)到較好的壓縮效果，二值圖像游程編碼需和其它一些編碼混合使用。本文中我才用游程編碼和哈夫曼編碼混合使用。游程壓縮作為數(shù)據(jù)壓縮技術(shù)的一個(gè)分支，理論淺顯，走過(guò)半個(gè)多世紀(jì)的離散余弦變換理論在數(shù)據(jù)壓縮領(lǐng)域至今不衰；近來(lái)，小波變換理論更使數(shù)據(jù)壓縮技術(shù)登峰造極，圖像壓縮的JPEG2000標(biāo)準(zhǔn)是小波理論傲視群雄?？梢灶A(yù)見(jiàn)，新的數(shù)學(xué)理論將不斷為數(shù)據(jù)壓縮技術(shù)輸入新鮮血液，因此數(shù)學(xué)理論決不可偏廢。最后，給出一點(diǎn)使用無(wú)損壓縮算法的建議。由于每種無(wú)損壓縮都有自己的適用范圍，壓縮比受不失真要求的限制，真正意義上高壓縮比的通用無(wú)損壓縮算法目前哈有待繼續(xù)研究。因此在選用算法之前需要對(duì)圖像數(shù)據(jù)進(jìn)行分析，使用時(shí)根據(jù)數(shù)據(jù)表現(xiàn)出的特點(diǎn)，利用算法的思想，靈活使用算法是提高壓縮比的有效手段。參考文獻(xiàn)1王增輝，雷加一種變游程編碼的測(cè)試數(shù)據(jù)壓縮方法理論與方法200952許川佩，董祥健一種交替游程編碼的SOC測(cè)試數(shù)據(jù)壓縮方法計(jì)算機(jī)工程與應(yīng)用2010，46（25）3劉娟，詹文法，黃忠基于交替變游程編碼的測(cè)試數(shù)據(jù)壓縮方法安慶師范學(xué)院學(xué)報(bào)201154詹文法，梁華國(guó)，時(shí)峰，黃正峰，歐陽(yáng)一鳴一種共游程的測(cè)試數(shù)據(jù)壓縮方案計(jì)算機(jī)研究與發(fā)展20085彭喜元，俞洋基于變游程編碼的測(cè)試數(shù)據(jù)壓縮算法電子學(xué)報(bào)200726于翔。數(shù)據(jù)壓縮技術(shù)分析。青海大學(xué)學(xué)報(bào)200287祝本明，劉桂華。一種改進(jìn)的游程編碼算法西南科技大學(xué)學(xué)報(bào)200798MICHALSTABNO，ROBERTWREMBELRHLBITMAPCOMPRESSIONTECHNIQUEBASEDONRUNLENGTHANDHUFFMANENCODINGINFORMATIONSYSTEMS20099CRISTIANOMAGULHARI,IVANILSBONATTI,PEDROLDPERESANADAPTIVERUNLENGTHENCODINGMETHODFORTHECOMPRESSIONOFELECTROCARDIOGRAMSMEDICALENGINEERING這些字符ISTICS測(cè)定（1）行無(wú)序，部分有序，并下令由一個(gè)索引值屬性，（2）索引的屬性不同的樞機(jī)主教伊蒂埃斯（多達(dá)20,000個(gè)不同的值），和（3）的數(shù)據(jù)集由100,000,000股行相對(duì)于比較RLHN和RLH效率壓縮位圖的修改。本文的結(jié)構(gòu)如下。第2部分介紹了基本本文中使用的定義和概念。第3節(jié)提出RLH和RLHN壓縮技術(shù)。第4節(jié)討論的實(shí)驗(yàn)結(jié)果RLH的，RLHN和華的評(píng)價(jià)。最后，第5節(jié)總結(jié)，并得出結(jié)論的文件。12造紙重點(diǎn)，貢獻(xiàn)和輪廓在本文中，我們提出了一個(gè)替代的位圖壓縮技術(shù)，提供精確的編碼（1）良好的查詢響應(yīng)時(shí)間和（2）的尺寸小壓縮的位圖。位圖壓縮技術(shù)我們開(kāi)發(fā)被稱為運(yùn)行長(zhǎng)度霍夫曼（RLH），的。同樣，在英國(guó)廣播公司（BBC）和華，建議技術(shù)基于游程長(zhǎng)度編碼。然而，它不同于英國(guó)廣播公司（BBC）和華就以下。首先，RLH計(jì)數(shù)位的值之間的距離1，而不是相同的值的連續(xù)位的長(zhǎng)度。該距離成為接下來(lái)編碼的符號(hào)哈夫曼編碼技術(shù)10。其次，RLH確實(shí)將位圖轉(zhuǎn)換為字提高了一個(gè)位圖的壓縮比。為了更好地支持位圖更新中，我們提出的一個(gè)變種的RLH壓縮的技術(shù)，稱為RLHN。RLHN一個(gè)位圖壓縮被分成N比特的長(zhǎng)度的話，則每個(gè)N位的字被壓縮RLH。RLH和RLHN壓縮技術(shù)實(shí)施和華實(shí)驗(yàn)比較。作為一個(gè)參考我們選擇華，因?yàn)閴嚎s位圖華提供更好的查詢響應(yīng)時(shí)間比位圖壓縮與BBC26,32。本文擴(kuò)展了我們以前的工作25就到RLHN的壓縮技術(shù)的發(fā)展接受字的長(zhǎng)度等于256，512，1024，2048位比較RLH，RLHN，和華就CPU時(shí)間和I/O處理時(shí)間這些字符ISTICS測(cè)定（1）行無(wú)序，部分有序，并下令由一個(gè)索引值屬性，（2）索引的屬性不同的樞機(jī)主教伊蒂埃斯（多達(dá)20,000個(gè)不同的值），和（3）的數(shù)據(jù)集由100,000,000股行相對(duì)于比較RLHN和RLH效率壓縮位圖的修改。本文的結(jié)構(gòu)如下。第2部分介紹了基本本文中使用的定義和概念。第3節(jié)提出RLH和RLHN壓縮技術(shù)。第4節(jié)討論的實(shí)驗(yàn)結(jié)果RLH的，RLHN和華的評(píng)價(jià)。最后，第5節(jié)總結(jié)，并得出結(jié)論的文件。2基本定義21位圖索引位圖索引是基于所謂的位圖。一位圖是一個(gè)位向量。從域的每一個(gè)值索引的屬性相關(guān)已自己的位圖。該每個(gè)位圖中的位的數(shù)目的數(shù)目等于行存儲(chǔ)了表T中。創(chuàng)建一個(gè)位圖值V索引屬性，A介紹了這些在T的行A值是V。在該位圖中，位編號(hào)N設(shè)置為“1”，如果A的第N行的價(jià)值等于V。否則位設(shè)置為0。位圖索引的概念說(shuō)明一個(gè)例子。讓我們考慮表的客戶和創(chuàng)建位圖索引其性別屬性，如圖所示。1。由于域索引的屬性只包含兩個(gè)不同的價(jià)值觀，指數(shù)是由兩個(gè)位圖。例如，第一位圖描述值女位設(shè)置為0，因?yàn)榈膶傩孕缘牡谝恍兄械闹凳遣皇且粋€(gè)女性22華BBC壓縮如前所述，華和BBC壓縮SION技術(shù)都是基于運(yùn)行長(zhǎng)度編碼。該運(yùn)行長(zhǎng)度編碼的基本思想包括編碼連續(xù)的比特具有相同的值的向量（無(wú)論是0或1）為（1）中的所有位共同的價(jià)值矢量（即，無(wú)論是“0”由零組成的一個(gè)矢量或1的向量組成的）和（2）的長(zhǎng)度矢量（即，具有相同值的位的數(shù)量）在編碼之前，位圖被分成詞。接著，詞語(yǔ)被分組為所謂的運(yùn)行。運(yùn)行組成的話，可以是填充或尾巴。填充代表一系列的比特組成的字相同的值。字表示序列的尾部?jī)蓚€(gè)“0”和“1”比特組成。填充被壓縮因?yàn)樗麄兺|(zhì)化的內(nèi)容，而尾巴沒(méi)有。英國(guó)廣播公司（BBC）和華之間的主要區(qū)別是英國(guó)廣播公司（BBC）劃分成8位字位向量，而華將其劃分為31位字。此外，英國(guó)廣播公司（BBC）使用四個(gè)不同類型的運(yùn)行時(shí)，根據(jù)填充的長(zhǎng)度和結(jié)構(gòu)的尾巴。議員只使用一個(gè)不同的運(yùn)行。說(shuō)明的WAH壓縮的總體思路一個(gè)例子。為了簡(jiǎn)單起見(jiàn)，讓我們假設(shè)使用一個(gè)32位的處理器。位圖的COM壓制是由5456位組成的，如圖中所示。2一26。華壓縮的位圖被執(zhí)行三個(gè)下面的步驟。在第一步驟中，位圖被分為若干組由31位組成的，如圖中所示。2灣在該示例中176創(chuàng)建組。在第二步驟中，相鄰的被合并成一個(gè)組含有相同位基，如圖中所示。2。由于第1組是異類，即，它是由“0”和“1”的位，它是不被合并與一組。組2175是同質(zhì)（0位組成），他們合并成一個(gè)大基，中圖表示。2C為2175組。本組包括174了31位。最后一組176，類似于第1組，是異質(zhì)的，它不能被與合并前組。作為結(jié)果合并組，三最終組被創(chuàng)建，如圖中所示。2三。在第三步驟中，被編碼的最后三個(gè)組如下所示（參見(jiàn)圖2中的32BIT字D）。第一組代表在第一次運(yùn)行的尾部。的最重要的位（最左邊）有值“0”表示一個(gè)尾巴。31下一頁(yè)位1組的原始位。第二組（A組2175）表示第二次運(yùn)行的填充。的最顯著位（位置31）被設(shè)置為“1”表示填充。在位置2的位30設(shè)置為0表示所有位原組2175值“0”，即填充用于壓縮組的所有位具有價(jià)值0。該其余的30位被用于編碼數(shù)字同質(zhì)群體充滿0在這個(gè)例子中，有174組。均質(zhì)的數(shù)量組所表示的二進(jìn)制值等于000000000000000000000010101110，存儲(chǔ)上在其余30位。最后31位，記為176組，代表第二次運(yùn)行的尾巴。的最在這組有顯著位值“0”表示一個(gè)尾巴。其余31位是原組176位。23霍夫曼編碼在霍夫曼編碼10，原始符號(hào)從壓縮的文件被替換的位串。更多一個(gè)給定的符號(hào)經(jīng)常出現(xiàn)在壓縮文件用于表示符號(hào)的較短的比特串。編碼后的符號(hào)和它們的相應(yīng)的位串表示為所謂哈夫曼樹(shù)。哈夫曼樹(shù)用于壓縮和解壓?；舴蚵幋a算法，用一個(gè)例子說(shuō)明。3RLH壓縮RLH技術(shù)中提出的壓縮位圖本文是根據(jù)游程長(zhǎng)度編碼和HUFFMAN編碼。有兩個(gè)特點(diǎn)RLH區(qū)別于其競(jìng)爭(zhēng)對(duì)手（英國(guó)廣播公司（BBC）和WAH）。首先，RLH計(jì)數(shù)的價(jià)值位之間的距離“1”，而比位向量的長(zhǎng)度相同的值，這是類似于增量編碼。其次，RLH不劃分位圖轉(zhuǎn)換為字，即整個(gè)位圖被壓縮。兩位值1之間的距離代表數(shù)位值“0”這兩個(gè)位之間。為在RLH，例如，位載體000011110100編碼以下的數(shù)字序列400012。我們假設(shè)的開(kāi)始和結(jié)束的位向量被解釋為位值“1”這種假設(shè)沒(méi)有任何影響的RLH壓縮技術(shù)的概念。代碼400012應(yīng)解釋如下。第一明確1中的編碼比特矢量000011110100處于隱式地從“1”（位）的四個(gè)位置的距離開(kāi)始的矢量在最左邊的位置，第二個(gè)“1”是在距離為0位，距離最近的1的左側(cè)第三1是在距離為0的位，從最近的“1”到左邊，等這樣的解決方案可以保證，當(dāng)密度減小，則位圖使用的符號(hào)的數(shù)編碼位圖降低過(guò)。運(yùn)行長(zhǎng)度編碼用距離將進(jìn)一步被稱為游程長(zhǎng)度編碼。修改后的運(yùn)行長(zhǎng)度編碼所編碼的位圖接下來(lái)HUFFMAN編碼壓縮。的輸入值霍夫曼編碼算法的頻率所有所有編碼位值“1”之間的距離位圖。一個(gè)常見(jiàn)的哈夫曼樹(shù)建頻率，它是進(jìn)一步用于編碼的距離。哈夫曼樹(shù)的大小影響的性能位圖的壓縮和解壓。從每形成的實(shí)驗(yàn)事實(shí)證明，霍夫曼的大小樹(shù)是小。例如，對(duì)于一個(gè)測(cè)試表，存儲(chǔ)100,000,000行和索引的基數(shù)屬性等于20000，哈