C#与SQL实现字符串相似度算法对比与应用

C# 实现：基于 Levenshtein 距离的动态规划算法

在 C# 开发中，计算字符串相似度最经典且准确的方法是编辑距离（Edit Distance）算法，特别是莱文斯坦距离（Levenshtein Distance）。该算法通过计算将一个字符串转换成另一个字符串所需的最少单字符编辑（插入、删除或替换）次数来衡量差异。相似度通常定义为：1 - (编辑距离 / 最大长度)。

第1步：初始化状态矩阵

首先需要获取两个输入字符串的长度，并创建一个二维整型数组 dif。该矩阵的行数为 str1.Length + 1，列数为 str2.Length + 1。初始化时，首行和首列分别填充其对应的索引值，这代表了从一个空字符串转换到当前前缀所需的删除或插入操作次数。

public static float Levenshtein(string str1, string str2)
{
    int len1 = str1.Length;
    int len2 = str2.Length;
    // 创建二维数组，多出一行一列用于处理空字符串边界条件
    int[,] dif = new int[len1 + 1, len2 + 1];

    // 初始化第一列：将空字符串变为 str1[0...i] 需要 i 次插入
    for (int a = 0; a <= len1; a++)
        dif[a, 0] = a;

    // 初始化第一行：将空字符串变为 str2[0...j] 需要 j 次插入
    for (int a = 0; a <= len2; a++)
        dif[0, a] = a;

第2步：填充动态规划矩阵

使用双重循环遍历两个字符串的每个字符。比较 str1[i-1] 与 str2[j-1]，若字符相同，则当前成本为左上角的值；若不同，则成本为左上角值加1。随后，取以下三个方向的最小值作为当前位置 dif[i, j] 的值：

• 左上角+代价：代表替换或匹配操作。
• 左侧+1：代表在 str2 中插入一个字符。
• 上方+1：代表在 str2 中删除一个字符（相对于 str1）。

    int temp;
    for (int i = 1; i <= len1; i++)
    {
        for (int j = 1; j <= len2; j++)
        {
            // 如果字符相同，temp为0（无额外代价），否则为1（替换代价）
            if (str1.Substring(i - 1, 1) == str2.Substring(j - 1, 1))
                temp = 0;
            else
                temp = 1;

            // 取三个可能来源中的最小值
            dif[i, j] = Min(dif[i - 1, j - 1] + temp,
                            dif[i, j - 1] + 1,
                            dif[i - 1, j] + 1);
        }
    }

第3步：计算最终相似度并返回结果

矩阵右下角的值 dif[len1, len2] 即为编辑距离。为了得到 0 到 1 之间的相似度分数，使用公式 1 - (编辑距离 / 较长字符串长度)。最后需要实现一个辅助函数 Min 来获取三个整数中的最小值。

    // 计算相似度
    return 1 - (float)dif[len1, len2] / Math.Max(str1.Length, str2.Length);
}

// 辅助函数：返回三个数中的最小值
private static int Min(int i, int j, int k)
{
    return i < j ? (i < k ? i : k) : (j < k ? j : k);
}

SQL 实现：基于子串匹配的自定义函数

在 SQL Server 中，可以通过创建自定义标量函数来实现字符串相似度计算。此示例采用了一种基于“连续子串匹配”的策略：提取两个字符串的所有长度大于等于2的子串，找出共同存在的子串，并根据最长共同子串的长度占整体最大长度的比例来估算相似度。

第1步：定义函数结构与变量初始化

函数接收两个 varchar(50) 参数，返回值为 nvarchar(4000)（实际存储百分比数值字符串）。内部声明了必要的计数器、最大长度变量以及两个临时表 @tb1 和 @tb2 用于存储子串。

CREATE FUNCTION get_semblance_By_2words 
(
    @word1 varchar(50), 
    @word2 varchar(50)  
) 
RETURNS nvarchar(4000) 
AS 
BEGIN
    DECLARE @re INT
    DECLARE @maxLenth INT
    DECLARE @i INT, @l INT
    DECLARE @tb1 TABLE(child VARCHAR(50)) 
    DECLARE @tb2 TABLE(child VARCHAR(50))
    
    SET @i=1
    SET @l=2
    SET @maxLenth=len(@word1)
    
    -- 确定两个字符串中较长的长度，用于后续分母计算
    IF len(@word1) < len(@word2) 
    BEGIN
        SET @maxLenth=len(@word2)
    END

第2步：生成并存储所有有效子串

使用嵌套 WHILE 循环遍历第一个字符串。外层循环控制子串长度 @l（从2开始），内层循环控制起始位置 @i。将提取出的子串插入临时表 @tb1。注意原始逻辑中内层循环条件可能存在截断风险，但在标准用法中通常旨在收集主要特征片段。

    -- 处理第一个字符串的子串
    WHILE @l <= len(@word1)  
    BEGIN 
        WHILE @i < len(@word1)-1 
        BEGIN 
            INSERT @tb1 (child) VALUES(SUBSTRING(@word1, @i, @l))
            SET @i=@i+1 
        END
        SET @i=1 
        SET @l=@l+1 
    END

    -- 重置指针以处理第二个字符串
    SET @i=1 
    SET @l=2 

    WHILE @l <= len(@word2)  
    BEGIN 
        WHILE @i < len(@word2)-1 
        BEGIN 
            INSERT @tb2 (child) VALUES(SUBSTRING(@word2, @i, @l))
            SET @i=@i+1 
        END
        SET @i=1 
        SET @l=@l+1 
    END  

第3步：匹配子串并计算相似度

通过连接两个临时表，查找共同存在的子串 a.child = b.child。计算最长共同子串长度的百分比作为相似度评分。如果没有任何匹配，默认返回0。

    SELECT @re=isnull(max(len(a.child)*100/@maxLenth),0) 
    FROM @tb1 a, @tb2 b 
    WHERE a.child=b.child 
    
    RETURN @re 
END
GO

第4步：测试调用示例

执行以下语句测试函数效果，例如比较“我是谁”和“我是谁啊”：

--select dbo.get_semblance_By_2words('我是谁','我是谁啊') --输出: 75

应用场景与建议

C# 算法优势：Levenshtein 算法是业界标准，能够精确捕捉字符级别的增删改变化，适合需要高精度模糊匹配的后端服务，如拼写检查、文档去重或敏感词过滤。
SQL 函数优势：该方法利用数据库自身的集合运算能力，减少了应用层与数据库之间的数据传输开销。如果在数据库中频繁进行大规模数据的比对查询，直接在 T-SQL 层实现可以避免网络往返延迟。然而，该 SQL 示例采用的是启发式子串匹配，而非严格的编辑距离，因此其结果可能与 C# 版本存在差异，更适合对“包含关系”敏感的粗略排序场景。

以上就是C#和SQL实现的字符串相似度计算的详细内容，更多关于编程技巧与数据库优化的资料请关注本站其它相关文章！