摘要：編碼技術研究的一個重要方面是信源編碼。文章介紹了日常生活、生產(chǎn)實踐中的幾種常見信源編碼方法，如等長編碼、香農編碼、哈夫曼編碼，另外還介紹了靜態(tài)奇偶編碼和動態(tài)的哈夫曼編碼，重點是用程序算法來實現(xiàn)這些編碼方法。通過對這幾種最常見也是最基本的編碼方法的介紹及程序實現(xiàn)，并對編碼結果和算法的時間復雜性進行比較分析，使讀者對信息論和數(shù)據(jù)結構知識有進一步的理解，認識到選擇一種好的編碼技術或者一個好的算法具有非常重要的現(xiàn)實意義。

關鍵詞：編碼技術；信源編碼；動態(tài)哈夫曼編碼；靜態(tài)奇偶編碼

中圖分類號：TU757文獻標識碼：A文章編號：1009－2374(2009)12－0001－02

一、編碼

(一)編碼簡介

我們處在一個信息飛速增長的時代，隨著科技與經(jīng)濟的迅速發(fā)展，海量的信息進入了我們的生活，各種信息傳輸設備也隨之發(fā)展，鑒于人們對信息傳輸有效性和可靠性的不斷要求，如何正確而迅速的處理和傳輸數(shù)據(jù)就成為目前科學界急待解決的一大問題，因此，編碼技術研究在人們生產(chǎn)生活中的重要性也日益顯現(xiàn)。

(二)信源編碼的意義

電路通常只有兩中穩(wěn)定狀態(tài)：導通與阻塞、高電位與低電位，因此用二進制0、1來表示各種信息，這樣實現(xiàn)起來比較容易，電路簡單，成本低廉。而存貯在計算機中的形形色色的信息或數(shù)據(jù)，在本質上來講都是一些“0”和“1”組成的序列。

計算機中普遍使用的ASCII碼采用7位二進制數(shù)來表示字符，它實際是一種等長編碼。在實際應用中，經(jīng)常使用的字符比較集中，每個字符使用的頻率相差很大，如果能根據(jù)信源中字符使用頻率的高低不同，采用不同長度的二進制來表示字符，用短一些的編碼來表示使用頻率高的字符，而用相對長一些的編碼來表示使用頻率低的字符，很顯然這樣就可以直接減少數(shù)據(jù)存儲和傳輸時的開銷，同時也能對數(shù)據(jù)起到保護作用，而這也正式信源須要進行編碼的原因和意義。

二、信源編碼方法

(一)哈夫曼編碼介紹

哈夫曼樹又稱最優(yōu)樹，是一類帶權路徑長度最短的樹，在實際中有著廣泛的應用。給出路徑和路徑長度的概念，在樹形存貯結構中，一個結點到另一個結點之間的分支構成這兩個結點之間的路徑，路徑上的分支數(shù)目稱為路徑長度。樹的帶權路徑長度則是樹中所有葉子結點的帶權路徑長度之和，通常記為WPL=w₁*l₁+…W_n*l_n，w_i表示該結點的權重，1_i表示該結點的路徑長度。其中帶權路徑長度WPL最小的二叉樹稱為最優(yōu)二叉樹或哈夫曼樹。哈夫曼樹在解某些判定問題時往往可以得到最佳的判定算法。例如要判定一個班級學生的分數(shù)等級，共有差、中、好三等，可以通過哈夫曼編碼來實現(xiàn)，如果判定過程需要反復的使用，而且每次的輸入量很大，則需要考慮這一方法的質量問題，實際上，這三種成績段的分布顯然是不均勻的，假設其分布規(guī)律為：0～59分段占總數(shù)的5％、60～84分段占總數(shù)的60％、85～100分段各占總數(shù)的35％。則其中60％的人需要進行2次的比較、35％的人需要進行3次的比較才能得出結果，假設有100名同學的話，需要判斷5+60*2+35*3=230次。

