The prevention of error propagation in dictionary compression with update and deletion

In earlier work, we presented the k-error protocol, a technique for protect ing a dynamic dictionary lossless data compression method from error propag ation as the result of errors on the communication channel or compressed fi le. In the worst case, the protocol only protects against k errors total; h owever, it gives very high probability protection against a sustained error rate. Here, we further develop this protocol and present experiments showi ng that in practice this approach is both fast and highly effective against a noisy channel or faulty storage medium. We also address the issue of dyn amically deleting strings. Although without modification most standard meth ods used in practice (e.g., LRU strategies) perform poorly with respect to error propagation, we propose and analyze some that are very robust, includ ing a strategy based on leaf pruning.