Porównanie ciągów podobieństwa w Javie

Chcę porównać kilka ciągów ze sobą i znaleźć te, które są najbardziej podobne. Zastanawiałem się, czy jest jakaś biblioteka, metoda lub najlepsza praktyka, które zwróciłyby mi, które ciągi są bardziej podobne do innych ciągów. Na przykład:

• „Szybki lis skoczył” -> „Lis skoczył”
• „Szybki lis skoczył” -> „Lis”

Z tego porównania wynika, że ​​pierwsze jest bardziej podobne niż drugie.

Chyba potrzebuję jakiejś metody, takiej jak:

double similarityIndex(String s1, String s2)

Czy gdzieś jest coś takiego?

EDYCJA: Dlaczego to robię? Piszę skrypt, który porównuje dane wyjściowe pliku MS Project z danymi wyjściowymi jakiegoś starszego systemu, który obsługuje zadania. Ponieważ starszy system ma bardzo ograniczoną szerokość pola, po dodaniu wartości opisy są skracane. Chcę mieć półautomatyczny sposób na znalezienie wpisów z MS Project, które są podobne do wpisów w systemie, abym mógł uzyskać wygenerowane klucze. Ma wady, ponieważ nadal musi być ręcznie sprawdzany, ale zaoszczędziłoby to dużo pracy

Tak, istnieje wiele dobrze udokumentowanych algorytmów, takich jak:

• Podobieństwo cosinusowe
• Podobieństwo Jaccarda
• Współczynnik kości
• Dopasowanie podobieństwa
• Nakładanie się podobieństwa
• itd itd

Dobre podsumowanie („Sam's String Metrics”) można znaleźć tutaj (oryginalny link nie działa, więc prowadzi do archiwum internetowego)

Sprawdź również te projekty:

• Simmetrics
• jtmt

Powszechnym sposobem obliczania podobieństwa między dwoma ciągami w sposób 0% -100% , stosowanym w wielu bibliotekach, jest zmierzenie, ile (w%) musiałbyś zmienić dłuższy ciąg, aby zamienić go na krótszy:

/**
 * 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

Obliczanie editDistance():

Powyższa editDistance()funkcja ma obliczyć odległość edycji między dwoma ciągami. Jest kilka implementacji tego kroku, każda może lepiej pasować do konkretnego scenariusza. Najpopularniejszym jest algorytm odległości Levenshteina i użyjemy go w naszym przykładzie poniżej (w przypadku bardzo dużych ciągów inne algorytmy prawdopodobnie będą działać lepiej).

Oto dwie opcje obliczania odległości edycji:

• Możesz użyć implementacji odległości Levenshteina z Apache Commons Text : apply(CharSequence left, CharSequence rightt)
• Zaimplementuj to we własnym zakresie. Poniżej znajdziesz przykładową realizację.

Przykład pracy:

Zobacz demo online tutaj.

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

}

Wynik:

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"

Przetłumaczyłem algorytm odległości Levenshteina na 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];
};

Możesz użyć odległości Levenshteina, aby obliczyć różnicę między dwoma strunami. http://en.wikipedia.org/wiki/Levenshtein_distance

Rzeczywiście istnieje wiele miar podobieństwa ciągów:

• Odległość edycji Levenshteina;
• Odległość Damerau-Levenshteina;
• Podobieństwo Jaro-Winklera;
• Najdłuższa odległość edycji wspólnej sekwencji;
• Q-Gram (Ukkonen);
• odległość n-Gram (Kondrak);
• Indeks Jaccarda;
• Współczynnik Sorensena-Dice'a;
• Podobieństwo cosinusowe;
• ...

Możesz znaleźć wyjaśnienie i implementację java tutaj: https://github.com/tdebatty/java-string-similarity

Możesz to osiągnąć za pomocą biblioteki apache commons java . Spójrz na te dwie funkcje w nim zawarte:
- getLevenshteinDistance
- getFuzzyDistance

Teoretycznie można porównać odległości edycji .

Odbywa się to zwykle za pomocą edycji miary odległości . Wyszukiwanie frazy „edit distance java” powoduje wyświetlenie wielu bibliotek, takich jak ta .

Brzmi jak wykrywacz plagiatów , jeśli twój ciąg zamieni się w dokument. Może wyszukiwanie z tym terminem przyniesie coś dobrego.

„Programowanie zbiorowej inteligencji” zawiera rozdział poświęcony określaniu, czy dwa dokumenty są podobne. Kod jest w Pythonie, ale jest czysty i łatwy do przeniesienia.

Dzięki pierwszej osobie odpowiadającej, myślę, że istnieją 2 obliczenia computeEditDistance (s1, s2). Ze względu na duże nakłady czasu postanowił poprawić wydajność kodu. Więc:

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


 }
}

Możesz również użyć algorytmu z, aby znaleźć podobieństwo w ciągu. Kliknij tutaj https://teakrunch.com/2020/05/09/string-similarity-hackerrank-challenge/