View source for LZ77 and LZ78

{{Short description|Lossless data compression algorithms}}
{{Use dmy dates|date=August 2021}}
'''LZ77''' and '''LZ78''' are the two [[lossless data compression]] [[algorithm]]s published in papers by [[Abraham Lempel]] and [[Jacob Ziv]] in 1977<ref>{{cite journal
 | first1 = Jacob
 | last1 = Ziv
 | author-link1 = Jacob Ziv
 | first2 = Abraham
 | last2 = Lempel
 | author-link2 = Abraham Lempel
 | title = A Universal Algorithm for Sequential Data Compression
 | journal = [[IEEE Transactions on Information Theory]]
 | volume = 23
 | issue = 3
 | pages = 337–343
 | date = May 1977
 | doi = 10.1109/TIT.1977.1055714
 | citeseerx = 10.1.1.118.8921
| s2cid = 9267632
 }}</ref> and 1978.<ref>{{cite journal
 | first1 = Jacob
 | last1 = Ziv
 | author-link1 = Jacob Ziv
 | first2 = Abraham
 | last2 = Lempel
 | author-link2 = Abraham Lempel
 | title = Compression of Individual Sequences via Variable-Rate Coding
 | journal = [[IEEE Transactions on Information Theory]]
 | volume = 24
 | issue = 5
 | pages = 530–536
 | date = September 1978
 | doi = 10.1109/TIT.1978.1055934 | citeseerx = 10.1.1.14.2892
}}</ref>
They are also known as '''Lempel-Ziv 1''' (LZ1) and '''Lempel-Ziv 2''' (LZ2) respectively.<ref>{{USPTO Patent|patnum=5532693|title=Adaptive data compression system with systolic string matching logic}}</ref> These two algorithms form the basis for many variations including [[Lempel–Ziv–Welch|LZW]], [[Lempel–Ziv–Storer–Szymanski|LZSS]], [[Lempel–Ziv–Markov chain algorithm|LZMA]] and others. Besides their academic influence, these algorithms formed the basis of several ubiquitous compression schemes, including the one used in [[GIF]] and the [[DEFLATE]] algorithm used in [[Portable Network Graphics|PNG]] and [[Zip (file format)|ZIP]].

They are both theoretically [[dictionary coder]]s. LZ77 maintains a sliding window during compression. This was later shown to be equivalent to the ''explicit dictionary'' constructed by LZ78—however, they are only equivalent when the entire data is intended to be decompressed.

