Lempel-Ziv Algorithm

A Lempel-Ziv Algorithm is a Lossless Data Compression Algorithm that was developed by Abraham Lempel and Jacob Ziv in 1977 and 1978.

• AKA: LZ77+LZ78.
• Example(s):
  • LZ77 Algorithm,
  • LZ78 Algorithm,
  • Lempel-Ziv Jeff Bonwick (LZJB) Algorithm,
  • Lempel-Ziv-Markov Chain Algorithm (LZMA),
  • Lempel-Ziv-Oberhumer (LZO) Algorithm,
  • Lempel-Ziv-Stac (LZS) Algorithm,
  • Lempel-Ziv-Storer-Szymanski (LZSS) Algorithm,
  • Lempel-Ziv-Welch (LZW) Algorithm,
  • LZWL Algorithm,
  • LZX Algorithm,
  • Lempel-Ziv Ross Williams (LZRW) Algotihm.
  • …
• Counter-Example(s):
  • BPE Algorithm,
  • BPEmb Algorithm,
  • Deflate Algorithm,
  • SentencePiece Algorithm,
  • Sequitur Algorithm,
  • WordPiece Algorithm.
• See: IEEE Medal of Honor, Lossless Data Compression, Algorithm, Abraham Lempel, Jacob Ziv, IEEE Transactions on Information Theory, Lempel–Ziv–Welch, Lempel-Ziv-Storer-Szymanski, Lempel-Ziv-Markov Chain Algorithm, GIF, DEFLATE, Portable Network Graphics.

---

---

References

2021

• (Wikipedia, 2021) ⇒ https://en.wikipedia.org/wiki/LZ77_and_LZ78 Retrieved:2021-5-2.
  • LZ77 and LZ78 are the two lossless data compression algorithms published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978. They are also known as LZ1 and LZ2 respectively. These two algorithms form the basis for many variations including LZW, LZSS, LZMA and others. 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. They are both theoretically dictionary coders. 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. The algorithms were named an IEEE Milestone in 2004. In 2021 Jacob Ziv was awarded the IEEE Medal of Honor for his involvement in their development.

---