Python 编辑距离

版权所有 (C) 2019-2021 - Benjamin Paassen
机器学习研究组
卓越认知交互技术中心 (CITEC)
比勒费尔德大学

该程序是免费软件；您可以根据自由软件基金会发布的 GNU 通用公共许可条款重新分发和/或修改它；许可证的第 3 版，或（由您选择）任何更高版本。

分发此程序的目的是希望它有用，但不提供任何保证；甚至没有对适销性或特定用途适用性的默示保证。有关详细信息，请参阅 GNU 通用公共许可证。

您应该已经收到了一份 GNU 通用公共许可证的副本以及该程序；如果没有，请参阅http://www.gnu.org/licenses/。

介绍

该库包含用于任意节点类型的序列和树的几种编辑距离和对齐算法。此外，该库包含每个算法的多个回溯机制，以便于更详细的解释和后续处理。最后，该库提供了嵌入编辑距离学习的参考实现（BEDL；Paaßen 等人，2018 年），它使用户能够学习编辑距离参数，而不是手动指定它们。

有关如何使用该库的信息，请参阅快速入门指南，并参阅下面的列表以获取随附算法的完整列表。详细的 API 文档可在readthedocs.org上找到。

如果您在学术工作中使用此库，请引用：

• Paaßen, B., Mokbel, B. 和 Hammer, B. (2015)。智能辅导系统的自适应序列差异测量工具箱。在 OC Santos、JG Boticario、C. Romero、M. Pechenizkiy、A. Merceron、P. Mitros、JM Luna 等人。（编辑），第八届教育数据挖掘国际会议论文集（第 632-632 页）。国际教育数据挖掘协会。（链接）

该库历史上基于其 Java 版本 TCS Alignment Toolbox。

安装

这个包在pypi上作为edist. 你可以通过安装它

pip install edist

如果你想从源代码构建这个项目，你需要先安装 cython，然后在这个目录中执行以下命令：

python3 cython_setup.py build_ext --inplace
cp *so edist/.

快速入门指南

我们的演示笔记本中有多个示例案例。尤其是：

• sed_demo.ipynb说明 Levenshtein 距离 (Levenshtein, 1965) 和仿射编辑距离 ( Gotoh, 1982 ) 以及它的回溯，
• dtw_demo.ipynb说明动态时间扭曲 ( Vintsyuk, 1968 ) 及其回溯和加速措施，
• ted_demo.ipynb说明了树编辑距离（Zhang 和 Shasha，1989 年）以及它的回溯和对编辑功能的支持，以及
• bedl_demo.ipynb说明了嵌入编辑远程学习（Paaßen 等人，2018 年）。

一般来说，应用这个库的工作方式如下。首先，您选择最适合您的数据和设置的编辑距离函数（有关所有可用函数的概述，请参见下文）。假设您的函数被调用distfun。x然后，您可以计算两个列表/树和yvia之间的距离distfun(x, y)。如果您希望计算整个列表/树数据集的所有成对距离的矩阵X，则可以multiprocess按如下方式使用该模块。

from edist.multiprocess import pairwise_distances_symmetric
D = pairwise_distances_symmetric(X, distfun)

如果您希望计算一个数据集X和另一个数据集之间所有成对距离的矩阵Y，可以使用以下函数。

from edist.multiprocess import pairwise_distances
D = pairwise_distances(X, Y, distfun)

如果您希望使用自定义局部距离函数delta，您可以将其作为附加参数提供给它distfun本身、to pairwise_distances_symmetric或 to pairwise_distances。

如果您希望计算两个列表/树之间的最佳对齐x 并y根据distfun，您可以使用函数 distfun_backtrace(x, y). 请注意，在多个可能的最佳对齐的情况下，此函数将始终尽可能早地返回使用替换的选项。如果您希望对随机最优对齐进行采样，则可以使用distfun_backtrace_stochastic(x, y). 不幸的是，枚举整组协同最优对齐是不可行的，因为这组可能是指数级的。x然而，可以通过描述每个节点与 中的每个节点配对的概率来简明地描述协同最优对齐的分布y。该概率矩阵由函数计算distfun_backtrace_matrix(x, y)并遵循Paaßen (2018)开发的前向后向算法。

算法和函数列表

此库中包含以下编辑距离算法和函数。

