The Dyck Language Edit Distance Problem in Near-Linear Time
The Dyck Language Edit Distance Problem in Near-Linear Time
复制标题
近线性时间戴克语言编辑距离问题
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
B. Saha
中科院分区：
文献类型：
--
作者：
B. Saha
给定字母σ和在同一字母上定义的语法G，需要映射多少最小维修（插入，删除和替换）才能将σ映射到G中的有效成员中？ 1972年启动了此语言编辑距离问题的研究，为在O（| g | 2n3）时间内运行的上下文无语言提供动态编程算法，其中n是字符串长度，g是语法大小。后来的改进将运行时间减少到O（G N3），但输入长度上的立方时间复杂性具有将这些算法应用于本文的多种应用程序的主要瓶颈。自由语言，代表不同类型的均衡括号的语言，这在形式学理论的发展中是关键的。算法紧密近似于任何任意s的dyck（S）语言编辑距离问题。数据库，在编译器优化中生成自动校正的解析器，以结构生物学序列中的预测问题。语言。我们的主要结果是用于在o（n1+ϵ polylog（n））时间内进行的任何正整数的编辑距离计算的算法log | opt |），对于任何ϵ> 0。此处是dyck（s）和β（n）的最佳编辑距离，这是在类似时间内运行的较简单的字符串编辑距离问题允许O（N1 +ϵ + | opt | 2nϵ）时间，可以将近似因子降低到o（1/ϵ log | opt |）。 ），在接近线性的时间计算模型下在时间复杂性上显示出明显的差异。分布式验证）。因此，分别可以通过这些数据结构识别的任何语言也可以通过我们的算法有效地修复。
Given a string σ over alphabet Σ and a grammar G defined over the same alphabet, how many minimum number of repairs (insertions, deletions and substitutions) are required to map σ into a valid member of G? The seminal work of Aho and Peterson in 1972 initiated the study of this language edit distance problem providing a dynamic programming algorithm for context free languages that runs in O(|G|2n3) time, where n is the string length and G is the grammar size. While later improvements reduced the running time to O(G n3), the cubic time complexity on the input length held a major bottleneck for applying these algorithms to their multitude of applications. In this paper, we study the language edit distance problem for a fundamental context free language, DYCK(s) representing the language of well-balanced parentheses of s different types, that has been pivotal in the development of formal language theory. We provide the very first near-linear time algorithm to tightly approximate the DYCK(s) language edit distance problem for any arbitrary s. DYCK(s) language edit distance significantly generalizes the well-studied string edit distance problem, and appears in most applications of language edit distance ranging from data quality in databases, generating automated error-correcting parsers in compiler optimization to structure prediction problems in biological sequences. Its nondeterministic counterpart is known as the hardest context free language. Our main result is an algorithm for edit distance computation to DYCK(s) for any positive integer s that runs in O(n1+ϵ polylog(n)) time and achieves an approximation factor of O(1/ϵβ(n) log |OPT|), for any ϵ > 0. Here OPT is the optimal edit distance to DYCK(s) and β(n) is the best approximation factor known for the simpler problem of string edit distance running in analogous time. If we allow O(n1+ϵ + |OPT|2nϵ) time, then the approximation factor can be reduced to O(1/ϵ log |OPT|). Since the best known near-linear time algorithm for the string edit distance problem has β(n) = polylog(n), under near-linear time computation model both DYCK(s) language and string edit distance problems have polylog(n) approximation factors. This comes as a surprise since the former is a significant generalization of the latter and their exact computations via dynamic programming show a stark difference in time complexity. Rather less surprisingly, we show that the framework for efficiently approximating edit distance to DYCK(s) can be utilized for many other languages. We illustrate this by considering various memory checking languages (studied extensively under distributed verification) such as STACK, QUEUE, PQ and DEQUE which comprise of valid transcripts of stacks, queues, priority queues and double-ended queues respectively. Therefore, any language that can be recognized by these data structures, can also be repaired efficiently by our algorithm.