4

I need to perform a comparison between two XML documents. I've been looking at a lot of different xml-diffing tools typically mentioned here on Stack Overflow, but my needs are, of course, very peculiar and so they don't really fit. In short, I need to compare not the documents as a whole, but rather the element contents (While taking order into account), and I need a very specific output format rather than a traditional diff patch.

Please excuse this volume of text, but I find it difficult to explain it shorter.

First, my limitations

The solution must be Java-based, or integrateable with a command-line java application. It must also be free, because I'm not allowed to spend "real money" on this, only my work time (but not too much of course; I have a deadline looming over me) ... sounds familiar? Lastly, my goal is not a traditional diff patch result but a non-straightforward combination of both source files.

Second, a description of my data

Each document contains nodes of type text or section; texts are simple strings but sections can contain both text and more sections (they also have a name, given as an attribute). Furthermore, each node is tagged with revision information.

Here's a sample document. Note that for brevity, this appears to be a list; in actuality it's more prose-like -- that is to say, element order is very important.

<document diff="=" revision="1">
  <text diff="=" revision="1">Apples</text>
  <text diff="=" revision="1">Chxrries</text>
  <section diff="=" revision="1" name="Blue ones">
    <text diff="=" revision="1">Grapes</text>
    <section diff="=" revision="1" name="More">
      <text diff="=" revision="1">Blueberries</text>
    </section>
    <text diff="=" revision="1">Oranges</text>
  </section>
</document>

This needs to be compared to a new version, which contains changes but no revision information (yet!). In this example, I've fixed a typo in the 2nd element, and I've moved another element, but there could be much more extensive changes, such as addition or deletion of entire sections.

<document>
  <text>Apples</text>
  <text>Oranges</text>
  <text>Cherries</text>
  <section name="Blue ones">
    <text>Grapes</text>
    <section name="More">
      <text>Blueberries</text>
    </section>
  </section>
</document>

The goal is to create a third XML document with all information. Note that the diff tags of the affected elements have been changed ("*" represents a change within the element) and their revision numbers have been bumped; unchanged elements keep their old revision info.

<document diff="*" revision="2">
  <text diff="=" revision="1">Apples</text>
  <text diff="+" revision="2">Oranges</text>
  <text diff="-" revision="2">Chxrries</text>
  <text diff="+" revision="2">Cherries</text>
  <sectio diff="*" revision="1"n name="Blue ones">
    <text diff="=" revision="1">Grapes</text>
    <section diff="=" revision="1" name="More">
      <text diff="=" revision="1">Blueberries</text>
    </section>
    <text diff="-" revision="2">Oranges</text>
  </section>
</document>

The result, then, is not a diff patch, but a full document with updated revision information.

Third, what I do have working -- and my problem

I have most of this working, using a custom java function that does line-by-line comparison -- except that it fails in one particular use case, namely that when the old version contains a particular text more than once, and the non-last of them is changed in the new version. This would "trick" the comparator into matching the old-version text with the following new-version text, instead of recognising the one-text change for what it is. Although the result is technically correct, the added "noise" of unnecessary additions and removals mask this fact, and for humans it's plainly a mess to look at (and, incidentally, this markup is intended for human readability). Now, exactly because of my line-by-line approach, I find this very difficult to fix.

Here's an example of a use case that tricks my code. First, a simple fruit basket:

<document diff="=" revision="1">
  <text diff="=" revision="1">Apples</text>
  <text diff="=" revision="1">Oranges</text>
  <text diff="=" revision="1">Apples</text>
  <text diff="=" revision="1">Cherries</text>
  <text diff="=" revision="1">Apples</text>
</document>

Now, let's alter the 2nd "Apples" item:

<document>
  <text>Apples</text>
  <text>Oranges</text>
  <text>Bananas</text>   <--- I've only changed this
  <text>Cherries</text>
  <text>Apples</text>
  <text>Grapes</text>
</document>

The result, incorrectly, becomes:

<document diff="*" revision="2">
  <text diff="=" revision="1">Apples</text>
  <text diff="=" revision="1">Oranges</text>
  <text diff="+" revision="2">Bananas</text>   <--- Addition, okay
  <text diff="+" revision="2">Cherries</text>   <--- Incorrectly added
  <text diff="=" revision="1">Apples</text>   <--- Incorrectly matches the next occurrence
  <text diff="-" revision="2">Cherries</text>   <--- Incorrectly removed
  <text diff="-" revision="2">Apples</text>   <--- Incorrectly removed
  <text diff="=" revision="1">Grapes</text>   <--- Back on track, after the next occurrence of the changed element
</document>

True, I could probably alleviate this issue but implementing some form of look-ahead, but I wouldn't be able to tell how far to look ahead, and it therefore sounds like a very messy work-around rather than a true solution.

...so in closing, I'm desperate for an xml diff tool that allows me to analyse the data content and create this very particular output. Either that, or any tips to how I could avoid this particular pitfall.

If you have any suggestions, or questions for elaboration, I'm very eager to hear from you.


This is a re-statement of a previous question. Unfortunately, I'm not able to offer any bounties to advertise it, but hopefully my new explanation here will fare better.


For what it's worth, here's my algorithm, which does not seem to be listed on the DiffAlgorithm page that @LarsH linked to:

Compare two lists: call them lL and lR for the left- and right-hand sides. Create two "primary" pointers iL and iR and set them to the first elements of each list. For the loop, use these primary pointers to set primary elements eL and eR, so that eL=lL(iL) and eR=lR(iR). Compare eL and eR. If eL matches eR, we can copy eL to the result as a match and advance both primary pointers by one slot. If eL and eR do not match, create a secondary pointer (iR2), initialise it to the slot after iR (iR2=iR+1) and scan the remainder of lR (setting eR2=lR(iR2) as we go). If eL is not matched in the remainder of lR, eL must have been deleted, and we can add eL to the result as a deletion and advance only the primary pointer iL (so that the next comparison will compare the next eL with the same eR). If eL is found to match eR2 (at position iR2>iR), then all elements in the range [iR,iR2[ must have been added. We can then add each element in that range of lR to the result as an addition, and set iR=iR2. We can also add the element eL to the result as a match (because it was matched at eR2), and finally repeat the comparison at the new primary pointer positions. Do all this while iterating over the shorter of the two lists; then, add the remainder of lL as deletions or add the remainder of lR as additions.

2 Answers 2

1

Turns out, my need had no solution at the time! Meanwhile, I've developed my own xml-diff routine that is specific to my problem, so I ended up with a working solution.

Then, in late 2011, this was published: Slashdot: Researchers Expanding Diff, Grep Unix Tools

Dartmouth computer scientists presented variants of the grep and diff Unix command line utilities that can handle more complex types of data. The new programs, called Context-Free Grep and Hierarchical Diff, will provide the ability to parse blocks of data rather than single lines. The research has been funded in part by Google and the U.S. Energy Department.

0

+1 good question. I can't think of a workaround other than a lookahead, but you may find something in the diff algorithm literature (check http://c2.com/cgi/wiki?DiffAlgorithm). Is the algorithm you are using based on one that's described on that page? If not, you may want to try the algorithm described there (Myers 1986). It seems to be designed to optimize the number of diff operations, within a limit based on the size of the input.

I tried Oxygen's XML diff program (after stripping the revision attributes), and didn't get better results than yours, so I doubt the solution is trivial.

1
  • Thanks for the +1, @LarsH. I've posted an abstract of my algorithm above; it appears to be different from the ones listed on your page. I've already taken a peek at the Myers paper, and agree that it's "extremely dense reading". I'm afraid I don't have "around a month of study to fully understand", so I guess I'll try to patch my algo with some look-ahead.
    – KlaymenDK
    Jun 27, 2011 at 13:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.