相关疑难解决方法(0)

这更像是一个CS问题,但却是一个有趣的问题:

假设我们有2个树结构,其中重组的节点或多或少相同.你怎么找到的

1. 任何
2. 在某种意义上是最小的

操作顺序

• MOVE(A, B) - 在节点B下移动节点A(使用整个子树)
• INSERT(N, B)- 在节点B下插入新节点N.
• DELETE (A) - 删除节点A(使用整个子树)

将一棵树转换为另一棵树.

显然可能存在这样的转变是不可能的情况,小孩子是带有孩子B的根A到带有孩子A的根B等等.在这种情况下,算法将简单地传递" 不可能 " 的结果.

更为壮观的版本是网络的概括,即当我们假设一个节点可以在树中多次出现(实际上有多个"父")时,禁止循环.

免责声明:这不是一个功课,实际上它来自一个真正的业务问题,我发现很有趣,想知道是否有人可能知道一个解决方案.

在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 …