maintitle.gif (3356 bytes)
menu_intro.gif (1886 bytes)
menu_bar_78.GIF (1870 bytes)

Variations of LZW Compression

 

Method

Author

Year

Description

LZ77 Ziv and Lempel

1977

Send pairs with pointer and character. Pointer is fix-size and indicates a substring in the previous N characters.
LZR Rodeh et al.

1981

Send pairs with pointer and character. Pointer is variable-size and indicates a substring anywhere in the previous characters.
LZSS Bell

1986

A flag bit distinguishes sending of pointer or character. Pointer is fix-size and indicates a substring in the previous N characters.
LZB Bell

1987

Same as LZSS, except that pointer is variable-size
LZH Bell

1987

Same as LZSS, except that Huffman coding is used for pointers on a second pass.
LZ78 Ziv and Lempel

1978

Send pairs of pointer and character. Pointer indicates a previously parsed substring which is stored in a dictionary
LZW Welch

1984

Include all alphabets in dictionary initially. Therefore only outputs fix-size pointers.
LZC Thoman et al.

1985

As suggested by Welch, a variable-size pointer scheme is implemented.
LZT Tischer

1987

Same as LZW, except that the parsed strings in dictionary are stored as a Least Recently Used list.
LZJ Jakobsson

1985

Same as LZW, except that pointers can reach anywhere in the previous characters.
LZFG Fiala and Greece

1989

By breaking up strings in the sliding window, pointers are formed from a tree data structure.

Table 1: Summary of principal LZ variations. (N is the size of window used in dictionary)

 

Dictionary-based Compressors
Concept
Algorithm
Example
Variations

back to top | home