📄 lzwexp.htm
字号:
<html>
<head>
<title>file:///d:/程序资料/format2/lzwexp.txt</title>
</head>
<body background="../jpg/di1.JPG">
<p align="center"><font size="6" color="#0000ff">lzw and gif explained----steve blackstock</font></p>
<div align="center"><center>
<table border="0" width="80%">
<tr>
<td width="100%"> <pre> i hope this little document will help enlighten those of you out there
who want to know more about the lempel-ziv welch compression algorithm, and,
specifically, the implementation that gif uses.
before we start, here's a little terminology, for the purposes of this
document:</pre>
<pre> "character": a fundamental data element. in normal text files, this is
just a single byte. in raster images, which is what we're interested in, it's
an index that specifies the color of a given pixel. i'll refer to an arbitray
character as "k".
"charstream": a stream of characters, as in a data file.
"string": a number of continuous characters, anywhere from one to very
many characters in length. i can specify an arbitrary string as "[...]k".
"prefix": almost the same as a string, but with the implication that a
prefix immediately precedes a character, and a prefix can have a length of
zero. so, a prefix and a character make up a string. i will refer to an
arbitrary prefix as "[...]".
"root": a single-character string. for most purposes, this is a
character, but we may occasionally make a distinction. it is [...]k, where
[...] is empty.
"code": a number, specified by a known number of bits, which maps to a
string.
"codestream": the output stream of codes, as in the "raster data"
"entry": a code and its string.
"string table": a list of entries; usually, but not necessarily, unique.
that should be enough of that.</pre>
<pre> lzw is a way of compressing data that takes advantage of repetition of
strings in the data. since raster data usually contains a lot of this
repetition, lzw is a good way of compressing and decompressing it.
for the moment, lets consider normal lzw encoding and decoding. gif's
variation on the concept is just an extension from there.
lzw manipulates three objects in both compression and decompression: the
charstream, the codestream, and the string table. in compression, the
charstream is the input and the codestream is the output. in decompression,
the codestream is the input and the charstream is the output. the string table
is a product of both compression and decompression, but is never passed from
one to the other.
the first thing we do in lzw compression is initialize our string table.
to do this, we need to choose a code size (how many bits) and know how many
values our characters can possibly take. let's say our code size is 12 bits,
meaning we can store 0->fff, or 4096 entries in our string table. lets also
say that we have 32 possible different characters. (this corresponds to, say,
a picture in which there are 32 different colors possible for each pixel.) to
initialize the table, we set code#0 to character#0, code #1 to character#1,
and so on, until code#31 to character#31. actually, we are specifying that
each code from 0 to 31 maps to a root. there will be no more entries in the
table that have this property.
now we start compressing data. let's first define something called the
"current prefix". it's just a prefix that we'll store things in and compare
things to now and then. i will refer to it as "[.c.]". initially, the current
prefix has nothing in it. let's also define a "current string", which will be
the current prefix plus the next character in the charstream. i will refer to
the current string as "[.c.]k", where k is some character. ok, look at the
first character in the charstream. call it p. make [.c.]p the current string.
(at this point, of course, it's just the root p.) now search through the
string table to see if [.c.]p appears in it. of course, it does now, because
our string table is initialized to have all roots. so we don't do anything.
now make [.c.]p the current prefix. look at the next character in the
charstream. call it q. add it to the current prefix to form [.c.]q, the
current string. now search through the string table to see if [.c.]q appears
in it. in this case, of course, it doesn't. aha! now we get to do something.
add [.c.]q (which is pq in this case) to the string table for code#32, and
output the code for [.c.] to the codestream. now start over again with the
current prefix being just the root p. keep adding characters to [.c.] to form
[.c.]k, until you can't find [.c.]k in the string table. then output the code
for [.c.] and add [.c.]k to the string table. in pseudo-code, the algorithm
goes something like this:</pre>
<pre> [1] initialize string table;
[2] [.c.] <- empty;
[3] k <- next character in charstream;
[4] is [.c.]k in string table?
(yes: [.c.] <- [.c.]k;
go to [3];
)
(no: add [.c.]k to the string table;
output the code for [.c.] to the codestream;
[.c.] <- k;
go to [3];
)</pre>
<pre> it's as simple as that! of course, when you get to step [3] and there
aren't any more characters left, you just output the code for [.c.] and throw
the table away. you're done.
wanna do an example? let's pretend we have a four-character alphabet:
a,b,c,d. the charstream looks like abacaba. let's compress it. first, we
initialize our string table to: #0=a, #1=b, #2=c, #3=d. the first character is
a, which is in the string table, so [.c.] becomes a. next we get ab, which is
not in the table, so we output code #0 (for [.c.]),
and add ab to the string table as code #4. [.c.] becomes b. next we get
[.c.]a = ba, which is not in the string table, so output code #1, and add ba
to the string table as code #5. [.c.] becomes a. next we get ac, which is not
in the string table. output code #0, and add ac to the string table as code
#6. now [.c.] becomes c. next we get [.c.]a = ca, which is not in the table.
output #2 for c, and add ca to table as code#7. now [.c.] becomes a. next we
get ab, which is in the string table, so [.c.] gets ab, and we look at aba,
which is not in the string table, so output the code for ab, which is #4, and
add aba to the string table as code #8. [.c.] becomes a. we can't get any more
characters, so we just output #0 for the code for a, and we're done. so, the
codestream is #0#1#0#2#4#0.
a few words (four) should be said here about efficiency: use a hashing
strategy. the search through the string table can be computationally
intensive, and some hashing is well worth the effort. also, note that
"straight lzw" compression runs the risk of overflowing the string table -
getting to a code which can't be represented in the number of bits you've set
aside for codes. there are several ways of dealing with this problem, and gif
implements a very clever one, but we'll get to that.
an important thing to notice is that, at any point during the
compression, if [...]k is in the string table, [...] is there also. this fact
suggests an efficient method for storing strings in the table. rather than
store the entire string of k's in the table, realize that any string can be
expressed as a prefix plus a character: [...]k. if we're about to store [...]k
in the table, we know that [...] is already there, so we can just store the
code for [...] plus the final character k.
ok, that takes care of compression. decompression is perhaps more
difficult conceptually, but it is really easier to program.
here's how it goes: we again have to start with an initialized string
table. this table comes from what knowledge we have about the charstream that
we will eventually get, like what possible values the characters can take. in
gif files, this information is in the header as the number of possible pixel
values. the beauty of lzw, though, is that this is all we need to know. we
will build the rest of the string table as we decompress the codestream. the
compression is done in such a way that we will never encounter a code in the
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -