134
This is one critical difference between the “deletion” of a subsequence caused by a move
and that caused by an explicit deletion operation, and yet another way in which move is
logically distinct from copy plus deletion. However, despite the possibility that the position
of the zero-length segment representing deleted text is different than might otherwise be
expected, deletion is quite similar between Palimpsest and VTML. Deleted segments in one
sequence can be represented as corresponding to zero-length segments in the other.
Corresponding regions in that have been moved can also be represented as a correspon-
dence between subsequences just as in the case of deleted subsequences. The pairs of corre-
sponding segments will have two different sorted orders depending on whether they are ar-
ranged in sequence according to their order in one document or the other one. The
Palimpsest addresses of moved segments are different in both versions, since the Palimpsest
addresses will contain the IDs of any active moves that affect an address. The common in-
formation in these addresses makes the correspondences explicit.
Copy introduces a different relationship, one that is internal to each instance of a P-
sequence: that of duplication (perhaps also modified by other changes). Copy relationships
could potentially introduce a great deal of complexity into comparison reporting, if the rela-
tionships between all copies of a given section were to be considered in calculating the re-
sults of a comparison. Consider a single subsequence that has duplicated by copying multiple
times. If a comparison report that recognized a relationship between every sequence in ei-
ther document that shared data, then each copy in one document would have to be related
to each copy in the other document. This is bad. It is bad not only because comparison re-
ports should not have space requirements of O(n
2
)for a document withncopies, but because
the information in question is almost totally useless, since it is implicit in the internal copy
relationships of each document. Therefore, the only sensible correspondence between copy
results in two versions is the one that results when the addresses being compared are identi-
cal.
This is one critical difference between the “deletion” of a subsequence caused by a move
and that caused by an explicit deletion operation, and yet another way in which move is
logically distinct from copy plus deletion. However, despite the possibility that the position
of the zero-length segment representing deleted text is different than might otherwise be
expected, deletion is quite similar between Palimpsest and VTML. Deleted segments in one
sequence can be represented as corresponding to zero-length segments in the other.
Corresponding regions in that have been moved can also be represented as a correspon-
dence between subsequences just as in the case of deleted subsequences. The pairs of corre-
sponding segments will have two different sorted orders depending on whether they are ar-
ranged in sequence according to their order in one document or the other one. The
Palimpsest addresses of moved segments are different in both versions, since the Palimpsest
addresses will contain the IDs of any active moves that affect an address. The common in-
formation in these addresses makes the correspondences explicit.
Copy introduces a different relationship, one that is internal to each instance of a P-
sequence: that of duplication (perhaps also modified by other changes). Copy relationships
could potentially introduce a great deal of complexity into comparison reporting, if the rela-
tionships between all copies of a given section were to be considered in calculating the re-
sults of a comparison. Consider a single subsequence that has duplicated by copying multiple
times. If a comparison report that recognized a relationship between every sequence in ei-
ther document that shared data, then each copy in one document would have to be related
to each copy in the other document. This is bad. It is bad not only because comparison re-
ports should not have space requirements of O(n
2
)for a document withncopies, but because
the information in question is almost totally useless, since it is implicit in the internal copy
relationships of each document. Therefore, the only sensible correspondence between copy
results in two versions is the one that results when the addresses being compared are identi-
cal.
