This paper presents an ongoing research on the qualitative evaluation of di algorithms and the deltas they produce. Our analysis focuses on qualities that are seldom studied: instead of evaluating the speed or the memory requirements of an algorithm, we focus on how much natural, compact and t for use in a certain context the produced deltas are. This analysis started as a way to measure the naturalness of the deltas produced by JNDi , a di algorithm for XML-based literary documents. The deltas were considered natural if they expressed the changes in a way similar to how a human expert would do, an analysis that could only be carried out manually. Our research e orts have expanded into the de nition of a set of metrics that are, at the same time, more abstract (thus they capture a wider range of information about the delta) and completely objective (so they can be computed by automatic tools without human supervision).
algorithms and deltas The di algorithms have been widely studied in literature and applied to very different domains (source code revision, software engineering, collaborative editing, law making, etc.) and data structures (plain text, trees, graphs, ontologies, etc.). Their output is usually expressed as edit script s, also called deltas or patches. A delta is a set of operations that can be applied to the older document in order to obtain the newer one. Deltas are hardly ever unique, since multiple di erent sequences of operations can be devised, all capable of generating the newer document from the older one.
Each algorithm uses its own strategies and data-structures to calculate the \best" delta. Some of them are very fast, others use a limited amount of memory, others are specialized for use in a speci c domain and data format. Surprisingly enough, the evaluation of the quality of the deltas has received little attention.
The historical reason is that most algorithms have been proposed by the database community focusing more on e ciency rather than quality. Another reason is that the produced deltas are not easily comparable: not only each algorithm choose di erent sequences of changes, but they even use their own internal model and recognize their own set of changes. For example, some algorithms detect moves while others do not, or the same name is used for di erent operations. Given this degree of heterogeneity, it is hard to evaluate the quality of these algorithms in an automatic and objective way.
Nonetheless, we believe that such an evaluation is essential for the nal users and can e ectively support them in selecting the best algorithm for their needs.
It is important, for instance, that the operations contained in a delta re ect meaningful changes to the documents, i.e., the detected changes are as close as possible to the editing operations that were actually performed by the author on the original document. Our research started by studying a way to make this quality more explicit. 2
A
rst manual approach: naturalness in JNDi
In [
In relation to naturalness, in [
In our view, naturalness is a property connected to the human application and interpretation of document editing, i.e., it can be fully validated only by people that know the editing process. That is why we started researching into other more objective ways to indirectly measure the naturalness.
The rst approximation was to examine how close was the generated delta to the description of the changes given by an expert. The rst step to calculate such approximation is to create a gold standard (an ideal edit script) by comparing pairs of document versions, both visually and structurally. The second step is to identify clusters of changes in the delta of each algorithm that correspond to the changes in the gold standard, and to assign a similarity value to each one, depending on a number of parameters. Most of these operations are manual: we manually generate the gold standard, then we manually link the changes in the delta to the clusters, dealing with di erent output formats.
The key part of the second step consists in assigning a score to each cluster of edit operations to assess its naturalness, taking into account these aspects: 1. Minimality of the cluster : we consider a cluster composed of a few sophisticated changes more natural than a cluster composed of many basic changes. 2. Minimality of the number of nodes : we rate as more natural clusters that a ect fewer nodes, either elements or text characters: this penalizes imprecise edit scripts and rewards scripts in which only the needed nodes are modi ed. 3. Minimality of the length of text nodes : we regard as more natural the edit scripts in which the basic unit for text modi cations are the single words, not whole paragraphs; the insertion/removal of big chunks of text where only few characters have been changed is considered verbose and not natural. The score of the i-th cluster of the delta is calculated as the inverse of a weighted sum of the above mentioned parameters. Further coe cients me, mn and mc are needed to balance the weights (because, for instance, the number of characters is on average much higher than the number of edit actions or of a ected nodes). nat ( ; i) = (we me
mn
mc
Eventually, after various experiments on real-world documents, we instantiated the general formula as: nat( ; i) = (0:2
EDIT Si + 0:1
N ODESi + 0:0077
3
Automated analysis The JNDi naturalness formula as presented has two main issues. First, its evaluation is impossible to automate as it requires the identi cation of a gold standard for each cluster of each delta and the ability to match the generated changes to the corresponding changes in the gold standard. Second, di erent users have di erent requests and expectations for a di system and a single metric is not enough to show how well these requests are matched. Not only these requests are di erent, often they also con ict with each other: for example in certain cases a cursory summary of what has changed is enough, while in others an extreme level of detail is needed.
The idea of measuring objective indicators on the delta, on the other hand, is promising. The same idea of naturalness could be generalized and seen as one of the many qualities of a delta.
In order to de ne metrics for analyzing deltas under multiple aspects and in an objective way, one has to rely on properties that can be extracted and elaborated by automatic tools without resorting to human evaluations. To reach this goal we elaborated a universal delta model that works on linear texts, trees and graphs. This universal delta model is based on the concept of iterative recognition of more meaningful changes starting from simple changes. Using this model we extracted the properties shown in table 1.
By themselves, the values of these properties say little about the various qualities of the delta. However, once these properties have been extracted they form the base upon which we build several metrics, each of which focused on a single aspect of the analyzed delta. For instance the measure of how much redundant information has been included in a delta (the so called conciseness metric) uses two properties of deltas: the number of modi ed elements and the number of referenced-yet-not-modi ed elements. We derived four key metrics, described in table 2.
Preliminary experiments showed that these metrics are useful to characterize
di algorithms. In particular, we compared the deltas produced by three
wellknown XML di tools (JNDi [
De nition The total number of changes of which a change is composed of,
including itself.
The maximum number of encapsulation layers that must be
crossed to reach an atomic change.
The number of distinct changes encapsulated inside the change.
The number of distinct pieces of information that are included as
part of the change or of the encapsulated changes.
The minimum number of pieces of information that must be
modi ed by the change to ful ll its purpose.
The number of changes that are not encapsulated in any other
change.
Table 1. Properties of changes and deltas algorithms to detect many localized small changes instead of fewer big changes, or to aggregate changes, or to produce verbose output. In the future we plan to further investigate new metrics (together with their related qualities) and new applications to discover information about the editing process of documents.