java string similarity
v2.0.0
实现不同字符串相似性和距离度量的库。目前已实现了十几种算法（包括 Levenshtein 编辑距离和兄弟姐妹、Jaro-Winkler、最长公共子序列、余弦相似度等）。查看下面的汇总表以获取完整列表...
使用maven：
<dependency>
<groupId>info.debatty</groupId>
<artifactId>java-string-similarity</artifactId>
<version>RELEASE</version>
</dependency>
或者检查版本。
该库需要 Java 8 或更高版本。
下面介绍了每种实现算法的主要特征。 “成本”列给出了分别计算长度为 m 和 n 的两个字符串之间的相似度的计算成本的估计。
| 标准化？ | 公制？ | 类型 | 成本 | 典型用法 | ||
|---|---|---|---|---|---|---|
| 编辑 | 距离 | 不 | 是的 | O(m*n) 1 | ||
| 标准化编辑 | 距离 相似 | 是的 | 不 | O(m*n) 1 | ||
| 加权编辑 | 距离 | 不 | 不 | O(m*n) 1 | 光学字符识别 | |
| 达默劳-莱文斯坦3 | 距离 | 不 | 是的 | O(m*n) 1 | ||
| 最佳字符串对齐3 | 距离 | 不 | 不 | O(m*n) 1 | ||
| 贾罗-温克勒 | 相似 距离 | 是的 | 不 | O(m*n) | 错字更正 | |
| 最长公共子序列 | 距离 | 不 | 不 | O(m*n) 1,2 | diff 实用程序、GIT 协调 | |
| 度量最长公共子序列 | 距离 | 是的 | 是的 | O(m*n) 1,2 | ||
| N-Gram | 距离 | 是的 | 不 | O(m*n) | ||
| Q-Gram | 距离 | 不 | 不 | 轮廓 | O(m+n) | |
| 余弦相似度 | 相似 距离 | 是的 | 不 | 轮廓 | O(m+n) | |
| 杰卡德指数 | 相似 距离 | 是的 | 是的 | 放 | O(m+n) | |
| 索伦森-戴斯系数 | 相似 距离 | 是的 | 不 | 放 | O(m+n) | |
| 拉特克利夫-奥伯斯赫普 | 相似 距离 | 是的 | 不 | ？ |
[1] 在该库中，Levenshtein 编辑距离、LCS 距离及其同级是使用动态规划方法计算的，其成本为 O(mn)。对于 Levenshtein 距离，该算法有时称为Wagner-Fischer 算法（“字符串到字符串校正问题”，1974）。原始算法使用大小为 mxn 的矩阵来存储字符串前缀之间的编辑距离。
如果字母表是有限的，可以使用四位俄罗斯人的方法（Arlazarov et al.“On Economic Construction of the Transitive Close of a有向图”，1970）来加速计算。这是由 Masek 于 1980 年出版的（“计算字符串编辑距离的更快算法”）。该方法将矩阵分割为大小为 tx t 的块。每个可能的块都会被预先计算以生成一个查找表。然后可以使用该查找表来计算字符串相似度（或距离），单位为 O(nm/t)。通常，如果 m > n，则 t 被选择为 log(m)。因此，最终的计算成本为 O(mn/log(m))。此方法尚未实施（尚未）。
[2] 在“最大公共子序列的长度”中，KS Larsen 提出了一种在时间 O(log(m).log(n)) 内计算 LCS 长度的算法。但该算法的内存需求为 O(m.n²)，因此此处未实现。
[3] Damerau-Levenshtein 字符串距离有两种变体：相邻换位的 Damerau-Levenshtein（有时也称为无限制的 Damerau-Levenshtein 距离）和最佳字符串对齐（有时也称为限制编辑距离）。为了实现最佳字符串对齐，任何子字符串都不能编辑多次。
尽管该主题看起来很简单，但存在许多不同的算法来测量文本相似度或距离。因此该库定义了一些接口来对它们进行分类。
通常，实现 NormalizedStringSimilarity 的算法也会实现 NormalizedStringDistance，并且相似度 = 1 - 距离。但也有一些例外，例如 N-Gram 相似度和距离 (Kondrak)...
MetricStringDistance 接口：一些距离实际上是公制距离，这意味着验证三角形不等式 d(x, y) <= d(x,z) + d(z,y)。例如，Levenshtein 是公制距离，但 NormalizedLevenshtein 不是。
许多最近邻搜索算法和索引结构都依赖于三角不等式。您可以查看 Zezula 等人的“相似性搜索，度量空间方法”。进行调查。这些不能与非度量相似性度量一起使用。
阅读 Javadoc 了解详细说明
一些算法的工作原理是将字符串转换为 n-gram 集合（n 个字符的序列，有时也称为 k-shingles）。字符串之间的相似度或距离就是集合之间的相似度或距离。
其中一些，例如 Jaccard，将字符串视为木瓦的集合，并且不考虑每个木瓦出现的次数。其他方法（如余弦相似度）则使用有时称为字符串轮廓的方法，该轮廓考虑了每个木瓦出现的次数。
对于这些算法，在处理大型数据集时可能存在另一种用例：
两个单词之间的编辑距离是将一个单词更改为另一个单词所需的最小单字符编辑（插入、删除或替换）次数。
它是公制字符串距离。该实现使用动态规划（Wagner-Fischer 算法），只有 2 行数据。因此，空间需求为 O(m)，算法运行时间为 O(mn)。
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
Levenshtein l = new Levenshtein ();
System . out . println ( l . distance ( "My string" , "My $tring" ));
System . out . println ( l . distance ( "My string" , "My $tring" ));
System . out . println ( l . distance ( "My string" , "My $tring" ));
}
}该距离的计算方式为编辑距离除以最长字符串的长度。结果值始终在 [0.0 1.0] 区间内，但它不再是一个度量！
相似度计算为 1 - 归一化距离。
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
NormalizedLevenshtein l = new NormalizedLevenshtein ();
System . out . println ( l . distance ( "My string" , "My $tring" ));
System . out . println ( l . distance ( "My string" , "My $tring" ));
System . out . println ( l . distance ( "My string" , "My $tring" ));
}
}Levenshtein 的实现，允许为不同的字符替换定义不同的权重。
该算法通常用于光学字符识别 (OCR) 应用。对于 OCR，替换 P 和 R 的成本低于替换 P 和 M 的成本，因为从 OCR 的角度来看，P 与 R 相似。
它还可用于键盘输入自动更正。例如，此处替换 E 和 R 的成本较低，因为它们在 AZERTY 或 QWERTY 键盘上彼此相邻。因此，用户输错字符的可能性较高。
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
WeightedLevenshtein wl = new WeightedLevenshtein (
new CharacterSubstitutionInterface () {
public double cost ( char c1 , char c2 ) {
// The cost for substituting 't' and 'r' is considered
// smaller as these 2 are located next to each other
// on a keyboard
if ( c1 == 't' && c2 == 'r' ) {
return 0.5 ;
}
// For most cases, the cost of substituting 2 characters
// is 1.0
return 1.0 ;
}
});
System . out . println ( wl . distance ( "String1" , "Srring2" ));
}
}与 Levenshtein 类似，转置的 Damerau-Levenshtein 距离（有时也称为无限制的 Damerau-Levenshtein 距离）是将一个字符串转换为另一个字符串所需的最少操作数，其中操作定义为插入、删除或替换单个字符，或两个相邻字符的转置。
它确实尊重三角不等式，因此是公制距离。
不要将其与最佳字符串对齐距离混淆，最佳字符串对齐距离是一个扩展，其中任何子字符串都不能被编辑多次。
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
Damerau d = new Damerau ();
// 1 substitution
System . out . println ( d . distance ( "ABCDEF" , "ABDCEF" ));
// 2 substitutions
System . out . println ( d . distance ( "ABCDEF" , "BACDFE" ));
// 1 deletion
System . out . println ( d . distance ( "ABCDEF" , "ABCDE" ));
System . out . println ( d . distance ( "ABCDEF" , "BCDEF" ));
System . out . println ( d . distance ( "ABCDEF" , "ABCGDEF" ));
// All different
System . out . println ( d . distance ( "ABCDEF" , "POIU" ));
}
}将产生：
1.0
2.0
1.0
1.0
1.0
6.0
Damerau-Levenshtein 的最佳字符串对齐变体（有时称为受限编辑距离）计算在没有子字符串被编辑超过一次的情况下使字符串相等所需的编辑操作数，而真正的 Damerau-Levenshtein 则不存在这样的情况限制。与编辑距离算法的区别在于为转置操作添加了一次递归。
请注意，对于最佳字符串对齐距离，三角形不等式不成立，因此它不是真正的度量。
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
OptimalStringAlignment osa = new OptimalStringAlignment ();
System . out . println ( osa . distance ( "CA" , "ABC" ));;
}
}将产生：
3.0
Jaro-Winkler 是在记录链接（重复检测）领域开发的字符串编辑距离（Winkler，1990）。 Jaro-Winkler 距离度量经过专门设计，最适合短字符串（例如人名）以及检测换位拼写错误。
Jaro-Winkler 计算 2 个字符串之间的相似度，返回值位于区间 [0.0, 1.0] 内。它（大致）是 Damerau-Levenshtein 的变体，其中 2 个接近的字符的换位被认为不如 2 个彼此远离的字符的换位重要。 Jaro-Winkler 对不能表示为换位的添加或替换进行惩罚。
距离计算为 1 - Jaro-Winkler 相似度。
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
JaroWinkler jw = new JaroWinkler ();
// substitution of s and t
System . out . println ( jw . similarity ( "My string" , "My tsring" ));
// substitution of s and n
System . out . println ( jw . similarity ( "My string" , "My ntrisg" ));
}
}将产生：
0.9740740656852722
0.8962963223457336
最长公共子序列（LCS）问题在于找到两个（或更多）序列的最长公共子序列。它与查找公共子串的问题不同：与子串不同，子序列不需要占据原始序列中的连续位置。
它被 diff 实用程序、Git 用于协调多个更改等使用。
字符串 X（长度为 n）和 Y（长度为 m）之间的 LCS 距离为 n + m - 2 |LCS(X, Y)|最小值 = 0 最大值 = n + m
当只允许插入和删除（不允许替换），或者替换成本是插入或删除成本的两倍时，LCS 距离相当于 Levenshtein 距离。
该类实现了动态规划方法，其空间需求为 O(mn)，计算成本为 O(mn)。
在“最大公共子序列的长度”中，KS Larsen 提出了一种在 O(log(m).log(n)) 时间内计算 LCS 长度的算法。但该算法的内存需求为 O(m.n²)，因此此处未实现。
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
LongestCommonSubsequence lcs = new LongestCommonSubsequence ();
// Will produce 4.0
System . out . println ( lcs . distance ( "AGCAT" , "GAC" ));
// Will produce 1.0
System . out . println ( lcs . distance ( "AGCAT" , "AGCT" ));
}
}基于最长公共子序列的距离度量，来自 Daniel Bakkelund 的笔记“An LCS-based string metric”。 http://heim.ifi.uio.no/~danielry/StringMetric.pdf
距离计算为 1 - |LCS(s1, s2)| / 最大值（|s1|，|s2|）
public class MyApp {
public static void main ( String [] args ) {
info . debatty . java . stringsimilarity . MetricLCS lcs =
new info . debatty . java . stringsimilarity . MetricLCS ();
String s1 = "ABCDEFG" ;
String s2 = "ABCDEFHJKL" ;
// LCS: ABCDEF => length = 6
// longest = s2 => length = 10
// => 1 - 6/10 = 0.4
System . out . println ( lcs . distance ( s1 , s2 ));
// LCS: ABDF => length = 4
// longest = ABDEF => length = 5
// => 1 - 4 / 5 = 0.2
System . out . println ( lcs . distance ( "ABDEF" , "ABDIF" ));
}
}Kondrak 定义的归一化 N 元语法距离，“N 元语法相似性和距离”，字符串处理和信息检索，计算机科学讲义第 3772 卷，2005 年，第 115-126 页。
http://webdocs.cs.ualberta.ca/~kondrak/papers/spire05.pdf
该算法使用附加特殊字符“n”来增加第一个字符的权重。通过将总相似度得分除以最长单词的原始长度来实现归一化。
在论文中，Kondrak 还定义了一个相似性度量，但尚未实现。
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
// produces 0.583333
NGram twogram = new NGram ( 2 );
System . out . println ( twogram . distance ( "ABCD" , "ABTUIO" ));
// produces 0.97222
String s1 = "Adobe CreativeSuite 5 Master Collection from cheap 4zp" ;
String s2 = "Adobe CreativeSuite 5 Master Collection from cheap d1x" ;
NGram ngram = new NGram ( 4 );
System . out . println ( ngram . distance ( s1 , s2 ));
}
}一些算法的工作原理是将字符串转换为 n-gram 集合（n 个字符的序列，有时也称为 k-shingles）。字符串之间的相似度或距离就是集合之间的相似度或距离。
计算这些相似性和距离的成本主要由 k-shingling（将字符串转换为 k 个字符的序列）决定。因此，这些算法通常有两种用例：
直接计算字符串之间的距离：
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
QGram dig = new QGram ( 2 );
// AB BC CD CE
// 1 1 1 0
// 1 1 0 1
// Total: 2
System . out . println ( dig . distance ( "ABCD" , "ABCE" ));
}
}或者，对于大型数据集，预先计算所有字符串的配置文件。然后可以计算配置文件之间的相似性：
import info . debatty . java . stringsimilarity . KShingling ;
import info . debatty . java . stringsimilarity . StringProfile ;
/**
* Example of computing cosine similarity with pre-computed profiles.
*/
public class PrecomputedCosine {
public static void main ( String [] args ) throws Exception {
String s1 = "My first string" ;
String s2 = "My other string..." ;
// Let's work with sequences of 2 characters...
Cosine cosine = new Cosine ( 2 );
// Pre-compute the profile of strings
Map < String , Integer > profile1 = cosine . getProfile ( s1 );
Map < String , Integer > profile2 = cosine . getProfile ( s2 );
// Prints 0.516185
System . out . println ( cosine . similarity ( profile1 , profile2 ));
}
}请注意，这仅在使用相同的 KShingling 对象来解析所有输入字符串时才有效！
Q-gram 距离，由 Ukkonen 在“使用 q-gram 和最大匹配进行近似字符串匹配”中定义：http://www.sciencedirect.com/science/article/pii/0304397592901434
两个字符串之间的距离定义为其轮廓差异的 L1 范数（每个 n 元词出现的次数）：SUM( |V1_i - V2_i| )。 Q-gram 距离是 Levenshtein 距离的下界，但可以在 O(m + n) 中计算，其中 Levenshtein 需要 O(mn)
两个字符串之间的相似度是这两个向量表示之间的角度的余弦，并计算为 V1 。 V2 / (|V1| * |V2|)
距离计算为 1 - 余弦相似度。
与 Q-Gram 距离一样，输入字符串首先被转换为 n-gram 集合（n 个字符的序列，也称为 k-shingles），但这次不考虑每个 n-gram 的基数。每个输入字符串只是一组 n 元语法。然后 Jaccard 指数计算为 |V1 inter V2| / |V1 联合 V2|。
距离计算为 1 - 相似度。杰卡德指数是公制距离。
与 Jaccard 指数类似，但这次相似度计算为 2 * |V1 inter V2| / (|V1| + |V2|)。
距离计算为 1 - 相似度。
Ratcliff/Obershelp 模式识别，也称为格式塔模式匹配，是一种用于确定两个字符串相似性的字符串匹配算法。它由 John W. Ratcliff 和 John A. Obershelp 于 1983 年开发，并于 1988 年 7 月发表在 Dr. Dobb's Journal 上
Ratcliff/Obershelp 计算两个字符串之间的相似度，返回值位于区间 [0.0, 1.0] 内。
距离计算为 1 - Ratcliff/Obershelp 相似度。
import info . debatty . java . stringsimilarity .*;
public class MyApp {
public static void main ( String [] args ) {
RatcliffObershelp ro = new RatcliffObershelp ();
// substitution of s and t
System . out . println ( ro . similarity ( "My string" , "My tsring" ));
// substitution of s and n
System . out . println ( ro . similarity ( "My string" , "My ntrisg" ));
}
}将产生：
0.8888888888888888
0.7777777777777778
SIFT4 是一种通用字符串距离算法，其灵感来自 JaroWinkler 和最长公共子序列。它的开发是为了产生尽可能接近人类对弦距离的感知的距离测量。因此，它考虑了字符替换、字符距离、最长公共子序列等元素。它是通过实验测试开发的，没有理论背景。
import info.debatty.java.stringsimilarity.experimental.Sift4;
public class MyApp {
public static void main(String[] args) {
String s1 = "This is the first string";
String s2 = "And this is another string";
Sift4 sift4 = new Sift4();
sift4.setMaxOffset(5);
double expResult = 11.0;
double result = sift4.distance(s1, s2);
assertEquals(expResult, result, 0.0);
}
}
在您的项目中使用 java-string-similarity 并希望在这里提及它？请随时给我留言！
