자바의 유사성 문자열 비교

자바의 유사성 문자열 비교

---

여러 문자열을 서로 비교하고 가장 유사한 문자열을 찾고 싶습니다. 어떤 문자열이 다른 문자열과 더 유사한 지 알려주는 라이브러리, 방법 또는 모범 사례가 있는지 궁금합니다. 예를 들면 :

• "빠른 여우가 뛰어"-> "여우가 뛰어"
• "빠른 여우가 뛰어"-> "여우"

이 비교는 첫 번째가 두 번째보다 더 유사하다는 것을 반환합니다.

다음과 같은 방법이 필요하다고 생각합니다.

double similarityIndex(String s1, String s2)

어딘가에 그런 것이 있습니까?

편집 : 왜 이러는 거죠? MS 프로젝트 파일의 출력을 작업을 처리하는 일부 레거시 시스템의 출력과 비교하는 스크립트를 작성하고 있습니다. 레거시 시스템은 필드 너비가 매우 제한적이므로 값이 추가되면 설명이 축약됩니다. 생성 된 키를 얻을 수 있도록 MS Project의 항목이 시스템의 항목과 유사한 것을 찾는 반자동 방법을 원합니다. 여전히 수동으로 확인해야하는 단점이 있지만 많은 작업을 절약 할 수 있습니다.

---

예, 다음과 같이 잘 문서화 된 알고리즘이 많이 있습니다.

• 코사인 유사성
• Jaccard 유사성
• 주사위 계수
• 유사성 일치
• 중복 유사성
• 기타 등등

또는 이것을 확인할 수 있습니다

다음 프로젝트도 확인하십시오.

• http://www.dcs.shef.ac.uk/~sam/simmetrics.html
• http://jtmt.sourceforge.net/

---

많은 라이브러리에서 사용되는 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 distance 구현을 사용할 수 있습니다 .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 거리 알고리즘 을 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 distance를 사용하여 두 문자열의 차이를 계산할 수 있습니다. http://en.wikipedia.org/wiki/Levenshtein_distance

---

실제로 많은 문자열 유사성 측정이 있습니다.

• Levenshtein 편집 거리;
• Damerau-Levenshtein 거리;
• Jaro-Winkler 유사성;
• 가장 긴 Common Subsequence 편집 거리;
• Q-Gram (Ukkonen);
• n- 그램 거리 (Kondrak);
• Jaccard 색인;
• Sorensen-Dice 계수;
• 코사인 유사성;
• ...

You can find explanation and java implementation of these here: https://github.com/tdebatty/java-string-similarity

---

You can achieve this using the apache commons java library. Take a look at these two functions within it:
- getLevenshteinDistance
- getFuzzyDistance

---

Theoretically, you can compare edit distances.

---

This is typically done using an edit distance measure. Searching for "edit distance java" turns up a number of libraries, like this one.

---

Sounds like a plagiarism finder to me if your string turns into a document. Maybe searching with that term will turn up something good.

"Programming Collective Intelligence" has a chapter on determining whether two documents are similar. The code is in Python, but it's clean and easy to port.

---

Thank to the first answerer, I think there are 2 calculations of computeEditDistance(s1, s2). Due to high time spending of it, decided to improve the code's performance. So:

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]);
    }


 }
}

참고URL : https://stackoverflow.com/questions/955110/similarity-string-comparison-in-java