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

["Johannes.Lichtenberger" <Johannes.Lichtenberger@uni-konstanz.de>]

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.

I've implemented something similar for Wikipedia. I'm splitting
Wikipedia at page-elements which denote the articles, sorting it with
Hadoop Map/Reduce (distributed sorting), because the articles as well as
the revisions are not sorted and then I provide hourly, daily and I
think monthly revisions.

I just have to replace my Diff-Shredder. But I think it would maybe
really make sense to implement or use an algorithm which can't be used
on very large instances but on some kind of splitted data, like I've
done with Wikipedia. I think most XML files are currently part of a
collection and therefore can be handled very well. Therefore I could
also use an "established" hierarichal algorithm. Currently I'm aiming
towards the algorithm described in "Change Detection in Hierarchically
Structured Information" from Chawathe.

regards,
Johannes