zbMATH — the first resource for mathematics

A formal investigation of diff3. (English) Zbl 1135.68375
Arvind, V. (ed.) et al., FSTTCS 2007: Foundations of software technology and theoretical computer science. 27th international conference, New Delhi, India, December 12–14, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-77049-7/pbk). Lecture Notes in Computer Science 4855, 485-496 (2007).
Summary: The diff3 algorithm is widely considered the gold standard for merging uncoordinated changes to list-structured data such as text files. Surprisingly, its fundamental properties have never been studied in depth.
We offer a simple, abstract presentation of the diff3 algorithm and investigate its behavior. Despite abundant anecdotal evidence that people find diff3’s behavior intuitive and predictable in practice, characterizing its good properties turns out to be rather delicate: a number of seemingly natural intuitions are incorrect in general. Our main result is a careful analysis of the intuition that edits to “well-separated” regions of the same document are guaranteed never to conflict.
For the entire collection see [Zbl 1134.68001].

68P05 Data structures
Full Text: DOI