LZ78 Compression Algorithm Implementation

Question

## Problem

Implement the LZ78 lossless compression algorithm. You are given an input string and must produce a list of (index, character) pairs representing the compressed output.

LZ78 builds a dictionary incrementally: start with an empty dictionary. At each step, find the longest prefix of the remaining input that exists in the dictionary, emit `(dict_index, next_char)`, then add the new phrase to the dictionary.

```python
def lz78_compress(s: str) -> list[tuple[int, str]]:
    # return list of (dictionary_index, character) pairs
    pass

def lz78_decompress(pairs: list[tuple[int, str]]) -> str:
    pass
```

```
Input:  "abacabac"
Output: [(0,'a'), (0,'b'), (1,'c'), (1,'b'), (3,'c')]
# dict after each step: {1:'a', 2:'b', 3:'ac', 4:'ab', 5:'abc'}

Decompress back: "abacabac"
```

## Follow-ups

1. What is the time complexity of your compression routine? How does dictionary lookup affect it?
2. How does LZ78 differ from LZ77? When would you prefer one over the other?
3. How would you handle a very large input that does not fit in memory?
4. Extend decompression to handle a corrupted pair `(idx, c)` where `idx` is out of range — return an error or partial result?

LZ78 Compression Algorithm Implementation

Question Details

Full Details

Topics

More from LinkedIn