What is LZ77 and LZ78?
{{complex|date=April 2021}} '''LZ77''' and '''LZ78''' are two [[lossless data compression]] [[Algorithm|algorithms]]. [[Abraham Lempel]] and [[Jacob Ziv]] published them in papers, in 1977<ref>{{cite journal|last1=Ziv|first1=Jacob|author-link1=Jacob Ziv|last2=Lempel|first2=Abraham|author-link2=Abraham Lempel|date=May 1977|title=A Universal Algorithm for Sequential Data Compression|journal=[[IEEE Transactions on Information Theory]]|volume=23|issue=3|pages=337–343|citeseerx=10.1.1.118.8921|doi=10.1109/TIT.1977.1055714|s2cid=9267632 }}</ref> and 1978.<ref>{{cite journal|last1=Ziv|first1=Jacob|author-link1=Jacob Ziv|last2=Lempel|first2=Abraham|author-link2=Abraham Lempel|date=September 1978|title=Compression of Individual Sequences via Variable-Rate Coding|journal=[[IEEE Transactions on Information Theory]]|volume=24|issue=5|pages=530–536|citeseerx=10.1.1.14.2892|doi=10.1109/TIT.1978.1055934}}</ref> They are also known as '''LZ1''' and '''LZ2'''. Today, there are many variations of these algorithms. Examples of such variations are [[Lempel–Ziv–Welch|LZW]], [[Lempel-Ziv-Storer-Szymanski|LZSS]], or [[Lempel-Ziv-Markov chain algorithm|LZMA]]. Lempel-Ziv-Welch (LZW) is a variant that was published in 1983, and that was used for the [[Graphics Interchange Format|GIF]] format used by [[Compuserve]], or the the [[DEFLATE]] algorithm used in [[Portable Network Graphics|PNG]] and [[ZIP (file format)|ZIP]]. They are both theoretically [[Dictionary coder|dictionary coders]]. LZ77 uses a [[sliding window]] during compression. Later, this was shown to be equivalent to the explicit dictionary constructed by LZ78. There are limitations though: The two methods are only equivalent when all of the data is 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