• Levenshtein 距离/序列编辑距离（Levenshtein，1965）：
  • edist.sed.standard_sed(x, y)用于序列之间的编辑距离计算，每次替换、删除x和y插入的成本为 1。
  • edist.sed.sed_string(x, y)相同，但专为字符串设计，因此速度更快（〜因子 3）。
  • edist.sed.standard_sed_backtrace(x, y)用于标准编辑距离的回溯。
  • edist.sed.standard_sed_backtrace_stochastic(x, y)同样，但返回一个随机的最佳对齐而不是一个固定的对齐。
  • edist.sed.standard_sed_backtrace_matrix(x, y)x相同，但返回和元素之间所有配对的概率分布y。
  • edist.sed.sed(x, y, delta)用于使用自定义元素距离函数进行编辑距离计算delta。
  • edist.sed.sed_backtrace(x, y, delta)使用自定义元素距离函数回溯编辑距离delta。
  • edist.sed.sed_backtrace_stochastic(x, y, delta)同样，但返回一个随机的最佳对齐而不是一个固定的对齐。
  • edist.sed.sed_backtrace_matrix(x, y, delta)x相同，但返回和元素之间所有配对的概率分布y。
• 动态时间扭曲距离（DTW；Vintsyuk，1968 年）：
  • edist.dtw.dtw_numeric(x, y)用于两个时间序列x和之间的 DTW 计算y，每个都以双精度数组的形式给出。
  • edist.dtw.dtw_manhattan(x, y)用于两个时间序列x和之间的 DTW 计算y，每个都作为双矩阵给出。两帧之间的距离定义为曼哈顿距离。
  • edist.dtw.dtw_euclidean(x, y)用于两个时间序列x和之间的 DTW 计算y，每个都作为双矩阵给出。两帧之间的距离定义为欧几里得距离。
  • edist.dtw.dtw_string(x, y)用于两个字符串之间的 DTW 计算 x和y.
  • edist.dtw.dtw(x, y, delta)用于两个任意序列之间的 DTW 计算x并y使用自定义元素距离函数delta。
  • edist.dtw.dtw_backtrace(x, y, delta)用于带有自定义元素距离函数的 DTW 回溯delta。
  • edist.dtw.dtw_backtrace_stochastic(x, y, delta)同样，但返回一个随机的最佳对齐而不是一个固定的对齐。
  • edist.dtw.dtw_backtrace_matrix(x, y, delta)x相同，但返回和元素之间所有配对的概率分布y。
• 仿射编辑距离（Gotoh，1982）：
  • edist.aed.aed(x, y, rep, gap, skip)对于 两个 任意 序列 之间 的 仿射 编辑 距离 计算x,y其中 每个 帧 替换 用 函数 评分rep, 每个 删除 和 插入 都 用 函数 评分gap, 每个 删除 和 插入 扩展 都 用 函数 评分skip.
  • edist.aed.aed_backtrace(x, y, rep, gap, skip)用于使用替换成本函数rep、删除/插入成本函数gap和间隙扩展成本函数 对仿射编辑距离进行回溯skip。
  • edist.aed.aed_backtrace_stochastic(x, y, delta)同样，但返回一个随机的最佳对齐而不是一个固定的对齐。
  • edist.aed.aed_backtrace_matrix(x, y, delta)x相同，但返回和元素之间所有配对的概率分布y。
• 树编辑距离（TED；Zhang 和 Shasha，1989 年）：
  • edist.ted.standard_ted(x_nodes, x_adj, y_nodes, y_adj)x用于树和之间的编辑距离计算y，它们都以节点列表/邻接列表格式给出。两个列表都应该是深度优先搜索顺序，例如，树 a(b, c) 应该表示为两个列表['a', 'b', 'c']和[[1, 2], [], []]。替换、删除和插入的成本固定为 1。
  • edist.ted.standard_ted_backtrace(x_nodes, x_adj, y_nodes, y_adj) 用于树编辑距离的回溯。
  • edist.sed.standard_sed_backtrace_matrix(x_nodes, x_adj, y_nodes, y_adj)x相同，但返回和 元素之间所有配对的概率分布y。
  • edist.ted.ted(x_nodes, x_adj, y_nodes, delta)使用自定义节点距离函数进行树编辑距离计算delta。
  • edist.ted.ted_backtrace(x_nodes, x_adj, y_nodes, delta)用于使用自定义元素距离函数回溯树编辑距离delta。
  • edist.ted.ted_backtrace_matrix(x_nodes, x_adj, y_nodes, delta)x相同，但返回和元素之间所有配对的概率分布y。
