Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-26T17:37:22.211Z Has data issue: false hasContentIssue false
  • English
  • Français

Normalization of edit sequences for text synchronization

Published online by Cambridge University Press:  18 April 2011

Rafael C. Carrasco  and
Alexander Sánchez Díaz
Rafael C. Carrasco
Affiliation:
Departamento de Lenguajes y Sistemas Informàticos, Universidad de Alicante, 03071 Alicante, Spain. [email protected]
Alexander Sánchez Díaz
Affiliation:
Departamento de Computación. Universidad Agraria de La Habana. La Habana, Cuba. [email protected]
Get access

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 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.

Keywords

Edit distancetext synchronizationreconciliation of replicas
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 45 , Issue 2 , April 2011 , pp. 235 - 248
Copyright
© EDP Sciences, 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

S. Balasubramaniam and B.C. Pierce, What is a file synchronizer, in Forth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom'98) (1998) 98–1085.
Bille, P., A survey on tree edit distance and related problems. Theoret. Comput. Sci. 337 (2005) 217–239. CrossRef
T.H. Cormen, C.E. Leiserson and R.L. Rivest, Introduction to algorithms. 6th edition, MIT Press and McGraw-Hill Book Company (1992).
R. Cox and W. Josephson, File synchronization with vector time pairs. Technical Report MIT-CSAIL-TR-2005-014 and MIT-LCS-TM-650, MIT Computer Science and Artificial Intelligence Laboratory (2005).
C.A. Ellis and S.J. Gibbs, Concurrency control in groupware systems, in Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data. J. Clifford, B.G. Lindsay and D. Maier, Eds. ACM Press (1989) 399–407.
Foster, J.N., Greenwald, M.B., Kirkegaard, C., Pierce, B.C. and Schmitt, A., Exploiting schemas in data synchronization. J. Comput. System Sci. 73 (2007) 669–689. CrossRef
Imine, A., Rusinowitch, M., Oster, G. and Molli, P., Formal design and verification of operational transformation algorithms for copies convergence. Theoret. Comput. Sci. 351 (2006) 167–183. CrossRef
A.-M. Kermarrec, A.I.T. Rowstron, M. Shapiro and P. Druschel, The IceCube approach to the reconciliation of divergent replicas, in PODC 2001, Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing. ACM (2001) 210–218.
S. Khanna, K. Kunal and B.C. Pierce, A formal investigation of diff3, in Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Arvind and Prasad, Eds. (2007).
T. Lindholm, A three-way merge for XML documents, in DocEng '04: Proceedings of the 2004 ACM symposium on Document engineering. ACM, New York, NY, USA (2004) 1–10.
Lippe, E. and van Oosterom, N., Operation-based merging. SIGSOFT Softw. Eng. Notes 17 (1992) 78–87. CrossRef
Lushman, B., and Cormack, G.V., Proof of correctness of Ressel's adOPTed algorithm. Inform. Process. Lett. 86 (2003) 303–310. CrossRef
Masek, W.J. and Paterson, M.S., A faster algorithm computing string edit distances. J. Comput. System Sci. 20 (1980) 18–31. CrossRef
F. Mattern, Virtual time and global states of distributed systems, in Proc. Workshop on Parallel and Distributed Algorithms, M. Cosnard, Ed., Chateau de Bonas, France. Elsevier (1988) 215–226.
B.C. Pierce and J. Vouillon, What's in Unison? A formal specification and reference implementation of a file synchronizer. Technical Report MS-CIS-03-36, Dept. of Computer and Information Science, University of Pennsylvania (2004).
Ramsey, N. and Csirmaz, E., An algebraic approach to file synchronization. SIGSOFT Softw. Eng. Notes 26 (2001) 175–185. CrossRef
M. Ressel, D. Nitsche-Ruhland and R. Gunzenhäuser, An integrating, transformation-oriented approach to concurrency control and undo in group editors, in CSCW '96, Proceedings of the ACM 1996 Conference on Computer Supported Cooperative Work. Boston, MA, USA, ACM (1996) 288–297.
Saito, Y. and Shapiro, M., Optimistic replication. ACM Comput. Surv. 37 (2005) 42–81. CrossRef
H. Shen and C. Sun, A log compression algorithm for operation-based version control systems, in Proceedings of the 26th International Computer Software and Applications Conference on Prolonging Software Life: Development and Redevelopment, COMPSAC '02. IEEE Computer Society Washington, DC, USA (2002) 867–872.
T. Suel and N. Memon, Algorithms for delta compression and remote file synchronization, in Lossless Compression Handbook, K. Sayood, Ed. Academic Press (2003) 269–290.
C. Sun and C.A. Ellis, Operational transformation in real-time group editors: Issues, algorithms, and achievements, in CSCW98, Proceedings of the ACM 1998 Conference on Computer Supported Cooperative Work. ACM (1998) 59–68.
Sun, C., Jia, X., Zhang, Y., Yang, Y. and Chen, D., Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems. ACM Trans. Computer-Human Interaction 5 (1998) 63–108. CrossRef
Tichy, W.F., The string-to-string correction problem with block moves. ACM Trans. Comput. Syst. 2 (1984) 309–321. CrossRef
A. Tridgell and P. Mackerras, The rsync algorithm. Technical Report TR-CS-96-05, Department of Computer Science, Faculty of Engineering and Information Technology, The Australian National University (1996).
Zhang, K. and Shasha, D., Simple fast algorithms for the editing distance between trees and related problems. SIAM J. Comput. 18 (1989) 1245–1262. CrossRef