C#实现莱文斯坦距离计算字符串相似度详解

江岸

发布时间：2026-10-13| 2人浏览过

原创

莱文斯坦距离是衡量两个字符串相似程度的经典指标，广泛应用于文本比对、拼写纠错和查重系统。本文将详细介绍基于C#语言的莱文斯坦距离算法原理，并提供经过优化的完整代码实现，帮助您快速掌握如何在实际项目中计算字符串相似度。

什么是莱文斯坦距离

莱文斯坦距离（Levenshtein Distance），又称 LD 距离，是由俄国科学家 Vladimir Levenshtein 于1965年提出的概念。它用于计算两个字符串之间，从一个字符串转换成另一个字符串所需的最少编辑操作次数。允许的编辑操作包括：

将一个字符替换成另一个字符
插入一个字符
删除一个字符

数值越小表示两个字符串越相似，数值为0则意味着两个字符串完全相同。例如，对于字符串 A="abcd" 和 B="abc"，只需在B中插入一个字符即可完成转换，因此它们的莱文斯坦距离为1。

C# 算法实现原理

计算莱文斯坦距离的核心在于动态规划（Dynamic Programming）。算法构建一个二维数组 d[m+1, n+1]，其中 m 和 n 分别为两个字符串的长度。数组中的每一个值 d[i,j] 代表字符串 str1 的前 i 个字符与 str2 的前 j 个字符之间的距离。

具体步骤如下：

初始化：将第0行初始化为 0..n，第0列初始化为 0..m，表示空字符串与其他字符串的距离即为字符串长度。
状态转移：依次遍历两个字符串的每个字符。如果当前字符相等，则成本为0；如果不相等，成本为1。
取最小值：当前位置的值取以下三个方向的最小值加1：
- 上方格子的值（删除操作）
- 左方格子的值（插入操作）
- 左上方格子的值加上当前字符是否相等的标记（替换或匹配）
结果：最终 d[m,n] 即为两个字符串的莱文斯坦距离。

C# 代码实现

在实际应用中，直接比较原始字符串可能受到无关数据（如随机数字、ID等）的干扰。为了提高相似性计算的准确性，通常会在预处理阶段对数据进行清洗。以下代码展示了如何在 C# 中实现这一过程，包含了数字标准化处理和核心的距离计算逻辑。

using System;
using System.Text.RegularExpressions;

namespace StringSimilarity
{
    public class LDMaker
    {
        private char[] str1;
        private char[] str2;

        // 构造函数：接收两个字符串并进行预处理
        public LDMaker(string s1, string s2)
        {
            // 预处理：将所有数字替换为 "1"，减少数字噪声对相似性判断的干扰
            // 例如：在中文文本比对中，随机生成的数字可能导致误判
            s1 = Regex.Replace(s1, @"(\d+)", "1");
            s2 = Regex.Replace(s2, @"(\d+)", "1");

            str1 = s1.ToCharArray();
            str2 = s2.ToCharArray();
        }

        // 计算莱文斯坦距离
        public int GetLD()
        {
            try
            {
                int m = str1.Length; // 字符串1的长度
                int n = str2.Length; // 字符串2的长度

                // 创建二维数组存储中间结果
                // d[i, j] 表示 str1[0..i-1] 与 str2[0..j-1] 的距离
                int[,] d = new int[m + 1, n + 1];

                // 初始化边界条件
                for (int i = 0; i <= m; i++)
                    d[i, 0] = i;
                for (int j = 0; j <= n; j++)
                    d[0, j] = j;

                // 动态规划填表
                for (int i = 1; i <= m; i++)
                {
                    for (int j = 1; j <= n; j++)
                    {
                        // 如果字符相同，cost为0，否则为1
                        int cost = (str1[i - 1] == str2[j - 1]) ? 0 : 1;

                        // 三种操作：删除(d[i-1,j]+1), 插入(d[i,j-1]+1), 替换/匹配(d[i-1,j-1]+cost)
                        d[i, j] = Math.Min(Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1), d[i - 1, j - 1] + cost);
                    }
                }

                return d[m, n];
            }
            catch (Exception)
            {
                // 异常情况返回一个大数，表示无法计算或极度不相似
                return 10000;
            }
        }
    }
}

如何使用与优化建议

调用上述类非常简单，只需实例化 LDMaker 并传入两个待比较的字符串即可获取距离值。

string textA = "Hello World 123";
string textB = "Hello World 456";

LDMaker ld = new LDMaker(textA, textB);
int distance = ld.GetLD();
Console.WriteLine($"莱文斯坦距离: {distance}");

注意事项：