Understanding LZ78 Compression Algorithm: Theory and Code

1. Introduction and Core Concepts

The lz78 compression algorithm is a foundational dictionary-based lossless compression technique that revolutionized how we think about data redundancy. Introduced in 1978 by Abraham Lempel and Jacob Ziv as the successor to their landmark LZ77 algorithm, LZ78 takes a fundamentally different approach to building its dictionary. While LZ77 uses a sliding window to reference previously seen data, LZ78 builds an explicit, ever-growing dictionary of phrases encountered in the input. This simple yet powerful idea forms the basis for many modern compression formats, including the ubiquitous LZW variant used in GIF images and early Unix compress utilities.

At its core, the lz78 compression algorithm belongs to the family of adaptive compression methods. This means it does not require prior knowledge of the input data's statistics, unlike static Huffman coding which needs a precomputed frequency table. Instead, LZ78 learns the structure of the data as it processes it, dynamically adding new phrases to its dictionary. Each phrase consists of a previously seen dictionary entry plus one new character. This prefix property ensures that the dictionary can be efficiently reconstructed during decompression without needing to be transmitted explicitly, which is a key reason for its elegance and efficiency.

Understanding LZ78 matters today for several reasons beyond historical interest. First, it provides the clearest illustration of dictionary coding principles, making it an essential pedagogical tool for anyone studying data compression, information theory, or algorithm design. Second, its concepts directly underpin more advanced algorithms like LZW, LZMA, and Deflate that power web servers, databases, and network protocols. Finally, LZ78 demonstrates critical trade-offs in algorithm design: the balance between compression ratio, memory usage, and processing speed. For developers building systems that handle large-scale text, logs, or genomic data, grasping these trade-offs is crucial for selecting the right compression strategy.

Why Dictionary-Based Compression Works

Most real-world data is highly redundant. Natural language repeats words and phrases, source code repeats keywords, and log files contain recurring patterns. Dictionary methods exploit this by replacing repeated substrings with short references (indices) to a dictionary. LZ78 is particularly effective when the input contains many repeated phrases, because once a phrase is added to the dictionary, any future occurrence can be encoded as a single integer pointer rather than as literal characters. Over a long file, this yields substantial savings.

Unlike entropy encoders that work at the level of individual symbols, LZ78 operates at the phrase level. This allows it to capture higher-order redundancy that single-symbol methods miss. The algorithm's adaptive nature also means it performs well on heterogeneous data where statistics change over time, as the dictionary continuously evolves to reflect the most recent patterns in the stream.

2. How It Works

The mechanism of the lz78 compression algorithm can be understood as a two-phase process that interleaves parsing and dictionary construction. The encoder maintains a dictionary that is initially populated with a single entry representing the empty string at index 0. As it scans the input from left to right, it searches for the longest prefix of the remaining input that already exists in the dictionary. Once this longest match is found, the encoder outputs a token consisting of two parts: the index of the matched prefix and the next character that follows it in the input. It then adds the concatenation of that prefix and the new character to the dictionary as a new entry.

For example, if the dictionary currently contains "A" at index 1 and "AB" at index 2, and the remaining input begins with "ABC", the longest match is "AB" (index 2). If the next character is "C", the encoder will output the pair (2, 'C') and add the new phrase "ABC" to the dictionary with the next available index, 3. This process guarantees that every dictionary entry is an extension of a previous entry by exactly one character, which creates a trie-like structure that is both compact and easy to search. The decoder can replicate this process perfectly because it builds the identical dictionary in the same order from the sequence of tokens alone.

Decompression is even simpler and completely deterministic. The decoder starts with the same initial dictionary containing only the empty string. For each incoming token (index, character), it looks up the string associated with the index, appends the character to it, outputs the resulting string, and adds it to its own dictionary. Because the encoder and decoder add entries in the exact same order, their dictionaries remain synchronized without any additional communication. The final token may be a special case where the input ends exactly on a dictionary phrase, often encoded as (index, EOF) or simply (index) without a trailing character.

The Prefix Property and Trie Structure

