An order-2 context model for data compression with reduced time and space requirements
Debra A. Lelewer, Daniel S. Hirschberg · 1990
Context modeling has emerged as the most promising new approach to compressing text. While context-modeling algorithms provide very good compression, they suffer from the disadvantages of being quite slow and requiring large amounts of main memory in which to execute. We describe a context-model-based algorithm that runs significantly faster and uses less space than earlier context models. Although our algorithm does not achieve the compression performance of competing context models, it does provide a significant improvement over the widely-used Unix utility compress in terms of both use of memory and compression performance. Introduction The most widely used data compression algorithms, including the Unix utility compress, are based on the work of Ziv and Lempel [ZL78]. These are dynamic algorithms that build a dictionary representative of the input text and code dictionary entries using fixed-length codewords. Compress typically reduces a file to 40--50% of its original size. Co...