LZ78 Algorithm

LZ78 is a lossless data-compression algorithm published by Abraham Lempel and Jacob Ziv in 1978, also known as Lempel-Ziv 2. Unlike its sliding-window predecessor LZ77, LZ78 is theoretically a dictionary coder built from an explicit dictionary that is constructed during encoding and decoding as a new phrase is added whenever a token is output, a design that could in principle allow random access to the input if the entire dictionary were known in advance, though in practice the dictionary is built incrementally rather than in advance. LZ78 forms the basis of later variations including LZW, and LZ77 and LZ78 together were named an IEEE Milestone in 2004.