基于游程編碼數(shù)據(jù)壓縮算法設(shè)計(jì)與實(shí)現(xiàn)

本科畢業(yè)設(shè)計(jì)〔論文〕基于游程編碼數(shù)據(jù)壓縮算法的設(shè)計(jì)與實(shí)現(xiàn)2023年6月本科畢業(yè)設(shè)計(jì)〔論文〕基于游程編碼數(shù)據(jù)壓縮算法的設(shè)計(jì)與實(shí)現(xiàn)燕山大學(xué)畢業(yè)設(shè)計(jì)〔論文〕任務(wù)書(shū)學(xué)院：里仁學(xué)院系級(jí)教學(xué)單位：學(xué)號(hào)學(xué)生姓名專(zhuān)業(yè)班級(jí)題目題目名稱基于游程編碼數(shù)據(jù)壓縮算法的設(shè)計(jì)與實(shí)現(xiàn)題目性質(zhì)1.理工類(lèi)：工程設(shè)計(jì)〔√〕；工程技術(shù)實(shí)驗(yàn)研究型〔〕；理論研究型〔〕；計(jì)算機(jī)軟件型〔〕；綜合型〔〕〔〕；3.外語(yǔ)類(lèi)〔〕；4.藝術(shù)類(lèi)〔〕題目類(lèi)型1.畢業(yè)設(shè)計(jì)〔√〕2.論文〔〕題目來(lái)源科研課題〔〕生產(chǎn)實(shí)際〔〕自選題目〔√〕主要內(nèi)容是基于游程編碼數(shù)據(jù)壓縮算法的設(shè)計(jì)與實(shí)現(xiàn)基本要求用c語(yǔ)言完成游程編碼，完成哈夫曼編碼；并畫(huà)出流程圖和結(jié)果圖，得出相應(yīng)結(jié)論。參考資料周次第1～4周第5～8周第9～13周第14～15周第16～17周應(yīng)完成的內(nèi)容熟悉課題，查閱、搜集相關(guān)資料，并完成開(kāi)題報(bào)告學(xué)習(xí)游程編碼、哈夫曼編碼方法，以及進(jìn)一步學(xué)習(xí)c語(yǔ)言編碼編寫(xiě)c語(yǔ)言程序?qū)崿F(xiàn)對(duì)數(shù)據(jù)的游程壓縮進(jìn)一步完善程序，并開(kāi)始撰寫(xiě)畢業(yè)論文總結(jié)畢設(shè)，完成論文，準(zhǔn)備辯論指導(dǎo)教師：職稱：教授2023年2月4日系級(jí)教學(xué)單位審批：年月日摘要本次畢業(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ù)的目的。本文主要介紹了信源編碼的分類(lèi)、獲得最正確編碼的方法、哈夫曼樹(shù)的構(gòu)建方法以及游程編碼的原理和實(shí)現(xiàn)技術(shù)，對(duì)游程長(zhǎng)度編碼技術(shù)做了較為全面地研究。包括游程數(shù)據(jù)壓縮、解壓縮過(guò)程，并給出了流程圖；哈夫曼數(shù)據(jù)壓縮、解壓縮過(guò)程，并給出流程圖和結(jié)果圖。關(guān)鍵詞游程編碼哈夫曼編碼壓縮AbstractThisgraduationdesignismainlybasedonrun-lengthcodingdatacompressionalgorithmdesignandimplementationofrun-lengthcodingisverysimple,encodinganddecodingspeed,wideapplication.Run-lengthcodingisacodingmethodforbinarysequence,isakindofcodingmethodforbinaryimage,theblackandwhitepixelsofcontinuous(run)indifferentcodecodeword.Run-lengthcodingisakindofsimplenondestructivedatacompressionmethod,theadvantageisthatofcompressionanddecompressionareveryfast.Itsmethodistocalculateacontinuouslengthofdatacompression,thedownsideistonotrepeatdatainsteadofincreasingcapacity.Run-lengthcodingisneedalotofbufferandchannel,sothedataaftertherun-lengthcodinginfurtherHuffmanencodinghasreachedmore.Sourcecodingismainlyintroducedinthispapertheclassification,theoptimalmethodofcoding,Huffmantree,constructionmethods,andtherun-lengthcodingprincipleandimplementationtechnology,thelengthoftherun-lengthencodingtechnologyisdonemorecomprehensiveresearch.Includingtherun-lengthdatacompressionanddecompressionprocess,andgivestheflowchart;Huffmandatacompressionanddecompressionprocess,chartandflowchartisgivenandtheresults.KeywordsRun-lengthcodingHuffmanencodingThecompression目錄TOC\o"1-3"\h\u摘要IAbstractII第1章緒論11.1課題背景1選題目的、意義22第2章信源編碼分類(lèi)32.1信源編碼32.1.1信源編碼簡(jiǎn)介3344567151515161619第3章游程編碼以及哈夫曼編20游程編碼20232830結(jié)論31參考文獻(xiàn)33致謝35附錄136附錄241附錄345附錄450緒論1.1課題背景信息時(shí)代人們對(duì)使用計(jì)算機(jī)獲取信息、處理信息的依賴性越來(lái)越高。多媒體計(jì)算機(jī)系統(tǒng)面臨的是數(shù)值、文字、語(yǔ)言、音樂(lè)、圖形、動(dòng)畫(huà)、靜圖像、電視視頻圖像等多種媒體承載的由模擬量轉(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，圖像尺寸為640×480pixete，每秒播放30幀的非壓縮彩色24位真彩色視頻的信息量為：640×480×3×30×60：1658880000Bytes，約為1.6GB(未含音頻信息的容量)，如果用650MB的CD-R來(lái)存放，需要3張。由此可見(jiàn)，在視頻信息的處理及應(yīng)用過(guò)程中壓縮及解壓縮技術(shù)是十分必要的[2]。數(shù)據(jù)壓縮技術(shù)主要采用兩種方法：一種是“保真率〞較高的無(wú)損壓縮法；另一種是以損失信息細(xì)節(jié)而換取較高壓縮比的有損壓縮法。無(wú)損壓縮雖然壓縮比不是很高，但復(fù)原后的文件與原數(shù)據(jù)文件完全相同，從而保證了信息細(xì)節(jié)的不失真，常用的方法有統(tǒng)計(jì)式壓縮法和字典式壓縮法，統(tǒng)計(jì)式壓縮法的編碼方案主要是霍夫曼(Hufman)編碼、算術(shù)編碼(AC)和游程長(zhǎng)度編碼(RLC)[2]。其中，游程長(zhǎng)度編碼是一種十分簡(jiǎn)單的壓縮方法，編碼／解碼的速度也非?？欤虼说玫搅藦V泛的應(yīng)用。許多圖形和視頻文件，如BMP，.TIF及.AVI等，都采用了這種壓縮方法，尤其適用于文本(文件)數(shù)據(jù)壓縮，它主要是去除文本中的冗余字符或字節(jié)中的冗余位以到達(dá)減少數(shù)據(jù)文件所占的存儲(chǔ)空間的目的[6]。飛速開(kāi)展的數(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)行哈夫曼編碼，采用該方法可以收到比擬理想的效果。選題目的、意義飛速開(kāi)展的數(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ú)損壓縮。本文主要介紹了信源編碼中的幾種最正確變長(zhǎng)編碼方法：香農(nóng)〔Shannon〕、費(fèi)諾〔Fano〕、哈夫曼〔Huffman〕編碼，以及這幾種編碼的編碼過(guò)程。然后主要描述了哈夫曼編碼方法以及如何構(gòu)造哈夫曼樹(shù)。然后詳細(xì)的介紹了游程編碼的編碼算法以及游程編碼的特點(diǎn)。畫(huà)出游程編碼哈夫曼編碼的流程圖，以及得出的結(jié)果圖，最后做出總結(jié)。第2章信源編碼分類(lèi)2.1信源編碼2.1.1信源編碼簡(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]。信源編碼就是從信源符號(hào)到碼符號(hào)的一種映射f，它把信源輸出的符號(hào)ui變換成碼元序列wi。信源編碼定義如圖2-1：圖2-1信源編碼定義圖信源編碼理論是信息論的一個(gè)重要分支,其理論根底是信源編碼的兩個(gè)定理。無(wú)失真信源編碼定理：是離散信源/數(shù)字信號(hào)編碼的根底；限失真信源編碼定理：是連續(xù)信源/模擬信號(hào)編碼的根底。信源編碼的分類(lèi)：離散信源編碼：獨(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ù)字化傳輸。2.1.4信源編碼的歷史最原始的信源編碼就是莫爾斯電碼，另外還有ASCII碼和電報(bào)碼都是信源編碼。但現(xiàn)代通信應(yīng)用中常見(jiàn)的信源編碼方式有：Huffman編碼、算術(shù)編碼、L-Z編碼，這三種都是無(wú)損編碼，另外還有一些有損的編碼方式。信源編碼的目標(biāo)就是使信源減少冗余，更加有效、經(jīng)濟(jì)地傳輸，最常見(jiàn)的應(yīng)用形式就是壓縮。另外，在數(shù)字電視領(lǐng)域，信源編碼包括通用的MPEG—2編碼和H.264〔MPEG—Part10AVC〕編碼等相應(yīng)地，信道編碼是為了對(duì)抗信道中的噪音和衰減，通過(guò)增加冗余，如校驗(yàn)碼等，來(lái)提高抗干擾能力以及糾錯(cuò)能力[4]。但凡能載荷一定的信息量，且碼字的平均長(zhǎng)度最短，可別離的變長(zhǎng)碼的碼字稱為最正確變長(zhǎng)碼。為此必須將概率大的信息符號(hào)編以短的碼字，概率小的符號(hào)編以長(zhǎng)的碼字，使得平均碼字長(zhǎng)度最短。能獲得最正確編碼的方法主要有：香農(nóng)〔Shannon〕、費(fèi)諾〔Fano〕、哈夫曼〔Huffman〕編碼等。香農(nóng)第一定理指出了平均碼長(zhǎng)與信源之間的關(guān)系，同時(shí)也指出了可以通過(guò)編碼使平均碼長(zhǎng)到達(dá)極限值，這是一個(gè)很重要的極限定理。如何構(gòu)造這種碼？香農(nóng)第一定理指出，選擇每個(gè)碼字的長(zhǎng)度Ki滿足下式I(xi)≤K﹤I(xi)+1,〔2-1〕就可以得到這種碼。這種編碼方法就是香農(nóng)編碼。香農(nóng)編碼法冗余度稍大，實(shí)用性不大，但有重要的理論意義。編碼步驟如下：1〕將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列p〔x1〕≥p〔x2〕≥…≥p〔xn〕〔2-2〕2〕確定滿足以下不等式整數(shù)碼長(zhǎng)Ki：-log2p(xi)≤Ki＜-log2p(xi)+1〔2-3〕3)為了編成唯一可譯碼，計(jì)算第i個(gè)消息的累加概率Pi=p(xk)〔2-4〕4)將累加概率Pi變成二進(jìn)制數(shù)。5)取Pi二進(jìn)制數(shù)的小數(shù)點(diǎn)后Ki位即為該消息符號(hào)的二進(jìn)制碼字。設(shè)信源共7個(gè)符號(hào)消息，其概率和累加概率如表2-1，那么其香農(nóng)編碼過(guò)程如表2-1。所以信源符號(hào)的平均碼長(zhǎng)為：〔2-5〕平均信息傳輸率即編碼效率為：〔2-6〕表2-1香農(nóng)編碼過(guò)程信源消息符號(hào)Ai符號(hào)概率P(Ai〕累加概率Pi-logp(Ai)碼字長(zhǎng)度Ki碼字A1A2A3A4A5A6A70333334700000101110010111101111110費(fèi)諾編碼，它編碼后的費(fèi)諾碼要比香農(nóng)碼的平均碼長(zhǎng)小，消息傳輸速率大，編碼效率高，但它屬于概率匹配編碼它不是最正確的編碼方法。費(fèi)諾編碼步驟：將信源消息符號(hào)按其出現(xiàn)的概率大小依次排列：?！?〕將依次排列的信源符號(hào)按概率值分為兩大組，使兩個(gè)組的概率之和近似相同，并對(duì)各組賦予一個(gè)二進(jìn)制碼元“0〞和“1〞?！?〕將每一大組的信源符號(hào)再分為兩組，使劃分后的兩個(gè)組的概率之和近似相同，并對(duì)各組賦予一個(gè)二進(jìn)制符號(hào)“0〞和“1〞?！?〕如此重復(fù)，直至每個(gè)組只剩下一個(gè)信源符號(hào)為止。(5)信源符號(hào)所對(duì)應(yīng)的碼字即為費(fèi)諾碼。對(duì)表2-1中信源消息進(jìn)行費(fèi)諾編碼，那么編碼過(guò)程如表2-2。那么該費(fèi)諾編碼的平均碼長(zhǎng)：〔2-7〕信息傳輸速率〔2-8〕表2-2費(fèi)諾編碼過(guò)程消息符號(hào)Ai消息概率P〔Ai〕第一次分組第二次分組第三次分組第四次分組二元碼字碼長(zhǎng)KiA100002A2100103A310113A410102A5101103A61011104A7111114顯然費(fèi)諾碼要比上述香農(nóng)碼的平均碼長(zhǎng)小，消息傳輸速率大，說(shuō)明編碼效率高。哈夫曼編碼是一種常見(jiàn)的壓縮方法。它的根本原理是按照信號(hào)出現(xiàn)概率大小順序排列信源信號(hào)，并設(shè)法按逆序分配碼字字長(zhǎng)，使編碼的碼字是可辨識(shí)的。哈夫曼編碼步驟：首先把信源中的消息出現(xiàn)的頻率從小到大排列。每一次選出頻率最小的兩個(gè)值，作為二叉樹(shù)的兩個(gè)葉子節(jié)點(diǎn)，將和作為它們的根節(jié)點(diǎn)，這兩個(gè)葉子節(jié)點(diǎn)不再參與比擬，新的根節(jié)點(diǎn)參與比擬。重復(fù)(2)，直到最后得到和為1的根節(jié)點(diǎn)。將形成的二叉樹(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ì)表2-1中的信源數(shù)據(jù)進(jìn)行哈夫曼編碼，編碼過(guò)程如表2-3。表2-3哈夫曼編碼過(guò)程信源符號(hào)Ai概率p(Ai)編碼過(guò)程碼字Wi碼長(zhǎng)KiA1 0.260.350.390.6101102A2 0.260.3500.391112A3 0.2000.2610003A40.1800.1910013A500.1710103A60101104A7101114該哈夫曼碼的平均碼長(zhǎng)為〔2-9〕信息傳輸速率〔2-10〕由此可見(jiàn)，哈夫曼編碼的平均碼長(zhǎng)最小，消息傳輸速率最大，編碼效率最高。哈夫曼編碼是用概率匹配方法進(jìn)行信源編碼。他有兩個(gè)明顯的特點(diǎn)：一是哈夫曼碼的編碼方法保證了概率大的符號(hào)對(duì)應(yīng)于短碼，概率小的符號(hào)對(duì)應(yīng)于長(zhǎng)嗎，充分利用了短碼；二是縮減信源的最后兩個(gè)碼字總是最后一位不同，從而保證哈夫曼編碼是即時(shí)碼[6]。哈弗曼編碼幾乎是所有壓縮算法的根底，其實(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ù)就可以唯一解析成原始信息了：

要生成這種編碼，最方便的就是用二叉樹(shù)，考察一下下面這個(gè)樹(shù)

圖2-2二叉樹(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ù)如下：

A:6次

B:15次

C:2次

D:9次

E:1次用過(guò)用定長(zhǎng)的編碼，每個(gè)字符3bit，這篇文章總長(zhǎng)度為：

3*6+3*15+3*2+3*9+3*1=99〔2-11〕

而用上面用二叉樹(shù)生成的編碼，總長(zhǎng)度為:

2*6+3*15+2*2+2*9+2*1=80〔2-12〕顯然，這顆樹(shù)還可以進(jìn)一步優(yōu)化，使得編碼更短，比方下面的編碼

圖2-3二叉樹(shù)圖生成的數(shù)據(jù)長(zhǎng)度為：

3*6+1*15+4*2+2*9+4*1=63(2-13)可以看出，構(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ù)，這種算法由D.Huffman〔戴?哈夫曼〕提出，下面我們先來(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ù)：圖2-4原始節(jié)點(diǎn)2)將最小的兩個(gè)節(jié)點(diǎn)C和E結(jié)合起來(lái)：圖2-5C和E結(jié)合3)再將新的節(jié)點(diǎn)和A組合起來(lái)

