maintitle.gif (3356 bytes)
menu_intro.gif (1886 bytes)
menu_bar_77.GIF (1845 bytes)
 
lossless.jpg (77783 bytes)

Dictionary-based Compressors
Concept
Algorithm
Example
Shortcomings
Variations

The Algorithm

To encode the sequence in the look-ahead buffer, the encoder moves a search pointer back through the search buffer until it encounters a match to the first symbol in the look-ahead buffer. The distance of the pointer from the look-ahead buffer is called the offset. The encoder then examines the symbols following the symbol at the pointer location to see if they match consecutive symbols in the look-ahead buffer. The number of consecutive symbols in the search buffer that match consecutive symbols in the look-ahead buffer, starting with the first symbol, is called the length of the match. The encoder searches the search buffer for the longest match. Once the longest match has been found, the encoder encodes it with a triple <o, l, c>, where o is the offset, l is the length of the match, and c is the codeword corresponding to the symbol in the look-ahead buffer that follows the match. For example, in the diagram above, the longest match is the first ‘a’ of the search buffer. The offset o in this case is 7, the length of the match l is 4, and the symbol in the look-ahead buffer following the match is ‘r’. The reason for sending the third element in the triple is to take care of the situation where no match for the symbol in the look-ahead buffer can be found in the search buffer. In this case, the offset and match-length values are set to 0, and the third element of the triple is the code for the symbol itself.

The algorithm looks like the following:

while( lookAheadBuffer not empty )
{
    get a pointer (position, match) to the longest match
    in the window for the lookAheadBuffer;

    output a (position, length, char()) triple;
    shift the window length+1 characters along;
}

 For the decoding process, it is basically a table loop-up procedure and can be done by reversing the encoding procedures. We employ the same buffer sized n characters, and then use its first (N-n) spaces to hold the previously decoded characters, where N is the size of the window (sum of the size of the look-ahead buffer and the search buffer) used in the encoding process. If we break up each triple that we encounter back into its components:- position offset o, match length l, and the last symbol of the incoming stream c, we extract the match string from buffer according to o, and thus obtain the original content. What has been shifted out of the buffer is sent to the output. The process continues until all code words have been decoded, and the decoding is then complete.

 

back to top | home