The defining invariant of LZ78 is the prefix property: every phrase in the dictionary has its prefix (all but the last character) also present in the dictionary. This property is what makes the algorithm so efficient to implement using a trie (prefix tree). Each node in the trie corresponds to a dictionary entry, and each edge is labeled with a character. Traversing the trie according to the input characters allows the encoder to find the longest match in time proportional to the length of the match, rather than searching a flat list. This structure also ensures that no phrase is ever added twice and that the dictionary remains prefix-closed.

Token Format and Bit-Level Considerations

Conceptually, tokens are pairs of (index, character). In practice, the index is encoded using a variable number of bits that grows as the dictionary expands. If the dictionary has N entries, an index requires ceil(log2(N)) bits. The character is typically 8 bits for byte-oriented data. Early theoretical descriptions of LZ78 assumed fixed-width indices, but practical implementations use incremental bit-widths or entropy coding of the indices to improve compression. Understanding this distinction is important when calculating the true compressed size versus the number of tokens.

3. Implementation

Implementing the lz78 compression algorithm in Python provides excellent insight into its dictionary management and parsing logic. The naive approach uses a Python dictionary mapping strings to indices, which is clear and correct for moderate inputs. While not the most memory-efficient for huge files, it perfectly illustrates the algorithm's behavior and is sufficient for educational purposes and for compressing text files up to several megabytes. The key is to carefully manage the longest-match search and the dictionary update step.

The following implementation focuses on clarity and correctness. It processes the input string sequentially, building the dictionary and emitting tokens. Note how the dictionary is initialized with the empty string and how the algorithm handles the final phrase that may not have a trailing character. Error handling for empty inputs and proper escaping for HTML safety are also considered in the structure, even though the core logic remains simple.

def lz78_compress(data: str):
    """
    Compress a string using the LZ78 algorithm.
    Returns a list of (index, character) tuples.
    """
    # Dictionary maps phrase -> index. Index 0 is reserved for empty string.
    dictionary = {"": 0}
    next_index = 1
    result = []
    
    i = 0
    n = len(data)
    while i < n:
        # Find longest prefix of data[i:] that is in dictionary
        current = ""
        longest_index = 0
        j = i
        
        # Extend as long as current + next char exists in dict
        while j < n and (current + data[j]) in dictionary:
            current = current + data[j]
            longest_index = dictionary[current]
            j += 1
        
        # j is now at first char that creates a new phrase, or end of data
        if j < n:
            # Emit (index of longest match, next char) and add new phrase
            next_char = data[j]
            result.append((longest_index, next_char))
            new_phrase = current + next_char
            dictionary[new_phrase] = next_index
            next_index += 1
            i = j + 1
        else:
            # End of data reached exactly on a dictionary phrase
            # Emit final token with empty char marker if needed
            if current != "":
                result.append((longest_index, ""))
            break
            
    return result

Decompression mirrors compression but is simpler because it does not need to search for the longest match. It simply reconstructs the dictionary from the token stream. This asymmetry — where compression requires searching and decompression only requires lookups — is typical of many dictionary compressors and means decompression is almost always faster. The implementation below correctly handles the special final token and rebuilds the original data without loss.

def lz78_decompress(tokens):
    """
    Decompress a list of (index, character) tokens produced by LZ78.
    Returns the original string.
    """
    # Dictionary maps index -> phrase. Index 0 is empty string.
    dictionary = {0: ""}
    next_index = 1
    output_parts = []
    
    for index, char in tokens:
        # Lookup prefix phrase
        if index not in dictionary:
            raise ValueError(f"Invalid token index {index}")
        prefix = dictionary[index]
        # Reconstruct phrase
        phrase = prefix + char
        output_parts.append(phrase)
        # Add to dictionary (unless char is empty marker for final token)
        # We add even if char == "" to keep indices aligned, but don't output extra
        dictionary[next_index] = phrase
        next_index += 1
        
    return "".join(output_parts)

# Example usage
# compressed = lz78_compress("ABABABA")
# print(compressed)  # e.g., [(0, 'A'), (0, 'B'), (1, 'B'), (3, 'A')]
# print(lz78_decompress(compressed) == "ABABABA")  # True

