字符串相似度匹配算法
rehoni / 2021-10-11
相似度匹配算法
常见的字符串相似度算法包括编辑距离算法（EditDistance），n-gram算法，JaroWinkler算法以及Soundex算法。本文接下来大略的介绍一下这几种算法，有兴趣的读者可以在互联网找到一些更详细的资料。
最常见的相似度算法为编辑距离算法（EditDistance），该算法将两个字符串的相似度问题，归结为将其中一个字符串转化成另一个字符串所要付出的代价。转化的代价越高，说明两个字符串的相似度越低。通常可以选择的转化方式包含插入，替换以及删除。
N-Gram算法则是基于这样的一个假设： 即在字符串中第n个词的出现只与前面n-1个词相关，而与其他任何词都不相关，整个字符串出现的概率就是各个词出现的概率的乘积。 N-gram本身也代表目标字符串中长度为n的子串，举例，“ARM”在“ARMY”中，便是一个3-gram。当两个字符串中，相同的n-gram越多时，两个字串就会被认为更加相似。
Jaro Winkler则是将n-gram算法更进了一步。将n-gram中的不匹配的部分同时进行了换位的考虑，使得能获得更准确的相似程度。JaroWinkler在比较两个较短字符串的情况下，能够取得很好的结果。
Soundex算法与前面几种都不太相同。该算法的特点是，它所关注的问题并非两个字符串文本上的相似程度，而是发音的近似。首先，该算法会将两个字符串分别通过一定的hash算法转换成一个hash值，该值由四个字符构成，第一个字符为英文字母，后面三个为数字。进行转化的hash算法并非随机选取，而是利用了该拉丁文字符串的读音近似值。
当获得了两个字符串的读音上的hash值之后，该算法再对两个hash的相似度进行计算，便可以得出输入字符串的读音相似度。
Soundex算法的另一个应用场景在于，用户进行模糊查询时，可以通过Soundex值进行过滤，以提高查询性能。
Levenshtein Distance算法
In this article, we describe the Levenshtein distance, alternatively known as the Edit distance. The algorithm explained here was devised by a Russian scientist, Vladimir Levenshtein, in 1965.
Levenshtein Distance，也叫编辑距离，是一种度量两个序列(字符串)差异大小的方法。
两个序列(以单词为例，这里序列也可以表示一个句子)的Levenshtein distance是在使用一个单词修改为另一个单词时，通过编辑单个字符(如插入，删除，修改)所需要的最小次数。
通常允许三种类型的编辑：
- 插入字符c
- 删除字符c
- 字符c与c’ 替换
We know that at the end of the transformation, both Strings will be of equal length and have matching characters at each position. So, if we consider the first character of each String, we’ve got three options:Substitution:Determine the cost (D1) of substituting x[1] with y[1]. The cost of this step would be zero if both characters are same. If not, then the cost would be oneAfter step 1.1, we know that both Strings start with the same character. Hence the total cost would now be the sum of the cost of step 1.1 and the cost of transforming the rest of the String x[2:m] into y[2:n]Insertion:Insert a character in x to match the first character in y, the cost of this step would be oneAfter 2.1, we have processed one character from y. Hence the total cost would now be the sum of the cost of step 2.1 (i.e., 1) and the cost of transforming the full x[1:m] to remaining y (y[2:n])Deletion:Delete the first character from x, the cost of this step would be oneAfter 3.1, we have processed one character from x, but the full y remains to be processed. The total cost would be the sum of the cost of 3.1 (i.e., 1) and the cost of transforming remaining x to the full y
代码实现：在这里我使用java代码实现。在这里通过similarCalc来通过double的方式来计算最接近（最大的）的字符串。
部分工具函数
public static int costOfSubstitution(char a, char b) {
return a == b ? 0 : 1;
}
private static int min(int... numbers) {
return Arrays.stream(numbers).min().orElse(Integer.MAX_VALUE);
}
public static double similarCalc(String x, String y) {
int value = calculate2(x, y);
return 1 - (double) value / Math.max(x.length(), y.length());
}
递归版本
/**
* 递归法
*
* @param x 输入
* @param y 比较
* @return int 返回的距离
*/
static int calculate(String x, String y) {
if (x.isEmpty()) {
return y.length();
}
if (y.isEmpty()) {
return x.length();
}
int substitution = calculate(x.substring(1), y.substring(1))
+ costOfSubstitution(x.charAt(0), y.charAt(0));
int insertion = calculate(x, y.substring(1)) + 1;
int deletion = calculate(x.substring(1), y) + 1;
return min(substitution, insertion, deletion);
}
动态规划版本
/**
* 动态规划法
*
* @param x 输入
* @param y 比较
* @return int 返回的距离
*/
static int calculate2(String x, String y) {
int[][] dp = new int[x.length() + 1][y.length() + 1];
for (int i = 0; i <= x.length(); i++) {
for (int j = 0; j <= y.length(); j++) {
if (i == 0) {
dp[i][j] = j;
} else if (j == 0) {
dp[i][j] = i;
} else {
dp[i][j] = min(dp[i - 1][j - 1]
+ costOfSubstitution(x.charAt(i - 1), y.charAt(j - 1)),
dp[i - 1][j] + 1,
dp[i][j - 1] + 1);
}
}
}
return dp[x.length()][y.length()];
}
参考
The Levenshtein Distance Algorithm