LZ78 Dictionary Prefix Parsing
A growing dictionary compresses repeated phrases into references, and the final partial phrase needs its own precise rule.
Free theory articleA growing dictionary compresses repeated phrases into references, and the final partial phrase needs its own precise rule.
Concept & interpretation
LZ78 is a dictionary-based lossless data compression algorithm published by Abraham Lempel and Jacob Ziv in 1978. Unlike LZ77, which uses a sliding window over previously seen text, LZ78 explicitly constructs a dictionary of phrases. As the algorithm parses the input stream, it continually adds new, longer phrases to this dictionary.
experiment
In this interactive LZ78 Dictionary Prefix Parsing module, you can trace the dictionary building process step by step.
- Select
0010011from the "Input word" dropdown. - Set "Inspected tokens" to
2. Observe the token stream updates to0:0 | 1:1and the decoded prefix matches001. - Increase the "Inspected tokens" to
4and watch the remaining tokens generated and dictionary expanding accordingly.