For larger inputs, a trie-based optimization avoids repeatedly concatenating strings and hashing them. Instead, each dictionary entry is a node with children indexed by character. This reduces the time to find the longest match from O(m * L) where m is match length and L is dictionary lookup cost to O(m) trie traversal. The following optimized version demonstrates this structure, which is closer to what production compressors use.

class TrieNode:
    def __init__(self, index, phrase=""):
        self.index = index
        self.phrase = phrase
        self.children = {}  # char -> TrieNode

def lz78_compress_trie(data: str):
    """Optimized LZ78 using a Trie for O(n) longest-match search."""
    root = TrieNode(0, "")
    next_index = 1
    result = []
    
    i = 0
    n = len(data)
    while i < n:
        node = root
        longest_index = 0
        j = i
        
        # Walk trie as far as possible
        while j < n and data[j] in node.children:
            node = node.children[data[j]]
            longest_index = node.index
            j += 1
            
        if j < n:
            next_char = data[j]
            result.append((longest_index, next_char))
            # Create new node for new phrase
            new_phrase = node.phrase + next_char
            new_node = TrieNode(next_index, new_phrase)
            node.children[next_char] = new_node
            next_index += 1
            i = j + 1
        else:
            if node != root:
                result.append((longest_index, ""))
            break
            
    return result

Finally, to evaluate effectiveness, you need to measure compression ratio and throughput. The compressed size is not simply the number of tokens; you must account for the bits needed to encode each index and character. The helper below calculates both the token count and an estimated bit size, which is essential for benchmarking against other algorithms and for understanding when LZ78 actually saves space.

import math

def compression_stats(original: str, tokens):
    """Calculate compression ratio and estimated bits."""
    original_bits = len(original) * 8
    if not tokens:
        return {"ratio": 0, "original_bits": original_bits, "compressed_bits": 0}
    
    # Estimate bits: index bits grow as dictionary grows
    compressed_bits = 0
    dict_size = 1
    for idx, ch in tokens:
        # Bits needed for index at this point
        idx_bits = math.ceil(math.log2(dict_size + 1)) if dict_size > 0 else 1
        char_bits = 8 if ch != "" else 0
        compressed_bits += idx_bits + char_bits
        dict_size += 1
        
    ratio = (1 - compressed_bits / original_bits) * 100 if original_bits > 0 else 0
    return {
        "original_bits": original_bits,
        "compressed_bits": compressed_bits,
        "compression_ratio_percent": round(ratio, 2),
        "num_tokens": len(tokens),
        "dictionary_size": dict_size - 1
    }

# Demo
# data = "TOBEORNOTTOBEORTOBEORNOT" * 10
# toks = lz78_compress(data)
# print(compression_stats(data, toks))

4. Step-by-Step Example

Walking through a concrete example makes the abstract dictionary-building process tangible. Let's compress the string "ABABABA" using the lz78 compression algorithm. We will maintain a dictionary that starts with entry 0: "" (empty string). The input pointer starts at position 0. At each step we find the longest dictionary match starting at the current position, output its index plus the next character, and add the new phrase to the dictionary.

Step 1: At position 0, the remaining input is "ABABABA". The longest prefix in the dictionary is "" (index 0), because "A" is not yet in the dictionary. The next character is 'A'. We output (0, 'A') and add "A" as entry 1. Pointer moves to position 1.

Step 2: At position 1, remaining input is "BABABA". Longest match is "" (index 0) again, since "B" is not in the dictionary. Output (0, 'B'), add "B" as entry 2. Pointer moves to position 2.

The process continues, and the dictionary grows to capture longer repeated phrases like "AB" and "ABA", which allows later tokens to encode two or three characters at once. This incremental learning is why LZ78's compression improves as it sees more data.

The final token stream is [(0, 'A'), (0, 'B'), (1, 'B'), (3, 'A')]. To decompress, the decoder starts with {0: ""}. It reads (0, 'A') → prefix "" + 'A' = "A", outputs "A", adds 1: "A". Next (0, 'B') → "B", adds 2: "B". Next (1, 'B') → dictionary[1]="A" + 'B' = "AB", outputs "AB", adds 3: "AB". Finally (3, 'A') → dictionary[3]="AB" + 'A' = "ABA", outputs "ABA". Concatenating outputs: "A" + "B" + "AB" + "ABA" = "ABABABA", perfectly reconstructed.

Notice how the number of tokens (4) is less than the number of characters (7), but the actual bit savings depend on index size. With a tiny dictionary, indices need 1-2 bits, so 4 tokens * (2 bits index + 8 bits char) = 40 bits versus 56 bits original, a modest saving that grows dramatically on longer, more repetitive texts. This example also highlights that LZ78 parses the input into distinct phrases ("A", "B", "AB", "ABA") that are all different — a property called the distinct phrase parsing.

Visualizing Dictionary Growth

If we view the dictionary as a trie, after this example the root has two children: 'A' (node 1) and 'B' (node 2). Node 1 has a child 'B' (node 3), and node 3 has a child 'A' (node 4). This tree structure shows how LZ78 reuses prefixes. Compressing a longer string like "ABABABABABAB" would continue extending this branch, creating nodes for "ABAB", "ABABA", etc., each time encoding longer phrases with a single token.

5. Complexity Analysis

Analyzing the lz78 compression algorithm requires distinguishing between the naive dictionary implementation and the optimized trie-based version, as their time complexities differ significantly. We also need to consider best, average, and worst-case inputs, which are defined by the redundancy of the data. Highly repetitive data yields long matches and fewer dictionary entries, while random data yields short matches and a rapidly growing dictionary.

In the naive implementation where the dictionary is a hash map from strings to indices, finding the longest match requires iteratively building candidate strings and checking membership. For an input of length n, the total work is proportional to the sum of the lengths of all phrases. In the worst case of an input with no repetition, such as "ABCDEFG...", each phrase is length 1, so we perform n lookups of length-1 strings, which is O(n) expected time due to hashing. In the best case of a highly repetitive string like "AAAAA...", the phrases grow as "A", "AA", "AAA", etc., and the total work remains O(n) but with fewer, longer hash operations. The trie version guarantees O(n) worst-case time because each input character is traversed exactly once.

Space complexity is dominated by the dictionary. In the worst case, the number of dictionary entries can be O(n) for random data, and each entry stores a phrase whose total length across all entries can be O(n * sqrt(n)) in naive storage, but O(n) nodes in a trie. Therefore, space is O(n) in the number of characters stored, though the constant factor is high. Decompression is always O(n) time and O(n) space, as it simply iterates over tokens and reconstructs phrases.

It is important to note that theoretical O(n) time assumes constant-time dictionary operations. In practice, memory hierarchy effects and the cost of growing index bit-widths matter. As the dictionary exceeds 512, 1024, 2048 entries, the index bit-width increases from 9 to 10 to 11 bits, which slightly reduces compression efficiency and may require re-encoding. Some implementations cap the dictionary size (e.g., at 4096 entries for 12-bit LZW) and then either freeze it or flush it, which bounds space to O(1) but can hurt ratio on large files.

Best vs Worst Case Inputs

Best case for compression ratio: a file consisting of a single repeated character or a small repeated pattern, e.g., "ABABAB...". LZ78 will quickly learn long phrases and encode the file in O(sqrt(n)) tokens, achieving near-optimal compression approaching the entropy. Worst case: random or already compressed data (e.g., encrypted bytes) where no phrase repeats. LZ78 will emit n tokens of the form (0, c), actually expanding the data because each token costs more than 8 bits. This is why real compressors check if compression helps and store data uncompressed if not.

6. Variations and Optimizations

The original lz78 compression algorithm, while elegant, has been refined into several practical variants that address its limitations in memory usage and compression speed. The most famous variant is LZW (Lempel-Ziv-Welch), introduced by Terry Welch in 1984. LZW simplifies LZ78 by removing the explicit next-character from the token. Instead, it initializes the dictionary with all 256 possible single-byte values, so every single character is already present. The encoder then finds the longest match and outputs only its index, and the new dictionary entry is the match plus the first character of the next match. This eliminates the need to transmit the trailing character, improving ratio and simplifying implementation, which is why LZW became the standard for GIF and TIFF.

Another important optimization is dictionary size management. Unbounded growth, as in pure LZ78, is impractical for streaming large files or for systems with limited memory. Common strategies include: (1) Fixed-size dictionary with LRU eviction, where least-recently-used entries are discarded; (2) Dictionary freezing, where once the dictionary is full no new entries are added and compression continues with the static dictionary; and (3) Dictionary reset, where the dictionary is flushed and rebuilt from scratch when compression ratio degrades. Each strategy trades off adaptivity for bounded memory, and the choice depends on whether the data's statistics are stationary or changing.

Further improvements involve entropy coding of the output tokens. Raw LZ78 tokens have non-uniform index distributions — small indices are far more common than large ones. Applying Huffman or arithmetic coding to the index stream can yield an additional 10-20% improvement. Modern algorithms like LZMA and Brotli combine LZ77-style matching with range coding and large dictionaries to achieve state-of-the-art ratios, but they still trace their lineage directly to the phrase-building insight of LZ78.

Practical Implementation Tricks

For high-performance implementations, several low-level tricks matter. Using a double-array trie or a hash table with open addressing can speed up child lookups. Encoding indices with variable-length codes like Elias gamma or delta coding reduces bit cost for small indices. For binary data, initializing the dictionary with all 256 bytes (as in LZW) avoids the (0, c) overhead for the first occurrence of each byte. Finally, using a sliding dictionary window that only retains recent phrases can improve cache locality and adapt faster to changing data, blending LZ78's explicit dictionary with LZ77's recency bias.

7. Real-World Applications

Although pure LZ78 is rarely used in isolation today, its principles and its direct descendant LZW have been deployed widely across web servers, databases, networks, and file systems. Understanding where dictionary compression excels helps engineers decide when to apply it versus alternatives like Huffman-only or transform-based methods.

In web servers, HTTP compression (Content-Encoding: gzip, deflate) historically relied on Deflate, which combines LZ77 and Huffman coding. However, the dictionary concept from LZ78 influences how servers compress dynamic content like JSON APIs and HTML. For highly repetitive JSON responses from databases, a pre-shared dictionary approach inspired by LZ78 can pre-populate the dictionary with common keys and structures, dramatically improving compression for small payloads where traditional sliding-window methods have little history to reference. This is the idea behind SDCH and Brotli's dictionary feature used by CDNs.

Databases and storage engines use dictionary compression extensively for columnar data. Systems like Apache Parquet, ClickHouse, and Oracle's Hybrid Columnar Compression build dictionaries per column or per row group. For columns with low cardinality — such as status codes, country names, or categorical features — dictionary encoding (essentially LZ78 with a frozen dictionary per block) can reduce storage by 80-90% and also accelerate queries because predicates can be evaluated directly on dictionary indices without decompressing. Write-ahead logs and backup systems also use LZ78-style phrase dictionaries to deduplicate repeated SQL statements or log lines.

In networking, the V.42bis modem standard and some IoT lightweight protocols use LZW with a small fixed dictionary (512-2048 entries) because it requires minimal RAM and provides good compression for textual AT commands and sensor readings. File formats like GIF still use LZW for image data, where each image's color table serves as an initial dictionary. Even in modern version control systems like Git, delta compression uses dictionary-like techniques to store similar objects efficiently, echoing LZ78's phrase reuse.

When Not to Use LZ78

LZ78 is less suitable for data that is already compressed or encrypted, for very short messages where dictionary overhead dominates, or for data requiring random access. In those cases, entropy coders or block-based compressors with independent blocks are preferable. For large-scale analytics, columnar dictionary encoding is often combined with run-length and bit-packing to balance ratio and decode speed.

8. Comparison with Alternatives

Choosing a compression algorithm requires understanding how the lz78 compression algorithm compares to its relatives and to fundamentally different approaches. The table below provides a feature-by-feature comparison that is essential for system design and for interview discussions. LZ77, LZ78, LZW, Huffman, and Deflate represent the major milestones in lossless compression, each with distinct trade-offs in dictionary management, speed, and ratio.

