A Compression Algorithm Using Mis-aligned Side-information

Abstract

We study the problem of compressing a source sequence in the presence of side-information that is related to the source via insertions, deletions and substitutions. We propose a simple algorithm to compress the source sequence when the side-information is present at both the encoder and decoder. A key attribute of the algorithm is that it encodes the edits contained in runs of different extents separately. For small insertion and deletion probabilities, the compression rate of the algorithm is shown to be asymptotically optimal.

7 pages, 2 figures, 1 table. A shorter version is submitted to IEEE International Symposium on Information Theory (ISIT), 2012

References in corpus (2)

• Efficient File Synchronization: a Distributed Source Coding Approach
• A Compression Algorithm Using Mis-aligned Side-information

Cited by in corpus (6)

• Low-Complexity Interactive Algorithms for Synchronization from Deletions, Insertions, and Substitutions
• Reference Based Genome Compression
• A Compression Algorithm Using Mis-aligned Side-information
• Lossy Compression of Quality Values via Rate Distortion Theory
• File Updates Under Random/Arbitrary Insertions And Deletions
• Scalable String Reconciliation by Recursive Content-Dependent Shingling