圖2-6新節(jié)點(diǎn)結(jié)合圖4)再將D節(jié)點(diǎn)參加

圖2-7新節(jié)點(diǎn)結(jié)合圖5)如此循環(huán)，最終得到一個(gè)最優(yōu)二叉樹(shù)

圖2-8最優(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)化。然后往前步進(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ù)。游程長(zhǎng)度RL(Run-Length)，簡(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)制碼字給出這些信息的一類(lèi)方法。游程編碼的根本原理是：用一個(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)度L(0)和L(l)?！?〞游程和“l(fā)〞游程總是交替出現(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]。游程編碼仍是變長(zhǎng)碼，有其固有的缺點(diǎn)，及需要大量的緩沖和優(yōu)質(zhì)的信道。此外，編程長(zhǎng)度可以從一直到無(wú)限，這在碼字的選擇和碼表的建立方面都有困難，實(shí)際應(yīng)用是尚需采用某些措施來(lái)改良。一般情況下游程長(zhǎng)度越長(zhǎng)，其概率越小，這在以前的計(jì)算中也可以看見(jiàn)，而且將隨著長(zhǎng)度的增大漸進(jìn)向零。對(duì)于小概率的碼字，其長(zhǎng)度為到達(dá)概率匹配或較長(zhǎng)，損失不會(huì)太大，也就是對(duì)平均碼字長(zhǎng)度影響較小。再按哈夫曼編碼或其他方法處理以到達(dá)壓縮碼率的目的。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)位(don’tcaresbit)填充時(shí)，要盡量時(shí)這種影響降到最低。所謂無(wú)關(guān)位是指無(wú)論它們的取值是0還是1都不會(huì)影響測(cè)試結(jié)果。不過(guò)由此也可看出待測(cè)試數(shù)據(jù)的游程長(zhǎng)度加上2所對(duì)應(yīng)的FDR碼就是相應(yīng)的共前綴碼，假設(shè)這兩個(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〕與共前綴碼的編碼方案類(lèi)似，該方案注意到初始測(cè)試數(shù)據(jù)中有的相鄰游程是相同的，于是就用一個(gè)標(biāo)志位來(lái)表示后面的相同游程，所以該方案被稱為共游程碼。顯然該編碼方案的數(shù)據(jù)壓縮率比共前綴碼高一些，不考慮相鄰游程的長(zhǎng)度相同的前提下，編碼方法與共前綴碼相同。對(duì)共游程碼編碼方案，如果有假設(shè)干相鄰游程相同，那么后面的一個(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)度碼〔Co-PrefixalRunLengthcodes，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ì)ISCAS-89基準(zhǔn)電路硬故障測(cè)試集的分析對(duì)不同的電路各組共前綴次數(shù)的分布不均勻，因此CPRL碼引入了一個(gè)參變量M,M表示確定的組號(hào)，M取值不同，編碼結(jié)果就不同。但對(duì)于具體的編碼，M是事先確定好的常數(shù)，顯然M的取值范圍在1和最大組號(hào)之間。CPRL碼的具體編碼方法如下：假設(shè)待編碼的0游程長(zhǎng)度所在的組號(hào)≤M,那么直接用FDR碼字表示CPRL碼字，原因是組號(hào)小的碼字前綴位數(shù)也短；假設(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組成；假設(shè)待編碼的0游程長(zhǎng)度所在的組號(hào)≥M，且相鄰游程長(zhǎng)度不在同一組內(nèi)，那么各游程的CPRL碼字由對(duì)應(yīng)的FDR碼字加一位標(biāo)志位組成。下面給出一個(gè)CPRL碼的編碼實(shí)例：〔參變量M=1〕編碼前的初始測(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位〕。本章主要介紹了信源編碼中的幾種最正確信源變長(zhǎng)編碼:香農(nóng)〔Shannon〕、費(fèi)諾〔Fano〕、哈夫曼〔Huffman〕編碼，以及這幾種編碼的編碼過(guò)程,然后主要介紹了哈夫曼樹(shù)的構(gòu)成步驟，以及游程編碼的算法和編碼特點(diǎn)。第3章游程編碼以及哈夫曼編游程編碼游程編碼是針對(duì)于二元序列的壓縮編碼方法，在二元序列中，只有兩種符號(hào)，即“0〞游程和“1〞游程，“0〞游程和“l(fā)〞游程總是交替出現(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ù)寫(xiě)入壓縮數(shù)據(jù)文件中，然后再把存放器中字符不相等的字符放入存放器中，并把計(jì)數(shù)器置1。游程編碼數(shù)據(jù)壓縮算法流程圖如圖3-1：數(shù)據(jù)解碼算法流程如下：1)翻開(kāi)壓縮數(shù)據(jù)文件和恢復(fù)文件；2)從壓縮文件中循環(huán)讀出字符和該字符連續(xù)的個(gè)數(shù),在恢復(fù)文件中連續(xù)寫(xiě)入從壓縮文件中讀出的字符,寫(xiě)的次數(shù)等于該字符連續(xù)的個(gè)數(shù):。游程編碼數(shù)據(jù)解壓縮算法流程圖3-2圖3-1游程編碼數(shù)據(jù)壓縮算法游程圖圖3-2游程編碼數(shù)據(jù)解碼流程圖哈夫曼編碼是一種常見(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)類(lèi)型，需要定義的有當(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è)字符，那么2*N-1就為最終根節(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ù)的流程圖如圖3-3：圖3-3構(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’。以此類(lèi)推進(jìn)行編碼直到根節(jié)點(diǎn)為止。此時(shí)的編碼是逆向的，所以需要將碼值逆向存儲(chǔ)。依次對(duì)每一個(gè)葉子節(jié)點(diǎn)進(jìn)行編碼操作，即可得到當(dāng)前哈夫曼樹(shù)的編碼表。構(gòu)建哈夫曼編碼表的算法流程圖如圖3-4：有了碼表就可以進(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)中。編碼流程圖如圖3.4：在解碼時(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)。以此類(lèi)推，一直走到葉子節(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(chǎn)’到‘z’都進(jìn)行了編碼，所以此步省略了，因?yàn)榫幋a表是唯一的。需要的時(shí)候可以在Encoder函數(shù)中先進(jìn)行判定。解碼圖：進(jìn)行完編碼后的平均碼長(zhǎng)為：〔3-1)信息傳輸速率：〔3-2〕壓縮前二元序列長(zhǎng)度為49，進(jìn)行游程編碼后序列長(zhǎng)度為36，再進(jìn)行哈夫曼編碼后序列長(zhǎng)度為29。即總的壓縮效率為59%，而游程壓縮效率為80%。所以進(jìn)行兩次編碼后的壓縮效率比單一一次的游程編碼的壓縮效率高很多。這次的仿真只是對(duì)于一段很短的二元序列，而且各游程長(zhǎng)度也很短，所以還不能過(guò)很好的表達(dá)出游程編碼的壓縮效率。但對(duì)于二值圖像序列的就能夠很好的表達(dá)出游程編碼的壓縮效率，然后在進(jìn)行哈夫曼編碼就能夠很好的表達(dá)出這種方法的壓縮效率。游程編碼是一種簡(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ō)也簡(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)編碼的開(kāi)展及現(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)題，如何把書(shū)籍和網(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)SOC測(cè)試數(shù)據(jù)壓縮方法.計(jì)算機(jī)工程與應(yīng)用.2023，46〔25〕[12]BoYe,QianZhao,DuoZhou,XiaohuaWang,MinLuo.Testdatacompressionusingalternatingvariablerun-lengthcode.INTEGRATION,theVLSIjournal.2023[14]方建平,郝躍,劉紅俠,SOC致謝本設(shè)計(jì)的完成是在我們的導(dǎo)師許成謙老師的細(xì)心指導(dǎo)下進(jìn)行的。在每次設(shè)計(jì)遇到問(wèn)題時(shí)老師不辭辛苦的講解才使得我的設(shè)計(jì)順利的進(jìn)行。從設(shè)計(jì)的選題到資料的搜集直至最后設(shè)計(jì)的修改的整個(gè)過(guò)程中，花費(fèi)了許老師很多的珍貴時(shí)間和精力，在此向?qū)煴硎局孕牡馗兄x！導(dǎo)師嚴(yán)謹(jǐn)?shù)闹螌W(xué)態(tài)度，開(kāi)拓進(jìn)取的精神和高度的責(zé)任心都將使學(xué)生受益終生！

