最短编辑距离算法（字符串比较）数据结构

一、编辑距离
1、从字符串a变为字符串b所需要的元操作有3种：

增加一个字符
删除一个字符
变化一个字符

【最短编辑距离算法（字符串比较）】2、编辑距离：从字符串a变为b所需要的最少操作步骤。
二、最短编辑距离（动态规划）
首先定义一个函数——step(i, j)，它表示第一个字符串的长度为i的子串到第二个字符串的长度为j的子串的编辑距离。
显然可以有如下动态规划公式：

if i == 0 且 j == 0，step(i, j) = 0
if i == 0 且 j > 0，step(i, j) = j
if i > 0 且j == 0，step(i, j) = i
if i ≥ 1且 j ≥ 1 ，step(i, j) == min{ step(i-1, j) + 1, step(i, j-1) + 1, step(i-1, j-1) + f(i, j) }，当第一个字符串的第i个字符不等于第二个字符串的第j个字符时，f(i, j) = 1；否则，f(i, j) = 0。

P1：初始化如下矩阵

文章图片

P2：计算step(1, 1)，step(0, 1) + 1 == 2，step(1, 0) + 1 == 2，step(0, 0) + f(1, 1) == 0 + 1 == 1，min(step(0, 1)，step(1, 0)，step(0, 0) + f(1, 1))==1，因此step(1, 1) == 1。依次类推：

文章图片

从上图可以看出从hug---->huge的最短编辑距离为1.Java实现如下：

/** * 最短编辑距离算法 */ public class Levenshtein { /** * 获取两字符串的相似度 * @param source 初始串 * @param target 比较串 * @return 相似度 */ public static float getSimilarityRatio(String source, String target) { return 1 - (float) compare(source, target) / Math.max(source.length(), target.length()); } private static int compare(String source, String target) {int matrix[][]; int n = source.length(); int m = target.length(); int i; //source索引 int j; //target索引 char ch1; char ch2; int temp; //记录相同字符,值为0/1if (n == 0) return m; if (m == 0) return n; matrix = new int[n + 1][m + 1]; for (i = 0; i <= n; i++) { //初始化第一列 matrix[i][0] = i; }for (j = 0; j <= m; j++) { //初始化第一行 matrix[0][j] = j; }for (i = 1; i <= n; i++) { //遍历source ch1 = source.charAt(i - 1); //匹配target for (j = 1; j <= m; j++) { ch2 = target.charAt(j - 1); if (ch1 == ch2) temp = 0; else temp = 1; //左+1,上+1,左上+temp 取最小 matrix[i][j] = min(matrix[i - 1][j] + 1, matrix[i][j - 1] + 1, matrix[i - 1][j - 1] + temp); } } return matrix[n][m]; } private static int min(int one, int two, int three) { return (one = one < two ? one : two) < three ? one : three; } public static void main(String[] args) { String source = "中国"; String target = "中国人"; System.out.println("similarityRatio=" + Levenshtein.getSimilarityRatio(source, target)); } }