The tree edit distance problem is a natural generalization of the classic string edit distance problem. Given two ordered, edge-labeled trees $T_1$ and $T_2$, the edit distance between $T_1$ and $T_2$ is defined as the minimum total cost of operations that transform $T_1$ into $T_2$. In one operation, we can contract an edge, split a vertex into two or change the label of an edge. For the weighted version of the problem, where the cost of each operation depends on the type of the operation and the label on the edge involved, $\mathcal{O}(n^3)$ time algorithms are known for both rooted and unrooted trees. The existence of a truly subcubic $\mathcal{O}(n^{3-\epsilon})$ time algorithm is unlikely, as it would imply a truly subcubic algorithm for the APSP problem. However, recently Mao (FOCS'21) showed that if we assume that each operation has a unit cost, then the tree edit distance between two rooted trees can be computed in truly subcubic time. In this paper, we show how to adapt Mao's algorithm to make it work for unrooted trees and we show an $\widetilde{\mathcal{O}}(n^{(7\omega + 15)/(2\omega + 6)}) \leq \mathcal{O}(n^{2.9417})$ time algorithm for the unweighted tree edit distance between two unrooted trees, where $\omega \leq 2.373$ is the matrix multiplication exponent. It is the first known subcubic algorithm for unrooted trees. The main idea behind our algorithm is the fact that to compute the tree edit distance between two unrooted trees, it is enough to compute the tree edit distance between an arbitrary rooting of the first tree and every rooting of the second tree.


翻译:树编辑距离问题是经典的字符串编辑距离问题的自然推广。给定两个有序的、边标记的树 $T_1$ 和 $T_2$,$T_1$ 和 $T_2$ 之间的编辑距离被定义为将 $T_1$ 转变为 $T_2$ 所需操作的最小总成本。在一次操作中,我们可以收缩一条边,将一个顶点分裂为两个或者改变一条边的标签。对于带权版本的问题,其中每个操作的成本取决于操作的类型和涉及的边上的标签,已知根据不同的树形结构(有根或无根),树编辑距离问题的时间复杂度均为 $\mathcal{O}(n^3)$。真正的子立方 $\mathcal{O}(n^{3-\epsilon})$ 时间复杂度的算法不太可能存在,因为它将意味着求解“所有点对最短路径”(APSP)问题的真正子立方时间复杂度算法存在。然而,最近,Mao (FOCS'21) 显示,如果我们假设每个操作的成本为单位成本,则两个根树之间的树编辑距离可以在真正的子立方时间内计算。在本文中,我们展示了如何调整Mao算法使其适用于无根树,并且我们展示了一种无权无根树编辑距离的 $\widetilde{\mathcal{O}}(n^{(7\omega + 15)/(2\omega + 6)}) \leq \mathcal{O}(n^{2.9417})$ 时间算法,其中 $\omega \leq 2.373$ 是矩阵乘法的指数。它是无根树的第一个已知子立方算法。我们算法的主要思想是:为了计算两个无根树之间的树编辑距离,只需要计算第一棵树的任意根以及第二棵树的每个根之间的树编辑距离即可。

0
下载
关闭预览

相关内容

NeurlPS 2022 | 自然语言处理相关论文分类整理
专知会员服务
48+阅读 · 2022年10月2日
自然语言处理顶会NAACL2022最佳论文出炉!
专知会员服务
42+阅读 · 2022年6月30日
【干货书】开放数据结构,Open Data Structures,337页pdf
专知会员服务
16+阅读 · 2021年9月17日
100+篇《自监督学习(Self-Supervised Learning)》论文最新合集
专知会员服务
164+阅读 · 2020年3月18日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
pytorch中六种常用的向量相似度评估方法
极市平台
22+阅读 · 2021年12月9日
语义分割+视频分割开源代码集合
极市平台
35+阅读 · 2018年3月5日
【CNN】一文读懂卷积神经网络CNN
产业智能官
18+阅读 · 2018年1月2日
上百份文字的检测与识别资源,包含数据集、code和paper
数据挖掘入门与实战
17+阅读 · 2017年12月7日
【推荐】图像分类必读开创性论文汇总
机器学习研究会
14+阅读 · 2017年8月15日
国家自然科学基金
3+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Arxiv
0+阅读 · 2023年6月2日
Arxiv
0+阅读 · 2023年6月2日
Arxiv
0+阅读 · 2023年6月1日
Arxiv
0+阅读 · 2023年5月30日
VIP会员
相关基金
国家自然科学基金
3+阅读 · 2015年12月31日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2008年12月31日
Top
微信扫码咨询专知VIP会员