【文章內(nèi)容簡介】 LZW編碼運算的 第一步 ： 初始化一個編譯表 (String Table)，假設(shè)這個編譯表的大小是 12位的，也就是最多有 4096個單位，另外假設(shè)我們有 32個不同的字符（也可以認為 圖像 的每個像素最多有 32種顏色），表示為 a， b， c， d， e...，初始化編譯表：第 0項為 a，第 1項為 b，第 2項為 c...一直到第 31項，我們把這 32項就稱為根 (Root)。 開始編譯，先定義一個前綴對象 Current Prefix，記為 [.c.]，現(xiàn)在它是空的，然后定義一個當(dāng)前字符串 Current String，標(biāo)記為 [.c.]k， [.c.]就為 Current Prefix，k就為當(dāng)前讀取字符?，F(xiàn)在來讀取數(shù)據(jù)流的第一個字符，假如為 p，那么 Current String就等于 [.c.]p（由于 [.c.]為空，實際上值就等于 p），現(xiàn)在在編譯表中查找有沒有Current String的值，由于 p就是一個根，我們已經(jīng)初始了 32個根，當(dāng)然可以找到，把 p設(shè)為 Current Prefix 的值，不做任何事繼續(xù)讀取下一個字符，假設(shè)為 q， Current String就等于 [.c.]q（也就是 pq），看看在編譯表中有沒有該值，當(dāng)然。沒有，這時我們要做下面的事情：將 Current String 的值（也就是 pq）添加到編譯表的第 32項，把 Current Prefix 的值（也就是 p）在編譯表中的索引輸出到編碼流，修改 Current Prefix為 q。繼續(xù)往下讀，如果在編譯表中可以查 找到 Current String 的值 ([.c.]k)，則把 Current String 的值 ([.c.]k)賦予 Current Prefix；如果查找不到，則添加 2022 級本科畢業(yè)設(shè)計論文 第 10 頁 共 26 頁 Current String的值 ([.c.]k)到編譯表，把 Current Prefix的值 ([.c.])在編譯表中所對應(yīng)的索引輸出到編碼流，同時修改 Current Prefix 為 k ，這樣一直循環(huán)下去直到數(shù)據(jù)流結(jié)束。 來看一個具體的例子 ,我們假設(shè)字符集是 0255的 256個字節(jié)值，這 256個符號組成了一個初始的編譯表，分別編號為 0到 255。 LZW的壓縮編碼就從這個編譯表開始。對于消息 =WED=WE=WEE=WEB=WET 我們看如何進行編碼。 首先編譯表中的 0255分別對應(yīng)了 256 個編譯表中的條目，即字節(jié)值 0255，所以消息中的每一單個的字符都在編譯表中出現(xiàn)過，或者說都能被檢測到，我們一步一步看其輸出編碼的過程和編譯表的變化，設(shè)當(dāng)前位置為原消息中需要確定輸出編碼的字符所在位置，最初為 0，對應(yīng)字符“ =”。 第 1步，看當(dāng)前位置以及其后還有多長的字符，作為一個整體是編譯表的條目，顯然“ =”已經(jīng)在編譯表中，而“ =W”則不是，這時輸出“ =”的編碼 61，同時把“ =W”添加到編譯表中 (見表 1),所以編譯表的第 257個條目為“ =W”，令其編號為 256，當(dāng)前位置前移一位，變?yōu)?1，當(dāng)前字符為“ W”。 第 2步，從消息的第 1個位置開始，“ W”已經(jīng)在編譯表中了，而“ WE”不是，同樣的，輸出“ W”的編碼 87，同時把“ WE” 添加到編譯表中，編號為 257，當(dāng)前位置變?yōu)?2，當(dāng)前字符為“ E”。 第 3步，從消息的第 2個位置開始，“ E” 已經(jīng)在編譯表中了，而“ ED” 不是，同樣的，輸出“ E”的編碼 69，同時把“ ED” 添加到編譯表中，編號為 258，當(dāng)前位置變?yōu)?3，當(dāng)前字符為“ D”。 第 4步，從消息的第 3個位置開始，“ D”已經(jīng)在編譯表中了，而“ D=” 不是，同樣的，輸出“ D”的編碼 68，同時把“ D=”添加到編譯表中，編號為 259，當(dāng)前位置變?yōu)?4，當(dāng)前字符為“ =”。 第 5步，從消息的第 4個位置開始，“ =”和“ =W”（ 256）已經(jīng)在編譯表中了，而“ =WE” 不是，輸出“ =W”的編碼 256，同時把“ =WE”添加到編譯表中，編號為 260，當(dāng)前位置變?yōu)?6，當(dāng)前字符為“ E”。 2022 級本科畢業(yè)設(shè)計論文 第 11 頁 共 26 頁 第 6步，從消息的第 6個位置開始，“ E”已經(jīng)在編譯表中了，而“ E=” 不是，輸出“ E”的編碼 69，同時把“ E=”添加到編譯表中，編號 為 261，當(dāng)前位置變?yōu)?7，當(dāng)前字符為“ =”。 第 7步，從消息的第 7個位置開始，“ =”、“ =W”（ 256）、“ =WE”（ 260）已經(jīng)在編譯表中了，而“ =WEE” 不是，輸出“ =WE”的編碼 260，同時把“ =WEE” 添加到編譯表中，編號為 262，當(dāng)前位置變?yōu)?10，當(dāng)前字符為“ E”。 第 8步，從消息的第 10個位置開始，“ E”、“ E=”（ 261）已經(jīng)在編譯表中了，而“ E=W” 不是，輸出“ E=”的編碼 261，同時把“ E=W”添加到編譯表中，編號為 263，當(dāng)前位置變?yōu)?12，當(dāng)前字符為“ W”。 第 9步，從消息的第 12個位置 開始，“ W”、“ WE”（ 257）已經(jīng)在編譯表中了，而“ WEB” 不是，輸出“ WE”的編碼 257，同時把“ WEB”添加到編譯表中，編號為 264，當(dāng)前位置變?yōu)?14，當(dāng)前字符為“ B”。 第 10步，從消息的第 14個位置開始，“ B”已經(jīng)在編譯表中了，而“ B=” 不是，輸出“ B”的編碼 66，同時把“ B=”添加到編譯表中，編號為 265，當(dāng)前位置變?yōu)?15，當(dāng)前字符為“ =”。 第 11步，從消息的第 15個位置開始，“ =”、“ =W”（ 256）、“ =WE”（ 260）已經(jīng)在編譯表中了，而“ =WET” 不是，輸出“ =WE”的編碼 260，同時 把“ =WET” 添加到編譯表中，編號為 266，當(dāng)前位置變?yōu)?18，當(dāng)前字符為“ T”。 第 12步，從消息的第 18個位置開始，“ T”已經(jīng)在編譯表中了，而其后沒有了字符，輸出“ T”的編碼 84即完成整個的編碼過程。 整個的編碼結(jié)果為“ 6 8 6 6 25 6 260、 26 25 6 260、 84” (見表 2)。 LZW 的解碼運算 數(shù)據(jù)的解碼，其實就是數(shù)據(jù)編碼的逆向過程，要從已經(jīng)編譯的數(shù)據(jù)（編碼流）中找出編譯表，然后對照編譯表還原 圖像 的光柵數(shù)據(jù)。 壓縮過程中建立起來的龐大字典不需要傳遞給 LZW 的解 碼程序，這是 LZW效率的一個主要方面。 2022 級本科畢業(yè)設(shè)計論文 第 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 當(dāng)前字符序列 輸出編碼 新短語 (添至編譯表 ) =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 編碼過程示意表 首先，還是要初始化編譯表。 壓縮 文件的數(shù)據(jù)的第一個字節(jié)存儲的就是 LZW編碼的編碼大?。?若是圖像文件 等于 圖像 的位數(shù)），根據(jù)編碼大小，初始化編譯表的根條目（從 “ 0” 到 “ 2 的編碼大小次方 1” ），然后定義一個當(dāng)前編碼 Current Code，記作 [code]，定義一個 Old Code，記作 [old]。讀取第一個編碼到 [code]，這是一個根編碼，在編譯表中可以找到，把該編碼所對應(yīng)的字符輸出到數(shù)據(jù)流， [old]=[code]；讀取下一個編碼到 [code]，這就有兩種情況：在編譯表中有或沒有該編碼，我們先來看第一種情況：先輸出當(dāng)前編碼 [code]所對應(yīng)的字符（串）到數(shù)據(jù)流，然后把 [old]