Measuring the quality of diff algorithms: a formalization

•We study the quality of deltas produced by diff algorithms, regardless of their speed.•We present a formal way to compare the deltas and their properties.•It includes a uniform delta model and a set of quantitative metrics.•It makes it possible to compare algorithms with different aims and output formats.•We show how the metrics capture peculiarities of some widespread XML diff algorithms.

The automatic detection of differences between documents is a very common task in several domains. This paper introduces a formal way to compare diff algorithms and to analyze the deltas they produce. There is no one-fits-all definition for the quality of a delta, because it is strongly related to the application domain and the final use of the detected changes. Researchers have historically focused on minimality: reducing the size of the produced edit scripts and/or taming the computational complexity of the algorithms. Recently they started giving more relevance to the human interpretability of the deltas, designing tools that produce more readable, usable and domain-oriented results. We propose a universal delta model and a set of metrics to characterize and compare effectively deltas produced by different algorithms, in order to highlight what are the most suitable ones for use in a given task and domain.