📄 lzw.htm
字号:
<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=gb2312">
<title>lzw compression</title>
<meta name="generator" content="microsoft frontpage 3.0">
</head>
<body background="../jpg/di1.JPG">
<div align="center"><center>
<table border="0" width="88%">
<tr>
<td width="100%"><p align="center"><font size="6" color="#0000ff">lzw compression</font></p>
<font face="宋体" size="3"><p>lzw compression used to encode/decode a gif file by bob
montgomery </p>
<hr>
<p>encoder</p>
<p>consider the following input data stream in a 4 color (a, b, c, d) system. we will
build a table of codes which represent strings of colors. each time we find a new string,
we will give it the next code, and break it into a prefix string and a suffix color. the
symbols \ or --- represent the prefix string, and / represents the suffix color. the first
4 entries in the table are the 4 colors with codes 0 thru 3, each of which represents a
single color. the next 2 codes (4 and 5) are the clear code and the end of image code. the
first available code to represent a string of colors is 6. each time we find a new code,
we will send the prefix for that code to the output data stream. </p>
<p>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 .....<br>
\/\/---/-----/\/---/-------/\/ \/ \ /\/---/---/\ /\/-----/---/---/<br>
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 code<br>
6 8 10 8 14 16 8 13 7 prefix</p>
<p>the encoder table is built from input data stream. always start with the suffix of last
code, and keep getting colors until you have a new combination.</p>
<p>color code prefix suffix string output<br>
a 0 -<br>
b 1 -<br>
c 2 -<br>
d 3 -<br>
clear 4 -<br>
end 5 -</p>
<p>a \ a a first color is a special case.<br>
b / \ 6 a b ab a<br>
a | / 7 b a ba b<br>
b |<br>
a / | 8 6 a aba 6<br>
b |<br>
a |<br>
b \ / 9 8 b abab 8<br>
b / | 10 b b bb b<br>
b |<br>
a | / 11 10 a bba 10<br>
b |<br>
a |<br>
b |<br>
a / \ 12 9 a ababa 9<br>
a \ / 13 a a aa a<br>
c / \ 14 a c ac a<br>
d \ / 15 c d cd c<br>
a / | 16 d a da d<br>
c |<br>
d | / 17 14 d acd 14<br>
a |<br>
d / \ 18 16 d dad 16<br>
c \ / 19 d c dc d<br>
a / | 20 c a ca c<br>
b |<br>
a |<br>
a | / 21 8 a abaa 8<br>
a |<br>
b / | 22 13 b aab 13<br>
a |<br>
b / 23 7 b bab 7</p>
<p>the resultant output stream is: a b 6 8 b 10 9 a a c d 14 16 d c 8 .... </p>
<p>the gif encoder starts with a code length of 2+1=3 bits for 4 colors, so when the code
reaches 8 we will have to increase the code size to 4 bits. similarly, when the code gets
to 16 we will have to increse the code size to 5 bits, etc. if the code gets to 13 bits,
we send a clear code and start over. see gifencod.gif for a flow diagram of the encoding
process. this uses a tree method to search if a new string is already in the table, which
is much simpler, faster, and easier to understand than
hashing.===========================================================================</p>
<p>decoder</p>
<p>we will now see if we can regenerate the original data stream and duplicate the table
looking only at the output data stream generated by the encoder on the previous page. the
output data stream is:</p>
<p>a b 6 8 b 10 9 a a c d 14 16 d c 8 ....</p>
<p>the docoding process is harder to see, but easier to implement, than the encoding
process. the data is taken in pairs, and a new code is assigned to each pair. the prefix
is the left side of the pair, and the suffix is the color that the right side of the pair
decomposes to from the table. the decomposition is done by outputing the suffix of the
code, and using the prefix as the new code. the process repeats until the prefix is a
single color, and it is output too. the output of the decomposition is pushed onto a
stack, and then poped off the stack to the display, which restores the original order that
the colors were seen by the encoder. we will go thru the first few entries in detail,
which will hopefully make the process clearer. </p>
<p>the first pair is (a b), so the prefix of code 6 is a and the suffix is b, and 6
represents the string ab. the color a is sent to the display. the 2nd pair is (b 6), so
the prefix of code 7 is b and the suffix is the the last color in the decomposition of
code 6. code 6 decomposes into ba, so code 7 = ba, and has a suffix a. the color b is sent
to the display. the 3rd pair is (6 8) and the next code is 8. how can we decompose 8. we
know that the prefix of code 8 is 6, but we don't know the suffix. the answer is that we
use the suffix of the prefix code; a in this case since the suffix of 6 is a. thus, code 8
= aba and has a suffix a. we decompose 6 to get ba, which becomes ab when we pop it off
the stack to the display. the 4th pair is (8 b), so code 9 has a prefix of 8 and a suffix
of b, and code 9 = abab. we output aba to the stack, and pop it off to the display as
aba.the 5th pair is (b 10) and the next code is 10. the prefix of code 10 is b and the
suffix is b (since the prefix is b). code 10 = bb, and we output the prefix b to the
display.</p>
<p>the 6th pair is (10 9) and the next code is 11. thus the prefix of code 11 is 10 and
the suffix is the last color in the decomposition of 9, which is a. thus code 11 = bba,
and we output bb to the display. so far, we have output the correct colors stream a b ab
aba b bb to the display, and have duplicated the codes 6 thru 11 in the encoder table.
this process is repeated for the whole data stream to reconstruct the original color
stream and build a table identical to the one built by the encoder. we start the table
with codes 0-5 representing the 4 colors, the clear code, and the end code. when we get to
code 8, we must increse the code size to 5 bits, etc. see gifdecod.gif for a flow diagram
of the decoding process.</p>
<p>i hope this helps take some of the mystery out of lzw compression, which is really
quite easy once you 'see' it. bob montgomery</font></td>
</tr>
</table>
</center></div>
<p align="center"><a href="../index.htm">返回</a></p>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -