[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: XML diff tool / algorithm

• From: "Johannes.Lichtenberger" <Johannes.Lichtenberger@uni-konstanz.de>
• To: xml-dev@lists.xml.org
• Date: Tue, 28 Jun 2011 15:50:31 +0200

On 06/28/2011 12:37 PM, David Lee wrote:
> This is an interesting use case.  I have not personally seen anything that can handle what you're asking 'ideally'
> (although I've used several diff tools).
> In your case you need a tradeoff between ideal representation and time and space.
> 
> I suggest maybe a compromise, depending on how your DB handles fragmentation.   A lot of real-world XML, especially the big ones, are really large lists or heterogeneous collections that can be efficiently split at the root+1 level nodes.
> If you split documents at  this level (or some customizable level) then do a binary compare, or MD5 of each fragment (or however your nodes are represented) you may find an efficient algorithm which performs reasonably in time & space for a useful set of cases.
> Now finding inserts/deletes may be harder. - might require multiple passes.  But this approach would turn the diff into a linear instead of hierarchical diff, which has many known/published algorithms.  Certainly not perfect but may be vastly better then nothing.

Hm, another algorithm would be the one used in XyDiff, which makes use
of hash-signatures, which we have implemented as well, but I think it
doesn't produce "intuitive" diffs and furthermore they aren't minimal.

regards,
Johannes

• References:
  • XML diff tool / algorithm
    • From: "Johannes.Lichtenberger" <Johannes.Lichtenberger@uni-konstanz.de>
  • Re: XML diff tool / algorithm
    • From: Michael Kay <mike@saxonica.com>
  • Re: XML diff tool / algorithm
    • From: "Johannes.Lichtenberger" <Johannes.Lichtenberger@uni-konstanz.de>
  • RE: XML diff tool / algorithm
    • From: "David Lee" <dlee@calldei.com>