Cart
|
[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] Re: joining parallel markup
 On 3/14/06, Oleg A. Paraschenko <olpa@x...> wrote: > Hello Peter, > > thank you for answer. No problem, I'm surprised you haven't gotten any others. > ... > > > > > > <x><b>some <i>dummy</i></b><i> text</i></x>, > > > > > > or something like it. > > > > If you look at what you are asking for in the most general case, I > > believe the answer is not really: you want to to do generalized > > merging of graphs (which is believed to be a NP complete problem). > > I didn't know it. But trees are much simplier than graphs, so the > problem also should be much simplier. Well, yes, but XML isn't always a tree. If you're going to manage the XML by considering only simple element name, then yes, you may have a tree. However, if you've got to consider things like name spaces then you've may actually have a graph. I haven't given it much thought, but it seems that even the general case of merging non-structurally identical trees is NP complete. Consider the fact that identically named nodes may lie on different branches. The only way to evaluate whether two such nodes can in fact be merged is to look at the relationship of such nodes to every other node on the tree and decide if they match (whatever "match" might mean in this case). As such, this looks to be a classic travelling salesman traversal... > > If your domain is limited and common (eg. XHTML ) then you might get > > lucky and find some existing tools. Otherwise, I think you've got a > > good use case for rolling your own with XSLT... > > In fact, I've already draftly implemented it to support my upcoming > XTech paper on XSieve. Now I'm looking for other tools to compare them. > The best I found are LMNL and just-in-time trees, but they provide another > functionality. > Can you tell us a bit about the implementation? Is it for XHTML or more generalized? Do you handle name spaces? Do the trees have to have identical structures? The reason I ask is because we do some of this over several well defined cases (non-identical structure, but there are ways of identifying unique nodes) and as we move forward we're evolving more and more generic requirements that may eventually require us to try and evaluate structural equivalence. -- Peter Hunsberger 
|
PURCHASE STYLUS STUDIO ONLINE TODAY!Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced! 
Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|
|||||||||
