第4章統(tǒng)計編碼1

1、第四章第四章 統(tǒng)計編碼統(tǒng)計編碼數據壓縮的類型可逆的無失真編碼可逆的無失真編碼不可逆的有失真編碼不可逆的有失真編碼大多數計算機文件不允許在壓縮過程中丟失信息。大多數計算機文件不允許在壓縮過程中丟失信息。利用消息或消息序列出現概率的分布特性，注重尋找概率與利用消息或消息序列出現概率的分布特性，注重尋找概率與碼字長度間的最優(yōu)匹配。碼字長度間的最優(yōu)匹配。語音、圖像或其他物理過程的量化采樣。語音、圖像或其他物理過程的量化采樣。本章討論的內容對于計算機文件對于計算機文件邏輯壓縮邏輯壓縮(Logical Compression)物理壓縮物理壓縮(Physical Compression)由數據自身特點及設計

2、者技巧來決定的由數據自身特點及設計者技巧來決定的 “壓縮表示壓縮表示法法”，這種技巧在數據庫的數據結構設計中特別有效。，這種技巧在數據庫的數據結構設計中特別有效。減少計算機文件內部冗余度的統(tǒng)計編碼方法。減少計算機文件內部冗余度的統(tǒng)計編碼方法。本章討論的內容1基本原理基本原理2霍夫曼編碼霍夫曼編碼 3游程編碼游程編碼 4算術編碼算術編碼 本章內容本章內容5基于字典的編碼基于字典的編碼 唯一可譯碼的構造4.14.1 基本原理基本原理 編碼器的數字描述 變長碼的基本分析 唯一可譯碼的存在計算機文件字符集合(如文本);二進制符號集合(如數據);壓縮必須“透明”，恢復后的文件不允許有任何失真。 文件的冗

3、余度類型本節(jié)所指的冗余度，專指對數據解釋一無所知時由數據流中即可觀察到的，與具體應用背景無關的冗余。了解文件的冗余度，意在考慮有針對性的編碼方法。冗余類型 字符分布(Character Distribution) 字符重復(Character Repetition)在典型的字符串中，某些符號要比其他符號出現的更頻繁，在一份具體的文件中字符不會以等概率出現，字符的分布明顯地因文件而異，影響到字符的統(tǒng)計特性。對于字符重復所形成的符號串常常有更緊湊的編碼方式，例如：格式化文件中的空白、報表中的空格串和零串、業(yè)務圖表中的線圖包含成片的空白等。 高使用率模式(High-usage Patterns) 位

4、置冗余(Positional Redundancy)這四類冗余度之間有重疊某些符號序列會以較高的頻率反復出現，可用較少的位數表示，從而得到時間和空間的凈節(jié)約。若某些字符總是在各數據塊中可預見的位置上出現，那么這些字符至少是部分冗余的 ，例如：光柵掃描圖像中含有的豎線、報表文件中的某些字段的記錄幾乎總是相同的等等。圖4.1 一份零件報表中的冗余度的類型零件名: HEX NUT 1/4 20說 明: STEEL, STANDARD THREAD顏色碼:倉 庫: 45th STREET貨 位: 4R9存貨量: 0020再進貨量:0010文字長度可變,字母分布不同;空字段同樣的名字在文件中多次出現;數

5、值字段, 有限的字符變化; 編碼器的數字描述X =x1, , xnW =w1, , wnA =a1, , am編碼器圖4.2 編碼器的描述實際信源的編碼過程 消息集X：元素 x 叫做信號單元或消息； 輸出集W (代碼、碼組或碼書)：元素 w叫做碼字； 碼字的符號集A：元素 a 叫做碼元或者符號 以符號 A 構建代碼 W ; 建立 XW 對應關系;編碼過程例4-1X =x1, x2 , x3, A =0, 1, W =w1, w2, w3A2 =00, 01, 10, 11假設用構成代碼W , W 到 A2 的映射關系為 (完成步驟):R1 = (w1,01), (w2,10), (w3,11)

