LZW數據緊縮算法的道理剖析。本站提示廣大學習愛好者：（LZW數據緊縮算法的道理剖析）文章只能為提供參考，不一定能成為您想要的結果。以下是LZW數據緊縮算法的道理剖析正文
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,5代表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位。此處參照了http://blog.csdn.net/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,後綴變前綴
.......
一向處置到最初一個字符,
用一個表記載處置進程
CLEAR=256,END=257
.....
下面這個示例有些不克不及完全表現，別的一個例子是
原輸出數據為: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;
初始標號集因該為
而緊縮進程為:
.....
當停止到第12步的時刻，標號集應當為
8.LZW算法的偽代碼完成
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
9.LZW算法的流程圖
沒有安visio,畫了一個，比擬好看，
以上就是本文的全體內容，願望能給年夜家一個參考，也願望年夜家多多支撐。
