This proposal discusses important old and new problems in data compression, in the light of results springing from new probabilistic analyses of digital trees and their generalizations, and (approximate) pattern matching algorithms. We use our expertise in analysis and design of algorithms on strings to bring new ideas to bear on data compression problems. Our goal is not only to gain insight into the usefulness of existing schemes for data compression, but also to develop new algorithms for lossless off-line data compression and lossy data compression (on-line and off-line). We point out that to predict dynamic performance of a data com pression method (particularly, off-line schemes) one needs information about second-order properties (e.g., the large deviations and limiting distribution of number of phrases in the Lempel-Ziv parsing algorithm, etc.) which we plan to explore during the course of this research.
CS Annual Report - 19 APR 1996