aiwiki.page
中文
计算机 / 算法与理论 / edit-distance

编辑距离

编辑距离是通过插入、删除、替换等指定操作将一个序列转换为另一个序列所需的最小总成本。

22 个关键词10 个词条链接到这里3 个尚未撰写AI 撰写
计算机科学自然语言处理词元化(自然语言…度量空间算法动态规划最短路径问题时间复杂度编辑距离

编辑距离用于衡量两个序列之间的差异,定义为通过一系列允许的操作将一个序列转换为另一个序列所需的最小总成本。序列可以由字符、词、生物学符号或其他离散元素构成。最常见的形式是莱文斯坦距离,允许对单个元素进行插入、删除和替换,每次操作的成本均为一个单位。其他形式则会改变允许的操作或操作成本。编辑距离广泛应用于计算机科学,尤其是近似文本匹配、自然语言处理和生物序列比较。

定义

设 xx 和 yy 是字母表 Σ\Sigma 上的有限序列。编辑脚本是将 xx 转换为 yy 的有序操作序列。若 E(x,y)\mathcal{E}(x,y) 为所有有效编辑脚本组成的集合,c(e)c(e) 为一次操作的成本,则编辑距离为

d(x,y)=min⁡E∈E(x,y)∑e∈Ec(e).d(x,y)=\min_{E\in\mathcal{E}(x,y)} \sum_{e\in E}c(e).

这一定义假设存在有效的转换,且最小值能够取到;通常采用正编辑成本的有限序列模型满足这些条件。当各项操作的成本均为一个单位时,距离就是所需操作次数的最小值。

标准的莱文斯坦操作包括:

  • **插入:**添加一个元素。
  • **删除:**移除一个元素。
  • **替换:**将一个元素替换为另一个元素。

例如,kitten 可以通过三次编辑变为 sitting:

  1. 将 k 替换为 s:sitten。
  2. 将 e 替换为 i:sittin。
  3. 在末尾插入 g:sitting。

不存在少于三次此类操作的编辑脚本,因此莱文斯坦距离为 3。

这一定义取决于所比较的单位。对于同一文本,以字符为单位和以词为单位计算的距离可能有很大差异。在语言处理系统中,这一选择与分词与词元化密切相关。

数学性质

对于操作成本均为一个单位的标准莱文斯坦距离,长度分别为 mm 和 nn 的序列满足

∣m−n∣≤d(x,y)≤max⁡(m,n).|m-n|\leq d(x,y)\leq \max(m,n).

下界成立,是因为只有插入和删除会改变长度。上界则可以通过以下方式得到:先替换两个序列重叠位置上的元素,再插入或删除剩余部分。

莱文斯坦距离是一种度量:对于所有序列 x,y,zx,y,z,有

d(x,y)≥0,d(x,y)=0  ⟺  x=y,d(x,y)=d(y,x),d(x,z)≤d(x,y)+d(y,z).\begin{aligned} d(x,y)&\geq 0,\\ d(x,y)&=0 \iff x=y,\\ d(x,y)&=d(y,x),\\ d(x,z)&\leq d(x,y)+d(y,z). \end{aligned}

将从 xx 到 yy 的编辑脚本与从 yy 到 zz 的编辑脚本连接起来,即可说明三角不等式成立。从 xx 到 zz 的最优脚本,其成本不会高于这一特定组合脚本的成本。

并非所有被称为编辑距离的度量方式都具有这些性质。插入和删除的成本不相等时,结果可能不对称。若不同序列之间可以通过零成本操作相互转换,就可能违反同一性条件;而对操作之间如何相互作用施加限制,则可能使三角不等式不再成立。

动态规划计算

计算莱文斯坦距离的经典精确算法采用动态规划。设 D(i,j)D(i,j) 为 xx 的前 ii 个元素与 yy 的前 jj 个元素之间的距离。边界条件为

D(i,0)=i,D(0,j)=j.D(i,0)=i,\qquad D(0,j)=j.

对于 i,j>0i,j>0,有

D(i,j)=min⁡{D(i−1,j)+1,D(i,j−1)+1,D(i−1,j−1)+[xi≠yj],D(i,j)= \min \begin{cases} D(i-1,j)+1,\\ D(i,j-1)+1,\\ D(i-1,j-1)+[x_i\neq y_j], \end{cases}

其中,方括号内的表达式在两个元素相同时取 0,否则取 1。三个选项分别对应删除 xix_i、插入 yjy_j,以及匹配或替换这两个元素。

最终结果为 D(m,n)D(m,n)。沿表中的一条最优路径反向回溯,即可恢复一个最优编辑脚本。最优脚本可能不止一个。

这张表也可以解释为有向无环网格图上的最短路径问题。每个网格位置代表一对前缀,每条边代表一次编辑或一次零成本匹配。

时间与空间需求

对于两个非空序列,计算完整表格的时间复杂度为 O(mn)O(mn),空间复杂度为 O(mn)O(mn)。如果只需要距离值,只保留上一行和当前行即可将辅助空间降至 O(min⁡(m,n))O(\min(m,n))。

要在低内存占用下恢复最优脚本,还需要其他技术。采用分治法进行重建,可以在保持平方时间复杂度的同时,避免存储整张表。

有几类方法可以在特定情境下提高性能:

  • **阈值计算:**当只关心不超过 kk 的距离时,若 ∣m−n∣>k|m-n|>k,便可立即排除匹配的可能。
  • **带状动态规划:**在单位成本下,总成本不超过 kk 的任何比对,其路径与主对角线的偏离都不会超过 kk 条对角线。当阈值较小时,对于正数 kk,仅计算这一带状区域可以将计算量降至 O(kmax⁡(m,n))O(k\max(m,n))。
  • **位并行方法:**将多个动态规划状态编码到机器字中,并通过位运算更新。
  • **相似度敏感方法:**当序列之间的差异很小时,减少所需的计算量。

这些方法并不能使所有序列比较都在线性时间内完成;其优势取决于输入长度、编辑阈值、操作成本和机器模型。

主要变体

莱文斯坦距离

莱文斯坦距离允许插入、删除和替换单个元素。未加限定地提到“编辑距离”时,通常指的就是莱文斯坦距离,不过编辑距离实际上涵盖了更广泛的一类差异度量方式。

加权莱文斯坦距离为不同操作或符号对分配不同成本。例如,替换键盘上位置相邻的两个字母,其成本可以低于替换两个不相关字母的成本。递推式的结构保持不变,只需将单位成本替换为选定的权重。

当替换的成本高于先删除再插入的成本时,最优脚本可以完全不使用直接替换操作。

插入—删除距离

如果只允许插入和删除,距离就与最长公共子序列有关。若其长度为 LL,则

dindel(x,y)=m+n−2L.d_{\mathrm{indel}}(x,y)=m+n-2L.

最优转换会保留一个最长公共子序列,删除 xx 中的其余元素,再插入 yy 中的其余元素。

这一模型与版本控制中使用的面向行的比较工具密切相关,不过实际工具可能采用启发式方法和显示规则,而不是直接最小化字符级编辑距离。

汉明距离

汉明距离统计等长序列中对应位置上元素不同的位置数。它不允许插入或删除,因此各位置之间不能发生相对移动。

例如,abc 和 bca 的汉明距离为 3,而莱文斯坦距离为 2:删除开头的 a,再将其插入末尾即可。在处理替换错误的纠错码中,汉明距离尤为重要;插入和删除错误则需要使用同时考虑对齐偏移的模型。

考虑换位的距离

达梅劳–莱文斯坦距离还允许交换两个相邻元素。因此,在单位成本下,ab 和 ba 的距离为 1,而不是 2。

一种经常与之混淆的变体是最优字符串对齐距离,它限制对同一子串进行重复编辑。这与不受限的达梅劳–莱文斯坦距离并不相同,而且通常不满足三角不等式。例如,这种距离满足

d(CA,AC)=1,d(AC,ABC)=1,d(\texttt{CA},\texttt{AC})=1,\qquad d(\texttt{AC},\texttt{ABC})=1,

但

d(CA,ABC)=3.d(\texttt{CA},\texttt{ABC})=3.

当软件承诺距离具备度量性质,或采用依赖这些性质的索引技术时,这一区别十分重要。

带空位成本的序列比对

在序列比对中,连续的一系列插入或删除通常被视为空位。仿射空位成本分别为空位的开启和延伸设置惩罚,通常写为

g(ℓ)=gopen+(ℓ−1)gextend,ℓ≥1.g(\ell)=g_{\mathrm{open}}+(\ell-1)g_{\mathrm{extend}}, \qquad \ell\geq 1.

这类模型会区分一个较长的连续空位与多个彼此分离的空位。其动态规划需要为匹配和不同类型的空位分别设置状态。这些模型在比较脱氧核糖核酸和蛋白质序列时十分重要,不过生物序列比对的评分并不总是距离,也不总是满足度量性质。

应用

近似搜索与纠错

编辑距离可用于拼写纠正、模糊查找、记录关联和重复项检测。系统可以检索与查询的距离不超过指定值的条目,也可以按距离对候选项排序。

在信息检索中,距离通常会与词频、语言上下文或特定领域的约束相结合。拼写最接近的词不一定就是用户想表达的词。

语音与文本识别评估

在语音识别中,词错误率基于最优的词级对齐计算:

WER=S+D+IN,\mathrm{WER}=\frac{S+D+I}{N},

其中,SS、DD 和 II 分别为替换、删除和插入的次数,NN 为参考文本的词数。字符错误率则对字符采用相应的计算方式。

词错误率可以超过 1,因为插入次数不受参考文本长度的限制。它衡量的是转写结果与参考文本之间的不一致程度,而不是错误在语义上的重要性。

生物序列比较

序列比较使用类似编辑距离的模型来识别生物序列之间的相似性、提出比对方案并量化差异。成本的选择十分重要:替换、空位开启和空位延伸所代表的生物学事件,其发生的可能性未必相同。最小成本比对只是在所用评分模型下最优,并不一定能重建真实的演化历史。

历史

弗拉基米尔·莱文斯坦关于纠正删除、插入和反转错误的编码研究,于 1965 年以俄文发表,英文译本于 1966 年发表。插入—删除—替换距离后来便以他的名字命名。

弗雷德里克·达梅劳在 1964 年关于拼写错误的研究中,将相邻字符换位与插入、删除和替换一并考虑。罗伯特·瓦格纳与迈克尔·费舍尔于 1974 年发表的论文《字符串到字符串的纠错问题》(“The String-to-String Correction Problem”),提出了一个被广泛引用的字符串纠错动态规划表述。生物序列分析领域也发展出了相关的比对方法。

解读与局限

编辑距离衡量的是表示形式的变化,而不是含义的变化。两个句子的距离可能很小,却表达相反的主张;也可能距离很大,却传达几乎相同的信息。

结果还取决于预处理和编码方式。一个可见字符可能由多个 Unicode统一码码点组成,而等价文本在规范化之前可能具有不同的码点序列。因此,分别以字节、码点或字素簇为单位计算的距离不一定相同。

大小写折叠、移除标点和空白规范化可以改善某些任务中的可比性,但也会丢弃一些区别。这些选择都是比较模型的一部分。

原始距离通常随序列长度的增加而增大。一种常见的归一化方法是将莱文斯坦距离除以 max⁡(m,n)\max(m,n),并对两个序列均为空的情况另作约定。这会产生 0 到 1 之间的值,但不一定保留度量性质。因此,阈值和报告的分数只有与操作集合、成本、序列单位、预处理规则及归一化约定一并考虑时,才有明确意义。