java string similarity
v2.0.0
さまざまな文字列の類似性と距離の測定を実装するライブラリ。現在、多数のアルゴリズム (レーベンシュタイン編集距離と兄弟、Jaro-Winkler、最長共通部分列、コサイン類似度など) が実装されています。完全なリストについては、以下の概要表を確認してください...
Maven の使用:
<dependency>
<groupId>info.debatty</groupId>
<artifactId>java-string-similarity</artifactId>
<version>RELEASE</version>
</dependency>
またはリリースを確認してください。
このライブラリには Java 8 以降が必要です。
実装された各アルゴリズムの主な特徴を以下に示します。 「コスト」列は、長さ m と n の 2 つの文字列間の類似性をそれぞれ計算するための計算コストの推定値を示します。
| 正規化？ | メトリック？ | タイプ | 料金 | 一般的な使用法 | ||
|---|---|---|---|---|---|---|
| レーベンシュタイン | 距離 | いいえ | はい | O(m*n) 1 | ||
| 正規化されたレーベンシュタイン | 距離 類似性 | はい | いいえ | O(m*n) 1 | ||
| 加重レーベンシュタイン | 距離 | いいえ | いいえ | O(m*n) 1 | OCR | |
| ダメラウ＝レーベンシュタイン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グラム | 距離 | はい | いいえ | O(m*n) | ||
| Qグラム | 距離 | いいえ | いいえ | プロフィール | O(m+n) | |
| コサイン類似度 | 類似性 距離 | はい | いいえ | プロフィール | O(m+n) | |
| ジャカードインデックス | 類似性 距離 | はい | はい | セット | O(m+n) | |
| ソーレンセン・ダイス係数 | 類似性 距離 | はい | いいえ | セット | O(m+n) | |
| ラトクリフ・オーバーシェルプ | 類似性 距離 | はい | いいえ | ? |
[1] このライブラリでは、レーベンシュタイン編集距離、LCS 距離、およびそれらの兄弟は、コスト O(mn) の動的計画法を使用して計算されます。レーベンシュタイン距離の場合、このアルゴリズムはWagner-Fischer アルゴリズムと呼ばれることもあります (「文字列間の補正問題」、1974 年)。元のアルゴリズムは、サイズ mxn の行列を使用して、文字列プレフィックス間のレーベンシュタイン距離を保存します。
アルファベットが有限であれば、ロシア人 4 人の方法(Arlazarov 他、「有向グラフの推移閉包の経済的構築について」、1970) を使用して計算を高速化することができます。これは 1980 年に Masek によって出版されました (「A Faster Algorithm Computing String Edit Distances」)。このメソッドは、行列をサイズ 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] ダメラウ-レーベンシュタイン文字列距離には、隣接する転置を伴うダメラウ-レーベンシュタイン (無制限のダメラウ-レーベンシュタイン距離とも呼ばれる) と最適な文字列配置 (制限された編集距離とも呼ばれる) の 2 つのバリエーションがあります。最適な文字列配置を実現するために、部分文字列を複数回編集することはできません。
このトピックは単純に見えるかもしれませんが、テキストの類似性や距離を測定するためのさまざまなアルゴリズムが多数存在します。したがって、ライブラリはそれらを分類するためにいくつかのインターフェイスを定義します。
一般に、NormalizedStringSimilarity を実装するアルゴリズムは NormalizedStringDistance も実装し、類似度 = 1 - 距離となります。ただし、N-Gram の類似性と距離 (Kondrak) など、いくつかの例外があります...
MetricStringDistance インターフェイス: 距離のいくつかは実際にはメートル距離です。これは、三角不等式 d(x, y) <= d(x,z) + d(z,y) を検証することを意味します。たとえば、レーベンシュタインはメートル距離ですが、正規化レーベンシュタインはそうではありません。
最近傍検索アルゴリズムとインデックス構造の多くは、三角不等式に依存しています。 Zezulaらによる「類似性検索、計量空間アプローチ」を確認できます。調査のため。これらは、非メトリック類似性尺度とは使用できません。
詳細な説明については Javadoc を参照してください
いくつかのアルゴリズムは、文字列を n グラム (n 文字のシーケンス、k-シングルとも呼ばれる) のセットに変換することによって機能します。文字列間の類似性または距離は、セット間の類似性または距離になります。
jaccard など、それらの中には、文字列を帯状疱疹のセットとして考慮し、各帯状疱疹の出現数を考慮しないものもあります。コサイン類似度などの他の機能は、各シングルの出現数を考慮した、文字列のプロファイルと呼ばれることもある機能を使用して機能します。
これらのアルゴリズムでは、大規模なデータセットを扱うときに別の使用例が可能です。
2 つの単語間のレーベンシュタイン距離は、一方の単語をもう一方の単語に変更するために必要な単一文字の編集 (挿入、削除、または置換) の最小回数です。
メートル文字列の距離です。この実装では動的プログラミング (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" ));
}
}異なる文字置換に対して異なる重みを定義できるレーベンシュタインの実装。
このアルゴリズムは通常、光学式文字認識 (OCR) アプリケーションに使用されます。 OCR の場合、OCR の観点からは P は R と似ているため、P と R を置換するコストは、P と M を置換するコストよりも低くなります。
キーボード入力の自動修正にも使用できます。ここでは、たとえば、AZERTY キーボードまたは QWERTY キーボード上で E と R が隣り合って配置されているため、E と R を置換するコストが低くなります。したがって、ユーザーが文字を打ち間違えた可能性が高くなります。
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" ));
}
}レーベンシュタインと同様に、転置を伴うダメラウ・レーベンシュタイン距離 (無制限のダメラウ・レーベンシュタイン距離とも呼ばれる) は、ある文字列を別の文字列に変換するために必要な最小操作数であり、操作は文字列の挿入、削除、または置換として定義されます。単一の文字、または隣接する 2 つの文字の入れ替え。
これは三角不等式を尊重するため、メートル距離になります。
これを、部分文字列を複数回編集できない拡張である最適な文字列配置距離と混同しないでください。
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 の Optimal String Alignment バリアント (制限付き編集距離とも呼ばれる) は、どの部分文字列も複数回編集されないという条件で文字列を等しくするために必要な編集操作の数を計算しますが、真の Damerau-Levenshtein ではそのような計算は行われません。制限。レーベンシュタイン距離のアルゴリズムとの違いは、転置演算の反復が 1 つ追加されていることです。
最適な文字列配置距離については、三角不等式が成り立たないため、真の指標ではないことに注意してください。
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] の範囲内にあります。これは、(大まかに) ダメラウ・レーベンシュタインのバリエーションであり、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) 問題は、2 つ (またはそれ以上) のシーケンスに共通する最長の部分列を見つけることにあります。これは、共通の部分文字列を見つける問題とは異なります。部分文字列とは異なり、部分シーケンスは元のシーケンス内の連続した位置を占める必要はありません。
これは、diff ユーティリティや、複数の変更を調整するための Git などによって使用されます。
文字列 X (長さ n) と Y (長さ m) の間の LCS 距離は、n + m - 2 |LCS(X, Y)| です。最小 = 0 最大 = n + m
LCS 距離は、挿入と削除のみが許可される (置換なし) 場合、または置換のコストが挿入または削除のコストの 2 倍である場合、レーベンシュタイン距離と等価です。
このクラスは動的プログラミング アプローチを実装しており、スペース要件 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 グラム (n 個の文字のシーケンス、k シングルとも呼ばれる) のセットに変換することによって機能します。文字列間の類似性または距離は、セット間の類似性または距離になります。
これらの類似性と距離を計算するコストは、主に k-shingling (文字列を k 文字のシーケンスに変換する) によって支配されます。したがって、これらのアルゴリズムには通常、次の 2 つの使用例があります。
文字列間の距離を直接計算します。
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 グラム距離 (Ukkonen が「Q グラムと最大一致による文字列マッチングの近似」 http://www.sciencedirect.com/science/article/pii/0304397592901434 で定義)
2 つの文字列間の距離は、それらのプロファイルの差 (各 n グラムの出現数) の L1 ノルム: SUM( |V1_i - V2_i| ) として定義されます。 Q グラム距離はレーベンシュタイン距離の下限ですが、O(m + n) で計算できます。レーベンシュタインには O(mn) が必要です。
2 つの文字列間の類似性は、これら 2 つのベクトル表現の間の角度の余弦であり、 V1 として計算されます。 V2 / (|V1| * |V2|)
距離は 1 - コサイン類似度として計算されます。
Q-Gram 距離と同様に、入力文字列はまず n-gram のセット (n 文字のシーケンス、k-shingles とも呼ばれます) に変換されますが、今回は各 n-gram のカーディナリティは考慮されません。各入力文字列は単なる N グラムのセットです。次に、Jaccard インデックスは |V1 inter V2| として計算されます。 / |V1 ユニオン V2|。
距離は 1 - 類似度として計算されます。 Jaccard インデックスはメートル単位の距離です。
Jaccard インデックスと似ていますが、今回は類似度が 2 * |V1 inter V2| として計算されます。 / (|V1| + |V2|)。
距離は 1 - 類似度として計算されます。
Ratcliff/Obershelp パターン認識 (ゲシュタルト パターン マッチングとも呼ばれます) は、2 つの文字列の類似性を判断するための文字列マッチング アルゴリズムです。 1983 年に John W. Ratcliff と John A. Oberhelp によって開発され、1988 年 7 月に Dr. Dobb's Journal に掲載されました。
Ratcliff/Obershelp は 2 つの文字列間の類似性を計算し、戻り値は [0.0, 1.0] の範囲内にあります。
距離は、1 - ラトクリフ/オーバーシェルプの類似度として計算されます。
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 と Longest Common Subsequence からインスピレーションを得た汎用の文字列距離アルゴリズムです。これは、弦の距離に対する人間の認識にできるだけ近い距離測定値を生成するために開発されました。したがって、文字の置換、文字の距離、最長共通部分列などの要素が考慮されます。理論的な背景はなく、実験的なテストを使用して開発されました。
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 を使用し、それをここで言及したいですか?遠慮せずにラインを送ってください！