還要感謝和我同一設(shè)計(jì)小組的幾位同學(xué)，是你們?cè)谖移綍r(shí)設(shè)計(jì)中和我一起探討問(wèn)題，并指出我設(shè)計(jì)上的誤區(qū)，使我能及時(shí)的發(fā)現(xiàn)問(wèn)題把設(shè)計(jì)順利的進(jìn)行下去，沒(méi)有你們的幫助我不可能這樣順利地結(jié)稿，在此表示深深謝意。附錄1燕山大學(xué)本科畢業(yè)設(shè)計(jì)〔論文〕開(kāi)題報(bào)告課題名稱：基于游程編碼數(shù)據(jù)壓縮算法設(shè)計(jì)與實(shí)現(xiàn)年級(jí)專(zhuān)業(yè)：09通信工程學(xué)生姓名：李?lèi)傊笇?dǎo)教師：許成謙完成日期：2023年3月27日選題的依據(jù)：飛速開(kāi)展的數(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)行研究。通過(guò)對(duì)游程編碼(RunLengthEncoding,RLE)進(jìn)行研究,最后提出一種實(shí)現(xiàn)相對(duì)簡(jiǎn)單、壓縮效果比擬好的算法，采用該算法可以收到比擬理想的效果，根本克服由于RLE自身特點(diǎn)而引起的數(shù)據(jù)擴(kuò)張的現(xiàn)象。目前已提出的比擬有效的測(cè)試壓縮編碼算法主要有3大類(lèi)：〔1〕基于統(tǒng)計(jì)的編碼壓縮算法，如哈夫曼〔Huffman〕編碼、VIHC編碼；〔2〕基于游程〔run-lengthcoding〕的編碼壓縮算法，如Golomb編碼、FDR〔Frequency-directedrun-length〕編碼算法、Variable-Tail算法、交替游程算法〔alternatingrun-length〕；〔3〕基于字典的編碼算法，如Fixed-Length-Index-Dictionary算法、CDCR〔combiningdictionarycodingandLFSRreseeding〕。在以上編碼方法中，基于游程的編碼壓縮算法的效果是較好的，而且這種壓縮算法的解壓電路是不依賴于測(cè)試向量集的，這一點(diǎn)在待測(cè)電路重新設(shè)計(jì)或測(cè)試向量集合發(fā)生修改的情況下特別有用[1]?；谟纬叹幋a中的各種編碼:〔1〕Golomb碼和FDR碼都是基于測(cè)試集中0個(gè)數(shù)多于1個(gè)數(shù)的事實(shí)而對(duì)連續(xù)的0進(jìn)行編碼，并未把連續(xù)的0和1都進(jìn)行編碼，因此存在一定的缺陷。(2)交替游程編碼〔AlternativeRun-LengthEncoding〕，這種編碼算法既考慮測(cè)試數(shù)據(jù)中連續(xù)出現(xiàn)的“0〞，也考慮連續(xù)出現(xiàn)的“1〞，可以大大減少長(zhǎng)度較短的游程數(shù)量，提高了編碼效率，硬件開(kāi)銷(xiāo)也小，取得了比擬好的效果[2][3]。(3)共游程編碼，這種編碼除了像傳統(tǒng)的變長(zhǎng)到變長(zhǎng)的編碼方案使用較短的代碼字來(lái)表示整個(gè)游程,還同時(shí)利用連續(xù)游程之間的相關(guān)性,對(duì)于連續(xù)的兩個(gè)或多個(gè)相同游程,后續(xù)每個(gè)游程僅用一位就可以表示。理論分析和實(shí)驗(yàn)結(jié)果證明本方案相對(duì)于傳統(tǒng)的游程編碼具有更好的數(shù)據(jù)壓縮效果[4]?！?〕變游程編碼，這種編碼算法既考慮測(cè)試數(shù)據(jù)中連續(xù)出現(xiàn)的“0〞，也考慮連續(xù)出現(xiàn)的“1〞，大大減小了長(zhǎng)度較短游程的數(shù)量，提高了編碼效率[5]。另外，將測(cè)試集中的無(wú)關(guān)位〔don’t-cares〕用特定的方法指定后，這種變游程編碼可以直接對(duì)原始測(cè)試集操作，因此解碼不需要CSR，降低了解碼器的硬件開(kāi)銷(xiāo)?？傊?，游程編碼壓縮數(shù)據(jù)的方法就是通過(guò)對(duì)連續(xù)出現(xiàn)的“0〞、“1〞進(jìn)行進(jìn)行相應(yīng)的壓縮來(lái)減小信源大小，以實(shí)現(xiàn)數(shù)據(jù)壓縮。選題意義：通過(guò)本次的畢業(yè)設(shè)計(jì)，使我進(jìn)一步的了解與掌握了游程編碼技術(shù)以及相關(guān)的壓縮編碼方面的知識(shí)，使我在課題的實(shí)施過(guò)程中學(xué)會(huì)已有知識(shí)的應(yīng)用，培養(yǎng)自己自主學(xué)習(xí)和發(fā)現(xiàn)問(wèn)題、解決問(wèn)題的能力。主要的研究?jī)?nèi)容、研究思路：設(shè)計(jì)內(nèi)容游程編碼是一種是一種相比照擬簡(jiǎn)單而且比擬容易實(shí)現(xiàn)的無(wú)損壓縮編碼，在二元序列中，只有兩種符號(hào)，即“0〞和“1〞，這些符號(hào)可連續(xù)出現(xiàn)，連“0〞這一段稱為“0〞游程，連“1〞這一段稱為“1〞游程。它們的長(zhǎng)度分別稱為游程長(zhǎng)度L(0)和L(l)?！?〞游程和“l(fā)〞游程總是交替出現(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á)壓縮碼率的目的。本次課設(shè)主要是編寫(xiě)一款c程序來(lái)完成游程的數(shù)據(jù)壓縮。設(shè)計(jì)思路1、熟悉游程編碼完成，能夠完成信源數(shù)據(jù)的游程壓縮，然后按照哈夫曼編碼方法處理數(shù)據(jù)已到達(dá)壓縮碼率的目的。2、熟悉vc++的應(yīng)用方法，能夠比擬熟悉的編寫(xiě)讀懂程序。3、編寫(xiě)c程序來(lái)實(shí)現(xiàn)游程壓縮以及相應(yīng)的解壓縮。畢業(yè)設(shè)計(jì)工作進(jìn)度安排〔1〕1-4周熟悉課題，查閱、搜集相關(guān)資料，并認(rèn)真學(xué)習(xí)研究并撰寫(xiě)開(kāi)題報(bào)告?！?〕5-10周學(xué)會(huì)運(yùn)用游程編碼壓縮/解壓信源數(shù)據(jù)的算法，并計(jì)算相應(yīng)數(shù)據(jù)；準(zhǔn)備中期報(bào)告〔3〕11-13周學(xué)習(xí)并編寫(xiě)相對(duì)應(yīng)的c語(yǔ)言程序已到達(dá)數(shù)據(jù)壓縮與解壓?！?)14-15周進(jìn)一步完善程序，并開(kāi)始撰寫(xiě)論文。〔5〕16-17周總結(jié)畢設(shè)，完成論文，準(zhǔn)備辯論。參考文獻(xiàn)SOC測(cè)試數(shù)據(jù)壓縮方法.計(jì)算機(jī)工程與應(yīng)用.2023，46〔25〕[12]BoYe,QianZhao,DuoZhou,XiaohuaWang,MinLuo.Testdatacompressionusingalternatingvariablerun-lengthcode.INTEGRATION,theVLSIjournal.2023[14]方建平,郝躍,劉紅俠,SOC附錄2燕山大學(xué)本科畢業(yè)設(shè)計(jì)〔論文〕文獻(xiàn)綜述課題名稱：基于游程編碼數(shù)據(jù)壓縮算法設(shè)計(jì)與實(shí)現(xiàn)年級(jí)專(zhuān)業(yè)：09通信工程學(xué)生姓名：李?lèi)傊笇?dǎo)教師：許成謙完成日期：2023年3月20日一、課題國(guó)內(nèi)外現(xiàn)狀數(shù)據(jù)壓縮技術(shù)主要采用兩種方法：一種是“保真率〞較高的無(wú)損壓縮法；另一種是以損失信息細(xì)節(jié)而換取較高壓縮比的有損壓縮法。無(wú)損壓縮雖然壓縮比不是很高，但復(fù)原后的文件與原數(shù)據(jù)文件完全相同，從而保證了信息細(xì)節(jié)的不失真，常用的方法有統(tǒng)計(jì)式壓縮法和字典式壓縮法，統(tǒng)計(jì)式壓縮法的編碼方案主要是霍夫曼(Hufman)編碼、算術(shù)編碼(AC)和游程長(zhǎng)度編碼(RLC)。其中，游程長(zhǎng)度編碼是一種十分簡(jiǎn)單的壓縮方法，編碼／解碼的速度也非?？欤虼说玫搅藦V泛的應(yīng)用。許多圖形和視頻文件，如BMP，.TIF及.AVI等，都采用了這種壓縮方法，尤其適用于文本(文件)數(shù)據(jù)壓縮，它主要是去除文本中的冗余字符或字節(jié)中的冗余位以到達(dá)減少數(shù)據(jù)文件所占的存儲(chǔ)空間的目的。研究主要成果基于游程編碼中的各種編碼:〔1〕Golomb碼和FDR碼都是基于測(cè)試集中0個(gè)數(shù)多于1個(gè)數(shù)的事實(shí)而對(duì)連續(xù)的0進(jìn)行編碼，并未把連續(xù)的0和1都進(jìn)行編碼，因此存在一定的缺陷[1]。(2)交替游程編碼〔AlternativeRun-LengthEncoding〕，這種編碼算法既考慮測(cè)試數(shù)據(jù)中連續(xù)出現(xiàn)的“0〞，也考慮連續(xù)出現(xiàn)的“1〞，可以大大減少長(zhǎng)度較短的游程數(shù)量，提高了編碼效率，硬件開(kāi)銷(xiāo)也小，取得了比擬好的效果[2][3]。(3)共游程編碼，這種編碼除了像傳統(tǒng)的變長(zhǎng)到變長(zhǎng)的編碼方案使用較短的代碼字來(lái)表示整個(gè)游程,還同時(shí)利用連續(xù)游程之間的相關(guān)性,對(duì)于連續(xù)的兩個(gè)或多個(gè)相同游程,后續(xù)每個(gè)游程僅用一位就可以表示。理論分析和實(shí)驗(yàn)結(jié)果證明本方案相對(duì)于傳統(tǒng)的游程編碼具有更好的數(shù)據(jù)壓縮效果[4]?！?〕變游程編碼，這種編碼算法既考慮測(cè)試數(shù)據(jù)中連續(xù)出現(xiàn)的“0〞，也考慮連續(xù)出現(xiàn)的“1〞，大大減小了長(zhǎng)度較短游程的數(shù)量，提高了編碼效率[5]。另外，將測(cè)試集中的無(wú)關(guān)位〔don’t-cares〕用特定的方法指定后，這種變游程編碼可以直接對(duì)原始測(cè)試集操作，因此解碼不需要CSR，降低了解碼器的硬件開(kāi)銷(xiāo)。三、開(kāi)展趨勢(shì)：游程壓縮作為數(shù)據(jù)壓縮技術(shù)的一個(gè)分支，理論淺顯，壓縮比之高已經(jīng)讓人刮目相看，走過(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é)理論決不可偏廢[7]。四、存在問(wèn)題游程編碼仍是變長(zhǎng)碼，有其固有的缺點(diǎn)，及需要大量的緩沖和優(yōu)質(zhì)的信道。此外，編程長(zhǎng)度可以從一直到無(wú)限，這在碼字的選擇和碼表的建立方面都有困難，實(shí)際應(yīng)用是尚需采用某些措施來(lái)改良。一般情況下游程長(zhǎng)度越長(zhǎng)，其概率越小，這在以前的計(jì)算中也可以看見(jiàn)，而且將隨著長(zhǎng)度的增大漸進(jìn)向零。對(duì)于小概率的碼字，其長(zhǎng)度為到達(dá)概率匹配或較長(zhǎng)，損失不會(huì)太大，也就是對(duì)平均碼字長(zhǎng)度影響較小。五、主要參考文獻(xiàn)SOC測(cè)試數(shù)據(jù)壓縮方法.計(jì)算機(jī)工程與應(yīng)用.2023，46〔25〕[12]BoYe,QianZhao,DuoZhou,XiaohuaWang,MinLuo.Testdatacompressionusingalternatingvariablerun-lengthcode.INTEGRATION,theVLSIjournal.2023[14]方建平,郝躍,劉紅俠,SOC附錄3燕山大學(xué)本科畢業(yè)設(shè)計(jì)〔論文〕中期報(bào)告課題名稱：基于游程編碼數(shù)據(jù)壓縮算法設(shè)計(jì)與實(shí)現(xiàn)年級(jí)專(zhuān)業(yè)：09通信工程學(xué)生姓名：李?lèi)傊笇?dǎo)教師：許成謙完成日期：2023年3月20日任務(wù)書(shū)中本階段工作目標(biāo)與任務(wù)要求任務(wù)書(shū)中本階段工作目標(biāo)是設(shè)計(jì)與完成c語(yǔ)言的游程編碼然后在進(jìn)行哈夫曼編碼，實(shí)現(xiàn)二元數(shù)據(jù)的無(wú)失真的壓縮編碼。本階段的任務(wù)要求：了解并掌握c語(yǔ)言的一些編碼算法；對(duì)二元數(shù)據(jù)進(jìn)行游程編碼并把編碼結(jié)果保存到指定位置；對(duì)進(jìn)行完游程編碼的二元序列在進(jìn)行哈夫曼編碼，得到壓縮數(shù)據(jù)，并保存到指定文件。目前已完成任務(wù)情況1、學(xué)習(xí)并掌握了更多的c語(yǔ)言程序設(shè)計(jì)方法，比方結(jié)構(gòu)體struct、c文件的讀寫(xiě)；2、游程編碼的程序流程圖如圖1；3、游程編碼又稱“運(yùn)行長(zhǎng)度編碼〞或“行程編碼〞，是一種統(tǒng)計(jì)編碼，該編碼屬于無(wú)損壓縮編碼，是柵格數(shù)據(jù)壓縮的重要編碼方法。對(duì)于二值圖有效。在對(duì)圖像數(shù)據(jù)進(jìn)行編碼時(shí)，沿一定方向排列的具有相同灰度值的像素可看成是連續(xù)符號(hào)，用字串代替這些連續(xù)符號(hào)，可大幅度減少數(shù)據(jù)量。游程編碼記錄方式有兩種：①逐行記錄每個(gè)游程的終點(diǎn)列號(hào)：②逐行記錄每個(gè)游程的長(zhǎng)度〔像元數(shù)〕第一種方式：AAABBACCCA圖1游程編碼流程圖這個(gè)柵格圖形就記為：A,3，B,5A,1，C,4，A,5第二種就記作：A,3，B,2A,1，C,3，A,1；4、利用c語(yǔ)言讀寫(xiě)方式來(lái)實(shí)現(xiàn)對(duì)二元序列游程編碼后在進(jìn)行哈夫曼編碼；5、哈夫曼編碼是一種常見(jiàn)的壓縮方法。它的根本原理是按照信號(hào)出現(xiàn)概率大小順序排列信源信號(hào)，并設(shè)法按逆序分配碼字字長(zhǎng)，使編碼的碼字是可辨識(shí)的；6、哈夫曼編碼步驟：1〕將信號(hào)源的符號(hào)按照出現(xiàn)概率遞減的順序排列?！沧⒁?，一定要遞減〕2〕將最下面的兩個(gè)最小出現(xiàn)概率入行合并相加，得到的霍夫曼編碼壓縮結(jié)果作為新符號(hào)的出現(xiàn)概率。3〕重復(fù)進(jìn)行步驟1和2直到概率相加的結(jié)果等于1為止。4〕在合并運(yùn)算時(shí)，概率大的符號(hào)用編碼0表示，概率小的符號(hào)用編碼1表示。5)記錄下概率為1處到當(dāng)前信號(hào)源符號(hào)之間的0，l序列，從而得到每個(gè)符號(hào)的編碼。三、存在的問(wèn)題和擬解決方法1、進(jìn)行游程編碼時(shí)不能確定首位游程是“0〞游程還是“1〞游程解決方法：編碼時(shí)直接規(guī)定首位是“1〞游程或是“0〞游程，即首位添加一個(gè)“1〞或一個(gè)“0〞，這樣有利于相應(yīng)的解碼；我假定首位游程為“1〞游程。如何運(yùn)用c語(yǔ)言進(jìn)行游程編碼解決方法：先記錄二元序列中游程個(gè)數(shù)，然后確定每個(gè)游程長(zhǎng)度，最后兩者結(jié)合求出結(jié)果及游程編碼結(jié)果，在求出每個(gè)游程在二元序列中所占百分比，以便于之后的哈夫曼編碼。如何對(duì)文件進(jìn)行哈夫曼編碼構(gòu)造出一個(gè)完整的哈夫曼樹(shù)，能夠很好的實(shí)現(xiàn)編碼和譯碼之間的互換過(guò)程，使用哈夫曼算法構(gòu)造哈夫曼樹(shù)過(guò)程，是從n棵知識(shí)一個(gè)根結(jié)點(diǎn)的樹(shù)組成的森林開(kāi)始的。在算法執(zhí)行中，哈夫曼樹(shù)是由假設(shè)干棵樹(shù)組成的森林，通過(guò)不斷地合作樹(shù)，最后得到一棵哈夫曼樹(shù)。附錄4燕山大學(xué)本科畢業(yè)設(shè)計(jì)〔論文〕外文翻譯課題名稱：基于游程編碼數(shù)據(jù)壓縮算法設(shè)計(jì)與實(shí)現(xiàn)年級(jí)專(zhuān)業(yè)：09通信工程學(xué)生姓名：李?lèi)傊笇?dǎo)教師：許成謙完成日期：2023年3月20日譯文：RLH：位圖壓縮技術(shù)基于游程長(zhǎng)度和Huffman編碼的原始研究文章關(guān)鍵詞：位圖索引位圖壓縮霍夫曼編碼運(yùn)行長(zhǎng)度編碼摘要在本文中，我們提出了一個(gè)應(yīng)用在壓縮位圖索引技術(shù)數(shù)據(jù)倉(cāng)庫(kù)。這種技術(shù)被稱為運(yùn)行長(zhǎng)霍夫曼〔RLH〕，是基于運(yùn)行長(zhǎng)度編碼和Huffman編碼。此外，我們提出了一個(gè)變種的RLH叫RLH-N。RLH-N的N位字壓縮位圖被分成RLH。RLH和實(shí)施RLH-N和實(shí)驗(yàn)比擬良好的字對(duì)齊混合〔WAH〕位圖壓縮技術(shù)，一直據(jù)報(bào)道，提供最短的查詢執(zhí)行時(shí)間。實(shí)驗(yàn)中討論本文說(shuō)明：〔1〕，RLH壓縮位圖小于相應(yīng)議員壓縮的位圖，而不管該索引的屬性的基數(shù)，〔2〕RLH-N壓縮位圖是小于相應(yīng)的華壓縮位圖一定范圍內(nèi)的基數(shù)，該索引的屬性，〔3〕RLH和RLH-N-壓縮位圖，提供更短的查詢響應(yīng)時(shí)間比華壓縮位圖，對(duì)于某些索引屬性的基數(shù)范圍，以及〔4〕RLH-N確保更短的更新時(shí)間的壓縮比RLH位圖。1介紹數(shù)據(jù)倉(cāng)庫(kù)〔DW〕是一個(gè)龐大的數(shù)據(jù)庫(kù)，集成來(lái)自多個(gè)存儲(chǔ)系統(tǒng)的數(shù)據(jù)企業(yè)內(nèi)的。通過(guò)這些數(shù)據(jù)的分析所謂的聯(lián)機(jī)分析處理〔OLAP〕應(yīng)用，系統(tǒng)蒸發(fā)散，基于復(fù)雜的查詢。OLAP查詢加盟多級(jí)表和過(guò)濾數(shù)據(jù)的事實(shí)表查詢謂詞的手段。通常情況下，分析數(shù)據(jù)存儲(chǔ)在事實(shí)數(shù)據(jù)表中，通過(guò)國(guó)外的參考尺寸鑰匙。其結(jié)果是，有許多事實(shí)記錄具有相同值的給定的外鍵。位圖索引[14,17]的根本數(shù)據(jù)之一衍生權(quán)證查詢優(yōu)化結(jié)構(gòu)。根本上，在最簡(jiǎn)單的形式中，位圖索引所謂的位圖組成的，其中每一個(gè)是一個(gè)位向量〔見(jiàn)第2局部〕。每個(gè)位被映射到一個(gè)排在索引表。如果一個(gè)位的值等于1，那么然后此位對(duì)應(yīng)的行具有一定的索引屬性值。查詢謂詞涉及的屬性可以通過(guò)位圖索引索引通過(guò)執(zhí)行按位AND，OR，或不快速答復(fù)位圖上的操作，這是一個(gè)很大的優(yōu)勢(shì)，位圖索引。一個(gè)位圖索引的大小在很大程度上依賴于的基數(shù)〔域?qū)挕乘饕龑傩?，即，一個(gè)位圖索引的大小增加時(shí)的基數(shù)索引的屬性增加。因此，屬性高基數(shù)〔寬域〕成為位圖索引非常大。因此，他們無(wú)法適應(yīng)主存儲(chǔ)器和訪問(wèn)數(shù)據(jù)的效率與支持等指標(biāo)惡化。1.1相關(guān)工作為了提高數(shù)據(jù)訪問(wèn)的效率支持位圖索引定義屬性高基數(shù)，以下兩種方法在研究文獻(xiàn)中已被提出，即：〔1〕擴(kuò)展的根本的位圖索引的結(jié)構(gòu)〔2〕位圖索引的壓縮技術(shù)。在第一種方法中，兩種主要的技術(shù)，一般所謂的分級(jí)，以及位切片，可以區(qū)分的。索引屬性的值是被分割成范圍。位圖的構(gòu)建代表一個(gè)給定的范圍內(nèi)的值，而不是一個(gè)獨(dú)特的值。一個(gè)位圖中的位表示的值是否一個(gè)給定的屬性的一排是在一個(gè)特定的范圍之內(nèi)。這技術(shù)也可以應(yīng)用于一個(gè)索引值時(shí)屬性被分成套。在文獻(xiàn)[12]中提出的技術(shù)可以被歸類(lèi)為分級(jí)更一般的形式。[12]套屬性值代表一起在一個(gè)位圖索引。這樣的技術(shù)減少存儲(chǔ)空間的高屬性基數(shù)。選擇的屬性值表示的這種索引是基于查詢模式頻率上的分布，以及屬性值。在[5]中，提出了另一種形式的分箱。這技術(shù)，稱為屬性映射，專(zhuān)注于管理箱分配到所有的索引屬性的總數(shù)。一屬性映射定義每個(gè)屬性的屬性，如使用該屬性的查詢的集合，分配值的屬性或?qū)傩缘木幋a值。的屬性被表示為位向量。一個(gè)查詢處理器需要擴(kuò)展，以便使用屬性映射。物業(yè)地圖支持多屬性查詢，不平等查詢或高選擇性查詢，它們更小于位圖索引。第二種方法是基于所謂的位切片指數(shù)[4,17,37]。的有序列表，它被定義每一個(gè)索引值屬性上的相同數(shù)量的n個(gè)比特來(lái)表示。作為一個(gè)因此，編碼值表中的格式為n位圖。該位圖被稱為位片。數(shù)據(jù)檢索和計(jì)算重刑支持的位分片索引算術(shù)metic[20]或通過(guò)一個(gè)專(zhuān)用的檢索功能[37]。另外，映射的數(shù)據(jù)結(jié)構(gòu)所需的編碼值映射到他們的真實(shí)值[37]。在第二種方法中，以提高工作效率位圖索引的高基數(shù)上定義的屬性，使用不同的位圖的壓縮技術(shù)。二在主無(wú)損耗的技術(shù)可以區(qū)分，即字節(jié)對(duì)齊的位圖壓縮錫永〔BBC〕[2]和字對(duì)齊混合〔WAH〕[26,33-35]。英國(guó)播送公司〔BBC〕和華是基于所謂的運(yùn)行長(zhǎng)度編碼。根本上，在這種編碼中，連續(xù)的向量。位相同的位值〔無(wú)論是''0''或''1''〕的一個(gè)實(shí)例的值〔例如，''1''〕，表示為計(jì)數(shù)的值。BBC英國(guó)播送公司〔BBC〕和華的根本區(qū)別是位圖劃分成8位字，而華分位圖到31位的話。更詳細(xì)的描述華第2.2節(jié)中給出。英國(guó)播送公司〔BBC〕和華提供最好的壓縮比位圖描述行有序索引屬性的值。否那么，壓縮比為惡化。對(duì)于密集均勻分布分布式數(shù)據(jù)位的值“1〞是密集的，但他們別離與比特值“0〞，因此，它可能是很難找到連續(xù)位向量的值''0''或''1''長(zhǎng)度為n的有8位，為英國(guó)播送公司〔BBC〕和N個(gè)31位華。然而，另一種技術(shù)，稱為近似編碼〔AE〕，用于壓縮位圖索引，提出了在[3]。AE提供近似查詢結(jié)果。假命中保證不會(huì)發(fā)生，即，滿足查詢的所有行謂詞納入查詢結(jié)果。此外，本誤報(bào)〔即準(zhǔn)確性，行不滿足有時(shí)包含在查詢查詢謂詞結(jié)果集〕的范圍從90％到100％。AE是基于Bloom過(guò)濾器。在AE，設(shè)置位圖被視為一個(gè)布爾值矩陣。的矩陣表示中以壓縮格式所謂的近似位圖〔AB〕。為了壓縮的布爾矩陣，它的編碼分為AB多個(gè)哈希函數(shù)，基于布魯姆過(guò)濾器。對(duì)于每一個(gè)向量在矩陣位，散列字符串HS是作為一個(gè)行號(hào)的功能構(gòu)造和矩陣中的列數(shù)。接下來(lái)，K獨(dú)立的哈希功能應(yīng)用了HS。所指出的位置哈希值被設(shè)置為''1''AB。在[11,18]，重新排序的列或行討論矩陣可以提高集群的相關(guān)細(xì)胞。這樣技術(shù)也可以適用于位圖索引被看作是矩陣。主要的想法是重新排列位圖矩陣，以獲得更好的聚類(lèi)''0''和''1''細(xì)胞，然后壓縮矩陣。由于采用了重新排序時(shí)，壓縮比可以得到改善。不幸的是，在重組問(wèn)題是NP-hard的[11]位圖索引，實(shí)施了重大市售CIAL數(shù)據(jù)庫(kù)管理系統(tǒng)中，可以是明確由用戶定義的，例如，甲骨文，SybaseIQ中，模型204，可以隱式地由系統(tǒng)使用，例如，MSSQL效勞器，IBMDB2。高級(jí)研究實(shí)現(xiàn)位圖索引表示由FastBit[24,15,19]RIDBit[15]。FastBit實(shí)現(xiàn)根本的位圖索引，分級(jí)，華位圖壓縮技術(shù)。在RIDBit，密集位圖存儲(chǔ)在B-樹(shù)的葉子。位圖替換的行ID，原本存儲(chǔ)在B樹(shù)葉子。稀疏將自動(dòng)轉(zhuǎn)換成位圖行ID。另一個(gè)研究領(lǐng)域相關(guān)的位圖索引COM的是文本PRESSION壓縮和倒排文件壓縮錫永在文本數(shù)據(jù)庫(kù)。幾個(gè)壓縮技術(shù)壓縮文本已經(jīng)提出，例如，[1,8,6]他們要么是基于哈夫曼編碼[10]或謝夫的Lempel編碼[38]。幾項(xiàng)技術(shù)也提出了用于壓縮倒排文件，例如，[7,13,23,29,30,39]。在[13,39]的作者提出了一種倒排索引列表中出現(xiàn)的壓縮技術(shù)項(xiàng)t為代表的數(shù)據(jù)文件中塊差距〔整數(shù)〕，而不是塊編號(hào)。差距進(jìn)一步由埃利亞斯編碼克編碼[7]。埃利亞斯克編碼正整數(shù)x由一個(gè)一元局部和二進(jìn)制的一局部。一元局部指定的比特?cái)?shù)必須代表X，而二進(jìn)制碼X位。編碼延伸埃利亞斯-克編碼。在編碼的x，一元局部被替換為克代碼。壽等人[23]的報(bào)告性能測(cè)試的壓縮唱倒名單〔偏移，文件的不同元素號(hào)〕，不同的編碼技術(shù)〔埃利亞斯克和編碼[7]以及哥倫布編碼[9]〕。Vo和莫法特[29]提出了一種壓縮技術(shù)，倒列表是基于一元編碼[31]。它是用于壓縮文件號(hào)碼。[30]比擬不同的方法來(lái)壓縮整數(shù)，包括埃利亞斯克和編碼，哥倫布編碼，和可變字節(jié)整數(shù)編碼。開(kāi)發(fā)的壓縮技術(shù)的倒立文件，壓縮整數(shù)，可能代表增量〔不同分配方法〕之間的值的序列。在RLH和RLHN壓榨技術(shù)，我們提出，距離位之間的值“1〞對(duì)應(yīng)這樣的增量。然而，RLH和RLH-N編碼這些三角洲哈夫曼編碼，而不是通過(guò)克或編碼。比擬RLH，RLH-N，和華就CPU時(shí)間和I/O處理時(shí)間;這些字符ISTICS測(cè)定：〔1〕行無(wú)序，局部有序，并下令由一個(gè)索引值屬性，〔2〕索引的屬性不同的樞機(jī)主教伊蒂埃斯〔多達(dá)20,000個(gè)不同的值〕，和〔3〕的數(shù)據(jù)集由100,000,000股行;相對(duì)于比擬RLH-N和RLH效率壓縮位圖的修改。本文的結(jié)構(gòu)如下。第2局部介紹了根本本文中使用的定義和概念。第3節(jié)提出RLH和RLH-N壓縮技術(shù)。第4節(jié)討論的實(shí)驗(yàn)結(jié)果RLH的，RLH-N和華的評(píng)價(jià)。最后，第5節(jié)總結(jié)，并得出結(jié)論的文件。1.2造紙重點(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ù)，稱為RLH-N。RLH-N一個(gè)位圖壓縮被分成N比特的長(zhǎng)度的話，那么每個(gè)N位的字被壓縮RLH。RLH和RLH-N壓縮技術(shù)實(shí)施和華實(shí)驗(yàn)比擬。作為一個(gè)參考我們選擇華，因?yàn)閴嚎s位圖華提供更好的查詢響應(yīng)時(shí)間比位圖壓縮與BBC[26,32]。本文擴(kuò)展了我們以前的工作[25]就到：RLH-N的壓縮技術(shù)的開(kāi)展接受字的長(zhǎng)度等于256，512，1024，2048位;比擬RLH，RLH-N，和華就CPU時(shí)間和I/O處理時(shí)間;這些字符ISTICS測(cè)定：〔1〕行無(wú)序，局部有序，并下令由一個(gè)索引值屬性，〔2〕索引的屬性不同的樞機(jī)主教伊蒂埃斯〔多達(dá)20,000個(gè)不同的值〕，和〔3〕的數(shù)據(jù)集由100,000,000股行;相對(duì)于比擬RLH-N和RLH效率壓縮位圖的修改。本文的結(jié)構(gòu)如下。第2局部介紹了根本本文中使用的定義和概念。第3節(jié)提出RLH和RLH-N壓縮技術(shù)。第4節(jié)討論的實(shí)驗(yàn)結(jié)果RLH的，RLH-N和華的評(píng)價(jià)。最后，第5節(jié)總結(jié)，并得出結(jié)論的文件。2根本定義位圖索引是基于所謂的位圖。一位圖是一個(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è)女性如前所述，華和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è)不同類(lèi)型的運(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è)下面的步驟。在第一步驟中，位圖被分為假設(shè)干組由31位組成的，如圖中所示。2灣在該例如中176創(chuàng)立組。在第二步驟中，相鄰的被合并成一個(gè)組含有相同位基，如圖中所示。2。由于第1組是異類(lèi)，即，它是由“0〞和“1〞的位，它是不被合并與一組。組2-175是同質(zhì)〔''0''位組成〕，他們合并成一個(gè)大基，中圖表示。2c為2-175組。本組包括174了31位。最后一組176，類(lèi)似于第1組，是異質(zhì)的，它不能被與合并前組。作為結(jié)果合并組，三最終組被創(chuàng)立，如圖中所示。2三。在第三步驟中，被編碼的最后三個(gè)組如下所示〔參見(jiàn)圖2中的32-bit字D〕。第一組代表在第一次運(yùn)行的尾部。的最重要的位〔最左邊〕有值“0〞表示一個(gè)尾巴。31下一頁(yè)位1組的原始位。第二組〔A組2-175〕表示第二次運(yùn)行的填充。的最顯著位〔位置31〕被設(shè)置為“1〞表示填充。在位置2的位30設(shè)置為''0''表示所有位原組2-175值“0〞，即填充用于壓縮組的所有位具有價(jià)值''0''。該其余的30位被用于編碼數(shù)字同質(zhì)群體充滿''0''在這個(gè)例子中，有174組。均質(zhì)的數(shù)量組所表示的二進(jìn)制值等于000000000000000000000010101110，存儲(chǔ)上在其余30位。最后31位，記為176組，代表第二次運(yùn)行的尾巴。的最在這組有顯著位值“0〞表示一個(gè)尾巴。其余31位是原組176位。2.3霍夫曼編碼在霍夫曼編碼[10]，原始符號(hào)從壓縮的文件被替換的位串。更多一個(gè)給定的符號(hào)經(jīng)常出現(xiàn)在壓縮文件用于表示符號(hào)的較短的比特串。編碼后的符號(hào)和它們的相應(yīng)的位串表示為所謂哈夫曼樹(shù)。哈夫曼樹(shù)用