RAIRO-Theor. Inf. Appl.
Volume 45, Number 2, April-June 2011
|235 - 248
|18 April 2011
Normalization of edit sequences for text synchronization
Departamento de Lenguajes y Sistemas Informàticos,
Universidad de Alicante, 03071 Alicante, Spain.
2 Departamento de Computación. Universidad Agraria de La Habana. La Habana, Cuba. firstname.lastname@example.org
Accepted: 7 February 2011
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 Oi and the source file is given as a sequence Li 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 LM 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.
Mathematics Subject Classification: 68U99
Key words: Edit distance / text synchronization / reconciliation of replicas
© EDP Sciences, 2011
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.