【文章內容簡介】 、右子和父親指針。在建立哈夫曼樹之前還需要對出現(xiàn)的字符和權重進行統(tǒng)計和記錄，并且定義一個可以篩選出最小權重的函數(shù)。 初始化樹節(jié)點之后開始建立哈夫曼樹。先在所有可能出現(xiàn)的字符中篩選出當前權重最小的兩個字符，將這兩個字符分別作為新節(jié)點的左子和右子建立一個小的二叉樹，并將兩個字符的權重之和賦值給新節(jié)點，將新二叉樹放入篩選字符中，再將篩選過的兩個字符從篩選列表中淘汰掉。依次對列表中剩下的字符進行權重最小的篩選，直到根節(jié)點（如果編碼表共有N個字符，則2*N1就為最終根節(jié)點）為止，也就是當篩選列表為空的時候，哈夫曼樹即建立完成。對于哈夫曼編碼樹來說，由于哈夫曼編碼是前綴碼，所以所有要編碼的字符最終都將是這顆樹的葉子節(jié)點，而其它節(jié)點并沒有真正的字符意義。即當哈夫曼編碼樹建立之后，對樹的所有葉子節(jié)點進行打印可知道是否有字符遺漏或多余。 建立哈夫曼樹的流程圖如圖33：圖33構建哈夫曼樹流程圖 構建完哈夫曼樹后，根據(jù)建立哈夫曼樹建立哈夫曼碼表。建立編碼表時要根據(jù)每個出現(xiàn)的字符的權重對建立的哈夫曼樹的每個葉子節(jié)點進行編碼。編碼時要從葉子節(jié)點出發(fā)向根節(jié)點進行逆向編碼。判斷如果當前節(jié)點為左子則對其編碼‘0’，如果當前節(jié)點為右子則對其編碼‘1’。以此類推進行編碼直到根節(jié)點為止。此時的編碼是逆向的，所以需要將碼值逆向存儲。依次對每一個葉子節(jié)點進行編碼操作，即可得到當前哈夫曼樹的編碼表。 構建哈夫曼編碼表的算法流程圖如圖34： 有了碼表就可以進行編碼了。首先需要建立一個原始文件，在文件中輸入需要編碼的內容。之后將文件打開，將其中的內容存儲到字符串中以便程序編碼調用。開始對需要編碼的字符進行編碼，將字符逐一讀取與剛剛建立的編碼表中的每個葉子節(jié)點代表的字符進行比較，找出相同的對象，并將當前節(jié)點的編碼打印到屏幕，并將編碼存入到新建的密碼文件當中。： 在解碼時先打開密碼文件，將之前編碼后得到的密文內容存儲到字符串中以便解碼調用。開始對密文的字符串進行解碼，樹索引從根節(jié)點開始走，當密文中的當前字符是‘0’的時候，則索引走向左子節(jié)點；當是‘1’的時候，則走向右子節(jié)點。以此類推，一直走到葉子節(jié)點為止，則當前葉子節(jié)點所代表的字符即為前一段密文的解碼結果。再對下一個字符依次從根節(jié)點開始解碼，如此循環(huán)對每一段密文進行解碼直到解碼結束。將解碼打印到屏幕，并將解碼結果存入到新的解碼文件當中。在解碼之前，還應該先確認之前是否建立了哈夫曼樹并且是否構建了編碼表。不過由于本次將‘a(chǎn)’到‘z’都進行了編碼，所以此步省略了，因為編碼表是唯一的。需要的時候可以在Encoder 函數(shù)中先進行判定。對于二元序列：00011100001111100011111111110000000000000111110000000000000即（3,0）（3,1)（4,0）（5,1）(3,0)(10,1)(13,0)(5,1)(13,0)編碼圖：解碼圖：進行完編碼后的平均碼長為： （31)信息傳輸速率： （32） 壓縮前二元序列長度為49，進行游程編碼后序列長度為36，再進行哈夫曼編碼后序列長度為29。即總的壓縮效率為59%，而游程壓縮效率為80%。所以進行兩次編碼后的壓縮效率比單一一次的游程編碼的壓縮效率高很多。這次的仿真只是對于一段很短的二元序列，而且各游程長度也很短，所以還不能過很好的體現(xiàn)出游程編碼的壓縮效率。但對于二值圖像序列的就能夠很好的體現(xiàn)出游程編碼的壓縮效率，然后在進行哈夫曼編碼就能夠很好的體現(xiàn)出這種方法的壓縮效率。游程編碼是一種簡單的快捷的編碼方法，能夠有效的對二元序列進行無損壓縮，一般情況下，游程長度越大，其概率越小，而且隨著長度的增大逐漸趨向零。對于小概率的碼字，其長度未達到概率匹配或較長，損失不會太大，也就對平均碼字長度影響較小，這樣就可以對長游程不嚴格按哈夫曼碼步驟進行。哈夫曼碼是用概率匹配方法進行信源編碼。它有兩明顯的個特點：一是哈夫曼編碼方法保證了概率大的符號對應于短碼，概率小的符號對應于長碼，充分利用了短碼；一是縮減信源的最后兩個碼字總是最后一位不同，從而保證哈夫曼編碼是即時碼。哈夫曼變長碼的效率是相當高的，它可以單個信源符號編碼或用L較小的信源序列編碼，對編碼器的設計來說也簡單的多。但應當注意要達到很高的效率仍然需要按長序列來計算，這樣才能使平均碼字長度降低。參考文獻 結論游程編碼是圖像壓縮的基本算法，因此對于二元相關信源數(shù)據(jù)編碼研究變得尤為重要。為此，本人對游程編碼壓縮原理做了深入的學習，并結合哈夫曼編碼把其應用到二元相關信源數(shù)據(jù)的壓縮。經(jīng)過這段時間的學習與實踐，我對二元相關信源游程編碼與信號編碼的發(fā)展及現(xiàn)狀有了更深刻的認識，意識到數(shù)據(jù)壓縮與解壓對于信息時代的巨大影響及其潛在的經(jīng)濟效益，并對Microcsoft Visual C++軟件有了進一步的了解。經(jīng)過這一段的學習，我想我對于知識的獵取是有限的，關鍵是我學會了如何用認真、嚴謹?shù)膶W習態(tài)度去面對工作，如何用自學的方法來處理問題，如何把書籍和網(wǎng)上查找到的信息運用到實踐中去。二元相關游程編碼一般不直接應用與多灰度圖像，但比較適于二值圖像的編碼，例如傳真圖像的編碼等。為了達到較好的壓縮效果，二值圖像游程編碼需和其它一些編碼混合使用。本文中我才用游程編碼和哈夫曼編碼混合使用。游程壓縮作為數(shù)據(jù)壓縮技術的一個分支，理論淺顯，走過半個多世紀的離散余弦變換理論在數(shù)據(jù)壓縮領域至今不衰；近來，小波變換理論更使數(shù)據(jù)壓縮技術登峰造極，圖像壓縮的JPEG2000標準是小波理論傲視群雄?？梢灶A見，新的數(shù)學理論將不斷為數(shù)據(jù)壓縮技術輸入新鮮血液，因此數(shù)學理論決不可偏廢。最后，給出一點使用無損壓縮算法的建議。由于每種無損壓縮都有自己的適用范圍，壓縮比受不失真要求的限制，真正意義上高壓縮比的通用無損壓縮算法目前哈有待繼續(xù)研究。因此在選用算法之前需要對圖像數(shù)據(jù)進行分析，使用時根據(jù)數(shù)據(jù)表現(xiàn)出的特點，利用算法的思想，靈活使用算法是提高壓縮比的有效手段。 參考文獻[1]王增輝， [2]許川佩，46（25）[3]劉娟，詹文法，[4]詹文法，梁華國，時峰，黃正峰，[5]彭喜元，[6]于翔。數(shù)據(jù)壓縮技術分析。[7]祝本明，劉桂華。[8]Michal Stabno，Robert :Bitmap pression technique based on runlength and Huffman [9]Cristiano M. Agulhari, Ivanil S. Bonatti, Pedro . Adaptive Run Length Encoding method for the pression Engineering amp。 [10]馬寧 ,朱福萌 ,尹志軍, [11][12]Bo Ye , QianZhao , DuoZhou , XiaohuaWang , MinLuo .Test data pression using alternating variable runlength code .INTEGRATION, the VLSI journal .2011[13]商進，[14]方建平,郝　躍,劉紅俠,李　 致謝 致謝本設計的完成是在我們的導師許成謙老師的細心指導下進行的。在每次設計遇到問題時老師不辭辛苦的講解才使得我的設計順利的進行。從設計的選題到資料的搜集直至最后設計的修改的整個過程中，花費了許老師很多的寶貴時間和精力，在此向導師表示衷心地感謝！導師嚴謹?shù)闹螌W態(tài)度，開拓進取的精神和高度的責任心都將使學生受益終生！ 還要感謝和我同一設計小組的幾位同學，是你們在我平時設計中和我一起探討問題，并指出我設計上的誤區(qū)，使我能及時的發(fā)現(xiàn)問題把設計順利的進行下去，沒有你們的幫助我不可能這樣順利地結稿，在此表示深深謝意。附錄 附錄1燕 山 大 學本科畢業(yè)設計（論文）開題報告課題名稱： 基于游程編碼數(shù)據(jù)壓縮算法設計與實現(xiàn)學院（系）： 電子工程系 年級專業(yè)： 09通信工程 學生姓名： 李悅 指導教師： 許成謙 完成日期： 2013年3月27日 選題的依據(jù)： 飛速發(fā)展的數(shù)據(jù)壓縮和圖像編碼技術，給多媒體數(shù)據(jù)傳輸和數(shù)據(jù)存儲帶來極大的快捷和便利。但在某些數(shù)據(jù)安全性要求比較苛刻的領域，現(xiàn)在比較流行和壓縮效果好的壓縮算法幾乎都屬于有損范疇，對原始數(shù)據(jù)壓縮處理后有不同程度的損傷，無法完全恢復，以至于不能滿足技術要求，現(xiàn)有的無損壓縮方法，如Huffman、LZ 系列、算術編碼等壓縮方法盡管在某些方面各有優(yōu)點，但壓縮效果比較差或者算法實現(xiàn)比較困難，因此十分有必要對無損壓縮算法進行研究。通過對游程編碼(Run LengthEncoding,RLE)進行研究,最后提出一種實現(xiàn)相對簡單、壓縮效果比較好的算法，采用該算法可以收到比較理想的效果，基本克服由于RLE自身特點而引起的數(shù)據(jù)擴張的現(xiàn)象。 目前已提出的比較有效的測試壓縮編碼算法主要有3大類：（1）基于統(tǒng)計的編碼壓縮算法，如哈夫曼（Huffman）編碼、VIHC編碼；（2）基于游程（runlength coding）的編碼壓縮算法，如Golomb編碼、FDR（Frequencydirected runlength）編碼算法、VariableTail算法、交替游程算法（alternating runlength）；（3）基于字典的編碼算法，如FixedLengthIndexDictionary算法、CDCR（bining dictionary coding and LFSR reseeding）。在以上編碼方法中，基于游程的編碼壓縮算法的效果是較好的，而且這種壓縮算法的解壓電路是不依賴于測試向量集的，這一點在待測電路重新設計或測試向量集合發(fā)生修改的情況下特別有用[1]。 基于游程編碼中的各種編碼:（1）Golomb碼和FDR碼都是基于測試集中0 個數(shù)多于1 個數(shù)的事實而對連續(xù)的0 進行編碼，并未把連續(xù)的0 和1 都進行編碼，因此存在一定的缺陷。(2)交替游程編碼（Alternative RunLengthEncoding），這種編碼算法既考慮測試數(shù)據(jù)中連續(xù)出現(xiàn)的“0”，也考慮連續(xù)出現(xiàn)的“1”，可以大大減少長度較短的游程數(shù)量，提高了編碼效率，硬件開銷也小，取得了比較好的效果[2][3]。(3)共游程編碼，這種編碼除了像傳統(tǒng)的變長到變長的編碼方案使用較短的代碼字來表示整個游程,還同時利用連續(xù)游程之間的相關性,對于連續(xù)的兩個或多個相同游程,后續(xù)每個游程僅用一位就可以表示。 理論分析和實驗結果證明本方案相對于傳統(tǒng)的游程編碼具有更好的數(shù)據(jù)壓縮效果[4]。（4）變游程編碼，這種編碼算法既考慮測試數(shù)據(jù)中連續(xù)出現(xiàn)的“0 ”，也考慮連續(xù)出現(xiàn)的“1 ”，大大減小了長度較短游程的數(shù)量，提高了編碼效率[5]。 另外，將測試集中的無關位（don’tcares ）用特定的方法指定后，這種變游程編碼可以直接對原始測試集操作，因此解碼不需要CSR，降低了解碼器的硬件開銷。總之，游程編碼壓縮數(shù)據(jù)的方法就是通過對連續(xù)出現(xiàn)的“0”、“1”進行進行相應的壓縮來減小信源大小，以實現(xiàn)數(shù)據(jù)壓縮。選題意義：通過本次的畢業(yè)設計，使我進一步的了解與掌握了游程編碼技術以及相關的壓縮編碼方面的知識，使我在課題的實施過程中學會已有知識的應用，培養(yǎng)自己自主學習和發(fā)現(xiàn)問題、解決問題的能力。 主要的研究內容、研究思路：設計內容 游程編碼是一種是一種相對比較簡單而且比較容易實現(xiàn)的無損壓縮編碼，在二元序列中，只有兩種符號，即“0”和“1”，這些符號可連續(xù)出現(xiàn)，連“0”這一段稱為“0”游程，連“1”這一段稱為“1”游程。它們的長度分別稱為游程長度L(0)和L(l)?！?”游程和“l(fā)”游程總是交替出現(xiàn)的。如果規(guī)定二元序列是以“0”開始，第一個游程是“0”游程，第二個必為“1”游程，第三個又是“0”游程等等。對于隨機的二元序列，各游程長度將是隨機變量，其取值可為1，2，3，…，直到無限。將任何(二元)序列變換成一一對應的游程長度序列，再按哈夫曼編碼或其他方法處理以達到壓縮碼率的目的 。本次課設主要是編寫一款c程序來完成游程的數(shù)據(jù)壓縮。設計思路熟悉游程編碼完成，能夠完成信源數(shù)據(jù)的游程壓縮，然后按照哈夫曼編碼方法處理數(shù)據(jù)已達到壓縮碼率的目的。熟悉vc++的應用方法，能夠比較熟悉的編寫讀懂程序。編寫c程序來實現(xiàn)游程壓縮以及相應的解壓縮。