java string similarity
v2.0.0
다양한 문자열 유사성과 거리 측정을 구현하는 라이브러리입니다. 현재 12가지 알고리즘(Levenshtein 편집 거리 및 형제, Jaro-Winkler, Longest Common Subsequence, 코사인 유사성 등 포함)이 구현되어 있습니다. 전체 목록을 보려면 아래 요약 표를 확인하세요.
메이븐 사용하기:
<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 | 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) | |
| Sorensen-Dice 계수 | 유사 거리 | 예 | 아니요 | 세트 | O(m+n) | |
| Ratcliff-Obershelp | 유사 거리 | 예 | 아니요 | ? |
[1] 이 라이브러리에서는 Levenshtein 편집 거리, LCS 거리 및 해당 형제가 동적 프로그래밍 방법을 사용하여 계산되며 비용은 O(mn)입니다. Levenshtein 거리의 경우 이 알고리즘은 Wagner-Fischer 알고리즘 이라고도 합니다("문자열 간 수정 문제", 1974). 원래 알고리즘은 mxn 크기의 행렬을 사용하여 문자열 접두사 사이의 Levenshtein 거리를 저장합니다.
알파벳이 유한한 경우 네 명의 러시아인 방법 (Arlazarov et al. "Oneconomic construction of the Transitive closure of a 유향 그래프", 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] 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 et al.의 "유사성 검색, 미터법 공간 접근법"을 확인할 수 있습니다. 설문 조사를 위해. 이는 비메트릭 유사성 측정과 함께 사용할 수 없습니다.
자세한 설명은 Javadoc을 읽어보세요.
몇몇 알고리즘은 문자열을 n-그램 세트(n개 문자의 시퀀스, k-shingles라고도 함)로 변환하여 작동합니다. 문자열 간의 유사성 또는 거리는 세트 간의 유사성 또는 거리입니다.
Jaccard와 같은 일부는 문자열을 대상 포진의 집합으로 간주하고 각 대상 포진의 발생 횟수를 고려하지 않습니다. 코사인 유사성과 같은 다른 것들은 각 싱글의 발생 횟수를 고려하는 문자열 프로파일이라고 불리는 것을 사용하여 작업합니다.
이러한 알고리즘의 경우 대규모 데이터 세트를 처리할 때 또 다른 사용 사례가 가능합니다.
두 단어 사이의 Levenshtein 거리는 한 단어를 다른 단어로 변경하는 데 필요한 단일 문자 편집(삽입, 삭제 또는 대체)의 최소 수입니다.
미터법 문자열 거리입니다. 이 구현에서는 데이터 행이 2개뿐인 동적 프로그래밍(Wagner-Fischer 알고리즘)을 사용합니다. 따라서 공간 요구 사항은 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" ));
}
}이 거리는 levenshtein 거리를 가장 긴 문자열의 길이로 나누어 계산됩니다. 결과 값은 항상 [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은 이러한 작업을 제공하지 않습니다. 제한. 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는 두 문자열 간의 유사성을 계산하고 반환된 값은 [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(Longest Common Subsequence) 문제는 두 개 이상의 시퀀스에 공통되는 가장 긴 부분 수열을 찾는 것입니다. 이는 공통 하위 문자열을 찾는 문제와 다릅니다. 하위 문자열과 달리 하위 시퀀스는 원래 시퀀스 내에서 연속적인 위치를 차지할 필요가 없습니다.
이는 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의 "LCS 기반 문자열 메트릭" 노트에서 가장 긴 공통 부분 수열을 기반으로 한 거리 메트릭입니다. 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-Gram 거리, "N-Gram 유사성 및 거리", 문자열 처리 및 정보 검색, 컴퓨터 과학 강의 노트 3772, 2005, pp 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-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 개체를 사용하여 모든 입력 문자열을 구문 분석하는 경우에만 작동합니다!
Ukkonen이 "q-gram 및 최대 일치를 사용한 대략적인 문자열 일치"에서 정의한 Q-gram 거리 http://www.sciencedirect.com/science/article/pii/0304397592901434
두 문자열 사이의 거리는 프로필 차이(각 n-그램의 발생 횟수)에 대한 L1 표준(SUM( |V1_i - V2_i| ))으로 정의됩니다. Q-gram 거리는 Levenshtein 거리의 하한이지만 Levenshtein에서는 O(mn)이 필요한 O(m + n)으로 계산할 수 있습니다.
두 문자열 간의 유사성은 두 벡터 표현 사이의 각도의 코사인이며 V1 으로 계산됩니다. V2 / (|V1| * |V2|)
거리는 1 - 코사인 유사도로 계산됩니다.
Q-Gram 거리와 마찬가지로 입력 문자열은 먼저 n-gram 세트(k-shingles라고도 하는 n 문자 시퀀스)로 변환되지만 이번에는 각 n-gram의 카디널리티가 고려되지 않습니다. 각 입력 문자열은 단순히 n-gram 세트입니다. 그런 다음 Jaccard 지수는 |V1 inter V2|로 계산됩니다. / |V1 결합 V2|.
거리는 1 - 유사도로 계산됩니다. Jaccard 지수는 미터법 거리입니다.
Jaccard 지수와 유사하지만 이번에는 유사도가 2 * |V1 inter V2|로 계산됩니다. / (|V1| + |V2|).
거리는 1 - 유사도로 계산됩니다.
게슈탈트 패턴 일치라고도 알려진 Ratcliff/Obershelp 패턴 인식은 두 문자열의 유사성을 결정하기 위한 문자열 일치 알고리즘입니다. 1983년 John W. Ratcliff와 John A. Obershelp에 의해 개발되었으며 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 및 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를 사용하고 여기에 언급되기를 원하십니까? 주저하지 말고 연락주세요!
