Skip to main content

Error-resilient optimal data compression

Publication ,  Journal Article
Storer, JA; Reif, JH
Published in: SIAM Journal on Computing
January 1, 1997

The problem of communication and computation in the presence of errors is difficult, and general solutions can be time consuming and inflexible (particularly when implemented with a prescribed error detection/correction). A reasonable approach is to investigate reliable communication in carefully selected areas of fundamental interest where specific solutions may be more practical than general purpose techniques. In this paper, we study the problem of error-resilient communication and computation in a particularly challenging area, adaptive lossless data compression, where the devastating effect of error propagation is a long-standing open problem that was posed in the papers of Lempel and Ziv in the late 1970s. In fact, the non-error resilience of adaptive data compression has been a practical drawback of its use in many applications. Protocols that require the receiver to request retransmission from the sender when an error is detected can be impractical for many applications where such two-way communication is not possible or is self-defeating (e.g., with data compression, retransmission may be tantamount to losing the data that could have been transmitted in the mean time). In addition, bits of encoded data that are corrupted while data is in storage will in general not be recoverable and may corrupt the entire decompressed file. By error resilience, we mean that even though errors may not be detected, there are strong guarantees that their effects will not propagate. Our main result is a provable error-resilient adaptive lossless data-compression algorithm which nevertheless maintains optimal compression over the usual input distributions (e.g., stationary ergodic sources). We state our result in the context of a more general model that we call dynamic dictionary communication, where a sender and receiver work in a "lock-step" cooperation to maintain identical copies of a dictionary D that is constantly changing. For lossless data compression, the dictionary stores a set of strings that have been seen in the past and data is compressed by sending only indices of strings over the channel. Other applications of our model include robotics (e.g., remote terrain mapping) and computational learning theory.

Duke Scholars

Published In

SIAM Journal on Computing

DOI

ISSN

0097-5397

Publication Date

January 1, 1997

Volume

26

Issue

4

Start / End Page

934 / 949

Related Subject Headings

  • Computation Theory & Mathematics
  • 4903 Numerical and computational mathematics
  • 4901 Applied mathematics
  • 4613 Theory of computation
  • 0802 Computation Theory and Mathematics
  • 0101 Pure Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Storer, J. A., & Reif, J. H. (1997). Error-resilient optimal data compression. SIAM Journal on Computing, 26(4), 934–949. https://doi.org/10.1137/S0097539792240789
Storer, J. A., and J. H. Reif. “Error-resilient optimal data compression.” SIAM Journal on Computing 26, no. 4 (January 1, 1997): 934–49. https://doi.org/10.1137/S0097539792240789.
Storer JA, Reif JH. Error-resilient optimal data compression. SIAM Journal on Computing. 1997 Jan 1;26(4):934–49.
Storer, J. A., and J. H. Reif. “Error-resilient optimal data compression.” SIAM Journal on Computing, vol. 26, no. 4, Jan. 1997, pp. 934–49. Scopus, doi:10.1137/S0097539792240789.
Storer JA, Reif JH. Error-resilient optimal data compression. SIAM Journal on Computing. 1997 Jan 1;26(4):934–949.

Published In

SIAM Journal on Computing

DOI

ISSN

0097-5397

Publication Date

January 1, 1997

Volume

26

Issue

4

Start / End Page

934 / 949

Related Subject Headings

  • Computation Theory & Mathematics
  • 4903 Numerical and computational mathematics
  • 4901 Applied mathematics
  • 4613 Theory of computation
  • 0802 Computation Theory and Mathematics
  • 0101 Pure Mathematics