Weighted Edit Distance Computation: Strings, Trees, and Dyck
Weighted Edit Distance Computation: Strings, Trees, and Dyck
复制标题
加权编辑距离计算：字符串、树和 Dyck
DOI：
10.1145/3564246.3585178
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Saha, Barna
中科院分区：
文献类型：
--
作者：
Das, Debarati;Gilbert, Jacob;Hajiaghayi, MohammadTaghi;Kociumaka, Tomasz;Saha, Barna
给定两个字符串的长度超过字母表n，以及它们的编辑距离的上界，Myers（Mymica '86）和朗道和Vishkin（JCSS'88）的算法从近40年前开始计算未加权的字符串编辑距离在O（n+ k 2）时间内。迄今为止，它仍然是精确编辑距离计算的最快算法，并且在强指数假设下是最优的（Backurs和Indyk; STOC'15）。多年来，这个结果激发了许多发展，包括字符串编辑距离的快速近似算法以及用于树和Dyck编辑距离的推广的类似的n（n+poly（k））时间算法。尽管不加权的编辑距离在理论上是基本的，但几乎所有的实际应用都需要加权的编辑距离，其中不同的权重被分配给不同的编辑操作（插入、删除和替换），并且权重可能会随着正在编辑的字符而变化。给定一个权重函数w：Σ∪{ε} × Σ∪{ε} → ℝ≥ 0(such thatw(a,a) = 0 andw(a,B) ≥ 1 for alla,B∈ Σ∪{ε} witha≠B), the goal is to find an alignment that minimizes the total weight of edits.除了vanillaO（n2）时间动态规划算法和它的几乎平凡的O（nk）时间实现之外，（k是所寻求的总权重的上限），上述关于未加权编辑距离的发展都不适用于加权变体。（n+poly（k））时间算法，精确计算加权字符串编辑距离，从而弥合了我们对未加权和加权编辑距离的理解之间长达数十年的根本差距。然后，我们将这一结果推广到加权树和戴克编辑距离，带来了几个新的技术，这导致了一个确定性的算法，改进了以前的工作，即使是未加权树编辑距离。考虑到加权编辑距离是多么基本，我们相信我们的O（n+poly（k））时间算法将有助于该领域的进一步重大发展。
Given two strings of lengthnover alphabet Σ, and an upper boundkon their edit distance, the algorithm of Myers (Algorithmica’86) and Landau and Vishkin (JCSS’88) from almost forty years back computes the unweighted string edit distance inO(n+k2) time. To date, it remains the fastest algorithm for exact edit distance computation, and it is optimal under the Strong Exponential Hypothesis (Backurs and Indyk; STOC’15). Over the years, this result has inspired many developments, including fast approximation algorithms for string edit distance as well as similar Õ(n+poly(k))-time algorithms for generalizations to tree and Dyck edit distances. Surprisingly, all these results hold only for unweighted instances.While unweighted edit distance is theoretically fundamental, almost all real-world applications require weighted edit distance, where different weights are assigned to different edit operations (insertions, deletions, and substitutions), and the weights may vary with the characters being edited. Given a weight functionw: Σ∪{ε} × Σ∪{ε} → ℝ≥ 0(such thatw(a,a) = 0 andw(a,b) ≥ 1 for alla,b∈ Σ∪{ε} witha≠b), the goal is to find an alignment that minimizes the total weight of edits. Except for the vanillaO(n2)-time dynamic-programming algorithm and its almost trivialO(nk)-time implementation (kbeing an upper bound on the sought total weight), none of the aforementioned developments on the unweighted edit distance applies to the weighted variant.In this paper, we propose the firstO(n+poly(k))-time algorithm that computes the weighted string edit distance exactly, thus bridging a fundamental decades-old gap between our understanding of unweighted and weighted edit distance. We then generalize this result to the weighted tree and Dyck edit distances, bringing in several new techniques, which lead to a deterministic algorithm that improves upon the previous work even for unweighted tree edit distance. Given how fundamental weighted edit distance is, we believe ourO(n+poly(k))-time algorithm will be instrumental for further significant developments in the area.
登录
查看更多内容
DOI：
10.5555/1109557.1109644
发表时间：
2006-01
期刊：
--
影响因子：
--
作者：
Tugkan Batu;Funda Ergün;S. C. Sahinalp
通讯作者：
Tugkan Batu;Funda Ergün;S. C. Sahinalp
矩形单调最小加乘积的改进界限
影响因子：
0.5
作者：
Anita Dürr
通讯作者：
Anita Dürr
k-Dyck编辑距离问题的改进算法
DOI：
--
发表时间：
2021
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Dvir Fried;Shay Golan;Tomasz Kociumaka;T. Kopelowitz;E. Porat;Tatiana Starikovskaya
通讯作者：
Tatiana Starikovskaya
近线性时间戴克语言编辑距离问题
DOI：
--
发表时间：
2014
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
B. Saha
通讯作者：
B. Saha
DOI：
--
发表时间：
2000
期刊：
--
影响因子：
--
作者：
Dan Jurafsky;James H. Martin
通讯作者：
Dan Jurafsky;James H. Martin