An Improved Algorithm for The k-Dyck Edit Distance Problem
An Improved Algorithm for The k-Dyck Edit Distance Problem
复制标题
k-Dyck编辑距离问题的改进算法
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Tatiana Starikovskaya
中科院分区：
文献类型：
--
作者：
Dvir Fried;Shay Golan;Tomasz Kociumaka;T. Kopelowitz;E. Porat;Tatiana Starikovskaya
Dyck序列是平衡的开放和关闭括号（各种类型）的序列。进入戴克序列。只有距离最多为k，否则报告距离大于k，而Onak [Pods'16]表明阈值dyck编辑距离问题可以在O（N + K16）时间内解决工作，我们为阈值dyck编辑距离问题设计了新的算法，该距离的时间为O（n + K4.544184）时间高概率或O（n + K4.853059）确定了我们的算法。 Dyck编辑距离问题的属性，一种快速（最小值， +）矩阵产品的精制算法，以及对Valiant解析算法中使用的想法的仔细修改。
A Dyck sequence is a sequence of opening and closing parentheses (of various types) that is balanced. The Dyck edit distance of a given sequence of parentheses S is the smallest number of edit operations (insertions, deletions, and substitutions) needed to transform S into a Dyck sequence. We consider the threshold Dyck edit distance problem, where the input is a sequence of parentheses S and a positive integer k, and the goal is to compute the Dyck edit distance of S only if the distance is at most k, and otherwise report that the distance is larger than k. Backurs and Onak [PODS’16] showed that the threshold Dyck edit distance problem can be solved in O(n + k16) time. In this work, we design new algorithms for the threshold Dyck edit distance problem which costs O(n + k4.544184) time with high probability or O(n + k4.853059) deterministically. Our algorithms combine several new structural properties of the Dyck edit distance problem, a refined algorithm for fast (min , +) matrix product, and a careful modification of ideas used in Valiant’s parsing algorithm.