1. 首页首页
  2. 科技前沿科技前沿

2025年字符串编辑距离之Damerau–Levenshtein Distance

科技前沿 • • 阅读 43

字符串编辑距离之Damerau–Levenshtein Distance概述 Damerau Levenshtein Distance 用来测量两个字符序列之间的编辑距离的字符串度量标准 两个词的 Damerau Levenshtein Distance 是从一个词转换为另一个词的最少操作数 与 Levenshtein Distance 不同的是 除了单个字符的插入 删除和变更之外 还包括两个相邻字符的转换 定义

大家好，我是讯享网，很高兴认识大家。

概述

Damerau–Levenshtein Distance用来测量两个字符序列之间的编辑距离的字符串度量标准。两个词的Damerau–Levenshtein Distance是从一个词转换为另一个词的最少操作数，与Levenshtein Distance不同的是，除了单个字符的插入、删除和变更之外，还包括两个相邻字符的转换。

定义

对于两个字符串a
讯享网、b，函数d_{a,b}(i,j)表示a的前i个字符与b的前j个字符的编辑距离：

d_{a,b}(i,j)=\begin{cases} \max(i,j) & \text {if } \min(i,j)=0 \\ \min\begin{cases} d_{a,b}(i-1,j)+1\\ d_{a,b}(i,j-1)+1\\ d_{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})}\\ d_{a,b}(i-2,j-2)+1 \end{cases}& \text {if }i,j> 1 \text{ and }a_{i}=b_{j-1}\text{ and }a_{i-1}=b_{j}\\ \min\begin{cases} d_{a,b}(i-1,j)+1\\ d_{a,b}(i,j-1)+1\\ d_{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})} \end{cases}& \text{otherwise} \end{cases}

当 i,j> 1 \text{ and }a_{i}=b_{j-1}\text{ and }a_{i-1}=b_{j} 时，除了要计算Levenshtein Distance中所定义的插入、删除和变更操作的操作数以外，还要计算相邻字符转换的操作数，然后将四个操作数做对比取最小的值。

示例

以字符串a：aborad和b：aboard为例，求值过程如下图：

图片制作中。。。

如图字符串a、b的Damerau–Levenshtein Distance \operatorname{d}_{a,b}(6,6)为1，相似度Sim_{a,b}为：

Sim_{a,b}=1-(\operatorname{d}_{a,b}(6,6)/max(6,6))=0.8333\cdots

小讯
上一篇 2025-04-02 21:35
下一篇 2025-03-01 18:01

相关推荐

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/57518.html