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