xml - 设计一个数据结构来比较两个 XML 文档

Question

给定两个 XML 文档。想出一个数据结构和代码来比较两个文档并打印文档之间的差异。 (就像标签存在于一个标签中而不存在于另一个标签中，或者标签相同但数据可能不同等等)

我的方法:使用 N 叉树。 N 取决于 XML 文件中属性的数量。现在函数将类似于:

Bool IsIdentical(tree1,tree2)
{
   if(tree1 == NULL && tree2 == NULL)return true;
   if(tree1 || tree2) return false;
    if(tree1->data == tree2->data )return true;
   else return (Isindentical(tree1->firstchild,tree2->firstchild) &&  Isindentical(tree1->secondchild,tree2->secondchild) && ........ Isindentical(tree1->nthchild,tree2->nthchild) )

}

你能告诉我我的方法是正确的还是有任何其他数据结构可以比较？如果我的方法是正确的，那么请告诉我如何产生差异。

提前致谢

Answer 1

您的方法很合理。不需要在内存中同时保存两个 xml 文档的另一种方法是构造 Merkle tree对每个文档进行比较。

比较差异是一个更开放的问题，取决于您如何定义文档之间的“差异”。例如。 <tag 1><tag 2><tag 3>...对比<tag 1><tag 3> ，可以说 <tag 1>是唯一的公共(public)元素，或两者都是 <tag 1> & <tag 3>两者都是通用的。

最保守(因此也最简单)的方法是在节点的任何子节点不同时声明差异并在此时停止递归，即生成两棵树的交集。一个实现可能看起来像这样:

class Tree:
    def __init__(self, value, children):
        self.value = value
        self.children = children

def intersect(a, b):
    if a.value != b.value:
        return None
    children = [x for x in itertools.imap(intersect, a.children, b.children) if x is not None]
    return Tree(a.value, children)

请注意，根据您的目标，此解决方案可能过于保守。