It should be noted that each time a new string is added to the dictionary the prefix part of that new string already exists in the dictionary. It never happens that such a prefix is not in the dictionary.
Thus instead of storing the entire byte string at the new dictionary position it's enough to store the last byte of the new string and an index to the prefix for that string. This way even very large strings will only require one byte and one index value in the dictionary.
Thus instead of containing [prefix]-B pairs,
each dictionary item can simply contain
<index>-B pairs,
greatly decreasing memory usage. Typically the index takes 4 bytes and thus
each string in the dictionary can be made to take only 5 bytes.
(In practice this requires the indices and the bytes to be stored in separate arrays, else the compiler will most probably allocate 4 bytes for the byte value for memory alignment reasons. Often this extra memory usage is not so critical, though, and a simple LZW implementation may well just put the indices and the bytes in the same array.)
This also makes comparing dictionary elements faster because only the index-byte pairs need to be compared instead of the full strings.
Note that also the first 256 elements in the dictionary, which had empty prefixes, have now index values instead of prefixes as well. However, these index values should still mean "empty prefix". This can be achieved by assigning an invalid index value to these prefix indices (eg. -1). Each time this invalid value is found as prefix index, it's simply interpreted as "empty prefix".
When this is done, the algorithm has to be changed to do the same thing
as well. That is, in the same way as the dictionary, instead of using a
prefix-byte pair, it should use an index-byte pair.
The fundamental difference comes in step 5 in the previous algorithm: The
[prefix] part should be assigned with the index of the string
in the dictionary. This index is automatically found when the string is
searched in the dictionary, so this is not a problem.
If we rewrite the algorithm using this system, using the notation
<index> for a dictionary index and
<index to empty>
as the invalid index value denoting an empty prefix, it becomes:
<index> ← <index to empty>
B ← next byte in the input.
<index>B in the dictionary?
<index> ← index of
<index>B in the dictionary.
<index>B to the dictionary.
<index> to the result.
<index> ← B
<index> to the result.
Note that "index of [prefix] in the dictionary"
becomes simply "<index>" because that's precisely what
"<index>" is.
Speedwise the main issue is step 4, ie. searching the string in the dictionary. A naive solution would be to perform a linear search throughout the entire dictionary. However, this is a very slow and inefficient solution. A very efficient algorithm for this will be discussed in part 4.
Part 3: LZW with dynamic bit sizes
Copyright 2007: Juha Nieminen