• 无序树编辑距离（UTED；Zhang，1996）：
  • edist.uted.uted(x_nodes, x_adj, y_nodes, y_adj, delta)x用于树和之间的编辑距离计算y，它们都以节点列表/邻接列表格式给出。两个列表都应该是深度优先搜索顺序，例如，树 a(b, c) 应该表示为两个列表['a', 'b', 'c']和[[1, 2], [], []]。
  • edist.uted.uted_backtrace(x_nodes, x_adj, y_nodes, y_adj, delta)用于使用（可选）自定义元素距离函数回溯无序树编辑距离delta。
• 设置编辑距离（SetED；未发表，但使用Kuhn 的匈牙利算法，1955 年为核心）：
  • edist.seted.standard_seted(x, y)x用于集合和之间的集合编辑距离计算y，为方便起见，它们都以列表形式给出。替换、删除和插入的成本固定为 1。
  • edist.seted.standard_seted_backtrace(x, y)用于回溯设置的编辑距离。
  • edist.seted.seted(x, y, delta)使用自定义元素距离函数设置编辑距离计算delta。
  • edist.seted.seted_backtrace(x, y, delta)使用自定义元素距离函数回溯设置的编辑距离delta。

此外，该库包含一些帮助模块，即：

• edist.adp包含计算可以由常规语法定义的任意序列编辑距离的函数。这是基于Paaßen、Mokbel 和 Hammer ( 2016 ) 应用的代数动态规划框架（ADP； Giegerich、Meyer 和 Steffen，2004年）。尤其是：
  • edist.adp.edit_distance(x, y, grammar, deltas)计算由正则文法定义的序列编辑距离以及序列和之间grammar的成本函数 ，deltasxy
  • edist.adp.backtrace(x, y, grammar, deltas)计算所述编辑距离的回溯，
  • edist.adp.backtrace_stochastic(x, y, grammar, deltas)做同样的事情，但返回一个随机的最佳对齐而不是一个固定的对齐，并且
  • edist.adp.backtrace_matrix(x, y, grammar, deltas)x做同样的事情，但返回和的元素之间所有配对的概率分布y。
• edist.alignment模拟序列或树之间的回溯/对齐。edist.alignment.Alignment每个回溯函数（函数除外）都返回类的实例backtrace_matrix。
• edist.bedl支持嵌入编辑距离学习（BEDL； Paaßen 等人，2018 年）来学习编辑距离的参数，而不是手动学习它们。有关详细信息，请参阅bedl_demo。
• edist.edits支持对序列编辑建模的对象，特别是替换、删除和插入，并提供函数 ，alignment_to_script(alignment, x, y)该函数将序列 alignment之间的比对转换为转换为的编辑列表。xyxy
• edist.tree_edits支持建模树编辑的对象，特别是替换、删除和插入，并提供函数 ，该函数将树之间的alignment_to_script(alignment, x_nodes, y_adj, y_nodes, y_adj)对齐方式转换为编辑列表，然后转换为.alignmentxyxy
• edist.tree_utils是库使用的树处理支持函数的集合。图书馆用户感兴趣的可能如下：
  • edist.tree_utils.to_json将树写入 JSON 文件。
  • edist.tree_utils.from_json从 JSON 文件中读取树。
  • edist.tree_utils.dataset_from_json从包含 JSON 文件的目录中读取树列表。
  • edist.tree_utils.tree_to_string将树格式化为字符串。

背景

到目前为止，该库中涵盖的所有算法的背景都超出了本自述文件的范围（我们在下面列出了进一步阅读的材料）。但是，总之有几点值得注意：

