Reduced Offset Lempel Ziv
Reduced Offset Lempel Ziv , ( ROLZ ) is a data compression algorithm that was developed by Ross Williams. It is a dictionary method that is based on LZ77 , but in contrast to it, uses context-related methods. In terms of software, the concept was first implemented by Malcolm Taylor in his data compression program RK (or WinRK ). There is a free implementation (under LGPL ) with the QUAD compressor from Ilia Muraviev .
Versions of the algorithm
The attempt to reduce the possible values of the offsets has been made by many authors. Noteworthy here are:
LZFG-C2 (Edward R. Fiala, Daniel H. Greene, 1989)
Matches are not stored as pairs of length and offset, but by a special mark that belongs to a particular line in the dictionary.
LZRW4 (Ross Williams, 1991)
The Ross Williams LZRW4 algorithm corresponds to the ROLZ. Although the author did not make a usable implementation, his sample compressor roughly implements the ROLZ algorithm.
LZP1 – LZP4 (Charles Bloom, 1995)
LZP is a dictionary compressor whose coding of the matches works completely without offsets. For this purpose, the length of the match with the character string following the last occurrence of the previous context is stored in a list.
LZ77-PM (Dzung T. Hoang, Philip M. Long, Jeffrey Scott Vitter, 1995)
This algorithm differs from ROLZ only in that the context preceding a match may be of variable length instead of a context of a fixed degree.
ROLZ2 – ROLZ3 (Malcolm Taylor, 2005)
These algorithms are further developments of the original ROLZ:
- ROLZ2 should ensure maximum unpacking speeds
- ROLZ3 aims for maximum packing rates with negligible loss of speed when unpacking
Web links
- msoftware.co.nz - website of RK and WinRK
- quad.sourceforge.net - data compression program with open source implementation (under LGPL)
- ross.net/compression - descriptions and implementations of LZRW1 – LZRW4. The article on LZRW4 contains a theoretical treatise on the benefits of ROLZ.
- cbloom.com/src/index_lz.html - descriptions and implementations of various variants of LZP and LZCB
- arturocampos.com/ac_lzp.html - very useful description of Arturo Campos' LZP algorithm