首页 > 代码库 > C#实现Levenshtein distance最小编辑距离算法
C#实现Levenshtein distance最小编辑距离算法
Levenshtein distance,中文名为最小编辑距离,其目的是找出两个字符串之间需要改动多少个字符后变成一致。该算法使用了动态规划的算法策略,该问题具备最优子结构,最小编辑距离包含子最小编辑距离,有下列的公式。
其中d[i-1,j]+1代表字符串s2插入一个字母才与s1相同,d[i,j-1]+1代表字符串s1删除一个字母才与s2相同,然后当xi=yj时,不需要代价,所以和上一步d[i-1,j-1]代价相同,否则+1,接着d[i,j]是以上三者中最小的一项。
算法实现(C#):
假设两个字符串分别为source,target,其长度分别为columnSize,rowSize,首先申请一个(columnSize+1)*(rowSize+1)大小的矩阵,然后将第一行和第一列初始化,matrix[i,0]=i,matrix[0,j]=j,接着就按照公式求出矩阵中其他元素,结束后,两个字符串之间的编辑距离就是matrix[rowSize, columnSize]的值,代码如下:
public class StringComparator { public static int LevenshteinDistance(string source, string target) { int columnSize = source.Length; int rowSize = target.Length; if (columnSize == 0) { return rowSize; } if (rowSize == 0) { return columnSize; }
int[,] matrix = new int[rowSize + 1, columnSize + 1]; for (int i = 0; i <= columnSize; i++) { matrix[0, i] = i; } for (int j = 1; j <= rowSize; j++) { matrix[j, 0] = j; }
for (int i = 0; i < rowSize; i++) { for (int j = 0; j < columnSize; j++) { int sign; if (source[j].Equals(target[i])) sign= 0; else sign = 1; matrix[i + 1, j + 1] = Math.Min(Math.Min(matrix[i, j] + sign, matrix[i + 1, j]), matrix[i, j + 1] + 1); } } return matrix[rowSize, columnSize]; } public static float StringSimilarity(string source, string target) { int distance = LevenshteinDistance(source, target); float maxLength = Math.Max(source.Length, target.Length); return (maxLength - distance) / maxLength; } }
C#实现Levenshtein distance最小编辑距离算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。