A lossy data compression based on string matching: Preliminary analysis and suboptimal algorithms
Authors:
- Tomasz Łuczak,
- Wojeiech Szpankowsk
Abstract
A practical suboptimal algorithm (source coding) for lossy (non-faithful) data compression is discussed. This scheme is based on an approximate string matching, and it naturally extends lossless (faithful) Lempel-Ziv data compression scheme. The construction of the algorithm is based on a careful probabilistic analysis of an approximate string matching problem that is of its own interest. This extends Wyner-Ziv model to lossy environment. In this conference version, we consider only Bernoulli model (i.e., memoryless channel) but our results hold under much weaker probabilistic assumptions.
- Record ID
- UAM6446be062b084bd3bb5868355394d040
- Author
- Pages
- 102-112
- Book
- Crochemore Maxime , Maxime Crochemore Gusfield Dan Dan Gusfield (eds.): Combinatorial Pattern Matching, Lecture Notes In Computer Science, no. 807, 1994, Berlin, Heidelberg, Springer, 331 p., ISBN 9783540580942. DOI:10.1007/3-540-58094-8 Opening in a new tab
- ASJC Classification
- ; ; ; ; ; ; ;
- DOI
- DOI:10.1007/3-540-58094-8_9 Opening in a new tab
- URL
- https://link.springer.com/chapter/10.1007/3-540-58094-8_9 Opening in a new tab
- Language
- (en) English
- Score (nominal)
- 0
- Publication indicators
- = 5; = 17
- Citation count
- 17
Share
- Uniform Resource Identifier
- https://researchportal.amu.edu.pl/info/article/UAM6446be062b084bd3bb5868355394d040/
- URN
urn:amu-prod:UAM6446be062b084bd3bb5868355394d040
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or PerishOpening in a new tab system.