[Date Prev][Date Next][Thread Prev][Thread Next][Author Index][Date Index][Thread Index]
Version Compare/Merge: The Algorithm
- To: <xanatech>
- Subject: Version Compare/Merge: The Algorithm
- From: Marc Stiegler <marcs>
- Date: Sat, 7 Apr 90 23:09:22 PDT
All right, we're ready to program. The steps involved
in transforming the original document into the final
- Create a working document composed of movement runs.
- If the working document contains only a single
movement run, we're done: only insertions and deletions are
needed to transform the one document to the other.
- Repeat the following cycle until the working document
is composed of a single composite run.
-If there is are two runs that are properly
adjacent, meld them together into a composite run
- If there are no properly adjacent runs, look
for a reversed sequence. If there is a
reversed sequence, treat that sequence as a working
document and rearrange the sequence using the anchor
method (described below).
- If there are neither properly adjacent runs
nor reversed sequences, use the anchor method to select
and move a run.
-That's all, folks. Your document is transformed.
The only remaining question is, what is the anchor
method? Here goes:
-Find the current anchor for the working document.
-Compare the sizes of the 2 runs in the working
document which would be neighbors to the anchor in the
-Move the smaller of those 2 runs to be
properly adjacent to the anchor.
Wasn't that fun?
This algorithm has the following properties:
Unreversing reversed sequences tends to localize
motion--rather than moving each individual run in the
sequence to a distant location, you shuffle them all
locally and then move the collection as a single composite
run. The anchor method, meanwhile, enforces the movement of
small objects a long distance in preference to moving large
objects small distances. Note that the anchor method, when
used by itself, never produces nested motion; all nesting
arises from local reverses that then get moved again.
This algorithm does NOT guarantee a minimum total count
of movements. Therefore, it does not guarantees a
heuristically optimal result. However, you'll have to work
at it to construct a counterexample...at least, you'll have
to work to construct a counterexample that you yourself
understand (a random stream of sufficient length will
eventually supply the counterexample...but how well would
you, smart human, do at unraveling it yourself? :-)
The failures of this algorithm to create heuristically
optimal solutions are discussed in the section on
deficiencies coming up later.