6、R2 =(x1 ,w1), (x2 ,w2), (x3 ,w3)建立X 與 W 的映射關系為 (完成步驟):若xi(dk,dk+1, 1in, 0kJ-1, 為一模擬信號, 該編碼器實際就是一個量化器。編碼，就是將不同的消息用 不同的碼字來代替，或稱為從消息集到碼字集的一種映射(分組編碼或塊碼的概念)。 碼長: 組成碼字的符號個數, Li=2, 1i3, 等長(或定長)編碼: 采用相同長度的不同碼字去 代表一個消息集合中的不同消息; M元編碼(或M進制):取M個不同字符來組成碼字, 最常用的有二元編碼(或二進制)。 變長碼的基本分析對一個消息集合中的不同消息，采用不同長度的碼字表示。不等長(或

7、變長)編碼：采用變長碼可以提高編碼效率，即對相同的信息量所需的平均編碼長度可以短一些。1()njjjlP aL平均碼長：對對P(aj)大的大的aj 用短碼用短碼;對對P(aj)小的小的aj 用長碼用長碼; 當這些信息符號互不相關時當這些信息符號互不相關時,平均碼長比等長編碼的碼長短平均碼長比等長編碼的碼長短1843年，莫爾斯電報碼：字母莫爾斯碼鉛字數E12000T-9000A -8000I 8000N- 8000O- - -8000S 8000H 6400R - 6200D- 4400L - 4000U -3400C- - 3000字母莫爾斯碼鉛字數M- -3000F - 2500W - -2

8、000Y- - -2000G- - 1700P - - 1700B- 1600V - 1200K- -800Q- - -500J - - -400X- -400Z- - 200表4.1莫爾斯碼莫爾斯碼的形成: 首先找到各消息符號的統(tǒng)計特性: 再根據各符號出現的概率分布分 配不同長度的碼字:變長碼在編碼時要預先知道各種信息符號出現的概率，解碼也遠比等長碼復雜:正確識別碼字起點不容易;存在唯一可譯性問題;譯碼實時性問題;勻速輸入輸出匹配的緩存問題; 定義定義 4-1若W 中任一有限長的碼字序列(即有限長的一串W) ,可唯一地分割成一個一個碼字,稱為單義可譯或唯一可譯的,W 也叫做單義代碼。單義可譯

9、碼例4-2考慮以下幾種變長碼：信源字母概率碼A碼B碼C碼D碼E碼Fa1a2a3a41/21/41/81/80011001111110101101110010110111001011111010101111 碼A不是一一對應 ; 碼B是一一對應，但構成的序列不能被唯一分割;01110(0,1,1,1,0) (0,1,11,0) (0,11,1,0) (0,111,0)100111011010(10, 0, 111, 0, 110, 10) 碼C是唯一可譯的;信源字母碼B碼C碼Da1a2a3a401111110101101110010110111 碼D是在碼B各碼字(除了w1)之前加一個碼元“0”

10、, 成為唯一可譯的, 但平均碼長增加0.5bit; 碼F 即使從尾開始判斷, 也不是唯一可譯的;信源字母碼E碼Fa1a2a3a4001011111010101111101111010(10, 111, 10, 10)(101, 111, 0, 10)問題: 什么樣的碼才是唯一可譯的? 碼E的譯碼要求等到收到全部序列, 才能從尾開始進行判決, 產生了時間上延時和存儲容量的增加;0111111 111(a1 1111) (a2111) ( a311) 唯一可譯碼的存在目前還沒有一個明確的判斷唯一可譯碼的準則, 只有一個判斷不是唯一可譯碼的準則。定理 4.1(Kraft不等式)長度為L1, L2,

11、Ln 的 m 進制唯一可譯碼存在的充分必要條件是:含義：要求 Li 比較大(碼長不能過短)，意味著碼字可能的組合數多,不為別的碼字的字首。11niLim(4.1-1)Kraft不等式：只涉及唯一可譯碼的存在問題而并不涉及具體的碼?？捎脕砼卸骋唤M碼不是唯一可譯的，但不能判定是唯一可譯的。不滿足Kraft不等式的碼肯定不是唯一可譯碼，而滿足的也不一定就是唯一可譯的，但可以肯定若按這樣的Li 分配碼組，則必存在有一個唯一可譯碼(也可能不止一個)對應于信源符號。碼A碼B碼C碼D碼E碼F 的值7/411/4115/1611是否滿足Kraft不等式是否唯一可譯例4-3對于例4-2412iLi信源字母概率

12、碼A碼B碼C碼D碼E碼Fa1a2a3a41/21/41/81/80011001111110101101110010110111001011111010101111問題: 如何來確定碼字長度?如何在確定了碼字長度后找出唯一可譯碼?定理 4.2(按符號)變長編碼定理)對于符號熵為H(X)的離散無記憶信源進行m 進制不等長編碼, 一定存在一種無失真編碼方法, 其碼字平均長度 l 滿足:mXHlmXHlog)(1log)(4.1-2)小于上限的單義代碼總是存在的。當m=2，有(二進制編碼定理):此時l 叫編碼速率, 有時又叫比特率。對于m進制的不等長編碼的編碼速率定義為：mlRlog(4.1-4)(b

13、it) )(1)(XHlXH(4.1-3)定理4.2改述為：若H(X)R H(X)+, 就存在唯一可譯的變長碼;若R 1.75 碼長的一種設計為: L1 = 1, L2 = 2, L3 = L4 = 3信源字母概率碼A碼B碼C碼D碼E碼Fa1a2a3a41/21/41/81/80011001111110101101110010110111001011111010101111滿足上述碼長設計的碼如：例4.2中的碼C、E、F（滿足Kraft不等式）。如何做出具體的變長碼是變長碼的構造問題。 唯一可譯碼的構造唯一可譯碼的基本要求:碼字非續(xù)長對碼字序列能做出唯一正確的分割。充分條件若W 中任一碼字都不

14、是另一個碼字的字頭；或換句話說,任一碼字都不是由另一個碼字加上若干個碼元所構成，則W 就叫作非續(xù)長碼字或異字頭碼(Prefix Condition Code)。定義 4-2碼字非續(xù)長例4.2中:信源字母概率碼A碼B碼C碼D碼E碼Fa1a2a3a41/21/41/81/80011001111110101101110010110111001011111010101111碼A、碼B、碼D、碼E和碼F都含有續(xù)長碼，或同字頭碼；碼C是異字頭碼。不過非異字頭碼也并非一定不是唯一可譯，碼D和碼E就唯一可譯；碼D：各碼組靠“逗號”（碼元0）分開；碼E：為碼C的“鏡像”，具有“異后尾”，從 后向前即具有唯一可譯

15、性。異字頭條件保證譯出的碼字是唯一的且具有“即時性”，減少了譯碼延時。異字頭性質只是碼字可分離的充分條件，非續(xù)長碼也只是單義可譯代碼集合的一個子集。單義可譯碼非續(xù)長碼圖4.3 單義可譯碼與非續(xù)長碼二進制編碼通?？捎枚M碼樹(二叉樹)來表示各碼字的構成(根)(節(jié)點)圖4.4 二進碼樹C(節(jié)點)D(節(jié)點)串接的最大枝數為樹的節(jié)數， 圖4.4的節(jié)數為3。用碼樹表述任何一個代碼W, 異字頭條件就成為: W中所有的碼字 wi 均只對應地配置在終端節(jié)點上。圖4.5 碼C的樹結構(異字頭碼)根001110010110111根011100(011)(111)11(0)(01)碼E的樹結構(非異字頭碼)11ni

16、Lim此時碼C為用盡的異字頭碼, 有:倘若有一碼字為(0,10,110), 則該碼為非用盡的異字頭碼, 有:11niLim按照Kraft 不等式的要求，對n個消息x1, x2, ,xn分配了編碼長度L1,L2, ,Ln, 即可用二進碼樹來生成異字頭碼, 生成規(guī)律是: 從根出發(fā)開始生出2枝 ; 每一枝用一個碼元aj A=0,1來表示; 枝盡節(jié)來,節(jié)外生枝; 在第Li級端節(jié)點(Li級節(jié)點共有2Li個)上,配置信 號單元 xi , i=1,2, , n ; 從根開始直奔對應的端節(jié)點,沿途(聯枝)所遇到 的碼元 aj 所構成的符號,即為對應于該信號單元 xi 的碼字 wi 。異字頭碼無譯碼延時，構造簡

17、單。結論：任一唯一可譯碼，總可以用與各相應碼字長度一樣的異字頭碼代替。異字頭碼雖然只是唯一可譯碼的一種，但它具有代表性和普遍意義，在信息保持編碼中廣泛應用。長度為L1,L2, ,Ln的M進制異字頭碼存在的充要條件，也使Kraft不等式成立。4.2 霍夫曼編碼1952年 ，霍夫曼(D.A.Huffman) 提出霍夫曼編碼, 又稱最佳編碼根據字符出現概率來構造平均長度最短的異字頭碼字。 霍夫曼碼的構造理論基礎定理4.3在變長編碼中,若碼字長度嚴格按照所對應符號出現概率的大小逆序排列,則其平均長度最短。例4-6對一個7符號信源A=a1,a2, ,a7, 求其霍夫曼編碼信源符號 出現概率 a1 0.2

18、0 a2 0.19 a3 0.18 a4 0.17 a5 0.15 a6 0.10 a7 0.01 碼長 碼 字 2 11 2 10 3 011 3 010 3 001 4 0001 4 00000.26010.11010.35010.390110.61101.000編碼步驟： 將信源符號概率按遞減順序排列將信源符號概率按遞減順序排列; ; 將兩個最小的概率進行相加，并繼續(xù)這一步驟，直到概率將兩個最小的概率進行相加，并繼續(xù)這一步驟，直到概率 達到達到1.0為止為止; ; 在每對組合中的上部指定為在每對組合中的上部指定為1(或或0), ,下部指定為下部指定為0(或或1); ; 畫出每個信源符號概

19、率到畫出每個信源符號概率到1.0處的路徑處的路徑, ,記下沿路徑的記下沿路徑的1和和0 ; 對于每個信源符號都寫出對于每個信源符號都寫出1 1、0 0序列，則序列，則從右到左從右到左就得到霍就得到霍 夫曼編碼。夫曼編碼。011a3根例4-6的Huffman二進碼樹11a110a2010a4001a50001a60000a7例4-6的信源熵為:霍夫曼編碼的平均字長為:(bit) 61. 2)(log)()(71iiiapapAH(bit) 72.2)(71iiiLapl編碼效率:( )2.6196 %2.72H Al另例1對一個7符號信源A=a1,a2, ,a7, 求其霍夫曼編碼:信源符號 出現

20、概率 a1 0.35 a2 0.20 a3 0.15 a4 0.12 a5 0.10 a6 0.05 a7 0.03 碼長 碼 字 2 00 2 10 3 010 3 011 3 110 4 1110 4 11110.080.180.270.620.381.00111111000000關鍵：在每一步，總是最低概率的兩個符號構成一對。 注意注意：哈夫曼的編法并不唯一哈夫曼的編法并不唯一每次對縮減信源兩個概率最小的符號分配每次對縮減信源兩個概率最小的符號分配“0”和和“1”碼元是任意的，所以可得到不同的碼字。只要碼元是任意的，所以可得到不同的碼字。只要在各次在各次縮減信源中保持碼元分配的一致性縮減

21、信源中保持碼元分配的一致性，即能得到可分離即能得到可分離碼字。碼字。不同的碼元分配，得到的具體碼字不同，但碼長不同的碼元分配，得到的具體碼字不同，但碼長ki不不變，平均碼長也不變，所以沒有本質區(qū)別；變，平均碼長也不變，所以沒有本質區(qū)別；縮減信源時，若合并后的新符號概率與其他符號概率縮減信源時，若合并后的新符號概率與其他符號概率相等，從編碼方法上來說，相等，從編碼方法上來說，這幾個符號的次序可任意這幾個符號的次序可任意排列，編出的碼都是正確的，但得到的排列，編出的碼都是正確的，但得到的碼字不相同碼字不相同。不同的編法得到的不同的編法得到的碼字長度碼字長度k ki i也不盡相同也不盡相同。 單符號

22、離散無記憶信源單符號離散無記憶信源對其編二進制哈夫曼碼。對其編二進制哈夫曼碼。解：解：方法一方法一 合并后的新符號排在其它相同概率符號之后合并后的新符號排在其它相同概率符號之后12345,()0.40.20.20.10.1XxxxxxP X另例另例2 這兩種編碼哪一種更好呢，我們來計算一下二者的碼長。這兩種編碼哪一種更好呢，我們來計算一下二者的碼長。方法二：方法二：合并后的新符號排在其它相同概率符號的前面。合并后的新符號排在其它相同概率符號的前面。2221() ( )()qiiiiE lLP slL引入碼字長度偏離平均碼長方差的概念：36. 1 2)2 . 24(1 . 0)2 . 23(2

23、. 0 )2 . 22(2 . 0)2 . 21 (4 . 0 22222方法一：16. 0 2)2 . 23(1 . 0 2)2 . 22(2 . 0)2 . 22(4 . 02222方法二：兩種編碼的平均碼長是一樣的，都是兩種編碼的平均碼長是一樣的，都是2.2，那一種更好呢，我，那一種更好呢，我們可以計算一下平均碼長的方差。們可以計算一下平均碼長的方差。n可見：第二種編碼方法的碼長方差要小許多。意可見：第二種編碼方法的碼長方差要小許多。意味著第二種編碼方法的碼長變化較小，比較接近味著第二種編碼方法的碼長變化較小，比較接近于平均碼長。于平均碼長。第一種方法編出的第一種方法編出的5 5個碼字有

24、個碼字有4 4種不同的碼長；種不同的碼長；第二種方法編出的碼長只有第二種方法編出的碼長只有2 2種不同的碼長；種不同的碼長；顯然，顯然，第二種編碼方法更簡單、更容易實現，第二種編碼方法更簡單、更容易實現，所以更好。所以更好。結論：在哈夫曼編碼過程中，對縮減信源符號按概率結論：在哈夫曼編碼過程中，對縮減信源符號按概率由大到小的順序重新排列時，由大到小的順序重新排列時，應使應使合并后的新符號盡合并后的新符號盡可能排在靠前的位置可能排在靠前的位置，這樣可使合并后的新符號重復，這樣可使合并后的新符號重復編碼次數減少，使短碼得到充分利用編碼次數減少，使短碼得到充分利用。Huffman編碼和譯碼過程編碼和

25、譯碼過程編碼輸出Huffman碼流Huffman碼表傳輸接收的Huffman碼流緩沖器信源符號序列解碼解碼后的字符序列Huffman碼表 信源編碼基本定理霍夫曼編碼變長的代碼(只能分配接近log2pj的整數長碼字)定長的數據段當信源符號的概率 pj=2-k編碼效率等于100%例4-7:對于二值圖像，如傳真機文件，輸出非“黑”即“白”，有：X=x1，x2=白，黑，其概率與所傳文件有關，假設對某頁文件，有P(x1)=0.9, P(x2)=0.1 。不考慮信號間的關聯時，其信息熵為：()0.9log0.90.1 log0.10.469 (bit/pel)H X 此時W=0,1，無論用定長碼還是最佳編

26、碼, 平均碼長至少為l1=1 (bit) ；此時霍夫曼編碼無壓縮作用編碼效率為1 =H(X)/ l1=46.9 %解決辦法:定理4.4(信源編碼定理):A =a1, , am ;X K - X =x1, , xn 的延長;W K - W =w1, , wn 的延長, 其平均長度為lK ;P(wi)=P( xi), P(W)= P(wi), i=1,2, ,n ;如果要求W K 為單義代碼, 則:( )( )1loglogH XlH XmKmK(4.2-1)式(4.2-1)也叫做無失真編碼的基本定理。含義：如果我們把 X 延長后再對 K 元組( K 為延長長度)進行編碼，那么不必利用數據前后的關

27、聯，只要K 足夠大，則代表每消息單元 X 的平均符號個數l/K 可以任意趨向于下限。例4-8: 利用最佳編碼, 以例4-7來說明l/K趨向于下限的情況。把 X 延長到 X 2 ，假定信源是離散無記憶信源，有圖4.7所示 X 2 的最佳編碼：圖4.7 2單元延長信號的最佳編碼P(x1, x1) = P(x1)P( x1) =0.81P(x1, x2) = P(x1)P( x2) =0.09P(x2, x1) = P(x2)P( x1) =0.09P(x2, x2) = P(x2)P( x2) =0.010.100.191.00111000W 2 010110111W 2平均長度為:l2 =0.8

28、1+0.092+0.093+0.013=1.29 bit/pelW 2的每一個元素代表兩個消息單元,因此平均每一個消息單元的符號個數是:l2 /2 = 1.29/2 = 0.645 bit/pel2 =H(X)/( l2/2)=72.7 %編碼效率提高到:把 X 延長到 X 3 ，有圖4.8所示 X 3 的最佳編碼：圖4.8 3單元延長信號的最佳編碼P(x1, x1, x1) =0.729P(x1, x1, x2) =0.081P(x1, x2, x1) =0.081P(x2, x1, x1) =0.0810.0100.109111000P(x1, x2, x2) =0.009P(x2, x1

29、, x2) =0.009P(x2, x2, x1) =0.009P(x2, x2, x2) =0.0010.0180.0280.1620.2711.0000111001W 3111111111011101110101100011100W 3平均長度為:l3 =0.729+0.08133 +5( 30.09+0.001)=1.598 bit/pelW 3的每一個元素代表三個消息單元, 因此平均每一個消息單元的符號個數是:l3 /3 = 1.598/3 = 0.5327 bit/pel3 =H(X)/( l3/3)=88.0 %編碼效率提高到:繼續(xù)下去,就可使 lK /K 0.469, 或=100

30、% 進一步減小 l/K , 利用信號的前后關聯減小下限, 即利用:H(X, Y )H(X)+H(Y)(3.2-13)H(X | Y )H(X)(3.2-11b)或:可以減小下限,從而減小l/K要求知道P(X), P(X,Y) 或 P(X|Y) 才能進行最佳編碼。如果信號繼續(xù)有關聯可供利用，繼續(xù)延長，會使下限變得很小。信源編碼理論： 給定消息單元集合X、符號集合A和X的概率分布P(X)， 可以采用最佳編碼，使代碼W 的平均長度滿足; 如果把X 延長至 X K ,則不必考慮信號前后的關聯性, 就可以是代表一個消息單元的符號個數 l /K 任意接近 下限 H(X)/logm; 如果利用延長信號X K

31、的前后關聯,可使下限減小。具體實現時，如果將信號延長得過長，會使實際設備復雜到不合理的程度。1log)(,log)(mXHmXHl霍夫曼編碼選擇模型靜態(tài)統(tǒng)計模型 在編碼前統(tǒng)計要編碼的信息中所有字符的出現概率，然后根據統(tǒng)計出的信息建立編碼樹，進行編碼 。缺點 ： 對數據量較大的信息，靜態(tài)統(tǒng)計要消耗大量的時間； 必須保存統(tǒng)計出的結果以便解碼時構造相同的編碼樹，或者直接保存編碼樹本身，而且，對于每次靜態(tài)統(tǒng)計，都有不同的結果，必須分別予以保存，這要消耗大量的空間（這意味著壓縮效率的下降）； 靜態(tài)統(tǒng)計模型統(tǒng)計出的頻率是字符在整個文件中的出現頻率，往往反映不出字符在文件中不同局部出現頻率的變化情況，使用這

32、一頻率進行壓縮，大多數情況下得不到太好壓縮效果，文件有時甚至在壓縮后反而增大了。一種有效的“靜態(tài)統(tǒng)計模型”的替代方案 如果要壓縮的所有信息在分布上存在著共同的特征，使用語言學家事先已經建立好的字母頻率表來進行壓縮和解壓縮，不但不用保存多份統(tǒng)計信息，而且一般說來對該類文件有著較好的壓縮效果。比如我們要壓縮的是普通的英文文本，那么，字母 a 或者字母 e 的出現頻率應當是大致穩(wěn)定的。這種方案除了適應性不太強以外，偶爾還會有一些尷尬的時候。缺點 ：If Youth，throughout all history， had a champion to stand up for it； to show a

33、 doubting world that a child can think；and， possibly， do it practically； you wouldnt constantly run across folks today who claim that a child dont know anything. - Gadsby by E.V.Wright, 1939. 發(fā)現什么問題了嗎？整段話中竟沒有出現一次英文中出現頻率最高的字母 e 。對英文或中文文本，有一種比較實用的靜態(tài)模型：不是把字符而是把英文單詞或中文詞語作為統(tǒng)計頻率和編碼的單位進行壓縮。這種壓縮方式可以達到相當不錯的壓

34、縮效果，并被廣泛地用于全文檢索系統(tǒng)。自適應模型無需為解壓縮預先保存任何信息，整個編碼是在壓縮和解壓縮過程中動態(tài)創(chuàng)建的，而且自適應編碼由于其符號頻率是根據信息內容的變化動態(tài)得到的，更符合符號的局部分布規(guī)律，因此在壓縮效果上比靜態(tài)模型好許多。根據已經編碼的符號頻率決定下一個符號的編碼。算術編碼、字典編碼等更為適合采用自適應模型 但是，采用自適應模型必須考慮編碼表的動態(tài)特性，即編碼表必須可以隨時更新以適應符號頻率的變化。對于 Huffman 編碼來說，我們很難建立能夠隨時更新的二叉樹， 霍夫曼碼的局限性霍夫曼編碼文本文件壓縮二進制文件壓縮適用于經過符號合并局限性: 輸入符號數受限于可實現的霍夫曼碼表

35、尺寸 ; 譯碼復雜度; 需要知道輸入符號集的概率分布； 由于碼長不等，還存在一個輸入與輸出的速率 匹配問題。4.3 游程編碼游程長度(RL: Run Length,簡稱游程或游長)： 由字符(或信號采樣值)構成的數據流中各字符重復出現而形成的字符串的長度。用二進制碼字給出形成串的字符、串的長度及串的位置等信息，以此來恢復出原來的數據流。 游程長度編碼(RLC)：游程編碼類型：變長游程編碼變長游程編碼使用位數是固定的，即RL位數是固定的，如果灰度連續(xù)相同的個數超過了固定位數所能表示的最大值，則進入下一輪游程編碼；定長游程編碼定長游程編碼對不同范圍的游程采用不同位數的編碼，即表示RL位數不固定。

36、基本的游程編碼基本的RLC壓縮方法：最初出現在 IBM 3780 BYSYNC (Binary Synchronous Communication)通信協(xié)議中?；镜腞LC數據結構：XScRL數 據 流圖4.9 基本的RLC數據結構其中X ： 代表數據字符； Sc： Sc X，表示有一個字符在此位置； RL： 代表串（游程）的長度，字符重復出現的次數；只有當RL 3時, 才有數據壓縮效益。編碼時：先判斷RL值，再決定是否RLC； 解碼時：根據每一X后的碼字是否為Sc，再 決定下一個字的含義。 Assumption: Long sequences of identical symbols. Example,RLC壓縮效能:取決于數據流中重復字符出現次數、平均游程長度及所采用的編碼結構。平均重復長度重復出現10次的壓縮