LZ77, the predecessor to LZ78, uses a sliding window and encodes matches as (distance, length) pairs. It does not build an explicit dictionary but instead references the recent history buffer. This makes it more memory-efficient for streaming and better at capturing close repetitions, but it struggles with long-range repeats that have scrolled out of the window. LZ78's explicit dictionary, by contrast, remembers phrases indefinitely (until evicted), making it better for files where a phrase repeats after a long gap. LZW improves on LZ78 by preloading the dictionary and emitting only indices, which simplifies the format and improves ratio for byte-oriented data.

Huffman coding is an entropy coder, not a dictionary coder. It assigns shorter codes to frequent symbols and is optimal for known symbol frequencies, but it cannot exploit phrase-level redundancy. Deflate, the algorithm behind gzip and ZIP, combines the best of both worlds: it uses LZ77 for phrase matching and then Huffman-codes the resulting literals and match lengths. This hybrid approach generally outperforms pure LZ78 or pure Huffman alone, which is why Deflate remains dominant for general-purpose compression.

In practice, the choice often comes down to constraints. If you need the simplest possible decoder for embedded hardware, LZW is attractive. If you need maximum ratio for web assets, Brotli or LZMA (which use large dictionaries and context modeling) will beat pure LZ78. For database columns, a frozen LZ78-style dictionary per block is often optimal because it enables vectorized decoding and predicate pushdown, whereas LZ77's sliding window would require sequential decompression.

Empirical Rule of Thumb

On English text, expect Huffman alone to achieve ~60% of original size, LZ78/LZW ~45-50%, and Deflate/Brotli ~30-35%. On highly repetitive logs, dictionary methods can reach 10% or less, while Huffman may still hover around 50% because it cannot capture phrase repetition. Always benchmark on your actual data distribution.

9. Common Mistakes and Best Practices

Implementing and deploying the lz78 compression algorithm correctly requires avoiding several subtle pitfalls that can lead to incorrect decompression, poor compression ratios, or excessive memory use. One of the most common mistakes is mishandling the final phrase. If the input ends exactly on a dictionary phrase with no trailing character, some implementations incorrectly drop the last token or emit an extra empty character. The correct approach, as shown in the code above, is to emit a final token (index, "") and ensure the decoder handles empty-character tokens by not appending an extra byte but still adding the phrase to the dictionary to keep indices synchronized.

Another frequent error is using string concatenation for dictionary keys in a naive hash map without considering performance. In Python, repeatedly doing `current + data[j]` creates many temporary strings and can lead to O(n²) behavior on long repetitive inputs. The trie-based approach avoids this, but if you stay with a hash map, you should at least use incremental building and consider interning or using bytes. Similarly, failing to bound dictionary size is a classic production bug: an unbounded dictionary will eventually exhaust memory on large files or infinite streams. Always implement a maximum size (e.g., 4096 or 65536 entries) and a clear policy for what happens when it is reached — freeze, reset, or LRU eviction.

A third mistake is measuring compressed size incorrectly by counting tokens instead of bits. Beginners often report compression ratio as `len(tokens) / len(original)`, which is meaningless because a token is larger than a character. You must calculate the actual bit cost, including the growing index width, as demonstrated in the `compression_stats` helper. Failing to do so can lead to the false conclusion that LZ78 is compressing random data when it is actually expanding it. Always compare `compressed_bits` versus `original_bits`.

Best Practices Checklist

• Initialize correctly: Start with index 0 → "" and ensure both encoder and decoder use identical initialization. For LZW, preload 0-255 with single bytes.
• Bound your dictionary: Set a maximum size (e.g., 12-bit = 4096 entries) and define a reset or freeze policy. Monitor compression ratio to trigger resets.
• Use a trie for speed: For inputs larger than a few kilobytes, a trie or double-array trie will be significantly faster than string hashing.
• Handle binary data: Work with `bytes` objects rather than `str` when compressing arbitrary files to avoid Unicode issues and to correctly handle all 256 byte values.
• Test round-trip: Always verify `decompress(compress(data)) == data` on diverse inputs: empty string, single char, repetitive, random, and binary data with null bytes.
• Consider entropy coding: If you need better ratios, Huffman-code the index stream after LZ78 parsing rather than using fixed-width indices.
• Profile before deploying: Benchmark on your actual workload. For small messages (< 100 bytes), dictionary overhead may hurt; consider not compressing or using a pre-shared dictionary.

