Practical dictionary management for hardware data compression

Reviewer: Robert J. DeMattia

A new dictionary management algorithm for Lempel-Ziv encoders is described. The authors use a tagged-trie structure in order to manage the deletion of unnecessary leaf nodes. Using their algorithm and five other well-known algorithms, the authors compress 12 files that are representative of common types of data. The resulting evidence shows performance equal to or better than all other methods. The authors present evidence that their algorithm requires less hardware complexity and less memory than other methods. Most of the discussion centers on the encoding algorithm, with less time spent on the implementation. The discussion of the decoding algorithm is also limited. The paper does a good job of explaining the algorithm, though one of the figures could have been expanded to show more intermediate steps. Some inexperienced readers may have to draw a few supplemental diagrams in order to clarify things. Anyone with an understanding of decompression will find this easy reading, however. The innovative algorithm described in the paper makes it worthwhile reading for anyone interested in data compression. The parallel nature of the Lempel-Ziv algorithm and the authors' TAG algorithm provides an interesting challenge for hardware designers. Software designers may wish to investigate the pros and cons of this new approach further.