OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]
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.


[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]

News | XML in Industry | Calendar | XML Registry
Marketplace | Resources | MyXML.org | Sponsors | Privacy Statement

Copyright 1993-2007 XML.org. This site is hosted by OASIS