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