一个基于树编辑距离及其相关问题的调查-GitHub.PDF

⼀个基于树编辑距离及其相关问题的调查 作者：Philip Bille （这是一个基于欧洲联合IST-2001-35443 IST 项目支持的 DSSCV 部分工程的文献） 摘要： 我们通过删除，插入，和重新标记节点这些简单的本地操作来调查比较标签树的问题。通过 这些操作，会引发树编辑距离,调整距离,和其包容的问题。对于这些问题我们审查了已存可 用的和现存出现的结果，详细地，用一个或多种核心算法去解决这个问题。 关键字：树匹配，编辑距离 引子介绍： 树状结构是在电脑科学里是最常见并且被充分研究了的组合结构。特别是，比较树状结构的 问题发生在好几个不同的区域里，比如计算机生物学，结构化文本数据库，图像分析，自动 定理证明，以及编译程序优化。例如，在计算机生物学中，在多种距离措施下比较树状结构 与树状结构之间的相似性被用在RNA 的第二等结构比较中。 让T 作为一个根树。如果每个节点都是从一个确定的有穷字母Σ 赋值而来的符号，我们将T 称之为一个有标号树。如果在这个T 的同级兄弟树中，存在从左到右的顺序，我们将这个T 称之为一个有序树。在本文中我们考虑了通过在标记树上做出一些简单原始的的操作去匹配 问题。如果T 是一个有序树，这些操作就可以被如下定义： 重新标记 改变在T 里一个节点v 的标签 删除 删除一个T 中父节点是v的非根节点v，将v 的子节点变成v的子节点。这个子节点 将替代v，保证原有v孩子们的左右排序。（p1 完） 图1：a) 将节点标记l1 重新标记为l2。 b) 删除标记过的l2 节点。c) 将标记为l2 的节 点插入，使其作为l1 的子节点。 插入 删除的补充。插入一个节点v 作为v在T 中的一个子节点，使v 成为v子节点的同 时保证其孩子节点的排序。 图1 解释阐明了它的操作。对于无序树来说，操作也是相似的。在这种情况下，插入和删 除的操作是在子集上而不是子序列上。我们在编辑操作上定义了三个问题。将T1 和T2 成 为标记树（有序或无序）。 树编辑距离：假设我们现有一个定义在每个编辑操作上的花销函数。T1 与T2 间的编辑脚 本S 为将T1 转化为T2 编辑序列操作。S 的花销是在S 操作中的花销总数。T1 与T2 之 间最好的编辑脚本，是T1 与T2 间最小花销的编辑脚本，同时这个花销也是这个树编辑距 离。这个树编辑距离的问题所在是计算编辑距离和其相应的编辑脚本。（p2 完） 树对齐距离：假设我们现有一个定义在一对标签上的花销函数。从T1 和T2 获得的对齐操 作A 如下。首先，我们把有空格标记的节点插入T1 与T2 ，使得他们在忽略本身标签时可 以成为同构。接着把所得到的树按顶点对齐的方式重叠，最后得到的这个对齐A 就是每个 节点由一对标签标记的树。A 的花费是A 中每对相对标签花费的总数。T1 和T2 的最好的 对齐就是最小花费的对齐，这个花费被称为T1 和T2 的对齐距离。对齐距离的问题是去计 算对齐距离和一个相应的对齐操作。 树包含：T2 包含T1 ，并且只有在T2 中删除节点才能获得T1 。树包含问题是定义T1 是否 包含在T2 内。 在这篇文章里，我们会调查这些问题中的每一个，并讨论从它们中得到的结果。仅供参考， 在第27 页的表格 1 总结了大多数的可用结果。本文包含了所有这些问题，并附带讨论一些 其它的。树编辑距离问题是最常见的问题。对齐距离对应于一种被限制了的编辑距离，而树 包含是一种包括了编辑和对齐距离问题的特殊情况。除了这些简单的关系，我们也学习研究 了一些在编辑距离上有趣的变化，致使它现在成为了一个更复杂的画面。 我们审查了有序和无序版本的问题。对于无序的情况，我们发现最终导致所有的问题一般是 NP 难题。甚至于，树编辑距离和对齐距离问题都是 MAX SNP 难题[4]。然而，多项式时 间算法却可用于各种有趣的限制和一些特殊的情况。比如说，多项式时间算法可以用在当我 们对无序树编辑距离问题施加结构保留限制，使得不相交子树被映射到不相交子树时。并且， 用这样的方法还可以有效解决恒定度树的无序对齐问题。 有序版本的问题多项式时间算法已经存在。这些都是基于动态规划的基础技术（见，比如[9, 章节 15]），其中大部分都是简单的组合算法。然而就在最近，快速矩阵乘法，一种更高 级的技术已经能成功使用在树编辑距离问题上了[8]。 这个调查用了以下方式来处理这些问题。我们对于每个问题及其变体，都检查了有序和无序 版本的结果。在大多数的情况下会包括一个对问题的正式定义，一个可用结果的比较和一个 用于取得结果的技术的描述。更重要的是，我们还会针对每个问题选择一个或多