达梅劳–莱文斯坦距离是两个字符串之间的一种编辑距离:它表示将一个字符串变为另一个所需的单符号插入、删除、替换及相邻符号交换操作的最少次数。在标准形式下,每次操作的代价均为一。它扩展了莱文斯坦距离,将一次相邻交换视为一次编辑,而非两次,因此适合用来比较含有打字错误的字符串。无限制的距离必须与最优字符串对齐距离区分开来;后者是一种较简单的受限变体,但有些软件也用同一个名称来称呼它。
定义与基本操作
设 和 是字母表 上的有限字符串。它们的达梅劳–莱文斯坦距离记为 ,定义为使用以下四种操作将 变为 的最短编辑序列的长度:
| 操作 | 说明 | 示例 |
|---|---|---|
| 插入 | 添加一个符号 | cat → cart |
| 删除 | 移除一个符号 | cart → cat |
| 替换 | 将一个符号替换为另一个 | cat → cut |
| 相邻交换 | 交换两个相邻符号 | form → from |
交换操作仅限于相邻符号;交换任意两个相距较远的符号不能算作一次操作。
例如,
而这两个字符串之间的莱文斯坦距离为二。
这一定义适用于一般的序列,而不仅限于书面词语。符号可以是字符、词元或其他离散单位,前提是对相等关系及允许的操作作出一致的定义。
数学性质
当各项操作的代价均为一时,无限制达梅劳–莱文斯坦距离是有限字符串集合上的一种度量。它满足:
- 非负性: 。
- 同一性: 当且仅当 。
- 对称性: 。
- 三角不等式: 。
对称性源于每种允许的操作都有一个代价相同的逆操作。三角不等式则源于:将 变为 的操作序列之后,可以接上将 变为 的操作序列。
对于长度分别为 和 的字符串,
下界成立,是因为只有插入和删除会改变长度,而且每次只改变一。对于上界,可以先替换对应位置的符号,再插入或删除剩余的符号。
它与莱文斯坦距离的关系为
因为莱文斯坦距离允许的每一个编辑序列,在达梅劳–莱文斯坦距离中也都允许。汉明距离只统计等长序列中对应位置不相同的数量,而这两种距离都允许插入和删除操作。
无限制距离与最优字符串对齐距离
一个重要区别在于:后续编辑是否可以作用于字符串中已经编辑过的部分。
无限制达梅劳–莱文斯坦距离允许任意组合这四种基本操作。最优字符串对齐距离,简称 OSA 距离,则限制了已编辑子串的再次使用方式。它通常采用的动态规划递推式,只是在莱文斯坦递推式中加入一个局部的相邻交换情形。这种修改并不能在所有情况下计算出无限制距离。
一个典型例子是
第一次操作交换 C 和 A;第二次操作在它们之间插入 B。因此,
OSA 距离为这对字符串给出的结果是三。其限制使它无法涵盖上述仅需两次操作的序列。
这一区别也意味着 OSA 距离不满足三角不等式:
但
当算法依赖度量性质进行剪枝或建立索引时,这一区别尤为重要。标为“Damerau–Levenshtein”的软件接口,可能实现的是其中任意一种变体。
动态规划计算
两种变体都可以用动态规划计算,但需要采用不同的递推式。
受限递推式
设 表示 的前 个符号与 的前 个符号之间的 OSA 距离。初始化为
定义替换代价
通常的三个候选值为
若 、 且 ,则额外加入交换操作的候选值
这个递推式很简洁,但其交换情形只考虑紧邻当前计算位置的两个符号。
无限制递推式
对于无限制距离,计算时必须考虑这样的交换:两个端点之间,可能隔着从源字符串中删除的符号,或向目标字符串中插入的符号。
设 为长度分别为 和 的两个前缀之间的无限制距离,并令
在单元格 处,设:
- 为小于 且满足 的最大下标;
- 为小于 且满足 的最大下标。
除了插入、删除和替换的候选值,还需考虑
如果上述任一符号在更早的位置没有出现,则不计入这个候选值。式中各项依次表示:转换之前的前缀、删除源字符串中间的符号、交换匹配的两个端点,以及插入目标字符串中间的符号。
因此,
其中最后一个候选值仅在适用时纳入计算。
实现时,可以用数组或哈希表维护各符号最近一次出现的位置,而不必反复扫描前缀。
计算开销
对于长度分别为 和 的字符串,标准实现的时间复杂度为 。完整动态规划表的空间复杂度为 ;无限制距离的计算还需要维护符号出现位置的信息。
如果只计算 OSA 距离,可以使用三行滚动数组,将辅助存储空间降至 。同样的简单滚动数组方法不能直接用于无限制递推式,因为其交换候选值可能引用远早于当前行的行。
要恢复实际的编辑序列,需要保存回溯信息,或采用其他重建方法。仅计算距离数值,并不会自动得到一个对齐方案。
历史发展
这一名称源自弗雷德里克·J. 达梅劳和弗拉基米尔·I. 莱文斯坦的研究。达梅劳在 1964 年关于拼写错误检测与纠正的研究中,将插入、删除、替换和相邻交换视为重要的基本错误类型。莱文斯坦在 20 世纪 60 年代的研究则奠定了涉及删除、插入和替换操作的距离理论的基础。
后续算法研究发展出了高效处理交换操作的方法。罗伊·洛兰斯和罗伯特·A. 瓦格纳于 1975 年发表了一种针对扩展字符串纠错问题的算法,产生了重要影响。拼写错误模型与字符串纠错算法之间的历史联系,有助于解释为何受限变体与无限制变体有时会被混为一谈。
应用与局限
达梅劳–莱文斯坦距离用于近似字符串匹配、拼写纠正、信息检索和记录匹配。相邻交换操作使它尤其适合处理将 the 错写为 teh 之类的错误。
在自然语言处理中,它可以作为相似度特征,也可以帮助生成候选纠正结果。但它本身无法确定用户最可能想输入的词:对于编辑距离相同的候选词,词频、上下文、发音和键盘布局都可能成为区分依据。
以下几种建模选择会影响对距离的解读:
- 文本表示: Unicode统一码字符串可以按字节、码位或字素簇进行比较。采用不同单位,可能得到不同的距离。
- 预处理: 大小写折叠、去除标点或 Unicode 规范化,会改变比较时保留哪些差异。
- 操作代价: 单位代价将所有替换和相邻交换一视同仁。加权模型可以表达不同错误发生的可能性,但是否满足度量性质取决于代价规则。
- 长度归一化: 用与长度相关的分母作除数,可以方便不同长度字符串之间的比较,但所得分数并不一定是度量。
- 含义: 字符层面的距离小,并不意味着语义相近;语义相同的表达,其距离也可能很大。
对于长序列或大规模集合,时间复杂度为二次量级的两两比较可能开销很大。实际系统通常将编辑距离计算与候选筛选、索引、长度界限或最大允许距离等方法结合使用。