How Hard Is Computing the Edit Distance?
How Hard Is Computing the Edit Distance?
复制标题
计算编辑距离有多难？
DOI：
10.1006/inco.2000.2914
复制
发表时间：
2001
影响因子：
1
通讯作者：
G. Pighizzini
中科院分区：
文献类型：
--
作者：
G. Pighizzini
编辑距离的概念出现在非常不同的领域，例如自纠码、解析理论、语音识别和分子生物学。输入字符串和语言 L 之间的编辑距离是将输入字符串更改为 L 的句子所需的一系列编辑操作（将一个符号替换为另一个不正确的符号、插入无关符号、删除符号）的最小成本。在本文中，我们研究计算编辑距离的复杂性，发现可以有效评估该函数的语言类别和似乎难以计算的语言类别之间的清晰界限。我们的主要成果是一种并行算法，用于计算在多项式时间内工作的单向非确定性辅助下推自动机所接受的语言类的编辑距离，该类严格包含上下文无关语言。此外，我们表明可以扩展该算法，以便找到与输入字符串具有最小距离的语言的句子。
The notion of edit distance arises in very different fields such as self-correcting codes, parsing theory, speech recognition, and molecular biology. The edit distance between an input string and a language L is the minimum cost of a sequence of edit operations (substitution of a symbol in another incorrect symbol, insertion of an extraneous symbol, deletion of a symbol) needed to change the input string into a sentence of L. In this paper we study the complexity of computing the edit distance, discovering sharp boundaries between classes of languages for which this function can be efficiently evaluated and classes of languages for which it seems to be difficult to compute. Our main result is a parallel algorithm for computing the edit distance for the class of languages accepted by one-way nondeterministic auxiliary pushdown automata working in polynomial time, a class that strictly contains context?free languages. Moreover, we show that this algorithm can be extended in order to find a sentence of the language from which the input string has minimum distance.