ERROR-RESILIENT OPTIMAL DATA-COMPRESSION

The problem of communication and computation in the presence of errors is difficult, and general solutions can be time consuming and inflexi ble (particularly when implemented with a prescribed error detection/c orrection). A reasonable approach is to investigate reliable communica tion in carefully selected areas of fundamental interest where specifi c 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 l ong-standing open problem that was posed in the papers of Lempel and Z iv in the late 1970s. In fact, the non-error resilience of adaptive da ta compression has been a practical drawback of its use in many applic ations. 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 se lf-defeating (e.g., with data compression, retransmission may be tanta mount 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 thoug h errors may not be detected, there are strong guarantees that their e ffects will not propagate. Our main result is a provable error-resilie nt adaptive lossless data-compression algorithm which nevertheless mai ntains optimal compression over the usual input distributions (e.g., s tationary ergodic sources). We state our result in the context of a mo re 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 lo ssless data compression, the dictionary stores a set of strings that h ave been seen in the past; and data is compressed by sending only indi ces of strings over the channel. Other applications of our model inclu de robotics (e.g., remote terrain mapping) and computational learning theory.