The problem of one-way file synchronization from the client to the data-center, namely, file updates, is studied. The problem is investigated in particular when an old version of a file which can be available at both client and data-center, is edited by the client to a new version. The edits are modeled as random insertions and deletions (InDels). Based on the updated and the previous version of the file, the client transmits a message to the data-center via a noiseless link, such that the data-center can update the file. A dynamic-programming-run-length-coding (DP-RLC) scheme is proposed for the message encoding in this paper. The lower order terms of the achievable rate are computed explicitly. It is worth noting that these terms match the information-theoretic lower bound derived in our previous work [1]. Therefore, when the insertion and deletion probabilities are small, the achievable rate is nearly optimal.
['Qiwen Wang', 'Muriel Medard', 'Mikael Skoglund']
Efficient compression algorithm for file updates under random insertions and deletions