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

达梅劳–莱文斯坦距离

达梅劳–莱文斯坦距离是将一个字符串变为另一个所需的插入、删除、替换及相邻交换操作的最少次数。

14 个关键词1 个词条链接到这里1 个尚未撰写AI 撰写
编辑距离度量空间汉明距离算法动态规划哈希表时间复杂度空间复杂度达梅劳–莱…

达梅劳–莱文斯坦距离是两个字符串之间的一种编辑距离:它表示将一个字符串变为另一个所需的单符号插入、删除、替换及相邻符号交换操作的最少次数。在标准形式下,每次操作的代价均为一。它扩展了莱文斯坦距离,将一次相邻交换视为一次编辑,而非两次,因此适合用来比较含有打字错误的字符串。无限制的距离必须与最优字符串对齐距离区分开来;后者是一种较简单的受限变体,但有些软件也用同一个名称来称呼它。

定义与基本操作

设 x=x1x2⋯xmx=x_1x_2\cdots x_m 和 y=y1y2⋯yny=y_1y_2\cdots y_n 是字母表 Σ\Sigma 上的有限字符串。它们的达梅劳–莱文斯坦距离记为 dDL(x,y)d_{\mathrm{DL}}(x,y),定义为使用以下四种操作将 xx 变为 yy 的最短编辑序列的长度:

操作 说明 示例
插入 添加一个符号 cat → cart
删除 移除一个符号 cart → cat
替换 将一个符号替换为另一个 cat → cut
相邻交换 交换两个相邻符号 form → from

交换操作仅限于相邻符号;交换任意两个相距较远的符号不能算作一次操作。

例如,

dDL(form,from)=1,d_{\mathrm{DL}}(\texttt{form},\texttt{from})=1,

而这两个字符串之间的莱文斯坦距离为二。

这一定义适用于一般的序列,而不仅限于书面词语。符号可以是字符、词元或其他离散单位,前提是对相等关系及允许的操作作出一致的定义。

数学性质

当各项操作的代价均为一时,无限制达梅劳–莱文斯坦距离是有限字符串集合上的一种度量。它满足:

  • 非负性: d(x,y)≥0d(x,y)\geq 0。
  • 同一性: d(x,y)=0d(x,y)=0 当且仅当 x=yx=y。
  • 对称性: d(x,y)=d(y,x)d(x,y)=d(y,x)。
  • 三角不等式: d(x,z)≤d(x,y)+d(y,z)d(x,z)\leq d(x,y)+d(y,z)。

对称性源于每种允许的操作都有一个代价相同的逆操作。三角不等式则源于:将 xx 变为 yy 的操作序列之后,可以接上将 yy 变为 zz 的操作序列。

对于长度分别为 mm 和 nn 的字符串,

∣m−n∣≤dDL(x,y)≤max⁡(m,n).|m-n|\leq d_{\mathrm{DL}}(x,y)\leq \max(m,n).

下界成立,是因为只有插入和删除会改变长度,而且每次只改变一。对于上界,可以先替换对应位置的符号,再插入或删除剩余的符号。

它与莱文斯坦距离的关系为

dDL(x,y)≤dLev(x,y),d_{\mathrm{DL}}(x,y)\leq d_{\mathrm{Lev}}(x,y),

因为莱文斯坦距离允许的每一个编辑序列,在达梅劳–莱文斯坦距离中也都允许。汉明距离只统计等长序列中对应位置不相同的数量,而这两种距离都允许插入和删除操作。

无限制距离与最优字符串对齐距离

一个重要区别在于:后续编辑是否可以作用于字符串中已经编辑过的部分。

无限制达梅劳–莱文斯坦距离允许任意组合这四种基本操作。最优字符串对齐距离,简称 OSA 距离,则限制了已编辑子串的再次使用方式。它通常采用的动态规划递推式,只是在莱文斯坦递推式中加入一个局部的相邻交换情形。这种修改并不能在所有情况下计算出无限制距离。

一个典型例子是

CA→AC→ABC.\texttt{CA}\rightarrow\texttt{AC}\rightarrow\texttt{ABC}.

第一次操作交换 C 和 A;第二次操作在它们之间插入 B。因此,

dDL(CA,ABC)=2.d_{\mathrm{DL}}(\texttt{CA},\texttt{ABC})=2.

OSA 距离为这对字符串给出的结果是三。其限制使它无法涵盖上述仅需两次操作的序列。

这一区别也意味着 OSA 距离不满足三角不等式:

dOSA(CA,ABC)=3,d_{\mathrm{OSA}}(\texttt{CA},\texttt{ABC})=3,

但

dOSA(CA,AC)+dOSA(AC,ABC)=1+1=2.d_{\mathrm{OSA}}(\texttt{CA},\texttt{AC}) + d_{\mathrm{OSA}}(\texttt{AC},\texttt{ABC}) =1+1=2.

当算法依赖度量性质进行剪枝或建立索引时,这一区别尤为重要。标为“Damerau–Levenshtein”的软件接口,可能实现的是其中任意一种变体。

动态规划计算

两种变体都可以用动态规划计算,但需要采用不同的递推式。

受限递推式

设 Ri,jR_{i,j} 表示 xx 的前 ii 个符号与 yy 的前 jj 个符号之间的 OSA 距离。初始化为

Ri,0=i,R0,j=j.R_{i,0}=i,\qquad R_{0,j}=j.

