C# 实现基于编辑距离的字符串相似度对比类

设计思路与核心逻辑

该实现的核心在于动态规划。对于长度为 $M$ 和 $N$ 的两个字符串，初始化一个 $(M+1) \times (N+1)$ 的整数矩阵。矩阵中的每个单元格代表前缀子串之间的最小编辑步数：

• 状态转移：若当前字符相同，代价为左上角的值；若不同，则取“上方+1”、“左方+1”或“左上方+1”中的最小值。
• 相似率公式：相似度 $= 1 - (差异步数 / \max(长度))$。当差异步数为 0 时，结果为完全一致（Rate = 1）。

第 1 步：获取源码定义

首先确保项目中引用了必要的命名空间。以下代码定义了负责运算的主类 StringCompute 以及用于接收结果的结构体 Result。请将此段代码保存至您的项目中。

using System;
using System.Collections.Generic;
using System.Text;

public class StringCompute
{
  #region 私有变量
  private char[] _ArrChar1;
  private char[] _ArrChar2;
  private Result _Result;
  private DateTime _BeginTime;
  private DateTime _EndTime;
  private int _ComputeTimes;
  private int[,] _Matrix;
  private int _Column;
  private int _Row;
  #endregion

  #region 属性
  public Result ComputeResult
  {
    get { return _Result; }
  }
  #endregion

  #region 构造函数
  public StringCompute(string str1, string str2)
  {
    this.StringComputeInit(str1, str2);
  }
  public StringCompute()
  {
  }
  #endregion

  #region 算法实现
  /// 

  /// 初始化算法基本信息
  /// 
  private void StringComputeInit(string str1, string str2)
  {
    _ArrChar1 = str1.ToCharArray();
    _ArrChar2 = str2.ToCharArray();
    _Result = new Result();
    _ComputeTimes = 0;
    _Row = _ArrChar1.Length + 1;
    _Column = _ArrChar2.Length + 1;
    _Matrix = new int[_Row, _Column];
  }

  /// 

  /// 计算相似度（包含耗时统计）
  /// 
  public void Compute()
  {
    _BeginTime = DateTime.Now;
    InitMatrix();
    int intCost = 0;
    for (int i = 1; i < _Row; i++)
    {
      for (int j = 1; j < _Column; j++)
      {
        if (_ArrChar1[i - 1] == _ArrChar2[j - 1])
          intCost = 0;
        else
          intCost = 1;
        _Matrix[i, j] = Minimum(_Matrix[i - 1, j] + 1, 
                                _Matrix[i, j - 1] + 1, 
                                _Matrix[i - 1, j - 1] + intCost);
        _ComputeTimes++;
      }
    }
    _EndTime = DateTime.Now;
    
    // 计算逻辑：相似度 = 1 - (最小编辑距离 / 最长字符串长度)
    int intLength = _Row > _Column ? _Row : _Column;
    _Result.Rate = (1 - (decimal)_Matrix[_Row - 1, _Column - 1] / intLength);
    _Result.UseTime = (_EndTime - _BeginTime).ToString();
    _Result.ComputeTimes = _ComputeTimes.ToString();
    _Result.Difference = _Matrix[_Row - 1, _Column - 1];
  }

  /// 

  /// 快速计算（不记录时间开销）
  /// 
  public void SpeedyCompute()
  {
    InitMatrix();
    int intCost = 0;
    for (int i = 1; i < _Row; i++)
    {
      for (int j = 1; j < _Column; j++)
      {
        if (_ArrChar1[i - 1] == _ArrChar2[j - 1])
          intCost = 0;
        else
          intCost = 1;
        _Matrix[i, j] = Minimum(_Matrix[i - 1, j] + 1, 
                                _Matrix[i, j - 1] + 1, 
                                _Matrix[i - 1, j - 1] + intCost);
        _ComputeTimes++;
      }
    }
    int intLength = _Row > _Column ? _Row : _Column;
    _Result.Rate = (1 - (decimal)_Matrix[_Row - 1, _Column - 1] / intLength);
    _Result.ComputeTimes = _ComputeTimes.ToString();
    _Result.Difference = _Matrix[_Row - 1, _Column - 1];
  }

  /// 

  /// 重载：直接传入字符串进行计算
  /// 
  public void Compute(string str1, string str2)
  {
    this.StringComputeInit(str1, str2);
    this.Compute();
  }

  /// 

  /// 重载：直接传入字符串进行快速计算
  /// 
  public void SpeedyCompute(string str1, string str2)
  {
    this.StringComputeInit(str1, str2);
    this.SpeedyCompute();
  }

  private void InitMatrix()
  {
    for (int i = 0; i < _Column; i++) _Matrix[0, i] = i;
    for (int i = 0; i < _Row; i++) _Matrix[i, 0] = i;
  }

  private int Minimum(int First, int Second, int Third)
  {
    int intMin = First;
    if (Second < intMin) intMin = Second;
    if (Third < intMin) intMin = Third;
    return intMin;
  }
  #endregion
}

/// 

/// 封装计算结果的数据结构
/// 
public struct Result
{
  public decimal Rate;         // 相似度比例
  public string ComputeTimes;  // 遍历次数
  public string UseTime;       // 耗时描述字符串
  public int Difference;       // 最小编辑距离
}

第 2 步：在业务场景中调用

根据你的需求选择是否追踪性能（耗时）。以下是标准的调用示例，展示了实例化对象、触发计算以及提取关键数据的步骤。

// --- 方式一：仅关注结果，忽略计时开销 ---
StringCompute compute1 = new StringCompute();
compute1.SpeedyCompute("测试文本A", "测试文本B"); 

// 获取相似度，范围通常为 0.0 ~ 1.0
decimal similarityRate = compute1.ComputeResult.Rate;


// --- 方式二：记录具体执行耗时 ---
StringCompute compute2 = new StringCompute();
compute2.Compute("待对比内容1", "待对比内容2"); 

// 提取耗时信息
string timeConsumption = compute2.ComputeResult.UseTime;

完成判断与维护说明

当运行代码后，可以通过访问 ComputeResult.Rate 确认结果。如果两字符串完全相同，该值为 1；若完全不同且无重合部分，该值随字符串长度增加而逐渐趋近于 0。
在使用此类时，请注意：当需要处理极长文本（如超过几千字符）时，频繁的矩阵运算可能会成为性能瓶颈。建议在这种情况下先对长文本进行分块截取，或使用缓存策略优化重复比对的场景。

以上就是C#实现的字符串相似度对比类的详细内容，更多关于C#编程的资料请关注本站其它相关文章！