數(shù)據(jù)壓縮結(jié)課論文

《數(shù)據(jù)壓縮結(jié)課論文》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、霍夫曼(Huffman)編碼目錄摘要·································································2關(guān)鍵詞·······························································2正文·······························································2霍夫曼編碼的背景·················································2二元霍夫曼碼的編碼················

2、································3r元霍夫曼（Huffman）碼編········································6Huffman碼的最佳性·················································7Huffman7碼的優(yōu)點(diǎn)和缺點(diǎn)···········································8霍夫曼（Huffman）編碼摘要：隨著科學(xué)技術(shù)的發(fā)展和需求，人們廣發(fā)地致力于對(duì)各種文本、圖片、語言、聲音、活動(dòng)圖像和影視信號(hào)等實(shí)際信源進(jìn)行了實(shí)用壓縮方法和技術(shù)的研究，使信源的數(shù)據(jù)

3、壓縮技術(shù)得以蓬勃發(fā)展和走向成熟。信源編碼主要分為無失真信源編碼和限失真信源編碼。香農(nóng)第一定理告訴我們，信源的信息熵是是信源進(jìn)行無失真編碼的理論極限值，也就是說，總能找到某種合適的編碼方法使編碼后信源的信息傳輸率R’7任意地逼近信源的信息熵而不存在任何失真。故數(shù)據(jù)壓縮技術(shù)中無失真信源編碼又常稱為熵編碼。熵編碼中比較重要的一種編碼方法叫霍夫曼編碼。那么，什么是霍夫曼編碼呢？它又有什么用呢？它的產(chǎn)生給我們先輩們解決了什么問題呢？以下，我為大家一一講解。關(guān)鍵詞：霍夫曼（Huffman）編碼碼樹無損壓縮正文：霍夫曼編碼的背景1951年，霍夫曼和他在MIT信息論的同學(xué)需要選擇是完成學(xué)期報(bào)告還是期末考試。導(dǎo)

4、師RobertM.Fano給他們的學(xué)期報(bào)告的題目是，尋找最有效的二進(jìn)制編碼。由于他們無法證明哪個(gè)已有編碼是最有效的，霍夫曼放棄對(duì)已有編碼的研究，轉(zhuǎn)向新的探索，最終發(fā)現(xiàn)了基于有序頻率二叉樹編碼的想法，并很快證明了這個(gè)方法是最有效的。霍夫曼使用自底向上的方法構(gòu)建二叉樹，避免了次優(yōu)算法Shannon-Fano編碼的最大弊端──自頂向下構(gòu)建樹。1952年，DavidA.Huffman在麻省理工攻讀博士時(shí)所發(fā)明的，并發(fā)表于《一種構(gòu)建極小多余編碼的方法》（AMethodfortheConstructionofMinimum-RedundancyCodes）一文。它是是可變字長編碼(VLC)的一種，該方法完

5、全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長度最短的碼字，有時(shí)稱之為最佳編碼，一般就叫作Huffman編碼?；舴蚵鼔嚎s是個(gè)無損的壓縮算法，一般用來壓縮文本和程序文件?；舴蚵鼔嚎s屬于可變代碼長度算法一族。意思是個(gè)體符號(hào)（例如，文本文件中的字符）用一個(gè)特定長度的位序列替代。因此，在文件中出現(xiàn)頻率高的符號(hào)，使用短的位序列，而那些很少出現(xiàn)的符號(hào)，則用較長的位序列。7二元霍夫曼碼的編碼其原理步驟如下：（1）將q個(gè)信源符號(hào)按概率分布P()的大小，以遞減次序排列起來，設(shè)（2）用0和1碼符號(hào)分別分配給概率最小的兩個(gè)信源符號(hào)，并將這兩個(gè)概率最小的信源符號(hào)合并成一個(gè)新符號(hào)，并用這兩個(gè)最小概率之和作為新符號(hào)的概率，從而得

6、到只包含q-1個(gè)符號(hào)的新信源，并稱為S信源的縮減信源.（3）把縮減信源的符號(hào)扔以遞減次序排列，再將其最后兩個(gè)最小概率的信源符號(hào)合并成一個(gè)新符號(hào)，并用0和1碼符號(hào)表示，這樣又形成了q-2個(gè)符號(hào)的縮減信源。（4）依次繼續(xù)下去，直至縮減信源最后只剩兩個(gè)符號(hào)為止。將這最后兩個(gè)新符號(hào)用0和1碼符號(hào)表示。最后這兩個(gè)符號(hào)的概率之和必為1。然后從最后一級(jí)縮減信源開始，依編碼路徑由后向前返回，就得出各信源符號(hào)所對(duì)應(yīng)的碼符號(hào)序列，即得對(duì)應(yīng)的碼字。下面舉個(gè)例子說明這種編碼方法。例：離散無記憶信源,的概率分別為0.4，,0.2，0.2,0.1,0.1。其霍夫曼碼如下表：7霍夫曼碼的碼樹：r元霍夫曼（Huffman）碼

7、編碼注意三點(diǎn)：(1)將最小概率的r個(gè)符號(hào)分配碼元。(2)每次合并r個(gè)最小概率成為新信源，減少r-1個(gè)符號(hào)。(3)滿足式才能充分利用短碼?！旁纯s減次數(shù)，若不滿足,增加的概率項(xiàng)。例：四元Huffman碼，補(bǔ)二項(xiàng)7Huffman碼的最佳性對(duì)于給定分布的任何信源，存在一個(gè)最佳即時(shí)碼，此碼滿足以下性質(zhì)：（1）若(2)兩個(gè)最小概率的信源符號(hào)所對(duì)應(yīng)的碼字具有相同的碼長。(3)兩個(gè)最小概率的信源符號(hào)對(duì)應(yīng)的碼字