定义替换代价

ci,j={0,xi=yj,1,xi≠yj.c_{i,j}= \begin{cases} 0,&x_i=y_j,\\ 1,&x_i\ne y_j. \end{cases}

通常的三个候选值为

Ri,j=min⁡{Ri−1,j+1,  Ri,j−1+1,  Ri−1,j−1+ci,j}.R_{i,j}= \min\left\{ R_{i-1,j}+1,\; R_{i,j-1}+1,\; R_{i-1,j-1}+c_{i,j} \right\}.

若 i,j≥2i,j\geq2、xi=yj−1x_i=y_{j-1} 且 xi−1=yjx_{i-1}=y_j,则额外加入交换操作的候选值

Ri−2,j−2+1.R_{i-2,j-2}+1.

这个递推式很简洁,但其交换情形只考虑紧邻当前计算位置的两个符号。

无限制递推式

对于无限制距离,计算时必须考虑这样的交换:两个端点之间,可能隔着从源字符串中删除的符号,或向目标字符串中插入的符号。

设 Di,jD_{i,j} 为长度分别为 ii 和 jj 的两个前缀之间的无限制距离,并令

Di,0=i,D0,j=j.D_{i,0}=i,\qquad D_{0,j}=j.

在单元格 (i,j)(i,j) 处,设:

  • kk 为小于 ii 且满足 xk=yjx_k=y_j 的最大下标;
  • ℓ\ell 为小于 jj 且满足 yℓ=xiy_\ell=x_i 的最大下标。

除了插入、删除和替换的候选值,还需考虑

Dk−1,ℓ−1+(i−k−1)+1+(j−ℓ−1).D_{k-1,\ell-1} +(i-k-1) +1 +(j-\ell-1).

如果上述任一符号在更早的位置没有出现,则不计入这个候选值。式中各项依次表示:转换之前的前缀、删除源字符串中间的符号、交换匹配的两个端点,以及插入目标字符串中间的符号。

因此,

Di,j=min⁡{Di−1,j+1,Di,j−1+1,Di−1,j−1+ci,j,Dk−1,ℓ−1+(i−k−1)+1+(j−ℓ−1)},D_{i,j}= \min\left\{ \begin{aligned} &D_{i-1,j}+1,\\ &D_{i,j-1}+1,\\ &D_{i-1,j-1}+c_{i,j},\\ &D_{k-1,\ell-1}+(i-k-1)+1+(j-\ell-1) \end{aligned} \right\},

其中最后一个候选值仅在适用时纳入计算。

实现时,可以用数组或哈希表维护各符号最近一次出现的位置,而不必反复扫描前缀。

计算开销

对于长度分别为 mm 和 nn 的字符串,标准实现的时间复杂度为 O(mn)O(mn)。完整动态规划表的空间复杂度为 O(mn)O(mn);无限制距离的计算还需要维护符号出现位置的信息。

如果只计算 OSA 距离,可以使用三行滚动数组,将辅助存储空间降至 O(min⁡(m,n))O(\min(m,n))。同样的简单滚动数组方法不能直接用于无限制递推式,因为其交换候选值可能引用远早于当前行的行。

要恢复实际的编辑序列,需要保存回溯信息,或采用其他重建方法。仅计算距离数值,并不会自动得到一个对齐方案。

历史发展

这一名称源自弗雷德里克·J. 达梅劳和弗拉基米尔·I. 莱文斯坦的研究。达梅劳在 1964 年关于拼写错误检测与纠正的研究中,将插入、删除、替换和相邻交换视为重要的基本错误类型。莱文斯坦在 20 世纪 60 年代的研究则奠定了涉及删除、插入和替换操作的距离理论的基础。

后续算法研究发展出了高效处理交换操作的方法。罗伊·洛兰斯和罗伯特·A. 瓦格纳于 1975 年发表了一种针对扩展字符串纠错问题的算法,产生了重要影响。拼写错误模型与字符串纠错算法之间的历史联系,有助于解释为何受限变体与无限制变体有时会被混为一谈。

应用与局限

达梅劳–莱文斯坦距离用于近似字符串匹配、拼写纠正、信息检索和记录匹配。相邻交换操作使它尤其适合处理将 the 错写为 teh 之类的错误。

在自然语言处理中,它可以作为相似度特征,也可以帮助生成候选纠正结果。但它本身无法确定用户最可能想输入的词:对于编辑距离相同的候选词,词频、上下文、发音和键盘布局都可能成为区分依据。

以下几种建模选择会影响对距离的解读:

  • 文本表示: Unicode统一码字符串可以按字节、码位或字素簇进行比较。采用不同单位,可能得到不同的距离。
  • 预处理: 大小写折叠、去除标点或 Unicode 规范化,会改变比较时保留哪些差异。
  • 操作代价: 单位代价将所有替换和相邻交换一视同仁。加权模型可以表达不同错误发生的可能性,但是否满足度量性质取决于代价规则。
  • 长度归一化: 用与长度相关的分母作除数,可以方便不同长度字符串之间的比较,但所得分数并不一定是度量。
  • 含义: 字符层面的距离小,并不意味着语义相近;语义相同的表达,其距离也可能很大。

对于长序列或大规模集合,时间复杂度为二次量级的两两比较可能开销很大。实际系统通常将编辑距离计算与候选筛选、索引、长度界限或最大允许距离等方法结合使用。