【正文】 號的長度自動區(qū)分各自所對應的字符。 變長碼是近代通信技術(shù)發(fā)展的編碼理論技術(shù)，近代變長碼的編碼結(jié)構(gòu)不僅考慮消息發(fā)生的概率，而且還利用消息前后字母的關(guān)聯(lián)特性，因此利用變長碼可提高編碼效率。 當我們對文字信息進行編碼時，如果為出現(xiàn)概率較高的字母賦予 較短的編碼，為出現(xiàn)概率較低的字母賦予較長的編碼，總的編碼長度就能縮短不少。在 Morse碼表中，每個字母都對應于一個唯一的點劃組合，出現(xiàn)概率最高的字母 e被編碼為一個點 “ .” ，而出現(xiàn)概率較低的字母 z則被編碼為“ ..” 。 信息論之父 香農(nóng) 第一次用數(shù)學語言闡明了概率與信息冗余度的關(guān)系。這篇偉大的論文后來被譽為信息論的開山之作， 香農(nóng)提出的 信息熵也奠定了所有數(shù)據(jù)壓縮算法的理論基礎。利用信息熵公式，人們可以計算出信息編碼的極限，即在一定的概率模型下，無損壓縮的編碼長度不可能小于信息熵公式給出的結(jié)果。 1952年， Fano編碼。 1968 年前后， Shannon和 Fano的編碼方法，構(gòu)造出從數(shù)學角度看來更為完美的 ShannonFanoElias 編碼。1982年， Rissanen 和 。 Ziv和 Lempel 于 1977年發(fā)表題為 “ 順序數(shù)據(jù)壓縮的一個通用算法 (A Universal Algorithm for Sequential Data Compression） ” 的論文，后人稱 之 為 LZ77 算法。 1984年， T. A. Welch 發(fā)表了名為 “ 高性能數(shù)據(jù)壓縮技術(shù)（ A Technique for High Performance Data Compression） ” 的論文，描述了他在 Sperry 研究中心的研究成果，這是 LZ78算法的一個變種，也就是后來非常有名的 LZW算法。 壓縮分為有 損壓縮和無損壓縮。 4 LZW 壓縮算法 以色列數(shù)學家 Ziv和 Lemple在 IEEE上的兩篇文章，提出了兩種基于字典的壓縮算法，就是被廣泛引用的 LZ77和 LZ78算法，后來分別被改進成為 LZSS和 LZW，成了很長時間內(nèi)無失真壓縮的主流算法。 LZW壓縮算法 最終 由 LempleZivWelch 三個人 的名字命名。 LZW技術(shù)比其它大多數(shù)壓縮技術(shù)都復雜，壓縮效率也較高。在編碼時，數(shù)據(jù)流是輸入對象（ 圖像 的光柵數(shù)據(jù)序列），編碼流就是輸出對象（存儲在 GIF文件的 圖像 數(shù)據(jù)）；在解碼時，編碼流則是輸入對象，數(shù)據(jù)流是輸出對象；而編譯表是在編碼和解碼時都須要用借助的對象。 LZW壓縮的原理，就是先提取原始 圖像 數(shù)據(jù)中的不同圖案，基于這些圖案創(chuàng)建一個編譯表，然后用編譯表中的圖案索引來替代原始光柵數(shù) 據(jù)中的相應圖案，減少原始數(shù)據(jù)大小。 LZW 的編碼運算 LZW編碼運算的 第一步 ： 初始化一個編譯表 (String Table)，假設這個編譯表的大小是 12位的，也就是最多有 4096個單位，另外假設我們有 32個不同的字符（也可以認為 圖像 的每個像素最多有 32種顏色），表示為 a， b， c， d， e...，初始化編譯表：第 0項為 a，第 1項為 b，第 2項為 c...一直到第 31項，我們把這 32項就稱為根 (Root)?，F(xiàn)在來讀取數(shù)據(jù)流的第一個字符，假如為 p，那么 Current String就等于 [.c.]p（由于 [.c.]為空，實際上值就等于 p），現(xiàn)在在編譯表中查找有沒有Current String的值，由于 p就是一個根，我們已經(jīng)初始了 32個根，當然可以找到，把 p設為 Current Prefix 的值，不做任何事繼續(xù)讀取下一個字符，假設為 q， Current String就等于 [.c.]q（也就是 pq），看看在編譯表中有沒有該值，當然。繼續(xù)往下讀，如果在編譯表中可以查 找到 Current String 的值 ([.c.]k)，則把 Current String 的值 ([.c.]k)賦予 Current Prefix；如果查找不到，則添加 2022 級本科畢業(yè)設計論文 第 10 頁 共 26 頁 Current String的值 ([.c.]k)到編譯表，把 Current Prefix的值 ([.c.])在編譯表中所對應的索引輸出到編碼流，同時修改 Current Prefix 為 k ，這樣一直循環(huán)下去直到數(shù)據(jù)流結(jié)束。 LZW的壓縮編碼就從這個編譯表開始。 首先編譯表中的 0255分別對應了 256 個編譯表中的條目，即字節(jié)值 0255，所以消息中的每一單個的字符都在編譯表中出現(xiàn)過，或者說都能被檢測到，我們一步一步看其輸出編碼的過程和編譯表的變化，設當前位置為原消息中需要確定輸出編碼的字符所在位置，最初為 0，對應字符“ =”。 第 2步，從消息的第 1個位置開始，“ W”已經(jīng)在編譯表中了，而“ WE”不是，同樣的，輸出“ W”的編碼 87，同時把“ WE” 添加到編譯表中，編號為 257，當前位置變?yōu)?2，當前字符為“ E”。 第 4步，從消息的第 3個位置開始，“ D”已經(jīng)在編譯表中了，而“ D=” 不是，同樣的，輸出“ D”的編碼 68，同時把“ D=”添加到編譯表中，編號為 259，當前位置變?yōu)?4，當前字符為“ =”。 2022 級本科畢業(yè)設計論文 第 11 頁 共 26 頁 第 6步，從消息的第 6個位置開始，“ E”已經(jīng)在編譯表中了，而“ E=” 不是，輸出“ E”的編碼 69，同時把“ E=”添加到編譯表中，編號 為 261，當前位置變?yōu)?7，當前字符為“ =”。 第 8步，從消息的第 10個位置開始，“ E”、“ E=”（ 261）已經(jīng)在編譯表中了，而“ E=W” 不是，輸出“ E=”的編碼 261，同時把“ E=W”添加到編譯表中，編號為 263，當前位置變?yōu)?12，當前字符為“ W”。 第 10步，從消息的第 14個位置開始，“ B”已經(jīng)在編譯表中了，而“ B=” 不是，輸出“ B”的編碼 66，同時把“ B=”添加到編譯表中，編號為 265，當前位置變?yōu)?15，當前字符為“ =”。 第 12步，從消息的第 18個位置開始，“ T”已經(jīng)在編譯表中了，而其后沒有了字符，輸出“ T”的編碼 84即完成整個的編碼過程。 LZW 的解碼運算 數(shù)據(jù)的解碼，其實就是數(shù)據(jù)編碼的逆向過程，要從已經(jīng)編譯的數(shù)據(jù)（編碼流）中找出編譯表，然后對照編譯表還原 圖像 的光柵數(shù)據(jù)。 2022 級本科畢業(yè)設計論文 第 12 頁 共 26 頁 編碼（ Code） 前綴（ Prefix） ? ? 61 = ? ? 66 B ? ? 68 D 69 E ? ? 84 T ? ? 87 W ? ? 256 =W 257 WE 258 ED 259 D= 260 =WE 261 E= 262 =WEE 263 E=W 264 WEB 265 B= 266 =WET 當前字符序列 輸出編碼 新短語 (添至編譯表 ) =WED=WE=WEE=WEB=WET 61(=) 256(=W) WED=WE=WEE=WEB=WET 87(W) 257(WE) ED=WE=WEE=WEB=WET 69(E) 258(ED) D=WE=WEE=WEB=WET 68(D) 259(D=) =WE=WEE=WEB=WET 256(=W) 260(=WE) E=WEE=WEB=WET 69(E) 261(E=) =WEE=WEB=WET 260(=WE) 262(=WEE) E=WEB=WET 261(E=) 263(E=W) WEB=WET 257(WE) 264(WEB) B=WET 66(B) 265(B=) =WET 260(=WE) 266(=WET) T 84(T) 表 1 編碼生成的編譯表 表 2 編碼過程示意表 首先，還是要初始化編譯表。讀取第一個編碼到 [code]，這是一個根編碼，在編譯表中可以找到，把該編碼所對應的字符輸出到數(shù)據(jù)流， [old]=[code]；讀取下一個編碼到 [code]，這就有兩種情況：在編譯表中有或沒有該編碼，我們先來看第一種情況：先輸出當前編碼 [code]所對應的字符（串）到數(shù)據(jù)流，然后把 [old] 2022 級本科畢業(yè)設計論文 第 13 頁 共 26 頁 所對應的字符（串）當成 prefix [...]，當前編碼 [code]所對應的字符（串）的第一個字符當成 k，組合起來當前字符串 Current String 就為 [...]k，把 [...]k添加到編譯表，讀下一個編碼 ；我們來看看在編譯表中找不到該編碼的情況，回想一下編碼情況：如果數(shù)據(jù)流中有一個 p[...]p[...]pq 這樣的