Cart
[Home] [By Thread] [By Date] [Recent Entries]
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
[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] |
