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

111

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

Mario Ortegón
źródło

Odpowiedzi:

82

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:

dfa
źródło
18
+1 Witryna simmetrics nie wydaje się już aktywna. Jednak znalazłem kod na sourceforge: sourceforge.net/projects/simmetrics Dzięki za wskaźnik.
Michael Merchant
7
Link „możesz to sprawdzić” jest uszkodzony.
Kiril
1
Dlatego Michael Merchant umieścił powyżej poprawny link.
emilyk
2
Słoik dla simmetrics na sourceforge jest nieco przestarzały, github.com/mpkorstanje/simmetrics to zaktualizowana strona github z artefaktami maven
tom91136
Aby dodać do komentarza @MichaelMerchant, projekt jest również dostępny na github . Tam też nie jest zbyt aktywny, ale nieco nowszy niż sourceforge.
Ghurdyl,
163

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:


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"
acdcjunior
źródło
11
Metoda odległości Levenshteina jest dostępna w formacie org.apache.commons.lang3.StringUtils.
Cleankod,
@Cleankod Teraz jest częścią commons-text: commons.apache.org/proper/commons-text/javadocs/api-release/org/…
Luiz
15

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];
};
user493744
źródło
11

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

Florian Fankhauser
źródło
2
Levenshtein świetnie nadaje się do kilku strun, ale nie da się go skalować do porównań między dużą liczbą strun.
rozrzutny
Użyłem Levenshtein w Javie z pewnym sukcesem. Nie robiłem porównań na ogromnych listach, więc może to być hit wydajności. Jest to również trochę proste i można użyć pewnych poprawek, aby podnieść próg dla krótszych słów (takich jak 3 lub 4 znaki), które wydają się być postrzegane jako bardziej podobne niż powinny (to tylko 3 edycje z kota na psa). sugerowane poniżej są prawie takie same - Levenshtein to szczególna implementacja odległości edycji.
Rabarbar
Oto artykuł pokazujący, jak połączyć Levenshtein z wydajnym zapytaniem SQL: literatejava.com/sql/fuzzy-string-search-sql
Thomas W
10

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

Thibault Debatty
źródło
3

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

Laurence Gonsalves
źródło
3

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.

duffymo
źródło
3

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


 }
}
Mohsen Abasi
źródło