Java의 유사성 문자열 비교
https://stackoverflow.com/questions/955110
-
11-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
여러 문자열을 서로 비교하여 가장 유사한 문자열을 찾고 싶습니다.어떤 문자열이 다른 문자열과 더 유사한지 알려주는 라이브러리, 방법 또는 모범 사례가 있는지 궁금합니다.예를 들어:
- "빠른 여우가 뛰었다" -> "여우가 뛰었다"
- "빠른 여우가 뛰었다" -> "여우"
이 비교를 통해 첫 번째가 두 번째보다 더 유사하다는 결과가 나옵니다.
다음과 같은 방법이 필요한 것 같습니다.
double similarityIndex(String s1, String s2)
어딘가에 그런 것이 있습니까?
편집하다:내가 왜 이러는 걸까요?MS 프로젝트 파일의 출력을 작업을 처리하는 일부 레거시 시스템의 출력과 비교하는 스크립트를 작성 중입니다.레거시 시스템은 필드 너비가 매우 제한되어 있으므로 값을 추가할 때 설명이 축약됩니다.생성된 키를 얻을 수 있도록 MS 프로젝트의 항목이 시스템의 항목과 유사한 것을 찾는 반자동 방법이 필요합니다.여전히 수동으로 확인해야 한다는 단점이 있지만 많은 작업을 절약할 수 있습니다.
해결책
예, 다음과 같이 잘 문서화된 알고리즘이 많이 있습니다.
- 코사인 유사성
- 자카드 유사성
- 주사위의 계수
- 일치하는 유사성
- 중복 유사성
- 기타 등등
대안으로 이것을 확인할 수 있습니다
다음 프로젝트도 확인하세요.
다른 팁
일반적인 방법은 두 문자열 간의 유사성을 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 공용 텍스트의 Levenshtein 거리 구현:
apply(CharSequence left, CharSequence rightt) - 직접 구현해 보세요.아래에서 구현 예를 찾을 수 있습니다.
실제 사례:
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"
내가 번역한 Levenshtein 거리 알고리즘 자바스크립트로:
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 거리를 사용하여 두 문자열 간의 차이를 계산할 수 있습니다.http://en.wikipedia.org/wiki/Levenshtein_distance
실제로 문자열 유사성 측정 방법이 많이 있습니다.
- Levenshtein 편집 거리;
- 다메라우-레벤슈타인 거리;
- Jaro-Winkler 유사성;
- 가장 긴 공통 부분 시퀀스 편집 거리;
- Q-그램(Ukkonen);
- n-그램 거리(Kondrak);
- 자카드 지수;
- Sorensen-Dice 계수;
- 코사인 유사성;
- ...
여기에서 이에 대한 설명과 Java 구현을 찾을 수 있습니다.https://github.com/tdebatty/java-string-similarity
다음을 사용하여 이를 달성할 수 있습니다. 아파치 커먼즈 자바 라이브러리.그 안에 있는 다음 두 가지 기능을 살펴보세요.
- getLevenshtein거리
- getFuzzyDistance
이론적으로는 비교할 수 있습니다. 거리 편집.
처럼 들리는데 표절 찾기 당신의 문자열이 문서로 바뀌면 나에게.어쩌면 그 용어로 검색하면 뭔가 좋은 결과가 나올 수도 있습니다.
"집단지성 프로그래밍"에는 두 문서가 유사한지 판단하는 장이 있습니다.코드는 Python으로 되어 있지만 깔끔하고 이식하기 쉽습니다.
첫 번째 답변자 덕분에 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]);
}
}
}
제휴하지 않습니다 StackOverflow