Since LZ77 encodes and decodes from a sliding window over previously seen characters, decompression must always start at the beginning of the input.  Conceptually, LZ78 decompression could allow random access to the input if the entire dictionary were known in advance.  However, in practice the dictionary is created during encoding and decoding by creating a new phrase whenever a token is output.<ref>{{Cite web|url=https://cs.stanford.edu/people/eroberts/courses/soco/projects/data-compression/lossless/lz78/concept.htm|title=Lossless Data Compression: LZ78|website=cs.stanford.edu}}</ref>

The algorithms were named an [[List of IEEE milestones|IEEE Milestone]] in 2004.<ref>{{cite web
| url=https://www.ieeeghn.org/wiki/index.php/Milestones:Lempel-Ziv_Data_Compression_Algorithm,_1977
| title=Milestones:Lempel–Ziv Data Compression Algorithm, 1977
| date=2014-07-22
| work=IEEE Global History Network
| publisher=[[Institute of Electrical and Electronics Engineers]]
| access-date=2014-11-09}}</ref> In 2021 Jacob Ziv was awarded the [[IEEE Medal of Honor]] for his involvement in their development.<ref>{{Cite web|last=Joanna|first=Goodrich|title=IEEE Medal of Honor Goes to Data Compression Pioneer Jacob Ziv|url=https://spectrum.ieee.org/ieee-medal-of-honor-goes-to-data-compression-pioneer-jacob-ziv|access-date=2021-01-18|website=IEEE Spectrum: Technology, Engineering, and Science News|language=en}}</ref>

==Theoretical efficiency==
In the second of the two papers that introduced these algorithms they are analyzed as encoders defined by finite-state machines. A measure analogous to [[information entropy]] is developed for individual sequences (as opposed to probabilistic ensembles). This measure gives a bound on the [[data compression ratio]] that can be achieved. It is then shown that there exists finite lossless encoders for every sequence that achieve this bound as the length of the sequence grows to infinity. In this sense an algorithm based on this scheme produces asymptotically optimal encodings. This result can be proven more directly, as for example in notes by [[Peter Shor]].<ref>{{cite web
| url=https://math.mit.edu/~shor/PAM/lempel_ziv_notes.pdf
| title=Lempel–Ziv notes
| author=Peter Shor
| author-link=Peter Shor
| date=2005-10-14
| access-date=2014-11-09
| archive-date=28 May 2021
| archive-url=https://web.archive.org/web/20210528171521/http://www-math.mit.edu/~shor/PAM/lempel_ziv_notes.pdf
}}</ref>

Formally, (Theorem 13.5.2 <ref>{{Cite book |last=Cover |first=Thomas M. |title=Elements of information theory |last2=Thomas |first2=Joy A. |date=2006 |publisher=Wiley-Interscience |isbn=978-0-471-24195-9 |edition=2nd |location=Hoboken, N.J}}</ref>).

{{Math theorem|name=LZ78 is universal and entropic|note=|math_statement=

If <math display="inline">X</math> is a binary source that is stationary and ergodic, then <math display="block">\limsup_n \frac 1n l_{LZ78}(X_{1:n}) \leq h(X)</math> with probability 1. Here <math display="inline">h(X)</math> is the entropy rate of the source.
}}Similar theorems apply to other versions of LZ algorithm.

==LZ77==
LZ77 algorithms achieve compression by replacing repeated occurrences of data with references to a single copy of that data existing earlier in the uncompressed data stream. A match is encoded by a pair of numbers called a ''length-distance pair'', which is equivalent to the statement "each of the next ''length'' characters is equal to the characters exactly ''distance'' characters behind it in the uncompressed stream". (The ''distance'' is sometimes called the ''offset'' instead.)

To spot matches, the encoder must keep track of some amount of the most recent data, such as the last 2&nbsp;[[kilobyte|KB]], 4&nbsp;KB, or 32&nbsp;KB. The structure in which this data is held is called a ''sliding window'', which is why LZ77 is sometimes called ''sliding-window compression''. The encoder needs to keep this data to look for matches, and the decoder needs to keep this data to interpret the matches the encoder refers to. The larger the sliding window is, the longer back the encoder may search for creating references.

It is not only acceptable but frequently useful to allow length-distance pairs to specify a length that actually exceeds the distance. As a copy command, this is puzzling: "Go back ''four'' characters and copy ''ten'' characters from that position into the current position". How can ten characters be copied over when only four of them are actually in the buffer? Tackling one byte at a time, there is no problem serving this request, because as a byte is copied over, it may be fed again as input to the copy command. When the copy-from position makes it to the initial destination position, it is consequently fed data that was pasted from the ''beginning'' of the copy-from position. The operation is thus equivalent to the statement "copy the data you were given and repetitively paste it until it fits". 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]].

Another way to see things is as follows: While encoding, for the search pointer to continue finding matched pairs past the end of the search window, all characters from the first match at offset ''D'' and forward to the end of the search window must have matched input, and these are the (previously seen) characters that compose a single run unit of length ''L''<sub>R</sub>, which must equal ''D''.  Then as the search pointer proceeds past the search window and forward, as far as the run pattern repeats in the input, the search and input pointers will be in sync and match characters until the run pattern is interrupted.  Then ''L'' characters have been matched in total, ''L'' > ''D'', and the code is [''D'', ''L'', ''c''].

Upon decoding [''D'', ''L'', ''c''], again, ''D'' = ''L''<sub>R</sub>.  When the first ''L''<sub>R</sub> characters are read to the output, this corresponds to a single run unit appended to the output buffer.  At this point, the read pointer could be thought of as only needing to return int(''L''/''L''<sub>R</sub>) + (1 if ''L'' mod ''L''<sub>R</sub> ≠ 0) times to the start of that single buffered run unit, read ''L''<sub>R</sub> characters (or maybe fewer on the last return), and repeat until a total of ''L'' characters are read. But mirroring the encoding process, since the pattern is repetitive, the read pointer need only trail in sync with the write pointer by a fixed distance equal to the run length ''L''<sub>R</sub> until ''L'' characters have been copied to output in total.

Considering the above, especially if the compression of data runs is expected to predominate, the window search should begin at the end of the window and proceed backwards, since run patterns, if they exist, will be found first and allow the search to terminate, absolutely if the current maximal matching sequence length is met, or judiciously, if a sufficient length is met, and finally for the simple possibility that the data is more recent and may correlate better with the next input.

===Pseudocode===
The following [[pseudocode]] is a reproduction of the LZ77 compression algorithm sliding window.

 '''while''' input is not empty '''do'''
     match := longest repeated occurrence of input that begins in window
     
     '''if''' match exists '''then'''
         d := distance to start of match
         l := length of match
         c := char following match in input
     '''else'''
         d := 0
         l := 0
         c := first char of input
     '''end if'''
     
     '''output''' (d, l, c)
     
     discard ''l'' + 1 chars from front of window
     s := pop ''l'' + 1 chars from front of input
     append s to back of window
 '''repeat'''

===Implementations===
Even though all LZ77 algorithms work by definition on the same basic principle, they can vary widely in how they encode their compressed data to vary the numerical ranges of a length–distance pair, alter the number of bits consumed for a length–distance pair, and distinguish their length–distance pairs from ''literals'' (raw data encoded as itself, rather than as part of a length–distance pair). A few examples:
* The algorithm illustrated in Lempel and Ziv's original 1977 article outputs all its data three values at a time: the length and distance of the longest match found in the buffer, and the literal that followed that match. If two successive characters in the input stream could be encoded only as literals, the length of the length–distance pair would be 0.
* [[Lempel–Ziv–Storer–Szymanski|LZSS]] improves on LZ77 by using a 1-bit flag to indicate whether the next chunk of data is a literal or a length–distance pair, and using literals if a length–distance pair would be longer.
* In the PalmDoc format, a length–distance pair is always encoded by a two-byte sequence. Of the 16 bits that make up these two bytes, 11 bits go to encoding the distance, 3 go to encoding the length, and the remaining two are used to make sure the decoder can identify the first byte as the beginning of such a two-byte sequence.
* In the implementation used for many games by [[Electronic Arts]],<ref>{{cite web
| url=http://wiki.niotso.org/QFS_compression
| title=QFS Compression (RefPack)
| work=Niotso Wiki
| access-date=2014-11-09}}</ref> the size in bytes of a length–distance pair can be specified inside the first byte of the length–distance pair itself; depending on whether the first byte begins with a 0, 10, 110, or 111 (when read in [[Endianness|big-endian]] bit orientation), the length of the entire length–distance pair can be 1 to 4 bytes.
* {{As of|2008}}, the most popular LZ77-based compression method is [[DEFLATE]]; it combines LZSS with [[Huffman coding]].<ref>{{cite web
| url=https://www.zlib.net/feldspar.html
| title=An Explanation of the Deflate Algorithm
| first=Antaeus
| last=Feldspar
| date=23 August 1997
| work=comp.compression [[Usenet newsgroup|newsgroup]]
| publisher=zlib.net
| access-date=2014-11-09}}</ref> Literals, lengths, and a symbol to indicate the end of the current block of data are all placed together into one alphabet. Distances can be safely placed into a separate alphabet; because a distance only occurs just after a length, it cannot be mistaken for another kind of symbol or vice versa.

==LZ78==
The LZ78 algorithms compress sequential data by building a dictionary of token sequences from the input, and then replacing the second and subsequent occurrence of the sequence in the data stream with a reference to the dictionary entry.  The observation is that the number of repeated sequences is a good measure of the non random nature of a sequence.  The algorithms represent the dictionary as an n-ary tree where n is the number of tokens used to form token sequences.  Each dictionary entry is of the form {{code|1=dictionary[...] = {index, token} }}, where index is the index to a dictionary entry representing a previously seen sequence, and token is the next token from the input that makes this entry unique in the dictionary.  Note how the algorithm is greedy, and so nothing is added to the table until a unique making token is found.  The algorithm is to initialize last matching index = 0 and next available index = 1 and then, for each token of the input stream, the dictionary searched for a match: {{code|{{mset|last matching index, token}}}}. If a match is found, then last matching index is set to the index of the matching entry, nothing is output, and last matching index is left representing the input so far. Input is processed until a match is ''not'' found. Then a new dictionary entry is created, {{code|1=dictionary[next available index] = {last matching index, token} }}, and the algorithm outputs last matching index, followed by token, then resets last matching index = 0 and increments next available index.  As an example consider the sequence of tokens {{samp|AABBA}} which would assemble the dictionary;
{{pre|
0 {0,_}
1 {0,A}
2 {1,B}
3 {0,B}
}}
and the output sequence of the compressed data would be {{samp|0A1B0B}}.  Note that the last A is not represented yet as the algorithm cannot know what comes next. In practice an EOF marker is added to the input – {{samp|AABBA$}} for example.  Note also that in this case the output {{samp|0A1B0B1$}} is longer than the original input but compression ratio improves considerably as the dictionary grows, and in binary the indexes need not be represented by any more than the minimum number of bits.<ref>{{cite web |last1=Goemans |first1=Michel |title=Lempel-Ziv codes |url=https://math.mit.edu/~goemans/18310S15/lempel-ziv-notes.pdf |website=MIT Mathematics |date=27 April 2015}}</ref>

Decompression consists of rebuilding the dictionary from the compressed sequence.  From the sequence {{samp|0A1B0B1$}} the first entry is always the terminator {{samp|0 {...} }}, and the first from the sequence would be {{samp|1 {0,A} }}. The {{samp|A}} is added to the output. The second pair from the input is {{samp|1B}} and results in entry number 2 in the dictionary, {{samp|{{mset|1,B}}}}. The token "B" is output, preceded by the sequence represented by dictionary entry 1. Entry 1 is an 'A' (followed by "entry 0" – nothing) so {{samp|AB}} is added to the output.  Next {{samp|0B}} is added to the dictionary as the next entry, {{samp|3 {0,B} }}, and B (preceded by nothing) is added to the output. Finally a dictionary entry for {{samp|1$}} is created and {{samp|A$}} is output resulting in {{samp|A AB B A$}} or {{samp|AABBA}} removing the spaces and EOF marker.

==LZW==
[[Lempel–Ziv–Welch|LZW]] is an LZ78-based algorithm that uses a dictionary pre-initialized with all possible characters (symbols) or emulation of a pre-initialized dictionary. The main improvement of [[Lempel–Ziv–Welch|LZW]] is that when a match is not found, the current input stream character is assumed to be the first character of an existing string in the dictionary (since the dictionary is initialized with all possible characters), so only the ''last matching index'' is output (which may be the pre-initialized dictionary index corresponding to the previous (or the initial) input character). Refer to the [[Lempel–Ziv–Welch|LZW]] article for implementation details.

[[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]]. 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. A counter cycles through the dictionary.  When a new entry is needed, the counter steps through the dictionary until a leaf node is found (a node with no dependents).  This is deleted and the space re-used for the new entry. This is simpler to implement than LRU or LFU and achieves equivalent performance.

==See also==
* [[Lempel–Ziv–Stac]] (LZS)

==References==
{{Reflist}}

==External links==
*{{commons category-inline|LZ77 algorithm}}
*{{commons category-inline|LZ78 algorithm}}
* {{cite web
| url=http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/lz/lz77.html
| title=The LZ77 algorithm
| date=1997
| work=Data Compression Reference Center: RASIP working group
| publisher=[[Faculty of Electrical Engineering and Computing, University of Zagreb]]
| access-date=22 June 2012
| archive-url=https://archive.today/20130107232302/http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/lz/lz77.html
| archive-date=7 January 2013
}}

* {{cite web
| url=http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/lz/lz78.html
| title=The LZ78 algorithm
| date=1997
| work=Data Compression Reference Center: RASIP working group
| publisher=Faculty of Electrical Engineering and Computing, University of Zagreb
| access-date=22 June 2012
| archive-url=https://archive.today/20130107200800/http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/lz/lz78.html
| archive-date=7 January 2013
}}

* {{cite web
| url=http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/lz/lzw.html
| title=The LZW algorithm
| date=1997
| work=Data Compression Reference Center: RASIP working group
| publisher=Faculty of Electrical Engineering and Computing, University of Zagreb
| access-date=22 June 2012
| archive-url=https://archive.today/20130107170646/http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/lz/lzw.html
| archive-date=7 January 2013
}}

{{Compression Methods}}

{{DEFAULTSORT:Lz77 And Lz78}}
[[Category:Lossless compression algorithms]]
[[Category:Israeli inventions]]
[[Category:Data compression]]