字符串相关算法(编辑距离，最大公共字串)C#实现版-编辑距离,最大公共字串,C#

易尔译科技致力于互联网高端应用软件以及自然语言处理项目研发。
团队TM群：18653820 技术成长QQ群：13554183

字符串相关算法(编辑距离，最大公共字串)C#实现版

Post by 54admin, 2009-8-4, Views:

1. Levenshtein Distance

该算法又称之为 "编辑距离"，用于计算两个字符串的相似程度。原理很简单，就是返回将第一个字符串转换(删除、插入、替换)成第二个字符串的编辑次数。次数越少，意味着字符串相似度越高。

算法原理：Wikipedia - Levenshtein distance 本文摘自：http://www.rainsts.net/article.asp?id=767

Step1:

　　人民共和时代
　 0, 0, 0, 0, 0, 0, 0
中 1, 0, 0, 0, 0, 0, 0
华 2, 0, 0, 0, 0, 0, 0
人 3, 0, 0, 0, 0, 0, 0
民 4, 0, 0, 0, 0, 0, 0
共 5, 0, 0, 0, 0, 0, 0
和 6, 0, 0, 0, 0, 0, 0
国 7, 0, 0, 0, 0, 0, 0

Step2:

　　人民共和时代
　 0, 1, 2, 3, 4, 5, 6
中 1, 0, 0, 0, 0, 0, 0
华 2, 0, 0, 0, 0, 0, 0
人 3, 0, 0, 0, 0, 0, 0
民 4, 0, 0, 0, 0, 0, 0
共 5, 0, 0, 0, 0, 0, 0
和 6, 0, 0, 0, 0, 0, 0
国 7, 0, 0, 0, 0, 0, 0

Step3:

　　人民共和时代
　 0, 1, 2, 3, 4, 5, 6
中 1, 1, 2, 3, 4, 5, 6
华 2, 2, 2, 3, 4, 5, 6
人 3, 2, 3, 3, 4, 5, 6
民 4, 3, 2, 3, 4, 5, 6
共 5, 4, 3, 2, 3, 4, 5
和 6, 5, 4, 3, 2, 3, 4
国 7, 6, 5, 4, 3, 3, 4

算法实现：

public static int LevenshteinDistance(string s1, string s2)
{
  if (s1 == s2)
    return 0;
  else if (String.IsNullOrEmpty(s1))
    return s2.Length;
  else if (String.IsNullOrEmpty(s2))
    return s1.Length;

  var m = s1.Length + 1;
  var n = s2.Length + 1;
  var d = new int[m, n];

  // Step1
  for (var i = 0; i < m; i++) d[i, 0] = i;

  // Step2
  for (var j = 0; j < n; j++) d[0, j] = j;

  // Step3
  for (var i = 1; i < m; i++)
  {
    for (var j = 1; j < n; j++)
    {
      var cost = s1[i - 1] == s2[j - 1] ? 0 : 1;

      var deletion = d[i - 1, j] + 1;
      var insertion = d[i, j - 1] + 1;
      var substitution = d[i - 1, j - 1] + cost;

      d[i, j] = Math.Min(Math.Min(deletion, insertion), substitution);
    }
  }

  return d[m - 1, n - 1];
}

2. LCS

LCS (Longest Common Subsequence) 算法用于找出两个字符串最长公共子串。

算法原理：

(1) 将两个字符串分别以行和列组成矩阵。
(2) 计算每个节点行列字符是否相同，如相同则为 1。
(3) 通过找出值为 1 的最长对角线即可得到最长公共子串。

　人民共和时代
中 0, 0, 0, 0, 0, 0
华 0, 0, 0, 0, 0, 0
人 1, 0, 0, 0, 0, 0
民 0, 1, 0, 0, 0, 0
共 0, 0, 1, 0, 0, 0
和 0, 0, 0, 1, 0, 0
国 0, 0, 0, 0, 0, 0

为进一步提升该算法，我们可以将字符相同节点(1)的值加上左上角(d[i-1, j-1])的值，这样即可获得最大公用子串的长度。如此一来只需以行号和最大值为条件即可截取最大子串。

　人民共和时代
中 0, 0, 0, 0, 0, 0
华 0, 0, 0, 0, 0, 0
人 1, 0, 0, 0, 0, 0
民 0, 2, 0, 0, 0, 0
共 0, 0, 3, 0, 0, 0
和 0, 0, 0, 4, 0, 0
国 0, 0, 0, 0, 0, 0

算法实现：

public static string LCS(string s1, string s2)
{
  if (s1 == s2)
    return s1;
  else if (String.IsNullOrEmpty(s1) || String.IsNullOrEmpty(s2))
    return null;

  var d = new int[s1.Length, s2.Length];

  var index = 0;
  var length = 0;

  for (int i = 0; i < s1.Length; i++)
  {
    for (int j = 0; j < s2.Length; j++)
    {
      // 左上角值
      var n = i - 1 >= 0 && j - 1 >= 0 ? d[i - 1, j - 1] : 0;

      // 当前节点值 = "1 + 左上角值" : "0"
      d[i, j] = s1[i] == s2[j] ? 1 + n : 0;

      // 如果是最大值，则记录该值和行号
      if (d[i, j] > length)
      {
        length = d[i, j];
        index = i;
      }
    }
  }

  return s1.Substring(index - length + 1, length);
}

---------------

Tags: 编辑距离最大公共字串 C#

分类:信息提取 | 评论:15 | 引用:0 | 点击这里获取该日志的TrackBack引用地址

上一篇：搜索引擎中的URL判断（URL消重）
下一篇：政府应对舆情危机办法（精简自政府如何应对“舆情危机”）

或许你还对下面的文章感兴趣

在C#中完成海量数据的批量插入和更新 (2009-6-25 17:1:56)
C#下从HTML文件生成DOM树 (2009-5-17 20:50:51)
C#在word文档中替换字符串 (2009-5-9 9:53:26)
C#取得MS Word的总页数 (2009-5-8 14:39:49)
用C#写一个会自删除（自杀,自复制）的程序 (2009-4-22 20:22:36)
使用C#获取USB设备（优盘）永久不变的物理序列号全部方案。 (2009-4-22 19:14:58)
c#与WMI使用技巧集 (2009-4-22 18:50:1)
C#实现的编辑距离算法代码类文件 (2009-4-21 17:38:35)
C#模拟Post和Get方式发送数据 (2009-4-21 17:27:43)

Comments

发表评论:

◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。