Data Compression from the String Matching Perspective: Second Order Properties

该研究解决了数据压缩问题的算法设计和分析。该研究将利用数字树及其概括、近似模式匹配和与字符串相关的算法的新分析和概率分析的结果。研究的问题范围从离线的Lempel-Ziv压缩方案，Lempel-Ziv算法的有损扩展，到最短超弦问题（无损和有损版本）。主要目标是探索几种现有和新的数据压缩方案的二阶特性（如方差、极限分布、大偏差等），以获得这些方案的典型行为的更精细的信息。在推导结果时，使用了一种在数据压缩环境中新颖的技术，该技术属于“算法的分析分析”工具包。对一些开放问题的初步应用表明了该方法的潜力。＊＊＊

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. ***