C#实现编辑距离（Levenshtein）算法详解（小白也能轻松掌握的字符串相似度计算方法）

举个例子

比如，字符串 "kitten" 和 "sitting" 的编辑距离是 3，因为可以通过以下三步完成转换：

1. kitten → sitten（替换 k 为 s）
2. sitten → sittin（替换 e 为 i）
3. sittin → sitting（在末尾插入 g）

C#实现Levenshtein距离算法

我们可以使用动态规划来高效地计算两个字符串之间的编辑距离。核心思想是构建一个二维数组 dp[i, j]，表示将字符串 str1 的前 i 个字符转换为 str2 的前 j 个字符所需的最小操作数。

算法步骤：

1. 初始化一个 (m+1) × (n+1) 的二维数组，其中 m 和 n 分别是两个字符串的长度。
2. 第一行和第一列分别表示空字符串到目标字符串所需的操作数（即插入或删除全部字符）。
3. 遍历两个字符串，根据字符是否相等，决定当前单元格的值：
   - 如果相等：取左上角的值（无需操作）
   - 如果不等：取左、上、左上三个方向的最小值 + 1（对应插入、删除、替换）
4. 右下角的值即为最终的编辑距离。

C#代码实现：

public static int LevenshteinDistance(string str1, string str2){    if (string.IsNullOrEmpty(str1))        return str2?.Length ?? 0;        if (string.IsNullOrEmpty(str2))        return str1.Length;    int m = str1.Length;    int n = str2.Length;        // 创建二维数组 dp    int[,] dp = new int[m + 1, n + 1];    // 初始化第一列：str1 转为空字符串需删除所有字符    for (int i = 0; i <= m; i++)        dp[i, 0] = i;    // 初始化第一行：空字符串转为 str2 需插入所有字符    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 (str1[i - 1] == str2[j - 1])            {                // 字符相同，无需操作                dp[i, j] = dp[i - 1, j - 1];            }            else            {                // 取三种操作的最小值 + 1                dp[i, j] = Math.Min(                    Math.Min(dp[i - 1, j] + 1,     // 删除                             dp[i, j - 1] + 1),   // 插入                    dp[i - 1, j - 1] + 1); // 替换            }        }    }    return dp[m, n];}

如何使用这个函数？

你可以在你的 C# 项目中直接调用这个静态方法。例如：

class Program{    static void Main()    {        string word1 = "kitten";        string word2 = "sitting";                int distance = LevenshteinDistance(word1, word2);        Console.WriteLine($"\"{word1}\" 和 \"{word2}\" 的编辑距离是: {distance}");        // 输出: "kitten" 和 "sitting" 的编辑距离是: 3    }}

优化建议

上述实现的时间复杂度为 O(m×n)，空间复杂度也是 O(m×n)。如果只关心最终的编辑距离（而非具体的编辑路径），我们可以将空间复杂度优化到 O(min(m, n))，只需保存当前行和上一行的数据即可。这在处理长字符串时非常有用。

总结

通过本文，你已经掌握了 C#字符串比较 中最常用的 Levenshtein距离 算法。这项技术是许多高级文本处理功能的基础，比如自动纠错、模糊搜索、抄袭检测等。同时，这也是学习 动态规划算法 的经典入门案例。

希望这篇教程能帮助你理解并应用 C#编辑距离算法。动手试试吧！修改代码、测试不同字符串，你会对这个算法有更深的理解。