1、编辑距离
编辑距离:是衡量两个字符串之间差异的度量,它表示将一个字符串转换为另一个字符串所需的最少编辑操作次数(插入、删除、替换)。
2、相似度
计算方法可以有多种,其中一种常见的方法是将编辑距离归一化为0到1之间的范围(归一化编辑距离(Normalized Edit Distance)),将编辑距离除以较长字符串的长度。这样可以将相似度表示为一个百分比,其中0表示完全不相似,1表示完全相似。
请注意,这种归一化方法并不是唯一的,也不适用于所有情况。在实际应用中,你可以根据具体需求选择适合的相似度计算方法。例如,Jaro-Winkler相似度算法和Cosine相似度算法等都是常用的字符串相似度计算方法,它们不一定使用编辑距离作为基础。
3、相似度分类、测试
- 归一化编辑距离(Normalized Edit Distance)
- Jaro-Winkler相似度
- 余弦相似度(Cosine Similarity)
3.1、归一化编辑距离(Normalized Edit Distance)
解释:常用的,将编辑距离归一化为0到1之间的范围
使用、测试
String str1 = "h1e2l3l4o"; String str2 = "ddddhello"; //归一化编辑距离 @Test void contextLoads() { // commons-text 包:根据编辑距离计算:相似度 int editDistance = LevenshteinDistance.getDefaultInstance().apply(str1, str2); double similarity = 1 - ((double) editDistance / Math.max(str1.length(), str2.length())); System.out.println("commons-text 包:Edit Distance: " + editDistance); System.out.println("commons-text 包:Similarity: " + similarity); }
- 结果
3.1.1、数据库Oracle/DM实现的归一化编辑距离
见:https://www.cnblogs.com/kakarotto-chen/p/17752256.html
测试
-- oracle/dm实现的归一化编辑距离SELECT UTL_MATCH.edit_distance_similarity ('h1e2l3l4o', 'ddddhello') AS similarity
- 结果
3.2、Jaro-Winkler相似度
解释:我也看不懂,自行取用:https://www.jianshu.com/p/a4af202cb702
使用、测试
String str1 = "h1e2l3l4o"; String str2 = "ddddhello"; //Jaro-Winkler相似度 @Test public void test03()throws Exception{ JaroWinklerSimilarity js = new JaroWinklerSimilarity(); System.out.println("Jaro-Winkler相似度: " + js.apply(str1, str2)); }
- 结果
3.2.1、oracle/dm实现的:Jaro-Winkler相似度算法
- 和Java中的一模一样
-- oracle/dm实现的:Jaro-Winkler相似度算法SELECT UTL_MATCH.JARO_WINKLER_SIMILARITY('h1e2l3l4o', 'ddddhello') AS JaroWinkler相似度;
3.3、余弦相似度(Cosine Similarity)
- 解释:我也看不懂,自行取用
余弦相似度(Cosine Similarity)是通过计算两个向量之间的夹角来衡量它们的相似度。在这种情况下,我们可以将字符串视为向量,其中每个字符对应一个维度。对于左边字符串"h1e2l3l4o"和右边字符串"hello",我们可以将它们表示为以下向量:左边字符串向量:[1, 2, 3, 4, 5]右边字符串向量:[1, 1, 1, 1, 1]为了计算余弦相似度,我们需要计算这两个向量的点积和它们的模长。点积表示两个向量之间的相似程度,模长表示向量的长度。左边字符串向量的模长:sqrt(1^2 + 2^2 + 3^2 + 4^2 + 5^2) = sqrt(55)右边字符串向量的模长:sqrt(1^2 + 1^2 + 1^2 + 1^2 + 1^2) = sqrt(5)左边字符串向量和右边字符串向量的点积:11 + 21 + 31 + 41 + 51 = 1 + 2 + 3 + 4 + 5 = 15根据余弦相似度的公式,余弦相似度可以计算为点积除以两个向量的模长的乘积:余弦相似度 = 点积 / (左边字符串向量的模长 右边字符串向量的模长)= 15 / (sqrt(55) sqrt(5))≈ 0.745因此,左边字符串"h1e2l3l4o"和右边字符串"hello"的余弦相似度约为0.745。
- 测试、使用
String str1 = "h1e2l3l4o"; String str2 = "ddddhello"; //余弦相似度 @Test public void test02()throws Exception{ // commons-text 包 // 使用Cosine计算两个字符串的余弦距离 CosineDistance cd = new CosineDistance(); Double apply = cd.apply(str2, str1); System.out.println("Cosine相似度:" + apply); }
- 结果:不知道对不对
4、总结
- 上述三种的简单介绍:
上述三种的简单介绍
- 其他相似度
1. 编辑距离(Edit Distance):衡量两个字符串之间的差异,通过计算插入、删除和替换操作的最小次数来确定相似度。2. Hamming距离(Hamming Distance):用于比较两个等长字符串之间的差异,计算在相同位置上不同字符的数量。3. Damerau-Levenshtein距离:类似于编辑距离,但允许交换相邻字符的操作。4. Jaccard相似度(Jaccard Similarity):用于比较集合之间的相似度,计算两个集合的交集与并集的比值。5. Sørensen-Dice相似度:类似于Jaccard相似度,但计算两个集合的两倍交集与两个集合的元素总数之和的比值。6. Smith-Waterman算法:用于比较两个字符串之间的相似性,主要用于序列比对和字符串匹配。7. Longest Common Subsequence(LCS):计算两个字符串之间最长公共子序列的长度,用于衡量字符串的相似性。8. N-gram相似度:将字符串分割为连续的N个字符片段,比较两个字符串之间的N-gram的相似性。9. Cosine相似度(余弦相似度):用于比较两个向量之间的夹角,常用于文本相似度计算。
- 都是使用:Apache Commons Text:1.11.0包
// 实现字符串相似度算法的包 implementation 'org.apache.commons:commons-text:1.11.0'