Implementation and Experimental Evaluation of Flexible Parsing for Dynamic Dictionary Based Data Compression

Yossi Matias, Nasir M. Rajpoot, Süleyman Cenk SahinalpWAE 1998

Introduction

Dictionary-based data compression, exemplified by widely used tools like gzip (LZ77) and compress (LZW), typically relies on a "greedy" parsing strategy. In this approach, the encoder identifies the longest possible match in its current dictionary and outputs its index. While computationally efficient, this local optimization often leads to sub-optimal global compression. A long match chosen now might preclude even longer matches later, resulting in a higher total number of phrases.

This paper explores "Flexible Parsing" (FP), a technique that introduces a one-step lookahead to optimize phrase partitioning. By replacing the standard greedy approach with a more "farsighted" strategy, FP can achieve the minimum number of phrases for dictionaries that satisfy the prefix property.

Flexible Parsing and Theoretical Optimality

The core concept of Flexible Parsing is to replace the immediate gratification of greedy selection with a more strategic decision. Instead of simply picking the longest match starting at the current position, FP evaluates all possible matches. It selects the match that allows the next phrase to end at the furthest possible point in the data stream.

Comparison of standard greedy LZW parsing versus Flexible Parsing (LZWFP) on a sample input.

As illustrated in the comparison above, this lookahead strategy can result in a different, more efficient partitioning of the input string compared to the standard LZW algorithm. For dictionaries where every prefix of a phrase is also a phrase (the prefix property), this single-step lookahead is mathematically guaranteed to produce the optimal (minimum) number of phrases.

Practical Implementation via Randomized Data Structures

While FP is theoretically superior, traditional implementations using complex pointer-heavy structures are often slow and memory-intensive. The authors overcome this by utilizing Karp-Rabin fingerprints.

By employing hashing, the algorithm can perform "Extend" (adding a character to the end) and "Contract" (removing a character from the front) operations in $O(1)$ expected time. This randomized approach is significantly more cache-friendly than traditional trie-based implementations, allowing for a linear $O(n)$ time complexity that remains viable for large datasets.

Experimental Evaluation

The authors evaluated two variants—LZW-FP (standard LZW dictionary with FP) and FPA (a new dictionary scheme designed for FP)—against a diverse set of benchmarks including human DNA sequences, medical imaging (MR/CT scans), and the classic Calgary and Canterbury corpora.

Key Results

The experimental results demonstrate significant improvements in compression ratios:

  • DNA and Structured Data: FP-based methods achieved up to a 35% improvement over gzip on DNA sequences and pseudorandom strings.
  • Comparison to compress: LZW-FP and FPA consistently outperformed the standard UNIX compress utility, typically by 5% to 20% on larger files.
  • Scaling: The benefits of FP become more pronounced as file size increases. For files exceeding 1MB, the FPA-24 implementation outperformed gzip by nearly 5-8% even on standard text files.

Conclusion

Flexible Parsing bridges the gap between theoretical optimality and practical data compression. While the computational cost is higher—FP algorithms are currently 3 to 5 times slower than their greedy counterparts—the linear time complexity and substantial gains in compression ratio make it a compelling choice for specific domains. Particularly in fields like genomics and medical imaging, the "farsighted" approach of Flexible Parsing offers a significant advantage over industry-standard greedy algorithms.

Summary updated

BibTeX
@inproceedings{matias1998implementation,
  author = {Yossi Matias and Nasir M. Rajpoot and Süleyman Cenk Sahinalp},
  title = {{Implementation and Experimental Evaluation of Flexible Parsing for Dynamic Dictionary Based Data Compression}},
  booktitle = {WAE},
  year = {1998},
}
Figure