A client encoder edits a file, as modeled by an insertion-deletion (InDel) process. An old copy of the file is stored remotely at a data-centre decoder, and is also available to the client. We consider the problem of throughput- and computationally-efficient communication from the client to the data-centre, to enable the server to update its copy to the newly edited file. We study two models for the source files edit patterns: the random pre-edit sequence left-to-right random InDel (RPES-LtRRID) process, and the arbitrary pre-edit sequence arbitrary InDel (APES-AID) process. In both models, we consider the regime in which the number of insertions deletions is a small (but constant) fraction of the original file. For both models we prove information-theoretic lower bounds on the best possible compression rates that enable file updates. Conversely, our compression algorithms use dynamic programming (DP) and entropy coding, and achieve rates that are approximately optimal.
@cite_18: In the paper two combinatorial problems for the set Fnq of sequences of length n over the alphabet Fq= 0, 1, ?, q?1 are considered. The maximum size N?q(n, t) of the set of common subsequences of length n?t and the maximum size N+q(n, t) of the set of common supersequences of length n+t of two different sequences of Fnq are found for any nonnegative integers n and t. The number N?q(n, t)+1 (respectively, N+q(n, t)+1) is equal to the minimum number N of different subsequences of length n?t (supersequences of length n+t) of an unknown sequence X?Fnq which are sufficient for its reconstruction. Simple algorithms to recover X?Fnq from N?q(n, t)+1 of its subsequences of length n?t and from N+q(n, t)+1 of its supersequences of length n+t are given.
@cite_26: We study the problem of synchronization of two remotely located data sources, which are mis-synchronized due to deletions and insertions. This is an important problem since a small number of synchronization errors can induce a large Hamming distance between the two sources. The goal is to effect synchronization with the rate-efficient use of lossless bidirectional links between the two sources. In this work, we focus on the following model. A binary sequence X of length n is edited to generate the sequence at the remote end, say Y, where the editing involves random deletions and insertions, possibly in small bursts. The problem is to synchronize Y with X with minimal exchange of information (in terms of both the average communication rate and the average number of interactive rounds of communication). We focus here on the case where the number of edits is much smaller than n, and propose an interactive algorithm which is computationally simple and has near-optimal communication complexity. Our algorithm works by efficiently splitting the source sequence into pieces containing either just a single deletion insertion or a single burst deletion insertion. Each of these pieces is then synchronized using an optimal one-way synchronization code, based on the single-deletion correcting channel codes of Varshamov and Tenengolts (VT codes).
@cite_4: 
@cite_14: 
@cite_7: 
@cite_8: The problem of interactive communication of correlated files is further studied. A computationally feasible protocol is presented and bounds on its communication complexity and the number of rounds are derived.
@cite_6: We study the problem of synchronizing two files X and Y at two distant nodes A and B that are connected through a two-way communication channel. We assume that file Y at node B is obtained from file X at node A by inserting and deleting a small fraction of symbols in X. More specifically, we consider the case where X is a non-binary non-uniform string, and deletions and insertions happen uniformly with rates βd and βi, respectively. We propose a synchronization protocol between node A and node B that needs to transmit O(q H2(βd+βi)n log 1 βd+βi) bits (where n is the length of X, q is the alphabet size and H2 is the collision entropy of X) and reconstructs X at node B with error probability exponentially low in n. This protocol readily generalizes the recent result by Tabatabaei Yazdi and Dolecek that dealt with synchronization from binary uniform source and under only deletion errors.
@cite_27: 
@cite_15: 
@cite_25: 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.
@cite_11: In this paper, we consider a synchronization problem between nodes @math and @math that are connected through a two--way communication channel. Node @math contains a binary file @math of length @math and node @math contains a binary file @math that is generated by randomly deleting bits from @math , by a small deletion rate @math . The location of deleted bits is not known to either node @math or node @math . We offer a deterministic synchronization scheme between nodes @math and @math that needs @math transmissions and reconstructs @math at node @math with probability of error that is exponentially low in the size of @math . The rate of our scheme matches the optimal rate for this channel. Our scheme can be extended to other editing models, e.g., insertions, repetitions or replacements, as long as the rate of editing is small.
Various models of the file-synchronization problem have been considered in the literature -- see Table @math for a summary. Our work here differs from each of those works in significant ways. For instance, in our model the encoder knows both files, hence we design one-way communication protocols (rather than the multi-round protocols required in the models where the encoder and the decoder each has one version of the file as in @cite_8 @cite_4 @cite_26 @cite_15 @cite_11 @cite_6 ); hence our protocols are information-theoretically near-optimal (however for two-way communication model, computationally efficient schemes which achieve rates with constant factors to the lower bounds are already challenging). The one-way communication model studied in @cite_14 @cite_25 is the closest to our RPES-LtRRID model. For the information-theoretical lower bound, we differ from @cite_14 by considering both insertions and deletions, and arbitrary alphabet. The achievability scheme in @cite_25 matches the lower bound up to first order term for the random source edit model, whereas our scheme is universal" for both RPES-LtRRID and APES-AID models in our work. The literature on insertion deletion channels and error-correcting codes is also quite closely related -- indeed, we borrow significantly from techniques in @cite_18 @cite_27 @cite_7 .