Finally, be mindful of security and robustness. A maliciously crafted compressed file could claim a huge dictionary size or contain invalid indices that cause the decoder to allocate excessive memory or crash. Production decoders must validate every index, enforce maximum dictionary and output size limits, and handle truncated inputs gracefully. These defensive practices are what separate a textbook implementation from a production-ready one.

10. Interview Questions

Technical interviews frequently use the lz78 compression algorithm to test understanding of data structures, string algorithms, and system design trade-offs. The questions below are representative of what you might encounter for software engineering, backend, or data engineering roles, along with guidance on what interviewers look for in strong answers.

Q1: How does LZ78 differ from LZ77, and when would you prefer one over the other?

What to answer: Explain that LZ77 uses a sliding window and encodes (distance, length) references to recent history, while LZ78 builds an explicit dictionary of phrases and encodes (index, next_char). LZ77 is better for streaming with limited memory and for capturing local repetitions within the window, whereas LZ78 is better for capturing long-range repetitions because its dictionary persists indefinitely and can reference phrases seen much earlier. Mention that LZ77 is the basis for Deflate/gzip, while LZ78 led to LZW/GIF. A strong answer also discusses memory: LZ77 is O(window size), LZ78 is O(number of phrases) unbounded unless capped.

Q2: Walk through LZ78 compression for the input "AAAAAA" and give the token output.

What to answer: Demonstrate step-by-step parsing. Dictionary starts {0:""}. Position 0: longest match "" → output (0,'A'), add 1:"A". Position 1: remaining "AAAAA", longest match "A" (1) → output (1,'A'), add 2:"AA". Position 3: remaining "AAA", longest match "AA" (2) → output (2,'A'), add 3:"AAA". Position 6: end. Tokens: [(0,'A'), (1,'A'), (2,'A')]. Decompression yields "A" + "AA" + "AAA" = "AAAAAA". This tests understanding of distinct phrase parsing and the prefix property. Mention the final token handling if the input were "AAAAAAA" (7 As) you would have an extra (1,'') or similar depending on variant.

Q3: What is the time and space complexity of LZ78, and how would you optimize it?

What to answer: State that naive hash-map implementation is O(n) expected time but can degrade to O(n²) with collisions and O(n²) space if storing full strings, while trie-optimized is O(n) time and O(n) space where n is input length. Decompression is always O(n). For optimization, propose using a trie (each node stores children map) so each character is processed once, bounding dictionary size (e.g., 4096 entries) to limit memory, and using variable-bit encoding for indices. Also mention that for large alphabets, using a hash table for children instead of an array saves space.

Q4: Why does LZ78 sometimes expand data instead of compressing it, and how would you handle that in production?

What to answer: Explain that on random or high-entropy data (e.g., encrypted or already compressed files), LZ78 finds no long matches and emits many (0,c) tokens, each costing >8 bits (index bits + 8 bits char), so output is larger than input. In production, you should detect this by estimating compressed size and, if ratio is poor, store the block uncompressed with a header flag. Also implement dictionary reset or freezing to avoid wasting bits on large indices when the dictionary is not helping. This tests practical system design awareness.

Q5: How would you adapt LZ78 for compressing a column of strings in a database with low cardinality?

What to answer: Describe building a per-block dictionary (frozen LZ78 style) where you first collect distinct values, assign each an index, and then encode the column as an array of indices plus the dictionary. This is dictionary encoding, widely used in Parquet/ORC. It achieves high compression and allows query acceleration via dictionary filtering. Contrast with applying LZ78 directly to the concatenated column, which would be slower and not support random access. Mention techniques like bit-packing indices and using RLE on the index stream for further gains.

Preparing for these questions by implementing LZ78 from scratch, analyzing its complexity, and reasoning about its trade-offs will demonstrate both algorithmic depth and practical engineering judgment — exactly what interviewers seek when they ask about compression.