lz78.txt

PDF文件格式解析库源代码

The LZ78 is a dictionary-based compression algorithm that maintains an
explicit dictionary. 

When a symbol that not yet in the dictionary is encountered, the codeword has the
index value 0 and it is added to the dictionary. With this method, the algorithm 
gradually builds up a dictionary. The codewords output by the algorithm consist of 
two elements: an index referring to the longest matching dictionary entry and
the first non-matching symbol.

Encode Algorithm:

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), symbol);
		add phrase to the dictionary;
		word <- NIL;
	}
}

Decode Algorithm:

(index, symbol) <- read pair from input

if (index = 0)
{
	add symbol to the dictionary
	output symbol
}
else
{
	word <- look up dictionary by index
	phrase <- word + symbol
	add phrase to the dictionary
	output phrase
}


LZ78 has several weaknesses. First of all, the dictionary grows without
bounds. Various methods have been introduced to prevent this, the easiest
being to become either static once the dictionary is full or to throw
away the dictionary and start creating a new one from scratch.

The inclusion of an explicitly
coded symbol into every match may cause the next match to be worse
than it could be if it were allowed to include this symbol.