一、编辑距离
1、从字符串a变为字符串b所需要的元操作有3种：
2、编辑距离：从字符串a变为b所需要的最少操作步骤。
二、最短编辑距离（动态规划）
首先定义一个函数——step(i, j)，它表示第一个字符串的长度为i的子串到第二个字符串的长度为j的子串的编辑距离。显然可以有如下动态规划公式：
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++) { //遍历sourcech1 = source.charAt(i – 1);//匹配targetfor (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));}}
你可以用爱得到全世界，你也可以用恨失去全世界
