欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 汽车 > 新车 > 一文弄懂编辑距离算法(Levenshtein Distance)示例,通过动态规划计算两个字符串之间的最小编辑操作次数(插入、删除、替换)

一文弄懂编辑距离算法(Levenshtein Distance)示例,通过动态规划计算两个字符串之间的最小编辑操作次数(插入、删除、替换)

2025/3/16 12:38:03 来源:https://blog.csdn.net/m0_74107848/article/details/146284647  浏览:    关键词:一文弄懂编辑距离算法(Levenshtein Distance)示例,通过动态规划计算两个字符串之间的最小编辑操作次数(插入、删除、替换)

以下是一个使用C++实现的编辑距离算法(Levenshtein Distance)示例,通过动态规划计算两个字符串之间的最小编辑操作次数(插入、删除、替换):

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int minEditDistance(const string& word1, const string& word2) {int m = word1.length(), n = word2.length();vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));// 初始化边界条件for (int i = 0; i <= m; ++i) dp[i][0] = i;  // 删除所有字符for (int j = 0; j <= n; ++j) dp[0][j] = j;  // 插入所有字符// 填充DP表for (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j) {if (word1[i-1] == word2[j-1]) {dp[i][j] = dp[i-1][j-1];  // 字符相同,无需操作} else {dp[i][j] = 1 + min({dp[i-1][j],   // 删除word1[i]dp[i][j-1],   // 插入word2[j]dp[i-1][j-1]  // 替换字符});}}}return dp[m][n];
}int main() {string word1 = "kitten";  // 示例输入1string word2 = "sitting"; // 示例输入2int distance = minEditDistance(word1, word2);cout << "从 \"" << word1 << "\" 到 \"" << word2 << "\" 的最小编辑距离为: " << distance << endl;// 解释:kitten → sitten(替换k为s)→ sittin(替换e为i)→ sitting(插入g)return 0;
}

算法核心思想演示(文本修正场景)

想象场景:将单词"kitten"修正为"sitting",计算最少需要多少次单字符编辑操作:

操作步骤结果变化操作类型
1. 替换首字母kkitten → sitten替换(1次)
2. 替换中间esitten → sittin替换(2次)
3. 插入尾字母gsittin → sitting插入(3次)

动态规划三步走

  1. 定义状态表
    dp[i][j] 表示将 word1[0..i-1] 转换为 word2[0..j-1] 的最小操作次数

  2. 状态转移方程

    if word1[i-1] == word2[j-1]:dp[i][j] = dp[i-1][j-1]  # 无操作
    else:dp[i][j] = 1 + min(dp[i-1][j],    # 删除word1字符dp[i][j-1],    # 插入word2字符dp[i-1][j-1]   # 替换字符)
    
  3. 填表示例(kitten vs sitting)

    “”sitting
    “”01234567
    k11234567
    i22123456
    t33212345
    t44321234
    e55432234
    n66543323

执行结果

从 "kitten" 到 "sitting" 的最小编辑距离为: 3

算法特性

特性说明
时间复杂度O(m*n) (m,n为字符串长度)
空间复杂度O(m*n) (可优化为O(n))
优势精准量化文本相似度
适用场景拼写检查、生物信息学、语音识别

关键代码解析

  1. 边界初始化

    dp[i][0] = i; // 删除i次得到空串
    dp[0][j] = j; // 插入j次得到目标串
    
  2. 递推逻辑优化
    使用min({a,b,c})同时比较三种操作,保证代码简洁

  3. 空间压缩技巧
    使用滚动数组可将空间复杂度降至O(n)(示例未展示)


实际应用场景

  1. 文档比对工具:自动计算文稿修改量
  2. 基因序列分析:比对DNA链变异程度
  3. 搜索引擎:提供"您是不是要找…"建议
  4. 聊天机器人:纠正用户输入错别字

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词