lzw.txt

PDF文件格式解析库源代码

This improved version of the original LZ78 algorithm is perhaps the most
famous modification. Published by Terry Welch in 1984, it basically
applies the LZSS principle of not explicitly transmitting the next nonmatching
symbol to the LZ78 algorithm. 

The only remaining output of this improved algorithm are fixed-length references 
to the dictionary (indexes).  The dictionary has to be initialized with
all the symbols of the input alphabet and this initial dictionary needs to
be made known to the decoder.

Encode Algorithm:

initialize dictionary;
word <- NIL;

while (there is input)
{
	symbol <- next symbol from input;
	phrase <- word + symbol;
	
	if (phrase exists in the dictionary)
	{
		word <- phrase;
	}
	else
	{
		output (index(word));
		add phrase to the dictionary;
		word <- symbol;
	}
}
output (index(word));

Decode Algorithm:

initialize dictionary;
phrase <- NIL;

while (there is input)
{
	wordIndex <- next code from input;
	
	if (wordIndex exists in the dictionary)
	{
		word <- dictionary[wordIndex];
		phrase <- phrase + head(word);
		if(phrase.Length > 1)
		{
			add phrase to the dictionary;
		}
	}
	else
	{
		phrase <- phrase + head(phrase);
		add phrase to the dictionary;
		word <- phrase; //word <- dictionary[wordIndex];
	}
	phrase <- word;
	output (word);
}

In the original proposal, the pointer size is chosen to be 12 bit, allowing
for up to 4096 dictionary entries. Once this limit has been reached, the
dictionary becomes static.

GIF image compression is originally developed by CompuServe in the late 1980s,
the GIF file format employs the LZW technique for compression.

LZC is the variant of the LZW. It compresses according to the LZW principle
but returns to variable-length pointers like the original LZ78 algorithm.
It first starts with 9-bit indexes for the first 512 dictionary entries, 
then continues with 10-bit codes and so on until the user-specified limit has been
reached. Finally, the algorithm becomes a static encoder, regularly checking
the compression ratio. When it detects a decrease, it throws away the
dictionary and starts building up a new one from scratch.

LZFG uses the dictionary building technique from the original LZ78 algorithm,
but stores the elements in a trie data structure. In addition, a
sliding window like LZ77’s is used to remove the oldest entries from the
dictionary.