如何用C++实现编辑距离Levenshtein算法度量字符串相似度

编辑距离Levenshtein算法的核心思想是动态规划，通过构建一个二维状态数组来记录两个字符串在不同长度前缀之间的最小编辑次数，最终数组右下角的值就是两个完整字符串的编辑距离。编辑距离越小，说明两个字符串的相似度越高。

算法原理说明

假设我们有两个字符串，源字符串str1长度为m，目标字符串str2长度为n。我们定义二维数组dp[i][j]表示str1的前i个字符转换为str2的前j个字符所需的最小编辑次数，其中i的范围是0到m，j的范围是0到n。

状态转移规则如下：

• 当i为0时，dp[0][j]等于j，即空字符串转换为str2的前j个字符需要j次插入操作
• 当j为0时，dp[i][0]等于i，即str1的前i个字符转换为空字符串需要i次删除操作
• 当i和j都大于0时，如果str1[i-1]等于str2[j-1]，则dp[i][j] = dp[i-1][j-1]，不需要额外编辑操作
• 如果str1[i-1]不等于str2[j-1]，则dp[i][j]取dp[i-1][j] + 1（删除操作）、dp[i][j-1] + 1（插入操作）、dp[i-1][j-1] + 1（替换操作）三者中的最小值

C++底层实现源码

以下是完整的Levenshtein算法C++实现代码，包含核心计算逻辑和测试示例：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// 计算两个字符串的编辑距离
int levenshteinDistance(const string& str1, const string& str2) {
    int m = str1.size();
    int n = str2.size();
    // 创建二维dp数组，大小为(m+1)*(n+1)
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    // 初始化第一行，对应str1为空的情况
    for (int j = 0; j <= n; j++) {
        dp[0][j] = j;
    }
    // 初始化第一列，对应str2为空的情况
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i;
    }
    
    // 填充dp数组
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (str1[i - 1] == str2[j - 1]) {
                // 当前字符相同，不需要编辑操作
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // 取删除、插入、替换三种操作的最小值加1
                dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
            }
        }
    }
    
    // 返回最终编辑距离
    return dp[m][n];
}

// 根据编辑距离计算字符串相似度，范围0到1，1表示完全相同
double calculateSimilarity(const string& str1, const string& str2) {
    int distance = levenshteinDistance(str1, str2);
    int maxLength = max(str1.size(), str2.size());
    if (maxLength == 0) {
        return 1.0;
    }
    return 1.0 - (double)distance / maxLength;
}

int main() {
    // 测试示例
    string testStr1 = "kitten";
    string testStr2 = "sitting";
    
    int distance = levenshteinDistance(testStr1, testStr2);
    double similarity = calculateSimilarity(testStr1, testStr2);
    
    cout << "字符串1: " << testStr1 << endl;
    cout << "字符串2: " << testStr2 << endl;
    cout << "编辑距离: " << distance << endl;
    cout << "相似度: " << similarity << endl;
    
    return 0;
}

算法复杂度分析

上述实现的时间复杂度为O(m*n)，其中m和n分别是两个输入字符串的长度，因为需要填充一个(m+1)*(n+1)的二维数组。空间复杂度同样为O(m*n)，如果需要对空间进行优化，可以只保留两行数组来交替计算，将空间复杂度降低到O(min(m,n))。

实际应用场景

该算法可以直接应用到多个实际场景中，比如拼写检查工具中判断用户输入的单词和词库中单词的相似度，推荐最相近的正确单词；在文本去重场景中，判断两段文本是否属于重复内容；在生物信息学中，比对DNA序列的相似程度等。

C++Levenshtein算法字符串相似度编辑距离修改时间：2026-06-11 12:21:31