Normalization of edit sequences for text synchronization

¹ Departamento de Lenguajes y Sistemas Informàticos, Universidad de Alicante, 03071 Alicante, Spain. carrasco@dlsi.ua.es
² Departamento de Computación. Universidad Agraria de La Habana. La Habana, Cuba. alezsd@yahoo.com

Received: 7 May 2009
Accepted: 7 February 2011

Abstract

It often occurs that local copies of a text are modified by users but that the local modifications are not synchronized (thus allowing the merged text to become the source for later editions) until later when, for instance the network connection is reestablished. Since text editions usually affect a small fraction of the whole content, the history of edit operations provides a compact representation of the modified file. In this paper, we define a normal form for these records which will permit for the comparison of all text files that have been obtained by editing a common source S when the difference between each output file O_i and the source file is given as a sequence L_i of edit operations. We show that the normalized sequence is unique for all the equivalent text editions and provide efficient procedures with which to compute this normal form and to obtain the edit sequence L_M transforming S into a merged file M which integrates all the local modifications. We also discuss how these normalization can be integrated into the operational transformation paradigm for optimistic replication.