LZW壓縮的基本原理

1. 簡介

一種通用的無損的資料壓縮算法。

2. 術語

   1)'Character': 字元，一種基礎資料元素，在普通文本檔案中，它占用1個單獨的byte，而在圖像中，它卻是 一種代表給定像素顔色的索引值。

   2)'CharStream'：資料檔案中的字元流。

   3)'Prefix':字首。如這個單詞的含義一樣，代表着在一個字元最直接的前一個字元。一個字首字元長度可以為0,一個prefix和一個character可以組成一個字元串(string),

   4)'Suffix': 字尾，是一個字元，一個字元串可以由(A,B)來組成，A是字首,B是字尾,當A長度為0的時候，代表Root，根

   5)'Code:碼,用于代表一個字元串的位置編碼

   6)'Entry'，一個Code和它所代表的字元串(string)

3. 執行個體分析

輸入流，也就是原始的資料為:255,24,54,255,24,255,255,24,5,123,45,255,24,5,24,54..................

   這個正好可以看到是gif檔案中像素數組的一部分，如何對它進行壓縮

   因為原始資料可以用8bit來表示，故清除标志Clear=255+1 =256,結束标志為End=256+1=257，目前标号集為

   0 1 2 3 .................................................................................255 CLEAR END

   第一步,讀取第一個字元為255,在标記表裡面查找，255已經存在，我們已經認識255了，不做處理

   第二步,取第二個字元，此時字首為A,形成目前的Entry為(255,24),在标記集合不存在，我們并不認識255,24好，這次你小子來了，我就記住你，把它在标記集合中标記為258,然後輸出字首A,保留字尾24，并作為下一次的字首（字尾變字首)

   第三步，取第三個字元為54，目前Entry(24,54),不認識，記錄(24,54)為标号259,并輸出24,字尾變字首

   第四部：取第四個字元255,Entry=(54,255),不認識，記錄(54,255)為标号260,輸出54,字尾變字首

   第五步   取第5個字元24，entry=(255,24),啊，認識你，這不是老258麼，于是把字元串規約為258，并作為字首

   第六步  取第六個字元255,entry=(258,255)，不認識，記錄(258,255)為261,輸出258,字尾變字首

   .......

  一直處理到最後一個字元,

  用一個表記錄處理過程

   CLEAR=256,END=257

第幾步	字首	字尾	Entry	認識(Y/N)	輸出	标号
1	255	（，255）
2	255	24	(255,24)	N	255	258
3	24	54	(24,54)	N	24	259
4	54	255	(54,255)	N	54	260
5	255	24	(255,24)	Y
6	258	255	(258,255)	N	258	261
7	255	255	(255,255)	N	255	262

.....

上面這個示例有些不能完整展現，另外一個例子是

原輸入資料為: A B A B A B A B B B A B A B A A C D A C D A D C A B A A A B A B .....

采用LZW算法對其進行壓縮，壓縮過程用一個表來表述為:

注意原資料中隻包含4個character,A,B,C,D

用兩bit即可表述，根據lzw算法，首先擴充一位變為3為,Clear=2的2次方+1=4; End=4+1=5;

初始标号集因該為

1	2	3	4	5
A	B	C	D	Clear	End

而壓縮過程為:

第幾步	字首	字尾	Entry	認識(Y/N)	輸出	标号
1	A	（，A）
2	A	B	(A,B)	N	A	6
3	B	A	(B,A)	N	B	7
4	A	B	(A,B)	Y
5	6	A	(6,A)	N	6	8
6	A	B	(A,B)	Y
7	6	A	(6,A)	Y
8	8	B	(8,B)	N	8	9
9	B	B	(B,B)	N	B	10
10	B	B	(B,B)	Y
11	10	A	(10,A)	N	10	11
12	A	B	(A,B)	Y

.....

當進行到第12步的時候，标号集應該為

1	2	3	4	5	6	7	8	9	10	11
A	B	C	D	Clear	End	AB	BA	6A	8B	BB	10A

4. 僞代碼實作

STRING = get input character
 WHILE there are still input characters DO
     CHARACTER = get input character
     IF STRING+CHARACTER is in the string table then
         STRING = STRING+character
     ELSE
         output the code for STRING
         add STRING+CHARACTER to the string table
         STRING = CHARACTER
    END of IF
END of WHILE
output the code for STRING 


           

5. 來源

Robin's Space