其實，關於在LZW中使用散列的具體做法有很多種，開發者基於時間/空間上的不同考慮，會選擇不同的解決方案。
LZW算法中，首先建立壹個字符串表，把每壹個第壹次出現的字符串放入串表中，並用壹個數字來表示，這個數字與此字符串在串表中的位置有關，並將這個數字存入壓縮文件中，如果這個字符串再次出現時，即可用表示它的數字來代替，並將這個數字存入文件中。壓縮完成後將串表丟棄。如"print" 字符串，如果在壓縮時用266表示，只要再次出現，均用266表示，並將"print"字符串存入串表中，在圖象解碼時遇到數字266，即可從串表中查出266所代表的字符串"print"，在解壓縮時，串表可以根據壓縮數據重新生成。
壓縮算法的簡單示例，不是完全實現LZW算法，只是從最直觀的角度看lzw算法的思想
對原始數據ABCCAABCDDAACCDB進行LZW壓縮
原始數據中，只包括4個字符(Character),A,B,C,D,四個字符可以用壹個2bit的數表示，0-A,1-B,2-C,3-D,從最直觀的角度看，原始字符串存在重復字符：ABCCAABCDDAACCDB，用4代表AB,4代表CC，上面的字符串可以替代表示為:45A4CDDAA5DB,這樣是不是就比原數據短了壹些呢！
-------------------------------------------------------
LZW數據壓縮算法的原理分析
我希望通過本文的介紹，能給那些目前不太了解lzw算法和該算法在gif圖像中應用，但渴望了解它的人壹些啟發和幫助。拋磚引玉而已，更希望園子裏面兄弟提出寶貴的意見。
1.LZW的全稱是什麽?
Lempel-Ziv-Welch (LZW).
2. LZW的簡介和壓縮原理是什麽？
LZW壓縮算法是壹種新穎的壓縮方法，由Lemple-Ziv-Welch 三人***同創造，用他們的名字命名。它采用了壹種先進的串表壓縮，將每個第壹次出現的串放在壹個串表中，用壹個數字來表示串，壓縮文件只存貯數字，則不存貯串，從而使圖象文件的壓縮效率得到較大的提高。奇妙的是，不管是在壓縮還是在解壓縮的過程中都能正確的建立這個串表，壓縮或解壓縮完成後，這個串表又被丟棄。
LZW算法中，首先建立壹個字符串表，把每壹個第壹次出現的字符串放入串表中，並用壹個數字來表示，這個數字與此字符串在串表中的位置有關，並將這個數字存入壓縮文件中，如果這個字符串再次出現時，即可用表示它的數字來代替，並將這個數字存入文件中。壓縮完成後將串表丟棄。如"print" 字符串，如果在壓縮時用266表示，只要再次出現，均用266表示，並將"print"字符串存入串表中，在圖象解碼時遇到數字266，即可從串表中查出266所代表的字符串"print"，在解壓縮時，串表可以根據壓縮數據重新生成。
3.在詳細介紹算法之前，先列出壹些與該算法相關的概念和詞匯
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)
4.壓縮算法的簡單示例，不是完全實現LZW算法，只是從最直觀的角度看lzw算法的思想
對原始數據ABCCAABCDDAACCDB進行LZW壓縮
原始數據中，只包括4個字符(Character),A,B,C,D,四個字符可以用壹個2bit的數表示，0-A,1-B,2-C,3-D,從最直觀的角度看，原始字符串存在重復字符：ABCCAABCDDAACCDB，用4代表AB,4代表CC，上面的字符串可以替代表示為:45A4CDDAA5DB,這樣是不是就比原數據短了壹些呢！
5.LZW算法的適用範圍
為了區別代表串的值(Code)和原來的單個的數據值(String)，需要使它們的數值域不重合，上面用0-3來代表A-D,那麽AB就必須用大於3的數值來代替，再舉另外壹個例子，原來的數值範圍可以用8bit來表示，那麽就認為原始的數的範圍是0～255，壓縮程序生成的標號的範圍就不能為0～255（如果是0-255，就重復了）。只能從256開始，但是這樣壹來就超過了8位的表示範圍了，所以必須要擴展數據的位數，至少擴展壹位，但是這樣不是增加了1個字符占用的空間了麽？但是卻可以用壹個字符代表幾個字符，比如原來255是8bit,但是現在用256來表示254，255兩個數，還是劃得來的。從這個原理可以看出LZW算法的適用範圍是原始數據串最好是有大量的子串多次重復出現，重復的越多，壓縮效果越好。反之則越差，可能真的不減反增了。
6.LZW算法中特殊標記
隨著新的串(string)不斷被發現，標號也會不斷地增長，如果原數據過大，生成的標號集（string table)會越來越大，這時候操作這個集合就會產生效率問題。如何避免這個問題呢?Gif在采用lzw算法的做法是當標號集足夠大的時候，就不能增大了，幹脆從頭開始再來，在這個位置要插入壹個標號，就是清除標誌CLEAR，表示從這裏我重新開始構造字典，以前的所有標記作廢，開始使用新的標記。
這時候又有壹個問題出現，足夠大是多大？這個標號集的大小為比較合適呢？理論上是標號集大小越大，則壓縮比率就越高，但開銷也越高。 壹般根據處理速度和內存空間連個因素來選定。GIF規範規定的是12位，超過12位的表達範圍就推倒重來，並且GIF為了提高壓縮率，采用的是變長的字長。比如說原始數據是8位，那麽壹開始，先加上壹位再說，開始的字長就成了9位，然後開始加標號，當標號加到512時，也就是超過9為所能表達的最大數據時，也就意味著後面的標號要用10位字長才能表示了，那麽從這裏開始，後面的字長就是10位了。依此類推，到了2^12也就是4096時，在這裏插壹個清除標誌，從後面開始，從9位再來。
GIF規定的清除標誌CLEAR的數值是原始數據字長表示的最大值加1，如果原始數據字長是8，那麽清除標誌就是256，如果原始數據字長為4那麽就是16。另外GIF還規定了壹個結束標誌END，它的值是清除標誌CLEAR再加1。由於GIF規定的位數有1位（單色圖），4位（16色）和8位（256色），而1位的情況下如果只擴展1位，只能表示4種狀態，那麽加上壹個清除標誌和結束標誌就用完了，所以1位的情況下就必須擴充到3位。其它兩種情況初始的字長就為5位和9位。此處參照了/whycadi/
7.用lzw算法壓縮原始數據的示例分析
輸入流，也就是原始的數據為: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,後綴變前綴
.......
壹直處理到最後壹個字符