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 並希望在這裡提及它？請隨時給我留言！
