Efficient Parallel Output-Sensitive Edit Distance
Efficient Parallel Output-Sensitive Edit Distance
复制标题
DOI：
10.4230/lipics.esa.2023.40
复制
发表时间：
2023-06
期刊：
影响因子：
--
通讯作者：
Xiangyun Ding;Xiaojun Dong;Yan Gu;Youzhe Liu;Yihan Sun
中科院分区：
文献类型：
--
作者：
Xiangyun Ding;Xiaojun Dong;Yan Gu;Youzhe Liu;Yihan Sun
给定两个字符串\(A[1..n]\)和\(B[1..m]\)，以及一组允许用于编辑字符串的操作，\(A\)和\(B\)之间的编辑距离是将\(A\)转换为\(B\)所需的最少操作次数。顺序地，一个标准的动态规划（DP）算法以\(\Theta(nm)\)的代价解决编辑距离问题。在许多实际应用中，要比较的字符串是相似的且具有较小的编辑距离。为了实现高度实用的实现，我们专注于输出敏感的并行编辑距离算法，即当编辑距离较小时，实现比标准的\(\Theta(nm)\)算法渐近更好的代价界限。我们在论文中研究了四种算法，包括三种基于广度优先搜索（BFS）的算法和一种基于分治（DaC）的算法。我们基于BFS的解决方案基于兰道 - 维什金算法。我们为算法中所需的最长公共前缀（LCP）查询实现了三种不同的数据结构：使用并行后缀数组的经典解决方案，以及本文提出的两种基于哈希的解决方案。我们基于DaC的解决方案受到阿波斯托利科等人提出的输出不敏感解决方案的启发，并且我们提出了一种重要的改进使其成为输出敏感的。我们所有的算法都有良好的理论保证，并且它们在工作量（操作总数）、跨度（计算中最长的依赖链）和空间之间实现了不同的权衡。我们在合成数据和实际数据上对我们的算法进行测试和比较。在所有测试案例中，我们基于BFS的算法都优于ParlayLib中现有的并行编辑距离实现。通过比较我们的算法，我们也对不同输入模式下算法的选择有了更好的理解。我们相信我们的论文是并行编辑距离理论和实践的首次系统研究。
Given two strings $A[1..n]$ and $B[1..m]$, and a set of operations allowed to edit the strings, the edit distance between $A$ and $B$ is the minimum number of operations required to transform $A$ into $B$. Sequentially, a standard Dynamic Programming (DP) algorithm solves edit distance with $\Theta(nm)$ cost. In many real-world applications, the strings to be compared are similar and have small edit distances. To achieve highly practical implementations, we focus on output-sensitive parallel edit-distance algorithms, i.e., to achieve asymptotically better cost bounds than the standard $\Theta(nm)$ algorithm when the edit distance is small. We study four algorithms in the paper, including three algorithms based on Breadth-First Search (BFS) and one algorithm based on Divide-and-Conquer (DaC). Our BFS-based solution is based on the Landau-Vishkin algorithm. We implement three different data structures for the longest common prefix (LCP) queries needed in the algorithm: the classic solution using parallel suffix array, and two hash-based solutions proposed in this paper. Our DaC-based solution is inspired by the output-insensitive solution proposed by Apostolico et al., and we propose a non-trivial adaption to make it output-sensitive. All our algorithms have good theoretical guarantees, and they achieve different tradeoffs between work (total number of operations), span (longest dependence chain in the computation), and space. We test and compare our algorithms on both synthetic data and real-world data. Our BFS-based algorithms outperform the existing parallel edit-distance implementation in ParlayLib in all test cases. By comparing our algorithms, we also provide a better understanding of the choice of algorithms for different input patterns. We believe that our paper is the first systematic study in the theory and practice of parallel edit distance.