LZ77 and LZ78

LZ77Lempel-ZivLempel–ZivLZ78Lempel ZivLempel-Ziv compressionLempel–Ziv codingLZLZ algorithmLZ family
LZ77 and LZ78 are the two lossless data compression algorithms published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978.wikipedia
94 Related Articles

Abraham Lempel

Lempel
LZ77 and LZ78 are the two lossless data compression algorithms published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978.
Abraham Lempel (אברהם למפל, born 10 February 1936) is an Israeli computer scientist and one of the fathers of the LZ family of lossless data compression algorithms.

Lossless compression

losslesslossless data compressioncompression
LZ77 and LZ78 are the two lossless data compression algorithms published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978.
Because of patents on certain kinds of LZW compression, and in particular licensing practices by patent holder Unisys that many developers considered abusive, some open source proponents encouraged people to avoid using the Graphics Interchange Format (GIF) for compressing still image files in favor of Portable Network Graphics (PNG), which combines the LZ77-based deflate algorithm with a selection of domain-specific prediction filters.

Yaakov Ziv

Jacob ZivZiv
LZ77 and LZ78 are the two lossless data compression algorithms published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978.
Yaakov Ziv (יעקב זיו; born 1931) is an Israeli electrical engineer who, along with Abraham Lempel, developed the LZ family of lossless data compression algorithms.

Lempel–Ziv–Welch

LZWLempel-Ziv-WelchLempel-Ziv-Welch algorithm
These two algorithms form the basis for many variations including LZW, LZSS, LZMA and others.
It was published by Welch in 1984 as an improved implementation of the LZ78 algorithm published by Lempel and Ziv in 1978.

Lempel–Ziv–Markov chain algorithm

LZMALZMA2Lempel-Ziv-Markov chain algorithm
These two algorithms form the basis for many variations including LZW, LZSS, LZMA and others.
This algorithm uses a dictionary compression scheme somewhat similar to the LZ77 algorithm published by Abraham Lempel and Jacob Ziv in 1977 and features a high compression ratio (generally higher than bzip2) and a variable compression-dictionary size (up to 4 GB), while still maintaining decompression speed similar to other commonly used compression algorithms.

Portable Network Graphics

PNG.pngPNG image
Besides their academic influence, these algorithms formed the basis of several ubiquitous compression schemes, including GIF and the DEFLATE algorithm used in PNG and ZIP.
PNG uses DEFLATE, a non-patented lossless data compression algorithm involving a combination of LZ77 and Huffman coding.

GIF

animated GIF.gifGraphics Interchange Format
Besides their academic influence, these algorithms formed the basis of several ubiquitous compression schemes, including GIF and the DEFLATE algorithm used in PNG and ZIP.
In 1977 and 1978, Jacob Ziv and Abraham Lempel published a pair of papers on a new class of lossless data-compression algorithms, now collectively referred to as LZ77 and LZ78.

Lempel–Ziv–Storer–Szymanski

LZSS
These two algorithms form the basis for many variations including LZW, LZSS, LZMA and others.
Lempel–Ziv–Storer–Szymanski (LZSS) is a lossless data compression algorithm, a derivative of LZ77, that was created in 1982 by James Storer and Thomas Szymanski.

Run-length encoding

RLErun length encodingrun-length encoded
As this type of pair repeats a single copy of data multiple times, it can be used to incorporate a flexible and easy form of run-length encoding.
However, newer compression methods such as DEFLATE often use LZ77-based algorithms, a generalization of run-length encoding that can take advantage of runs of strings of characters (such as ).

Dictionary coder

dictionary codingdictionarydictionary compression
They are both theoretically dictionary coders.
Both the LZ77 and LZ78 algorithms work on this principle.

List of IEEE milestones

IEEE MilestoneIEEE MilestonesIEEE Milestone in Electrical Engineering
The algorithms were named an IEEE Milestone in 2004.

Lempel–Ziv–Stac

LZSStacker
Lempel–Ziv–Stac (LZS, or Stac compression) is a lossless data compression algorithm that uses a combination of the LZ77 sliding-window compression algorithm and fixed Huffman coding.

List of ITU-T V-series recommendations

V.90V.32bisV.34
BTLZ is an LZ78-based algorithm that was developed for use in real-time communications systems (originally modems) and standardized by CCITT/ITU as V.42bis.

Algorithm

algorithmsalgorithm designcomputer algorithm
LZ77 and LZ78 are the two lossless data compression algorithms published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978.

DEFLATE

deflateddeflate-decodeDeflate64
Besides their academic influence, these algorithms formed the basis of several ubiquitous compression schemes, including GIF and the DEFLATE algorithm used in PNG and ZIP.

Zip (file format)

ZIPZIP file.zip
Besides their academic influence, these algorithms formed the basis of several ubiquitous compression schemes, including GIF and the DEFLATE algorithm used in PNG and ZIP.

Sliding window protocol

sliding windowwindowsliding-window protocol
LZ77 maintains a sliding window during compression.

Entropy (information theory)

entropyinformation entropyShannon entropy
A measure analogous to information entropy is developed for individual sequences (as opposed to probabilistic ensembles).

Data compression ratio

compression ratiocompression ratios320 kbit/s
This measure gives a bound on the data compression ratio that can be achieved.

Peter Shor

Peter W. ShorShorShor, Peter
This result can be proven more directly, as for example in notes by Peter Shor.

Kilobyte

KBkilobytesK
To spot matches, the encoder must keep track of some amount of the most recent data, such as the last 2 kB, 4 kB, or 32 kB.

Trie

Digital treean in-place ''bitwise trie'' algorithmPrefix tree
When the trie-structured dictionary is full, a simple re-use/recovery algorithm is used to ensure that the dictionary can keep adapting to changing data.