LZ78 Dictionary Prefix Parsing

worked-example

Consider compressing the binary string 0010011 using LZ78. The dictionary starts with a single entry at index 0 representing the empty string. At each step, the algorithm finds the longest prefix in the dictionary that matches the current input, outputs its dictionary index and the following symbol, and then adds this new combination to the dictionary.

Input: 0010011
Dictionary: { 0: "" }

Step 1:
- Current input starts at pos 0: "0".
- Longest dict match: "" (index 0). Next char: "0".
- Output token: (0, "0").
- Add to dict: "0" at index 1.
- Dictionary: { 0: "", 1: "0" }

Step 2:
- Current input starts at pos 1: "01".
- Longest dict match: "0" (index 1). Next char: "1".
- Output token: (1, "1").
- Add to dict: "01" at index 2.
- Dictionary: { 0: "", 1: "0", 2: "01" }

Step 3:
- Current input starts at pos 3: "00".
- Longest dict match: "0" (index 1). Next char: "0".
- Output token: (1, "0").
- Add to dict: "00" at index 3.
- Dictionary: { 0: "", 1: "0", 2: "01", 3: "00" }

Step 4:
- Current input starts at pos 5: "11".
- Longest dict match: "" (index 0). Next char: "1".
- Output token: (0, "1").
- Add to dict: "1" at index 4.
- Dictionary: { 0: "", 1: "0", 2: "01", 3: "00", 4: "1" }

Step 5 (EOF):
- Current input starts at pos 6: "1", and there are no more characters.
- Longest dict match is "1" (index 4).
- The stream ends in an already known phrase, so emit (4, EOF).
- Do not add a new dictionary entry.

Resulting token stream: 0:0 | 1:1 | 1:0 | 0:1 | 4:EOF

experiment

In this interactive LZ78 Dictionary Prefix Parsing module, you can trace the dictionary building process step by step.

1. Select 0010011 from the "Input word" dropdown.
2. Set "Inspected tokens" to 2. Observe the token stream updates to 0:0 | 1:1 and the decoded prefix matches 001.
3. Increase the "Inspected tokens" to 4 and watch the remaining tokens generated and dictionary expanding accordingly.

limitations

The theoretical LZ78 algorithm presented here assumes an unbounded dictionary, which is impractical for compressing large files, as memory would grow infinitely and dictionary indices would require an increasing number of bits. In practice, algorithms like LZW (a derivative of LZ78) and practical implementations limit the dictionary size, often clearing it or freezing it when it becomes full. Additionally, without defining a specific bit-encoding scheme for the tokens (e.g., using a variable-length code for the dictionary index), calculating an exact compression ratio is impossible, as the literal string pairs and integer lengths vary.

references

The following reference provides the original foundational paper on the Lempel-Ziv dictionary prefix parsing method.

• Ziv, J., & Lempel, A. (1978). Compression of Individual Sequences via Variable-Rate Coding. IEEE Transactions on Information Theory, 24(5), 530-536.