반응형
Java에서의 유사성 문자열 비교
몇 개의 현을 비교해서 가장 비슷한 것을 찾고 싶습니다.어떤 문자열이 다른 문자열과 더 비슷한지 되돌아볼 수 있는 라이브러리, 메서드 또는 베스트 프랙티스가 있는지 궁금합니다.예를 들어 다음과 같습니다.
- "빠른 여우가 뛰어내렸다" -> "여우가 뛰어내렸다"
- "빠른 여우가 뛰어내렸다" -> "여우"
이 비교는 첫 번째가 두 번째보다 더 유사하다는 것을 반환합니다.
다음과 같은 방법이 필요할 것 같습니다.
double similarityIndex(String s1, String s2)
그런 게 어디 있어요?
EDIT: 내가 이걸 왜 하는 거지?MS 프로젝트 파일의 출력과 작업을 처리하는 레거시 시스템의 출력을 비교하는 스크립트를 작성하고 있습니다.레거시 시스템의 필드 폭은 매우 제한적이기 때문에 값을 추가하면 설명이 생략됩니다.생성된 키를 얻을 수 있도록 MS Project의 엔트리와 시스템상의 엔트리가 유사한지 반자동적인 방법을 찾고 싶습니다.아직 수작업으로 체크해야 하는 단점도 있지만 많은 작업을 줄일 수 있습니다.
많은 라이브러리에서 사용되는 것처럼 두 문자열 간의 유사도를 0%-100%로 계산하는 일반적인 방법은 긴 문자열을 짧은 문자열로 변환하려면 어느 정도(%)를 변경해야 하는지 측정하는 것입니다.
/**
* Calculates the similarity (a number within 0 and 1) between two strings.
*/
public static double similarity(String s1, String s2) {
String longer = s1, shorter = s2;
if (s1.length() < s2.length()) { // longer should always have greater length
longer = s2; shorter = s1;
}
int longerLength = longer.length();
if (longerLength == 0) { return 1.0; /* both strings are zero length */ }
return (longerLength - editDistance(longer, shorter)) / (double) longerLength;
}
// you can use StringUtils.getLevenshteinDistance() as the editDistance() function
// full copy-paste working code is below
의 계산editDistance():
그editDistance()위의 함수는 두 문자열 사이의 편집 거리를 계산합니다.이 단계에는 몇 가지 구현이 있으며, 각각이 특정 시나리오에 더 적합할 수 있습니다.가장 일반적인 것은 Levenshtein 거리 알고리즘입니다.이 알고리즘은 다음 예에서 사용합니다(매우 큰 문자열의 경우 다른 알고리즘이 더 잘 수행될 수 있습니다).
편집 거리를 계산하는 두 가지 옵션은 다음과 같습니다.
- Apache Commons Text의 Levenshtein 거리 구현을 사용할 수 있습니다.
- 직접 구현하십시오.구현 예는 다음과 같습니다.
작업 예:
public class StringSimilarity {
/**
* Calculates the similarity (a number within 0 and 1) between two strings.
*/
public static double similarity(String s1, String s2) {
String longer = s1, shorter = s2;
if (s1.length() < s2.length()) { // longer should always have greater length
longer = s2; shorter = s1;
}
int longerLength = longer.length();
if (longerLength == 0) { return 1.0; /* both strings are zero length */ }
/* // If you have Apache Commons Text, you can use it to calculate the edit distance:
LevenshteinDistance levenshteinDistance = new LevenshteinDistance();
return (longerLength - levenshteinDistance.apply(longer, shorter)) / (double) longerLength; */
return (longerLength - editDistance(longer, shorter)) / (double) longerLength;
}
// Example implementation of the Levenshtein Edit Distance
// See http://rosettacode.org/wiki/Levenshtein_distance#Java
public static int editDistance(String s1, String s2) {
s1 = s1.toLowerCase();
s2 = s2.toLowerCase();
int[] costs = new int[s2.length() + 1];
for (int i = 0; i <= s1.length(); i++) {
int lastValue = i;
for (int j = 0; j <= s2.length(); j++) {
if (i == 0)
costs[j] = j;
else {
if (j > 0) {
int newValue = costs[j - 1];
if (s1.charAt(i - 1) != s2.charAt(j - 1))
newValue = Math.min(Math.min(newValue, lastValue),
costs[j]) + 1;
costs[j - 1] = lastValue;
lastValue = newValue;
}
}
}
if (i > 0)
costs[s2.length()] = lastValue;
}
return costs[s2.length()];
}
public static void printSimilarity(String s, String t) {
System.out.println(String.format(
"%.3f is the similarity between \"%s\" and \"%s\"", similarity(s, t), s, t));
}
public static void main(String[] args) {
printSimilarity("", "");
printSimilarity("1234567890", "1");
printSimilarity("1234567890", "123");
printSimilarity("1234567890", "1234567");
printSimilarity("1234567890", "1234567890");
printSimilarity("1234567890", "1234567980");
printSimilarity("47/2010", "472010");
printSimilarity("47/2010", "472011");
printSimilarity("47/2010", "AB.CDEF");
printSimilarity("47/2010", "4B.CDEFG");
printSimilarity("47/2010", "AB.CDEFG");
printSimilarity("The quick fox jumped", "The fox jumped");
printSimilarity("The quick fox jumped", "The fox");
printSimilarity("kitten", "sitting");
}
}
출력:
1.000 is the similarity between "" and ""
0.100 is the similarity between "1234567890" and "1"
0.300 is the similarity between "1234567890" and "123"
0.700 is the similarity between "1234567890" and "1234567"
1.000 is the similarity between "1234567890" and "1234567890"
0.800 is the similarity between "1234567890" and "1234567980"
0.857 is the similarity between "47/2010" and "472010"
0.714 is the similarity between "47/2010" and "472011"
0.000 is the similarity between "47/2010" and "AB.CDEF"
0.125 is the similarity between "47/2010" and "4B.CDEFG"
0.000 is the similarity between "47/2010" and "AB.CDEFG"
0.700 is the similarity between "The quick fox jumped" and "The fox jumped"
0.350 is the similarity between "The quick fox jumped" and "The fox"
0.571 is the similarity between "kitten" and "sitting"
네, 다음과 같은 잘 문서화된 알고리즘이 많이 있습니다.
- 코사인 유사도
- 자카드 유사도
- 주사위 계수
- 매칭 유사성
- 중복 유사성
- /etc/setc/setc/setc/setc.
여기서 적절한 요약('Sam의 문자열 메트릭')을 찾을 수 있습니다(원래 링크가 비활성 상태이므로 인터넷 아카이브에 링크됩니다).
다음 프로젝트도 확인해 주세요.
Levenshtein 거리 알고리즘을 JavaScript로 변환했습니다.
String.prototype.LevenshteinDistance = function (s2) {
var array = new Array(this.length + 1);
for (var i = 0; i < this.length + 1; i++)
array[i] = new Array(s2.length + 1);
for (var i = 0; i < this.length + 1; i++)
array[i][0] = i;
for (var j = 0; j < s2.length + 1; j++)
array[0][j] = j;
for (var i = 1; i < this.length + 1; i++) {
for (var j = 1; j < s2.length + 1; j++) {
if (this[i - 1] == s2[j - 1]) array[i][j] = array[i - 1][j - 1];
else {
array[i][j] = Math.min(array[i][j - 1] + 1, array[i - 1][j] + 1);
array[i][j] = Math.min(array[i][j], array[i - 1][j - 1] + 1);
}
}
}
return array[this.length][s2.length];
};
실제로 많은 문자열 유사성 척도가 존재합니다.
- Levenshtein 편집 거리
- 다메라우-레벤슈테인 거리
- Jaro-Winkler 유사성;
- 최장 공통 후속 편집 거리
- Q그램(우크코넨);
- n-그램 거리(Kondrak);
- 자카드 지수
- 소렌센-다이스 계수
- 코사인 유사성
- ...
이러한 설명 및 Java 구현은 https://github.com/tdebatty/java-string-similarity 에서 확인할 수 있습니다.
Levenshtein 거리를 사용하여 두 문자열 간의 차이를 계산할 수 있습니다.http://en.wikipedia.org/wiki/Levenshtein_distance
Apache Commons Java 라이브러리를 사용하여 이를 수행할 수 있습니다.여기에서는, 다음의 2개의 기능을 봐 주세요.
- getLevenshteinDistance
- get Fuzzy Distance
첫 번째 응답자 덕분에 computeEditDistance(s1, s2)의 계산은 2개라고 생각합니다.시간이 많이 걸려서 코드 성능을 개선하기로 했습니다.그래서:
public class LevenshteinDistance {
public static int computeEditDistance(String s1, String s2) {
s1 = s1.toLowerCase();
s2 = s2.toLowerCase();
int[] costs = new int[s2.length() + 1];
for (int i = 0; i <= s1.length(); i++) {
int lastValue = i;
for (int j = 0; j <= s2.length(); j++) {
if (i == 0) {
costs[j] = j;
} else {
if (j > 0) {
int newValue = costs[j - 1];
if (s1.charAt(i - 1) != s2.charAt(j - 1)) {
newValue = Math.min(Math.min(newValue, lastValue),
costs[j]) + 1;
}
costs[j - 1] = lastValue;
lastValue = newValue;
}
}
}
if (i > 0) {
costs[s2.length()] = lastValue;
}
}
return costs[s2.length()];
}
public static void printDistance(String s1, String s2) {
double similarityOfStrings = 0.0;
int editDistance = 0;
if (s1.length() < s2.length()) { // s1 should always be bigger
String swap = s1;
s1 = s2;
s2 = swap;
}
int bigLen = s1.length();
editDistance = computeEditDistance(s1, s2);
if (bigLen == 0) {
similarityOfStrings = 1.0; /* both strings are zero length */
} else {
similarityOfStrings = (bigLen - editDistance) / (double) bigLen;
}
//////////////////////////
//System.out.println(s1 + "-->" + s2 + ": " +
// editDistance + " (" + similarityOfStrings + ")");
System.out.println(editDistance + " (" + similarityOfStrings + ")");
}
public static void main(String[] args) {
printDistance("", "");
printDistance("1234567890", "1");
printDistance("1234567890", "12");
printDistance("1234567890", "123");
printDistance("1234567890", "1234");
printDistance("1234567890", "12345");
printDistance("1234567890", "123456");
printDistance("1234567890", "1234567");
printDistance("1234567890", "12345678");
printDistance("1234567890", "123456789");
printDistance("1234567890", "1234567890");
printDistance("1234567890", "1234567980");
printDistance("47/2010", "472010");
printDistance("47/2010", "472011");
printDistance("47/2010", "AB.CDEF");
printDistance("47/2010", "4B.CDEFG");
printDistance("47/2010", "AB.CDEFG");
printDistance("The quick fox jumped", "The fox jumped");
printDistance("The quick fox jumped", "The fox");
printDistance("The quick fox jumped",
"The quick fox jumped off the balcany");
printDistance("kitten", "sitting");
printDistance("rosettacode", "raisethysword");
printDistance(new StringBuilder("rosettacode").reverse().toString(),
new StringBuilder("raisethysword").reverse().toString());
for (int i = 1; i < args.length; i += 2) {
printDistance(args[i - 1], args[i]);
}
}
}
이론적으로 편집 거리를 비교할 수 있습니다.
이 작업은 일반적으로 편집 거리 측정을 사용하여 수행됩니다."edit distance java"를 검색하면 다음과 같은 많은 라이브러리가 나타납니다.
당신의 끈이 문서로 바뀐다면 표절 발견자처럼 들리네요.그 용어로 검색하면 뭔가 좋은 게 나올지도 몰라요.
"Programming Collective Intelligence"에는 두 문서가 유사한지 여부를 판단하는 장이 있습니다.코드는 Python에 있지만 깨끗하고 휴대하기 쉽습니다.
라이브러리 없이 다음 "Levenshtein Distance" 알고리즘을 사용할 수 있습니다.
public static int getLevenshteinDistance(CharSequence s, CharSequence t) {
if (s == null || t == null) {throw new IllegalArgumentException("Strings must not be null");}
int n = s.length();
int m = t.length();
if (n == 0) {
return m;
}
else if (m == 0) {
return n;
}
if (n > m) {
// swap the input strings to consume less memory
final CharSequence tmp = s;
s = t;
t = tmp;
n = m;
m = t.length();
}
final int[] p = new int[n + 1];
// indexes into strings s and t
int i; // iterates through s
int j; // iterates through t
int upper_left;
int upper;
char t_j; // jth character of t
int cost;
for (i = 0; i <= n; i++) {
p[i] = i;
}
for (j = 1; j <= m; j++) {
upper_left = p[0];
t_j = t.charAt(j - 1);
p[0] = j;
for (i = 1; i <= n; i++) {
upper = p[i];
cost = s.charAt(i - 1) == t_j ? 0 : 1;
// minimum of cell to the left+1, to the top+1, diagonally left and up +cost
p[i] = Math.min(Math.min(p[i - 1] + 1, p[i] + 1), upper_left + cost);
upper_left = upper;
}
}
return p[n];
}
z 알고리즘을 사용하여 문자열의 유사성을 찾을 수도 있습니다.https://teakrunch.com/2020/05/09/string-similarity-hackerrank-challenge/ 를 클릭해 주세요.
언급URL : https://stackoverflow.com/questions/955110/similarity-string-comparison-in-java
반응형
'programing' 카테고리의 다른 글
| 동적 폭과 동일한 높이(CSS 유체 레이아웃) (0) | 2022.11.01 |
|---|---|
| Retrofit 2.0에서 인터셉터를 사용하여 헤더를 추가하는 방법 (0) | 2022.11.01 |
| Self-JOIN SQL 쿼리 성능 향상 (0) | 2022.11.01 |
| 롬복의 슈퍼 컨스트럭터에 전화하는 방법 (0) | 2022.11.01 |
| 스트림에서 Collections.toMap()을 사용할 때 목록의 반복 순서를 유지하려면 어떻게 해야 합니까? (0) | 2022.11.01 |