Ähnlichkeitszeichenfolgenvergleich in Java

Ich möchte mehrere Zeichenfolgen miteinander vergleichen und diejenigen finden, die am ähnlichsten sind. Ich habe mich gefragt, ob es eine Bibliothek, Methode oder bewährte Methode gibt, die mir zurückgibt, welche Zeichenfolgen anderen Zeichenfolgen ähnlicher sind. Beispielsweise:

• "Der schnelle Fuchs sprang" -> "Der Fuchs sprang"
• "Der schnelle Fuchs sprang" -> "Der Fuchs"

Dieser Vergleich würde ergeben, dass der erste ähnlicher ist als der zweite.

Ich denke, ich brauche eine Methode wie:

double similarityIndex(String s1, String s2)

Gibt es so etwas irgendwo?

EDIT: Warum mache ich das? Ich schreibe ein Skript, das die Ausgabe einer MS Project-Datei mit der Ausgabe eines Legacy-Systems vergleicht, das Aufgaben erledigt. Da das Legacy-System eine sehr begrenzte Feldbreite hat, werden die Beschreibungen beim Hinzufügen der Werte abgekürzt. Ich möchte eine halbautomatische Methode finden, um herauszufinden, welche Einträge aus MS Project den Einträgen im System ähnlich sind, damit ich die generierten Schlüssel erhalten kann. Es hat Nachteile, da es noch manuell überprüft werden muss, aber es würde viel Arbeit sparen

Ja, es gibt viele gut dokumentierte Algorithmen wie:

• Kosinusähnlichkeit
• Jaccard Ähnlichkeit
• Würfelkoeffizient
• Passende Ähnlichkeit
• Überlappungsähnlichkeit
• etc etc.

Eine gute Zusammenfassung ("Sam's String Metrics") finden Sie hier (ursprünglicher Link tot, daher Links zum Internetarchiv)

Überprüfen Sie auch diese Projekte:

• Simmetrics
• jtmt

Die übliche Methode zur Berechnung der Ähnlichkeit zwischen zwei Zeichenfolgen auf eine Weise von 0% bis 100% , wie sie in vielen Bibliotheken verwendet wird, besteht darin, zu messen, wie viel (in%) Sie die längere Zeichenfolge ändern müssten, um sie in die kürzere umzuwandeln:

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

Berechnung der editDistance():

Es editDistance()wird erwartet, dass die obige Funktion den Bearbeitungsabstand zwischen den beiden Zeichenfolgen berechnet . Für diesen Schritt gibt es mehrere Implementierungen , von denen jede besser zu einem bestimmten Szenario passt. Am gebräuchlichsten ist der Levenshtein-Distanzalgorithmus, den wir in unserem folgenden Beispiel verwenden werden (bei sehr großen Zeichenfolgen sind andere Algorithmen wahrscheinlich leistungsfähiger).

Hier sind zwei Optionen zum Berechnen der Bearbeitungsentfernung:

• Sie können die Implementierung von Levenshtein distance von Apache Commons Text verwenden : apply(CharSequence left, CharSequence rightt)
• Implementieren Sie es in Ihrem eigenen. Unten finden Sie eine Beispielimplementierung.

Arbeitsbeispiel:

Sehen Sie hier die Online-Demo.

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

}

Ausgabe:

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"

Ich habe den Levenshtein-Distanzalgorithmus in JavaScript übersetzt:

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

Sie können den Levenshtein-Abstand verwenden, um die Differenz zwischen zwei Zeichenfolgen zu berechnen. http://en.wikipedia.org/wiki/Levenshtein_distance

Es gibt in der Tat viele Maßstäbe für die Ähnlichkeit von Zeichenfolgen:

• Levenshtein bearbeiten Abstand;
• Damerau-Levenshtein-Entfernung;
• Jaro-Winkler-Ähnlichkeit;
• Längste gemeinsame Subsequenz-Bearbeitungsentfernung;
• Q-Gramm (Ukkonen);
• n-Gramm-Abstand (Kondrak);
• Jaccard-Index;
• Sorensen-Würfel-Koeffizient;
• Kosinusähnlichkeit;
• ...

Erklärungen und Java-Implementierung finden Sie hier: https://github.com/tdebatty/java-string-similarity

Sie können dies mit der Java-Bibliothek von Apache Commons erreichen . Schauen Sie sich diese beiden Funktionen an:
- getLevenshteinDistance
- getFuzzyDistance

Theoretisch können Sie Bearbeitungsabstände vergleichen .

Dies erfolgt normalerweise mithilfe eines Bearbeitungsabstandsmaßes . Wenn Sie nach "Edit Distance Java" suchen, werden eine Reihe von Bibliotheken wie diese angezeigt .

Klingt für mich wie ein Plagiatsucher , wenn sich Ihre Zeichenfolge in ein Dokument verwandelt. Vielleicht ergibt die Suche mit diesem Begriff etwas Gutes.

"Programmieren von kollektiver Intelligenz" enthält ein Kapitel zum Bestimmen, ob zwei Dokumente ähnlich sind. Der Code ist in Python, aber sauber und einfach zu portieren.

Dank des ersten Antwortenden denke ich, dass es 2 Berechnungen von computeEditDistance (s1, s2) gibt. Aufgrund des hohen Zeitaufwands wurde beschlossen, die Leistung des Codes zu verbessern. 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]);
    }


 }
}

Sie können auch den z-Algorithmus verwenden, um Ähnlichkeit in der Zeichenfolge zu finden. Klicken Sie hier https://teakrunch.com/2020/05/09/string-similarity-hackerrank-challenge/