Editing LZ77 and LZ78 (section)

==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>https://math.mit.edu/~goemans/18310S15/lempel-ziv-notes.pdf {{Bare URL PDF|date=March 2022}}</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.