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.
Mots-clés : edit distance, text synchronization, reconciliation of replicas
@article{ITA_2011__45_2_235_0, author = {Carrasco, Rafael C. and S\'anchez D{\'\i}az, Alexander}, title = {Normalization of edit sequences for text synchronization}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {235--248}, publisher = {EDP-Sciences}, volume = {45}, number = {2}, year = {2011}, doi = {10.1051/ita/2011017}, mrnumber = {2811656}, zbl = {1218.68193}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita/2011017/} }
TY - JOUR AU - Carrasco, Rafael C. AU - Sánchez Díaz, Alexander TI - Normalization of edit sequences for text synchronization JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2011 SP - 235 EP - 248 VL - 45 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita/2011017/ DO - 10.1051/ita/2011017 LA - en ID - ITA_2011__45_2_235_0 ER -
%0 Journal Article %A Carrasco, Rafael C. %A Sánchez Díaz, Alexander %T Normalization of edit sequences for text synchronization %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2011 %P 235-248 %V 45 %N 2 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita/2011017/ %R 10.1051/ita/2011017 %G en %F ITA_2011__45_2_235_0
Carrasco, Rafael C.; Sánchez Díaz, Alexander. Normalization of edit sequences for text synchronization. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 2, pp. 235-248. doi : 10.1051/ita/2011017. http://archive.numdam.org/articles/10.1051/ita/2011017/
[1] What is a file synchronizer, in Forth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom'98) (1998) 98-1085.
and ,[2] A survey on tree edit distance and related problems. Theoret. Comput. Sci. 337 (2005) 217-239. | MR | Zbl
,[3] Introduction to algorithms. 6th edition, MIT Press and McGraw-Hill Book Company (1992). | MR | Zbl
, and ,[4] 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).
and ,[5] 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.
and ,[6] Exploiting schemas in data synchronization. J. Comput. System Sci. 73 (2007) 669-689. | MR | Zbl
, , , and ,[7] Formal design and verification of operational transformation algorithms for copies convergence. Theoret. Comput. Sci. 351 (2006) 167-183. | MR | Zbl
, , and ,[8] 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.
, , and ,[9] A formal investigation of diff3, in Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Arvind and Prasad, Eds. (2007). | Zbl
, and ,[10] 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.
,[11] Operation-based merging. SIGSOFT Softw. Eng. Notes 17 (1992) 78-87.
and ,[12] Proof of correctness of Ressel's adOPTed algorithm. Inform. Process. Lett. 86 (2003) 303-310. | MR | Zbl
, and ,[13] A faster algorithm computing string edit distances. J. Comput. System Sci. 20 (1980) 18-31. | MR | Zbl
and ,[14] 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. | MR
,[15] 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). | Zbl
and ,[16] An algebraic approach to file synchronization. SIGSOFT Softw. Eng. Notes 26 (2001) 175-185.
and ,[17] 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.
, and ,[18] Optimistic replication. ACM Comput. Surv. 37 (2005) 42-81. | Zbl
and ,[19] 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.
and ,[20] Algorithms for delta compression and remote file synchronization, in Lossless Compression Handbook, K. Sayood, Ed. Academic Press (2003) 269-290.
and ,[21] 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.
and ,[22] Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems. ACM Trans. Computer-Human Interaction 5 (1998) 63-108.
, , , and ,[23] The string-to-string correction problem with block moves. ACM Trans. Comput. Syst. 2 (1984) 309-321.
,[24] The rsync algorithm. Technical Report TR-CS-96-05, Department of Computer Science, Faculty of Engineering and Information Technology, The Australian National University (1996).
and ,[25] Simple fast algorithms for the editing distance between trees and related problems. SIAM J. Comput. 18 (1989) 1245-1262. | MR | Zbl
and ,Cité par Sources :