如何检查两个Xml树的相似性(C#中的树编辑距离)

Question

在C#应用程序中,我需要检查算法的输出,该算法是针对另一个XML树的XML树,以查看它们是如何相似的.(节点顺序很重要,但结构(嵌套节点),节点名称更重要).也许数量adds,removes并moves在一些"发生树编辑距离 "的算法是一个很好的指标.但答案是更多Java或Python包.

所以,我尝试使用XMLDiffPatch,当算法类型设置为时,它运行良好Precise.但不好的是,它只是生成一个DiffGram需要分析的文件来查找操作数.此外,它非常多,并OutOfRangeException为一些XML树生成.为了我的目的,我也找不到更好的软件包.Net.有一些Xml差异包但可能没有或很少有Tree Edit Distance.

一个例子:

<A>
  <B>
    <C></C>
    <D></D>
    <E>
       <F>
       </F>
    </E>
  </B>
</A>

至:

<A>      
    <C></C>
    <D></D>
    <G></G>
</A>

到第一个XML转换为第二,你需要删除E和F(2和成本),那么你需要删除B(而不是其子树)和补充G.然后总费用是4.

所以,正如我在这里所知,我不应该要求包和工具,我要求一个简单的算法或(.Net中的树编辑距离算法)来做到这一点.这是我自己的算法,用于检查相似性并忽略次要差异(具有一个或几个嵌套节点),但它是非常主要的,仅用于起点:

public int XMLCompare(XmlNode primary, XmlNode secondary)
{
    int x = 0;
    if (secondary == null || primary == null)
        return 1;

    if (secondary.ChildNodes.Count == 1 && primary.ChildNodes.Count > 1)
    {
        x += XMLCompare(primary, secondary.ChildNodes[0]);
    }
    else if (secondary.ChildNodes.Count > 1 && primary.ChildNodes.Count == 1)
    {
        x += XMLCompare(primary.ChildNodes[0], secondary);
    }
    else
    {
        if (primary.Name.ToLower() != secondary.Name.ToLower())
            x = 1;
        int m = Math.Max(primary.ChildNodes.Count, secondary.ChildNodes.Count);
        for (int i = 0; i < m  i++)
        {
            x += XMLCompare(
            i < primary.ChildNodes.Count ? primary.ChildNodes[i] : null,  
            i < secondary.ChildNodes.Count ? secondary.ChildNodes[i] : null);

        }
    }

    return x;
}

Answer 1

微软为此提供了一个 API。检查这个。这可能是旧的 dll 参考，但仅供您参考，您需要使用类似的东西。C：\ Windows \程序集\ GAC \ XmlDiffPatch \ 1.0.8.28__b03f5f7f11d50a3a \ XmlDiffPatch.dll