將這種思想運用到編碼實踐中，便得到了哈夫曼編碼，以二元碼為例，設有離散信源s，所得信源符號列為{s₁，S₂，…，S_m｝，取值于有限符號集A，A={a₁，a₂，…，a_n｝，而該集合A中每個字符dj在信源S中出現(xiàn)的概率為：P={p₁，p₂，…，p_n}，其中p_i=L/M，L_i為符號a_j在信源S中出現(xiàn)的次數(shù)或頻度。

顯然按這種方式的話，信源X中概率最高的符號，被分配的碼字也一定最短，反之出現(xiàn)頻率最低的符號，被分配的碼字一定最長，雖然最終這樣獲得的碼字其長度是不相等的，但可以保證所得平均碼字長度最短，這也就是我們通常所說的最佳編碼思想。

(二)靜態(tài)奇偶編碼介紹

哈夫曼編碼效率雖然高，其算法卻略顯復雜，特別是無論什么樣的數(shù)據(jù)，該算法在開始編碼前，都要對其進行掃描統(tǒng)計以生成各字符的概率，還涉及到反復的排序計算，所以比較費時，而且生成的碼字總是不定的，它隨著信源的不同而不同，這就增加了譯碼的難度。因而有人針對這一情況提出了靜態(tài)奇偶編碼，這種算法也是基于概率排序的，即編碼前，總是先統(tǒng)計出信源中各字符出現(xiàn)的概率，然后根據(jù)概率分配碼字，其具體的生成方式是：對于一個符號，若其概率大小排序為第n位，則給這個符號分配的碼字的碼長是l_n=int[(n+1)／2]+1。

這樣，在編碼過程中可先行判斷其概率排序n是奇數(shù)還是偶數(shù)，如果n是奇數(shù)，則碼字中的前(n-1)位是“1”，最后一位是“0”；反之如果n是奇數(shù)，則碼字中的前(n-1)位是“0”，最后一位是“1”。其碼字結構非常的有規(guī)律，如果一個碼字前一部分是全“0”，則其結尾必定為一個“1”；反之如果一個碼前一部分是全“1”，則其結尾必定為一個“0”；而且表中的碼字總是成對出現(xiàn)，非奇即偶，奇偶碼互為取反，靜態(tài)奇偶編碼也是因此而得名。

靜態(tài)奇偶編碼算法的編碼過程很簡單：首先根據(jù)信源符號出現(xiàn)的概率排序，并由此確定各符號的碼長，之后每提取一個字符，就可以直接給出其碼字；同時其譯碼過程也很簡單，只須掃描所接收到的碼序列，從第一位開始搜索，如果是“0”，則到下一個非“0”為的這一段便是一個碼字，如果開始位是“1”，則到下一個非“1”為的這一段便是一個碼字，顯然要比哈夫曼編碼的譯碼過程簡單的多。

(三)動態(tài)哈夫曼編碼介紹

為了便于說明，我們定義si，表示信源字符串中的第i個字符。

在編碼開始前，需要首先引入一個空的葉結點，它的重量權值始終為0。初始的哈夫曼樹中只有一個根結點和一個空葉結點。

編碼子程序讀入第一個字符時，它將該字符加到根結點的右分枝上，而空葉結點仍留在左分枝上，然后將該字符以ASCII碼方式輸出。

以后每讀進一個字符S_i，編碼子程序都執(zhí)行以下的步驟：首先它檢查s_i是否出現(xiàn)在編碼樹中，如果是，編碼子程序就以靜態(tài)哈夫曼編碼中相同的方式對s_i進行編碼；如果S_i；不在編碼樹中，編碼子程序首先對空葉結點進行編碼，然后將S_i以ASCII碼的方式輸出，最后在編碼樹增加兩個

結點：在空葉結點的右分枝加入一個新結點，并將S_i放在里面，然后在其左分枝上加入一個新的空葉結點。

每處理一個字符，編碼子程序都需要修改各自的哈夫曼樹，為了修改的方便，樹中每個結點都具有一個序號，它是根據(jù)結點的重量由大到小排列而確定的一個遞減序列，不同層間從上到下，同層中的結點從右到左遞減。

動態(tài)哈夫曼編碼技術的關鍵就是如何將前t個字符的哈夫曼樹調整成一棵前(t+1)個字符的哈夫曼樹。為了解決上述問題，我們分兩步來進行，第一步我們把前t個字符的哈夫曼樹轉換成它的另一種形式，在該樹中只須在第二步中簡單地把由根到葉結點s_i路徑上的所有結點重量加1，就可以變成前(t+1)個字符的哈夫曼樹。其過程就是以葉結點s_i為初始的當前結點，重復地將當前結點與具有同樣重量的序號最大的結點進行交換，并使得后者的父結點成為新的當前結點，直到遇到根結點為止。

三、各編碼方法的比較

依據(jù)前面部分的論述，對于同—信源符號列“hatismath”，分別施以不同的編碼方法得到不同的編碼結果。

當然僅憑一個例子的運行時間并不能說明一個算法的優(yōu)劣，但是算法的時間復雜度在宏觀上給算法提供了一個衡量的尺度，表中等長編碼的時間復雜度最小，在程序運行過程中只須給該信源符號一個不同與其它符號的記錄號即可，不涉及排序等問題，將該記錄號轉換成對應的二進制便得到其對應碼字，而香農編碼則須要先進行排序以方便后面過程中概率的累計等計算，同時還要對其概率進行二進制的轉換，因而起算法的時間復雜度要高與等長編碼。同樣道理可得到哈夫曼編碼的時間復雜度，不過哈夫曼編碼能保證平均碼長最小，因而優(yōu)與香農編碼。靜態(tài)奇偶編碼在排序后即可直接的出各自的碼字，這也是其編嗎迅速的主要原因。至于動態(tài)哈夫曼編碼其時間復雜度也同樣為0(n²)，但是在動態(tài)編碼中，各信源符號的碼字是實時生成的，同時也是不斷變化的。

四、結論

通過前文的論述及比較，可得到如下結論：等長編碼只是一種比較初級的編碼方法，雖然其實現(xiàn)起來比較容易，但是它的編碼效率很低。香農編碼較之等長編碼來說，理論上有很大的進步，基本上實現(xiàn)了給出現(xiàn)概率高的字符配以較短的碼字，出現(xiàn)概率低的字符配以相對來說稍長的碼字，但是它仍然無法實現(xiàn)平均碼長的最短。

哈夫曼編碼又稱為最優(yōu)編碼，編碼效率在這幾種編碼方法中最好，但是其實現(xiàn)起來對時間和空間的要求較高，靜態(tài)奇偶編碼在信源字符集中元素不是很多，據(jù)相關統(tǒng)計分析為小于等于16時，有和哈夫曼編碼相當?shù)木幋a效率，而且靜態(tài)奇偶編碼實現(xiàn)起來要比哈夫曼編碼簡單的多。值得一提的是，經(jīng)過靜態(tài)奇偶編碼后的碼字序列其0、1分布是比較集中的其碼字形式為111…0或000…1，因此有利于進一步的壓縮。至于動態(tài)哈夫曼編碼，顯然其最終狀態(tài)是同哈夫曼編碼一致的，哈夫曼編碼需要統(tǒng)計各信源字符的概率，且各字符的碼字是編碼程序最終一起完成的，相比之下動態(tài)哈夫曼編碼則不須要統(tǒng)計各信源符號的概率，并且能夠實現(xiàn)即時編碼，對于一些須要快速傳遞控制信息的實時場合，動態(tài)哈夫曼編碼能在進行編碼的同時進行傳輸，并且它的編碼效率是趨近于哈夫曼編碼的。

參考文獻

[1]李亦農，李梅，信息論基礎教程[M]，北京：北京郵電大學出版社，2005

[2]石峰，莫忠息，信息論基礎[M]，武漢：武漢大學出版社，2002

[3]嚴蔚敏，吳偉民，數(shù)據(jù)結構C語言版[M]，北京：清華大學出版社，1997

[4]嚴蔚敏，吳偉民，數(shù)據(jù)結構習題集C語言版[M]北京：清華大學出版社，1997

[5]郭福順，廖明宏，數(shù)據(jù)結構與算法基礎[M]大連理工大學出版社，2000

作者簡介：徐國臣，男，黑龍江安達人，興安嶺地區(qū)公安邊防支隊助理工程師，研究方向：通訊。