计算使两个树结构相同的最小操作

这更像是一个 CS 问题，但也是一个有趣的问题:

假设我们有两个树结构，它们或多或少重新组织了相同的节点

  1. 任何
  2. 从某种意义上说

操作顺序

  • MOVE(A, B)-将节点 A 移动到节点 B 下(包含整个子树)
  • 在节点 B 下插入一个 新的节点 N
  • DELETE (A)-删除节点 A (包含整个子树)

把一棵树变成另一棵树。

很明显，有些情况下这样的转换是不可能的，比如根 A 和子 B 到根 B 和子 A 等等)。在这种情况下，算法只需提供一个结果“ 不可能”。

更壮观的版本是对网络的概括，即当我们假设一个节点可以在树中出现多次(实际上有多个“父节点”) ，而周期是禁止的。

免责声明: 这是 没有的一个家庭作业，实际上它来自一个真正的业务问题，我发现它非常有趣，如果有人可能知道一个解决方案。

33304 次浏览
小开
最佳答案

There is not only a Wikipedia article on graph isomorphism (as Space_C0wb0y points out) but also a dedicated article on the graph isomorphism problem. It has a section Solved special cases for which polynomial-time solutions are known. Trees is one of them and it cites the following two references:

小开

You weren't clear if you were comparing abstract syntax trees for source code, XML documents interpreted as trees, or some other type of tree.

There's a number of papers that discuss comparing syntax trees and computing minimum distances by various means. The ideas should be relevant.

A good paper is Change Distilling, which tries to compare the source code for two abstract syntax trees and report a minimal difference. The paper talks about a specific method, and also briefly mentions (and provides references) to a variety of similar techniques.

Few of these algorithms are actually realized in available tools for comparing computer program source text. Our Smart Differencer is one of them; it is driven by an explicit language grammar for many languages.

小开

如果有人发现这个问题，需要为 Node.js 或者浏览器实现一些东西，我将提供一个链接和代码示例，这是我写的一个实现，你可以在 github 上找到: (https://github.com/hoonto/jqgram.git)基于现有的 PyGram Python 代码(https://github.com/Sycondaman/PyGram)。

这是一个树编辑距离 近似值算法，但它比试图找到真正的编辑距离快得多。该近似在 O (n logn)时间和 O (n)空间中执行，而真编辑距离通常是 O (n ^ 3)或 O (n ^ 2) ，使用已知的真编辑距离算法。请参阅 PQ-Gram 算法来自的学术论文: (http://www.vldb2005.org/program/paper/wed/p301-augsten.pdf)

所以使用 jqgram:

例如:

var jq = require("jqgram").jqgram;
var root1 = {
"thelabel": "a",
"thekids": [
{ "thelabel": "b",
"thekids": [
{ "thelabel": "c" },
{ "thelabel": "d" }
]},
{ "thelabel": "e" },
{ "thelabel": "f" }
]
}


var root2 = {
"name": "a",
"kiddos": [
{ "name": "b",
"kiddos": [
{ "name": "c" },
{ "name": "d" },
{ "name": "y" }
]},
{ "name": "e" },
{ "name": "x" }
]
}


jq.distance({
root: root1,
lfn: function(node){ return node.thelabel; },
cfn: function(node){ return node.thekids; }
},{
root: root2,
lfn: function(node){ return node.name; },
cfn: function(node){ return node.kiddos; }
},{ p:2, q:3 },
function(result) {
console.log(result.distance);
});

得到一个介于0和1之间的数字。越接近零，这两个树看起来就越像 jqgram。一种方法可以是使用 jqgram 从许多树中缩小到几个密切相关的树，然后利用剩下的几个树的真实编辑距离，你需要更仔细地检查，为此你可以找到 Python 实现作为参考或者 Zhang & Shasha 算法的端口，例如。

注意，lfn 和 cfn 参数指定每个树应该如何独立地确定每个树根的节点标签名称和子数组，这样您就可以做一些有趣的事情，比如将对象与浏览器 DOM 进行比较。您所需要做的就是提供这些函数以及每个根，剩下的工作将由 jqgram 完成，调用 lfn 和 cfn 提供的函数来构建树。因此，在这个意义上(在我看来)它比 PyGram 更容易使用。另外，它的 Javascript，所以使用它的客户端或服务器端！

另外，要回答关于循环检测的问题，请查看 jqgram 内部的克隆方法，那里有循环检测，但是这要归功于节点克隆的作者，从中稍微修改并包含了该片段。

小开

尽管这个问题已经很老了，我还是要在下面添加一些参考资料和算法:

  1. X-Diff: 一种有效的 XML 文档变化检测算法，Yuan Wang，davidj.DeWitt，Jin-Yi Tsai
  2. KF-diff + : 高效的 XML 文档变化检测算法
  3. 一种检测多版本变化的算法 XML 文档
  4. XML 树中的变化检测: 一项调查，Luuk Peters
  5. 树型数据结构的相似性

此外，GitHub 上还有一些库和框架(用 javascript 编写) ，它们实现了树状结构的不同，例如处理 JSON 数据或 XML 树的应用程序(例如客户端 MVC/MVVM) :

  1. React.js
  2. JSON-Patch
  3. JSON 区
  4. ObjectDiff
小开

这被称为 树对树修正问题或 树对树编辑问题。由于某种原因，大多数处理这个问题的文献都明确地涉及到比较 XML 树，因此搜索“ XML 差分算法”会得到很多结果。除了尼科斯的链接列表，我还发现了以下内容:

我也强烈推荐阅读 XML 树中的变化检测: 概述，但它是从2005年开始的，所以它提到的工具几乎都不复存在了。比较 XML 文档作为引用感知的标记有序树对我到目前为止发现的一些算法有最直观的描述(从2.1.2节开始)。

不幸的是，似乎没有多少开源代码可以做到这一点，而且这些代码并不古老。都是些过于复杂的文件。:-/


提交答案