Re: [xml-dev] XML diff tool / algorithm

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