Reduced-offset Lempel Ziv
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)(Learn how and when to remove this template message)
||It has been suggested that this article be merged with LZ77 and LZ78. (Discuss) Proposed since August 2016.|
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
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)
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)
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)
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)
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)
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
- Quad data compression program with open source implementation (LGPL)
- descriptions and implementations of LZRW1–LZRW4. The article contains a theoretical treatise on LZRW4 about the benefits of ROLZ.
- descriptions and implementations of various versions of LZP and LZCB
- description of the LZP algorithm by Arturo Campos
|This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.|