A suboptimal lossy data compression based on approximate pattern matching

DOI10.1109/18.623143zbMath0953.94012WikidataQ105584734 ScholiaQ105584734MaRDI QIDQ4371886

Tomasz Łuczak, Wojciech Szpankowski

Publication date: 14 January 2001

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/18.623143

zbMATH Keywords

approximate string matching; stationary mixing sequences; compression rate; lossy data compression; lossless Lempel-Ziv data compression scheme; source coding algorithm; typical length

Mathematics Subject Classification ID

68P10: Searching and sorting

94A29: Source coding

94A34: Rate-distortion theory in information and communication theory

Related Items

R\'enyi entropy and pattern matching for run-length encoded sequences, The Rényi entropy function and the large deviation of short return times, Statistical inference for the \(\epsilon \)-entropy and the quadratic Rényi entropy, On approximate pattern matching for a class of Gibbs random fields, The asymptotics of waiting times between stationary processes, allowing distortion, Optimal data compression algorithm, Stochastic sub-additivity approach to the conditional large deviation principle, Complexity-compression tradeoffs in lossy compression via efficient random codebooks and databases, Shortest distance between multiple orbits and generalized fractal dimensions, Longest common substring for random subshifts of finite type, Matching strings in encoded sequences, Random databases with approximate record matching