[Date Prev][Date Next][Thread Prev][Thread Next][Author Index][Date Index][Thread Index]

*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 document are: - 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 final document. -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. --marcs

- Prev by Date:
**Version Compare/Merge: Definition of Terms** - Next by Date:
**Version Compare/Merge: The Program** - Previous by thread:
**Version Compare/Merge: Definition of Terms** - Next by thread:
**Re: Version Compare/Merge: The Algorithm** - Index(es):