1

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

My approach: 使用 N 叉树。N 取决于 XML 文件中的属性数量。Now 函数将类似于：

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) )

}

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

提前致谢

4

1 回答 1

0

你的方法是合理的。不需要将两个 xml 文档同时保存在内存中的另一种方法是为每个文档构建Merkle 树并比较它们。

比较差异是一个更开放的问题，取决于您如何定义文档之间的“差异”。例如<tag 1><tag 2><tag 3>...vs <tag 1><tag 3>，可以说这<tag 1>是唯一的共同元素，或者两者<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)

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

于 2012-09-02T22:49:23.733 回答