• 编辑距离算法很大程度上依赖于动态规划来提高效率，即将整个编辑距离计算分解为子任务并将这些子任务的结果制成表格。通过这种方式，我们可以在多项式时间内搜索一个指数级大的可能对齐空间。然而，这些分解依赖于元素距离函数$$是度量的关键假设\delta，特别是该函数是非负的，自距离为零，并且满足三角不等式。如果这些假设中的任何一个被打破，则可能存在动态规划计算未涵盖的更便宜的对齐方式。\delta因此，在生成您自己的$$ 函数时，这一点至关重要。
• 有趣的是，如果 $$\delta是一个度量，它的度量属性会转化为整体编辑距离（例如，请参阅 Paaßen，2019中的 Theorem 3.2. ）。这可以使处理编辑距离在数学上非常有吸引力。然而，这不适用于动态时间扭曲，它总是违反三角不等式。
• 尽管动态编程使编辑距离成为多项式，但对于长序列/大树来说，计算它们可能变得非常昂贵。具体来说，任意序列的编辑距离以$$为单位\mathcal{O}(m \cdot n)，其中$$m和$$n为输入序列的长度，树的编辑距离为\mathcal{O}(m^2 \cdot n^2)$$，设定的编辑距离为\mathcal{O}((m+n)^3)$$。幸运的是，这个库中提供的cython 实现相对较快，因此可以处理m, n$$ 甚至多达几千个元素（至少对于序列编辑）。尽管如此，选择最适合您的情况的编辑距离函数仍然是关键。例如，edist.sed.sed_string与更一般的edist.sed.sed.

有关算法的更多背景信息，请参阅有关Levenshtein 距离和动态时间扭曲的 Wikipedia 文章，有关仿射编辑距离的Gotoh (1982)论文，有关Paaßen (2018)的评论论文树编辑距离及其回溯，Paaßen（2019） 关于代数动态规划的论文的第 2.3.2 节，以及关于嵌入编辑远程学习的同一篇论文的第 4 章。

许可

该库在GNU 通用公共许可证版本 3下获得许可。

依赖项

这个库依赖于NumPy进行矩阵运算，并依赖于cython 来实现有效的 C 接口。此外，该bedl.py模块依赖于 scikit-learn的基本接口和SciPy的优化。最后，该seted.pyx模块依赖于SciPy来实现匈牙利算法（Kuhn，1955）。

文学

• Giegerich, R.、Meyer, C. 和 Steffen, P. (2004)。对序列数据进行动态规划的一门学科。计算机编程科学，51（3），215-263。doi: 10.1016/j.scico.2003.12.005
• Gotoh, O. (1982)。一种用于匹配生物序列的改进算法。分子生物学杂志，162（3），705-708。doi: 10.1016/0022-2836(82)90398-9
• 库恩，H. (1955)。分配问题的匈牙利方法。海军研究后勤季刊，2（1-2），83-97。doi: 10.1002/nav.3800020109
• Levenshtein, V. (1965)。能够纠正删除、插入和反转的二进制代码。苏联物理学 Doklady，10（8），707-710。
• Paaßen, B., Mokbel, B. 和 Hammer, B. (2015)。智能辅导系统的自适应序列差异测量工具箱。在 OC Santos、JG Boticario、C. Romero、M. Pechenizkiy、A. Merceron、P. Mitros、JM Luna 等人。（编辑），第八届教育数据挖掘国际会议论文集（第 632-632 页）。国际教育数据挖掘协会。关联
• Paaßen, B., Mokbel, B. 和 Hammer, B. (2016)。智能辅导系统中自动反馈提供的自适应结构度量。神经计算，192，3-13。doi: 10.1016/j.neucom.2015.12.108。 关联
• Paaßen, B., Gallicchio, C., Micheli, A., & Hammer, B. (2018)。通过自适应符号嵌入进行树编辑远程学习。第 35 届机器学习国际会议论文集 (ICML 2018)，3973-3982。 关联
• 帕森，B.（2018 年）。重新审视树编辑距离及其回溯：教程。arXiv：1805.06869。
• Paaßen, B. (2019)。结构化数据的度量学习。论文。比勒费尔德大学。doi: 10.4119/unibi/2935545
• 文丘克，TK（1968 年）。通过动态规划进行语音识别。控制论，4（1），52-57。doi: 10.1007/BF01074755
• Zhang, K. 和 Shasha, D. (1989)。树与相关问题之间编辑距离的简单快速算法。SIAM 计算杂志，18（6），1245-1262。doi: 10.1137/0218082
• 张凯（1996）。无序标记树之间的约束编辑距离。算法，15，205-222。doi: 10.1007/BF01975866