apted 1.0.3

信息

这是apted算法的python实现， 计算树编辑距离的最新解决方案[1,2]， 它取代了rted算法[3]。

它是原始Java实现的一个端口，可在 https://github.com/DatabaseGroup/apted。在港口期间，有些变化 是为了减少对称操作的重复 看起来更像是Python。

有关apted的更多信息，请访问以下网站 http://tree-edit-distance.dbresearch.uni-salzburg.at/

引用apted

如果你想在出版物中引用apted，请引用[1]和[2]。

许可证

源代码在根目录中的mit许可证下发布 项目的目录和每个源文件的头中。

输入

目前，我们只支持输入的所谓括号符号 例如，树的编码{A{B{X}{Y}{F}}{C}}对应于 以下树：

    A
   / \
  B   C
 /|\
X Y F

输出

我们的工具计算两个输出：-树编辑distance值- 将源树转换为目标树的最低成本。 -树编辑映射-对应于 树编辑距离值。未映射的节点将被删除 （源树）或插入（目标树）。

开始

这个版本在Python2.7、3.4、3.5和3.6上进行了测试。

首先，使用pip安装它：

pip install apted

如果要比较树{a{b}{c}和{a{b{d}}，请运行：

python -m apted -t {a{b}{c}} {a{b{d}}} -mv

输出为：

distance:             2
runtime:              0.000270843505859
{a{b}{c}} -> {a{b{d}}}
{c} -> None
{b} -> {b{d}}
None -> {d}

有关运行选项的详细信息，请运行

python -m apted -h

自定义

可以将算法自定义为使用自定义树运行 不同于简单字符串或自定义数据结构的标签。 此外，还可以自定义它以使用更复杂的 成本模型比单位成本。

对于自定义算法，可以创建自定义config类：

fromaptedimportAPTED,ConfigclassCustomConfig(Config):defrename(self,node1,node2):"""Compares attribute .value of trees"""return1ifnode1.value!=node2.valueelse0defchildren(self,node):"""Get left and right children of binary tree"""return[xforxin(node.left,node.right)ifx]apted=APTED(tree1,tree2,CustomConfig())ted=apted.compute_edit_distance()mapping=apted.compute_edit_mapping()

默认情况下，包含的config类考虑具有atribute的树 name作为标签，atributechildren作为从左到右的子项 预定。

除了config类之外，我们还提供 pereditionoperationconfig类，它允许您为 每次操作：

fromaptedimportAPTED,PerEditOperationConfigapted=APTED(tree1,tree2,PerEditOperationConfig(.4,.4,.6))ted=apted.compute_edit_distance()mapping=apted.compute_edit_mapping()

如果apted的主要用途是获取映射，则可以 配置算法以在 执行。为此，我们提供了一个函数meta_chained_config， 它修改现有的：

fromaptedimportAPTED,PerEditOperationConfig,meta_chained_confignew_config=meta_chained_config(PerEditOperationConfig)apted=APTED(tree1,tree2,new_config(.4,.4,.6))ted=apted.compute_edit_distance()mapping=apted.compute_edit_mapping()

注意，这种方法使用更多的内存，我们没有评估 对于具有较大规模的映射，其速度比原算法快 树。映射测试的执行时间与 原始算法。

贡献

请随意将请求重新提交到此存储库。

代码库遵循PEP8惯例。不过，这并不太严格。 例如，可以有超过79行的行 但尽量不要过多。

请在更改期间运行python test.py，以确保 一切正常。还需要使用coverage.py来检查 测试覆盖率：coverage run test.py。

原创作者

• Mateusz Pawlik
• 尼古拉斯·奥格斯顿

实现作者

• 乔·菲利佩·皮门特尔

参考文献

1. M.Pawlik和N.Augsten。树编辑距离：健壮和内存- 高效。信息系统56。2016年。
2. M.Pawlik和N.Augsten。树编辑的有效计算 距离。数据库系统上的acm事务项目（TODS）40（1）。2015年。
3. M.Pawlik和N.Augsten。rted:树编辑的健壮算法 距离。PVLDB 5（4）。2011年。