On the Optimality of Parsing in Dynamic Dictionary Based Data Compression

This paper considers the following question: once a (dynamic) dictionary construction scheme is selected, is there an efficient dynamic parsing method that results with the smallest number of phrases possible for the selected scheme, for all input strings. It is shown that greedy parsing, a method used in almost all dynamic dictionary based algorithms (including unix compress, gif image compression, and fax and modem standards), can be far from optimal for certain input strings. On the positive side, a simple parsing method is introduced which, for any selected dictionary scheme which has the prefix property (this includes virtually all the variations on Lempel-Ziv algorithms), is optimal with respect to the selected scheme for any input string. Also introduced is a simple data structure that enables an efficient dynamic implementation of the parsing method, in O(1) time per character and optimal space requirement. Some practical issues and experimental results (in comparison t