Data Compression from the String Matching Perspective: Second Order Properties

点击翻译按钮获取中文摘要

9415491 Szpankowski The research addresses the design and analysis of algorithms for data compression problems. The research will utilize results springing from new analytical and probabilistic analyses of digital trees and their generalizations, approximate pattern matching, and algorithms relating to strings. The problems investigated range from the off-line Lempel-Ziv compression scheme, lossy extensions of the Lempel-Ziv algorithm, to the shortest superstring problem (lossless and lossy versions). The main goal is to explore second-order properties (e.g. variances, limiting distributions, large deviations, etc.) of several existing and new data compression schemes in order to obtain more refined information about typical behavior of these schemes. In deriving the results, a technique, novel in the context of data compression, that belongs to the toolkit of the "analytical analysis of algorithms" is used. Initial applications to some open problems indicates the potential of the approach. ***