欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

字符串“编辑距离”(最大公共子串提取)

程序员文章站 2022-07-12 11:02:33
...

今天在群里聊天,提及了 "编辑距离" 算法。好久不用,重新练练手,免得日后用时乱找。 字符串“编辑距离”(最大公共子串提取)
            
    
    博客分类: 工具箱 算法J# 

1. Levenshtein Distance

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

算法原理:Wikipedia - Levenshtein distance

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

算法实现Code:

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

算法实现Code:

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);
}

相关标签: 算法 J#