Reduced-offset Lempel Ziv

From Wikipedia, the free encyclopedia
  (Redirected from Reduced Offset Lempel Ziv)
Jump to: navigation, search

Reduced-offset Lempel Ziv (ROLZ) is a data compression algorithm, which was developed by Ross Williams. It is a dictionary method, building on LZ77.

The technical concept was first described by Malcolm Taylor in his data compression program RK (or WinRK). By QUAD -Compressor of Ilia Muraviev there is a free implementation (under LGPL)

Versions of the algorithm[edit]

Trying to reduce the possible values of the offsets, has been made by many authors. Noteworthy are here:

LZFG-C2 (Edward R. Fiala, Daniel H. Greene, 1989)[edit]

Matches are not stored as pairs of length and offset, but by a special mark, which belong to a specific line in the dictionary.

LZRW4 (Ross Williams, 1991)[edit]

The LZRW4 algorithm by Ross Williams corresponds to ROLZ. Although the author undertook no useful implementation, realized his example compressor roughly the ROLZ algorithm.

LZP1–LZP4 (Charles Bloom, 1995)[edit]

LZP is a dictionary compressor whose coding of matches operates completely without offsets. Given the length of the agreement will be saved with the following on the last occurrence of the preceding context string in a list.

LZ77 PM (T. Hoang Dzung, Philip M. Long, Jeffrey Scott Vitter, 1995)[edit]

This algorithm differs from ROLZ only in that of a match previous context may be of variable length, instead of a context specified degree.

ROLZ2–ROLZ3 (Malcolm Taylor, 2005)[edit]

These algorithms are further developments of the original ROLZ:

  • ROLZ2 to ensure maximum decompression speed
  • ROLZ3 aims at maximum packing rate with negligible loss of speed when unpacking

External links[edit]