This topic encompasses the LZ77 algorithm and its descendant, LZSS. This is one of two seminal LZ compression algorithms developed in the late 70s. LZSS forms the core of the popular deflate algorithm when combined with a Huffman encoder on the back end.
A general purpose data compression library with very fast compression and decompression. It is available in ANSI C sources under GPL and some commercial license.
Created: 23/12/2006
by Maxim SmirnovMore...
This J2ME (Java 2 Microedition) application allows mobile phones to send/receive compressed messages in a deflate format, optimized for short strings. It can achieve the ratio 1/2, i.e. two original messages are compressed in only one message. A recipient must have the similar application.
It costs $10.
Created: 28/01/2006
by Antonio SantagiulianaMore...
LZPX is a fast file compressor/preprocessor. The main features of this program are: ultra fast compression and decompression speed, low memory usage and small size.
Created: 09/09/2005
by encodeMore...
This page describes Flexible Parsing, a proposed extension for dictionary based LZ compression schemes. Yossi Matias, Nasir Rajpoot, and Cenk Sahinalp have a summary of their work on this page, along with links to three PS format papers that go into detail on the results. The authors summarize this improved technique as "looking one step ahead for the longest phrase in the dictionary instead of trying to find the longest possible phrase at hand."
Created: 14/12/1999
by Mark NelsonMore...
This archive contains source files lzss.c, lzhuf.c, and lzari.c. They have virtually no documentation, but do a good job of compression. These files were quite influential in their day, particularly in Japan.
Created: 07/11/1999
by Mark NelsonMore...
This paper describes a few searching algorithms to be used on compressed files. An AC type algorithm for searching in Huffman encoded files, a KMP type algorithm for LZ derivatives and a BM type algorithm for searching in files compressed by Byte-Pair-Encoding (BPE). BPE gave results upto 3 times faster than those achieved by agrep.
Created: 12/06/2005
by Sachin GargMore...
The African Chief has a variety of compression programs listed here, including units for Delphi and Turbo Pascal. Techniques supported include LZSS and Zip. Most appear to include source.
Created: 02/11/1999
by Mark NelsonMore...
In this comp.compression posting, Ben Rudia-Gould opens up the compression format used by the PKWare Data Compression Library. This is the only place I have ever seen this information disclosed; PKWare has certainly not done so.
Created: 22/09/2001
by Mark NelsonMore...
Arturo Campos has been doing quite a bit of research on the LZP algorithm (first described by Charles Bloom.) This paper presents all of his results to date.
Created: 17/11/1999
by Mark NelsonMore...
Another article about LZP by Arturo Campos. This piece describes a specific implementation technique using linked lists.
Created: 17/11/1999
by Mark NelsonMore...
Arturo Campos presents the LZP algorithm, first described by Charles Bloom. LZP is a hybrid of dictionary based coding and statistical modeling. This means it has some of the elements of popular LZSS encoders, but takes advantage of PPM style modeling as well. The combination of the two leads to very good compression ratios.
Created: 17/11/1999
by Mark NelsonMore...
Arturo Campos explains some of the basics about LZ77 compression and its popular descendant, LZSS. This is one of Arturo's longer articles, and it includes a hefty does of 80x86 code for illustration purposes.
Created: 17/11/1999
by Mark NelsonMore...
Version 1.1 of the lossless data compression toolkit by Nico deVries. The C sources in this toolkit include an LZW compressor, AR002 archiver, a PPM like compressor using arithmetic compression, Huffman compressor, splay tree program, and LZRW1. Quite a variety.
Created: 14/11/1999
by Mark NelsonMore...
Arturo Campos explains how your implentation of an LZ77 compressor might benefit from an improved parsing algorithm. Instead of always using the longest match found at at the current position, Flexible Parsing attempts to find the optimal match which will lead to the best overall compresion.
Created: 17/11/1999
by Mark NelsonMore...
This article describes a relatively painless way to construct suffix trees. Once you have a suffix tree constructed, it is extremely easy to search for the longest match of a given string. This makes the suffix tree a nice data structure to use in macro replacement forms of data compression.
Created: 01/12/1999
by Mark NelsonMore...
D. T. Hoang, P. M. Long and J. S. Vitter. ``Dictionary Selection using Partial Matching,'' Information Sciences, 119(1-2), 57-72, 1999. This paper describes an attempt to squeeze improved compression out of existing dictionary-based schemes by using multiple context-based dictionaries for encoding.
Created: 08/04/2002
by Mark NelsonMore...
This page has links to the source code for a family of compressors written by Charles Bloom. This includes the LZP family, an LZW example, LZRW, and LZCB.
Created: 14/11/1999
by Mark NelsonMore...
The 1977 paper describing an algorithm for compression using pointers to previously seen text. This algorithm, later known as LZ77, is still one of the most widely used techniques for lossless data compression in use today.
Update 2004: Document is now packed in RAR format.
Created: 16/05/2004
by Mark NelsonMore...
The Basic Compression Library is a set of open source implementations of several well known lossless compression algorithms, including RLE, Huffman, LZ77 and Rice, written in portable ANSI C. The library has been created to be flexible and easy to understand. It is well documented, and easy to use and adapt to specific situations, such as custom compression methods and embedded systems.
Satisfied user Todd W said: I needed a simple set of compression routines for use in an embedded system. I must be able to store a fair amount of information in a small EEPROM as a generic database. The Huffman coder works very well in the application and has met my needs exactly! Very nice!
Created: 14/05/2004
by Mark NelsonMore...
Igor Pavlov has released his LZMA code in a separate SDK, and is claiming excellent performance characteristics that make this a potential hit in the embedded world.
Created: 22/02/2004
by Mark NelsonMore...
rzip is a compression program, similar in functionality to gzip or bzip2, but able to take advantage long distance redundencies in files, which can sometimes allow rzip to produce much better compression ratios than other programs. The original idea behind rzip is described in my PhD thesis (see http://samba.org/~tridge/), but the implementation in this version is considerably improved from the original implementation. The new version is much faster and also produces a better compression ratio.
Created: 14/02/2004
by Mark NelsonMore...
Michael Dipperstein describes his personal quest for understanding and implementation of LZSS coding. Full source included.
Created: 03/12/2003
by Mark NelsonMore...
An Open Source library that implements an LZSS algorithm, designed for speed. ANSI C, with 16- and 32-bit x86 assembler versions available as well.
Created: 13/09/2003
by Mark NelsonMore...
Compreso implements compressed sockets using an LZH algorithm, as implemented by Rolando Herrero. It does this cooperatively with the Win32 socket library, so you can only run this code under Windows. Freeware.
Created: 09/06/2003
by Mark NelsonMore...
The guys at iMatix had the idea that they could write a super-library of C functions that woud be so useful it would rule the world. As far as I can tell, it didn't catch on. However, there are a few compression functions here that some folks might find interesting.
Created: 04/05/2003
by Mark NelsonMore...
Mark Adler built a decompressor that is able to read streams built with PKWare's Data Compression Library. Since PKWare hasn't released source for DCL, this is a very good thing, and free to boot.
Created: 27/02/2003
by Mark NelsonMore...
Will McKee has released this as freeware - includes complete source to a string substitution compressor. From the description it sounds as though it's variant on LZSS, but I'll defer to anyone willing to do a real analysis.
Created: 09/12/2002
by Mark NelsonMore...
This is the data compression standard that implements the LZJH algorithm, and is used in V.90 and V.92 modems. The ITU wants to charge you a few bucks for this standard, but if you believe the post from Pete Fraser (listed elsewhere on DataCompression.info) you can get three free standards per year. Maybe this ought to be one of them.
Created: 09/11/2002
by Mark NelsonMore...
A C++ implementation of the LZSS / LZ77 algorithm. Also contains a description of the LZSS algorithm and my implementations of it as I learned more about it (hashing, lazy evaluation, etc.) All the code from my first attempt to the current version is included.
An anonymous visitor to Jonathan's page said it was "Pertinent, very useful, relevant, just what I needed."
Created: 30/10/2002
by Mark NelsonMore...
A couple of high school kids from Saratoga, CA, were regional winners in the Siemens Westinghouse Science and Technology competition.
Created: 12/10/2002
by Mark NelsonMore...
File and database compression components for Delphi. Compress to/from file, memory, and blob. Uses RLE, LZH, and LZW. Shareware.
Version 7.0 was released in September of 2002.
Created: 15/09/2002
by Mark NelsonMore...
The UPL Compression Library is a high-performance professional compression library. It offers the ability to compress and decompress data, buffers, strings or single files and features the latest innovations in data compression. The library offers eight extremely powerful compression algorithms. Dynamic Huffman, Arithmetic, BWT, Ppm and several Lempel Ziv flavors.
DataCompression.info user John G. had this to say: I was looking for adding a better compression to my Visual Basic project and it worked like a charm. The compression ratio is really good, better than Zip!
Created: 27/08/2002
by Mark NelsonMore...
by Kunihiko Sadakane, Hiroshi Imai. This paper proposes two new methods of performing fast string matching in LZ77 compression. One method uses a new hashing algorithm, the other uses suffix sorting.
Created: 16/07/2002
by Mark NelsonMore...
C++ code posted to comp.compression that describes extraction from PKWare's Data Compression Library.
Update: The author posted this correction to comp.compression:
There's a bug in the code posted 2001-10-07 19:36:38 PST. To fix:
In the
void tcDecoder::Decode(char *apBuffer, unsigned int *apSize, unsigned int anBufferSize)
function after both
if (lnIndex == mnCurrentPos) lnIndex = lnStartIndex;
add
if (lnIndex == mnDictionarySize) lnIndex = 0;
Created: 22/04/2002
by Mark NelsonMore...
This unit implements a component which allows the user to compress data using a combination of LZSS compression and adaptive Huffman coding (Similar to that use by LHARC 1.x), or conversely to decompress data that was previously compressed by this unit.
Created: 26/02/2002
by Mark NelsonMore...
For Delphi and other Windows compilers. Compression/ Decompression routines .DLL library. Mostly assembler, Fast decompression!
Created: 26/02/2002
by Mark NelsonMore...
LZSSLib is a compression library (DLL) for Windows programmers. You have access to compression/decompression functions permitting file-to-file operations. LZSSLib uses the LZSS algorithm with various modifications each providing different enhancements. Very simple to use: LZSSPackFile('PROG.EXE', 'PROG.LZS') Works with any language that supports DLL calling, such as Turbo Pascal, C/C++, Actor, Visual Basic, Realizer, even ObjectVision.
Created: 26/02/2002
by Mark NelsonMore...
The Data Compression Center gives an explanation of LZSS coding.
This link points to an archived site, as the original has disappeared. Links on the archived page may or may not work properly.
Created: 02/12/2000
by Mark NelsonMore...
Home of JCALG1, an LZSS derived lossless compression algorithm with full x86 32bit assembly source. Data Compressioni Library user comment: I found LZSS C source and an EXE. The EXE was useful for testing. I expect to use this in an embedded app after further research..
Created: 16/05/2000
by Mark NelsonMore...
An Optimizing Hybrid LZ77 RLE Data Compression Program, aka Improving Compression Ratio for Low-Resource Decompression by Pasi Ojala.
Presents a new literal tagging system, a fast exhaustive string
match algorithm, an optimal parsing algorithm, and results on
Calgary Corpus and Canterbury Corpus.
Created: 13/12/1999
by Mark NelsonMore...
A discussion of LZSS in Croatian.
This link points to an archived site, as the original has disappeared. Links on the archived page may or may not work properly.
Created: 19/11/1999
by Mark NelsonMore...
Ross Williams did some seminal work in the area of dictionary based encoders in the late 1980s and early 1990s. His LZRW algorithms were not only innovative and interesting, but they managed to place Ross right in the middle of some early software patent issues.
Created: 21/09/1999
by Mark NelsonMore...
