【文章內容簡介】 。他有兩個明顯的特點：一是哈夫曼碼的編碼方法保證了概率大的符號對應于短碼，概率小的符號對應于長嗎，充分利用了短碼；二是縮減信源的最后兩個碼字總是最后一位不同，從而保證哈夫曼編碼是即時碼 [6]。 哈弗曼編碼幾乎是所有壓縮算法的基礎，其實這個算法并不復雜，簡單的理解就是，如何用更短的 bit 來編碼數(shù)據(jù)。 我們知道普通的編碼都是定長的，比如常用的 ASCII 編碼 ,每個字符都是 8個 bit: 字符 編碼 A 00101001 B 00101010 C 00101011 ... ... 這樣，計算機就能很方便的把由 0和 1組成的數(shù)據(jù)流解析成原始信息，但我們知道，在很多情況下，數(shù)據(jù)文件中的字符出現(xiàn)的概率是不均勻的，比如在一篇英語文章中，字母 “E” 出現(xiàn)的頻率最高， “Z” 最低，如果我們使用不定長的 bit 編碼，頻率高的字母用比較短的編碼表示，頻率低的字母用長的編碼表示，豈不是可以大大縮小文件的空 間嗎 ? 但這就要求編碼要符合 “ 前綴編碼 ” 的要求，即較短的編碼不能是任何較長的編碼的前綴，這樣解析的時候才不會混淆，比如下面的編碼方法就符合前綴原則： 燕山大學本科生畢業(yè)設計（論文） 10 字符 編碼 A 0 B 10 C 110 D 1110 E 11110 ... ... 根據(jù)這個碼表，下面一段數(shù)據(jù)就可以唯一解析成原始信息了： 1110010101110110111100010 – DABBDCEAAB 要生成這種編碼，最方便的就是用二叉樹，考察一下下面這個樹 圖 22 二叉樹圖 把要編碼的字符放在二叉樹的葉子上，所有的左節(jié)點是 0，右節(jié)點是 1，從根瀏覽到葉子上，因為字符只能出現(xiàn)在樹葉上，任何一個字符的路徑都不會是另一字符路徑的前綴路徑，符合前綴原則編碼就可以得到 第 2章 信源編碼分類 11 字符 編碼 A 00 B 010 C 011 D 10 E 11 現(xiàn)在我們可以開始考慮壓縮的問題，如果有一篇只包含這五個字符的文章，而這幾個字符的出現(xiàn)的次數(shù)如下： A: 6次 B : 15次 C: 2次 D : 9次 E: 1次 用過用定長的編碼，每個字符 3bit， 這篇文章總長度為： 3*6 + 3*15 + 3*2 + 3*9 + 3*1 = 99 （ 211） 而用上面用二叉樹生成的編碼，總長度為 : 2*6 + 3*15 + 2*2 + 2*9 + 2*1 = 80 （ 212） 顯然，這顆樹還可以進一步優(yōu)化，使得編碼更短，比如下面的編碼 圖 23二叉樹圖 燕山大學本科生畢業(yè)設計（論文） 12 生成的數(shù)據(jù)長度為： 3*6 + 1*15 + 4*2 + 2*9 + 4*1 = 63 (213) 可以看出，構造更優(yōu)的二叉樹，原則就是權重越大的葉子，距離根應該越近，而我們的終級目標是生成 “ 最優(yōu) ” 的二叉樹，最優(yōu)二叉樹必須符合下面兩個條件： 所有上層節(jié)點都大于等于下層節(jié)點。 某節(jié)點，設其較大的子節(jié)點為ｍ，較小的子節(jié)點為ｎ，ｍ下的任一層的所有節(jié)點都應大于等于ｎ下的該層的所有節(jié)點。 上面這個例子是比較簡單的，實際的文件中，一個字節(jié)有 256種可能的取值，所以二叉樹的葉子節(jié)點多達 256個，最終的樹形可能非常 復雜，但有一種非常精巧的算法可以快速地建起一棵最優(yōu)二叉樹，這種算法由（戴 ?哈夫曼）提出，下面我們先來介紹哈弗曼算法的步驟，然后再來證明通過這么簡單的步驟得出的樹形確實是一棵最優(yōu)二叉樹。 哈夫曼算法的步驟是這樣的：從各個節(jié)點中找出最小的兩個節(jié)點，給它們建一個父節(jié)點，值為這兩個節(jié)點之和。然后從節(jié)點序列中去除這兩個節(jié)點，加入它們的父節(jié)點到序列中。重復上面兩個步驟，直到節(jié)點序列中只剩下唯一一個節(jié)點。這時一棵最優(yōu)二叉樹就已經建成了，它的根就是剩下的這個節(jié)點。 比如上面的例子，哈弗曼樹 建立的過程如下 : 1) 列出原始的節(jié)點數(shù)據(jù)： 圖 24原始節(jié)點 第 2章 信源編碼分類 13 2) 將最小的兩個節(jié)點 C和 E結合起來： 圖 25C和 E結合 3) 再將新的節(jié)點和 A組合起來 圖 26新節(jié)點結合圖 4) 再將 D節(jié)點加入 圖 27新節(jié)點結合圖 燕山大學本科生畢業(yè)設計（論文） 14 5) 如此循環(huán)，最終得到一個最優(yōu)二叉樹 圖 28最優(yōu)二叉樹圖 生成的數(shù)據(jù)文件長度為： 3*6 + 1*15 + 4*2 + 2*9 + 4*1 = 63 下面我們用逆推法來證明對于各種不同的節(jié)點序列，用哈弗曼算法建立起來的樹總是一棵最優(yōu)二叉樹： 當這個過程中的節(jié)點序列只有兩個節(jié)點時（比如前例中的 15和 18），肯定是一棵最優(yōu)二叉樹，一個編碼為 0，另一個編碼為 1，無法再進一步優(yōu)化。 然后往前步進，節(jié)點序列中不斷地減少一個節(jié)點，增加兩個節(jié)點，在步進過程中將始終保持是一棵最優(yōu)二叉樹，這是因為 : 按照哈弗曼樹的建立過程，新增的兩個節(jié)點是當前節(jié)點序列中最小的兩個，其他的任何兩個節(jié)點的父節(jié)點都大于（或等于）這兩個節(jié)點的父節(jié)點，只要前一步是最優(yōu)二叉樹，其他的任何兩個節(jié)點的 父節(jié)點就一定都處在它們的父節(jié)點的上層或同層，所以這兩個節(jié)點一定處在當前二叉樹的最低一層。 這兩個新增的節(jié)點是最小的，所以無法和其他上層節(jié)點對換。符合我們前面第 2章 信源編碼分類 15 說的最優(yōu)二叉樹的第一個條件。 只要前一步是最優(yōu)二叉樹，由于這兩個新增的節(jié)點是最小的，即使同層有其他節(jié)點，也無法和同層其他節(jié)點重新結合，產生比它們的父節(jié)點更小的上層節(jié)點來和同層的其他節(jié)點對換。它們的父節(jié)點小于其他節(jié)點的父節(jié)點，它們又小于其他所有節(jié)點，只要前一步符合最優(yōu)二叉樹的第二個條件，到這一步仍將符合。 這樣一步步逆推下去，在這個過程中哈弗曼樹每 一步都始終保持著是一棵最優(yōu)二叉樹。 游程編碼 游程長度 游程長度 RL(RunLength)，簡稱游程或游長，指的是由字符 (或信號取樣值 )構成的數(shù)據(jù)流中各個字符重復出現(xiàn)而形成的字符的長度。如果給出了形成串的字符，串的長度以及串的位置，就能恢復出原來的數(shù)據(jù)流，游程長度編碼 (RLC)就是用二進制碼字給出這些信息的一類方法。 游程編碼算法 游程編碼的基本原理是：用一個符號值或串長代替具有相同值的連續(xù)符號（連續(xù)符號構成了一段連續(xù)的“游程”，游程編碼因此而得名），使符號長度少于原 始數(shù)據(jù)的長度。只在各行或者各列數(shù)據(jù)的代碼發(fā)生變化時，一次記錄該代碼及相同代碼重復的個數(shù)，從而實現(xiàn)數(shù)據(jù)的壓縮。 在二元序列中，只有兩種符號，即“ 0”和“ 1”，這些符號可連續(xù)出現(xiàn)，連“ 0”這一段稱為“ 0”游程，連“ 1”這一段稱為“ 1”游程。它們的長度分別稱為游程長度L(0)和 L(l)?！?0”游程和“ l”游程總是交替出現(xiàn)的。如果規(guī)定二元序列是以“ 0”開始，第一個游程是“ 0”游程，第二個必為“ 1”游程，第三個又是“ 0”游程等等。對于隨機的二元序列，各游程長度將是隨機變量，其取燕山大學本科生畢業(yè)設計（論文） 16 值可為 1， 2， 3，?，直到無限。 將任何 (二元 )序列變換成一一對應的游程長度序列，再按哈夫曼編碼或其他方法處理以達到壓縮碼率的目的 [9]。 游程編碼特點 游程編碼仍是變長碼，有其固有的缺點，及需要大量的緩沖和優(yōu)質的信道。此外，編程長度可以從一直到無限，這在碼字的選擇和碼表的建立方面都有困難，實際應用是尚需采用某些措施來改進。 一般情況下游程長度越長，其概率越小，這在以前的計算中也可以看見，而且將隨著長度的增大漸進向零。對于小概率的碼字，其長度為達到概率匹配或較長，損失不會太大，也就是對平均碼字長度影響較小。再按哈夫曼編碼或其他方法處 理以達到壓縮碼率的目的。 幾種基于游程相關性的數(shù)據(jù)壓縮方案 1）共前綴碼 共前綴碼編碼時也是按照一定規(guī)律用盡量短的碼字來表示游程形式的初始測試數(shù)據(jù)，但該編碼壓縮方案進一步考慮了相鄰游程之間存在的聯(lián)系。如果相鄰游程的長度在同一組，則它們對應碼字的前綴是相同的即共前綴，可以用一個標志位來表示這些相鄰游程除第一個游程以外的其他游程的前綴，這樣數(shù)據(jù)壓縮率得以進一步提高。同組共前綴碼的前綴和后綴的位數(shù)相同，前綴和后綴相加對應的十進制數(shù)比對應的游程長度多 2，也就是說跟 FDR 碼相比，相同的碼字所表示的 游程長度少 2，使壓縮效果受到一些影響，因此對初始測試數(shù)據(jù)進行無關位 (don’t cares bit)填充時，要盡量時這種影響降到最低。所謂無關位是指無論它們的取值是 0 還是 1 都不會影響測試結果。不過由此也可看出待測試數(shù)據(jù)的游程長度加上 2 所對應的 FDR 碼就是相應的共前綴碼，若這兩個相差為 2 的游程長度在同一組內，則碼字長度并沒有增加，不會影響壓縮效果。 共前綴碼的前綴都是以 1 開始，以 0 結束的數(shù)字串，所以當相鄰游程長度在同一組時，可以用數(shù)字 0 來表示后面游程的碼字前綴，后綴則不變，這樣碼字的長 度進一步縮短。下面給出一個共前綴編碼的實例： 第 2章 信源編碼分類 17 編碼前的初始測試數(shù)據(jù)： 000000001 1 0000001 00000000000001 0000000000000001（ 47 位）； 編碼后的碼字： 110100 1000 110010 11100001 00011（ 29 位）。 可見數(shù)據(jù)串 00000000000001 和 0000000000000001 的游程長度分別為 13 和 15，都在第三組，前綴都為 1110，所以后一游程的碼字前綴用標志位 0 表示，其碼字為 0 0011。 2）共游程碼 前面 介紹的共前綴碼是利用游程長度同組的前綴相同，用標志位 0 加碼字后綴來表示后面的游程，從而進一步壓縮初始測試數(shù)據(jù)。共游程碼（ Sharing Run Length Code， SRLC）與共前綴碼的編碼方案類似，該方案注意到初始測試數(shù)據(jù)中有的相鄰游程是相同的，于是就用一個標志位來表示后面的相同游程，所以該方案被稱為共游程碼。顯然該編碼方案的數(shù)據(jù)壓縮率比共前綴碼高一些，不考慮相鄰游程的長度相同的前提下，編碼方法與共前綴碼相同。對共游程碼編碼方案，如果有若干相鄰游程相同，則后面的一個或多個相同游程都可以用唯一的標志位 來代替，從而大大減少了編碼碼字的長度，即進一步提高了測試數(shù)據(jù)壓縮率。 共游程碼的前綴都是以“ 1”開頭以“ 0”結尾的數(shù)字串，沒有以“ 0”開頭的前綴，所以可以用數(shù)字 0 來作為相鄰相同游程的標志位，即后面相鄰相同游程的碼字只有 1 位。顯然相鄰相同游程的長度越長，測試數(shù)據(jù)壓縮率就越高。由于初始測試數(shù)據(jù)中存在著大量的無關位，可以有意識的對它們進行賦值填充，以增加長度相同的相鄰游程的數(shù)量，從而降低碼字的長度。例如數(shù)據(jù)串 00000000000x 000000000001，其中的 x 是無關位，如果把它填充為 0 則該數(shù)據(jù)串是一 個長度為 23 的 0 游程，由編碼碼表可知其對應的碼字為 11101011（ 8 位）；如果把無關位賦值為 1，則數(shù)據(jù)串變成了兩個長度都為 11 的相鄰 0 游程，其對應的碼字為 110111 0（ 7 位），使碼字的長度減少了 1 位，提高了數(shù)據(jù)壓縮效果。 燕山大學本科生畢業(yè)設計（論文） 18 3）共前綴連續(xù)長度碼 共前綴連續(xù)長度碼（ Co Prefixal Run Length codes， CPRL）也考慮了相鄰游程的相關性。如果相鄰游程的長度在同一組內，則同組的后面的相鄰游程的前綴可以省略，則編碼后碼字的前綴越長，則壓縮效果越明顯。由于初始測試數(shù)據(jù)集中存 在大量的無關位，可以適當?shù)膶@些無關位進行賦值填充，增加 0 游程的長度，這些游程長度在同組的概率很高。該編碼方案為了增加 0 游程的長度，對填充后的測試數(shù)據(jù)采取了差分處理，即把測試數(shù)據(jù)等長劃分并進行異或邏輯運算。通過對 ISC