编辑距离是指利用字符操作,把字符串A转换成字符串B所需要的最少操作数。在这里定义的单字符编辑操作有且仅有三种:
譬如,"kitten" 和 "sitting" 这两个单词,由 "kitten" 转换为 "sitting" 需要的最少单字符编辑操作有:
1.kitten → sitten (substitution of "s" for "k")
2.sitten → sittin (substitution of "i" for "e")
3.sittin → sitting (insertion of "g" at the end)
因此,"kitten" 和 "sitting" 这两个单词之间的编辑距离为 3 。
一般来说,两个字符串的编辑距离越小,则它们越相似。如果两个字符串相等,则它们的编辑距离(为了方便,本文后续出现的“距离”,如果没有特别说明,则默认为“编辑距离”)为0(不需要任何操作)。
不难分析出,两个字符串的编辑距离肯定不超过它们的最大长度(可以通过先把短串的每一位都修改成长串对应位置的字符,然后插入长串中的剩下字符)。
给定两个字符串A和B,求字符串A至少经过多少步字符操作变成字符串B。
f(i,j) = max(i,j) if i与j其中一个为0<br>
f(i,j) = f(i-1,j-1) if a[i]=a[j]
f(i,j) = min (f(i-1,j-1) + 1,
f(i, j-1) + 1,
f(i-1, j) + 1);
这是一个动态规划问题.使用公式我们可以很快写出递归方法
public static int getEditDistanceByRecursion(String a, String b, int aIndex, int bIntex) {
if (Math.min(aIndex, bIntex) == 0) {
return Math.max(aIndex, bIntex);
}
if (a.charAt(aIndex) == b.charAt(bIntex)) {
return getEditDistanceByRecursion(a, b, aIndex - 1, bIntex - 1);
}
return Math.min(getEditDistanceByRecursion(a, b, aIndex - 1, bIntex - 1) + 1,
Math.min(getEditDistanceByRecursion(a, b, aIndex, bIntex - 1) + 1,
getEditDistanceByRecursion(a, b, aIndex - 1, bIntex) + 1));
}
但是递归的最大缺点为重复计算. 多次计算同一个结果. 我们需要一个表来存储重复计算的结果.
代码如下
public static int getEditDistance(String origin, String target) {
if (TextUtils.isEmpty(origin) && TextUtils.isEmpty(target)) {
return 0;
}
if (TextUtils.isEmpty(origin)) {
return target.length();
}
if (TextUtils.isEmpty(target)) {
return origin.length();
}
int[][] dp = new int[origin.length() + 1][target.length() + 1];
for (int i = 0; i <= origin.length(); i++) {
dp[i][0] = i;
}
for (int j = 0; j <= target.length(); j++) {
dp[0][j] = j;
}
for (int i = 1; i <= origin.length(); i++) {
for (int j = 1; j <= target.length(); j++) {
if (origin.charAt(i - 1) == target.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
dp[i][j] = Math.min(dp[i][j], Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
}
}
return dp[origin.length()][target.length()];
}
如果我们需要求两个字符串的相识度,则是:
public static float getSimilarity(String origin, String target) {
if (TextUtils.isEmpty(origin) || TextUtils.isEmpty(target)) {
return 0f;
}
return 1.0f - getEditDistance(origin, target) / (float) Math.max(origin.length(), target.length());
}
应用与思考 编辑距离是NLP基本的度量文本相似度的算法,可以作为文本相似任务的重要特征之一,其可应用于诸如拼写检查、论文查重、基因序列分析等多个方面。但是其缺点也很明显,算法基于文本自身的结构去计算,并没有办法获取到语义层面的信息。
由于需要利用矩阵,故空间复杂度为O(MN)。这个在两个字符串都比较短小的情况下,能获得不错的性能。不过,如果字符串比较长的情况下,就需要极大的空间存放矩阵。例如:两个字符串都是20000字符,则 LD 矩阵的大小为:20000 * 20000 * 2=800000000 Byte=800MB。
[1] https://blog.csdn.net/ghsau/article/details/78903076 [2] https://en.wikipedia.org/wiki/Levenshtein_distance [3] https://www.dreamxu.com/books/dsa/dp/edit-distance.html [4] https://www.jianshu.com/p/a96095aa92bc [5] https://www.jianshu.com/p/a617d20162cf