Perbandingan String Kemiripan di Java

Saya ingin membandingkan beberapa string satu sama lain, dan menemukan string yang paling mirip. Saya bertanya-tanya apakah ada pustaka, metode, atau praktik terbaik yang akan mengembalikan saya string mana yang lebih mirip dengan string lain. Sebagai contoh:

• "Rubah cepat melompat" -> "Rubah melompat"
• "Rubah cepat melompat" -> "Rubah"

Perbandingan ini akan mengembalikan bahwa yang pertama lebih mirip daripada yang kedua.

Saya rasa saya membutuhkan beberapa metode seperti:

double similarityIndex(String s1, String s2)

Apakah ada hal seperti itu di suatu tempat?

EDIT: Mengapa saya melakukan ini? Saya menulis skrip yang membandingkan output dari file MS Project dengan output dari beberapa sistem warisan yang menangani tugas. Karena sistem lama memiliki lebar bidang yang sangat terbatas, saat nilai ditambahkan, deskripsinya disingkat. Saya ingin beberapa cara semi-otomatis untuk menemukan entri mana dari MS Project yang mirip dengan entri pada sistem sehingga saya bisa mendapatkan kunci yang dihasilkan. Ini memiliki kekurangan, karena masih harus diperiksa secara manual, tetapi akan menghemat banyak pekerjaan

Ya, ada banyak algoritma yang terdokumentasi dengan baik seperti:

• Kesamaan kosinus
• Kesamaan Jaccard
• Koefisien dadu
• Kesamaan yang cocok
• Kesamaan yang tumpang tindih
• dll dll

Ringkasan yang bagus ("Sam's String Metrics") dapat ditemukan di sini (tautan asli mati, sehingga tertaut ke Arsip Internet)

Periksa juga proyek ini:

• Simmetrik
• jtmt

Cara umum untuk menghitung kemiripan antara dua string dengan cara 0% -100% , seperti yang digunakan di banyak pustaka, adalah mengukur berapa banyak (dalam%) Anda harus mengubah string yang lebih panjang untuk mengubahnya menjadi lebih pendek:

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

Menghitung editDistance():

The editDistance()fungsi di atas diharapkan untuk menghitung mengedit jarak antara dua string. Ada beberapa implementasi untuk langkah ini, masing-masing mungkin lebih sesuai dengan skenario tertentu. Yang paling umum adalah algoritma jarak Levenshtein dan kami akan menggunakannya dalam contoh di bawah ini (untuk string yang sangat besar, algoritma lain cenderung berkinerja lebih baik).

Berikut dua opsi untuk menghitung jarak edit:

• Anda dapat menggunakan implementasi jarak Levenshtein Apache Commons Text : apply(CharSequence left, CharSequence rightt)
• Menerapkannya sendiri. Di bawah ini Anda akan menemukan contoh penerapan.

Contoh kerja:

Lihat demo online di sini.

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

}

Keluaran:

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"

Saya menerjemahkan algoritma jarak Levenshtein ke dalam 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];
};

Anda dapat menggunakan jarak Levenshtein untuk menghitung perbedaan antara dua string. http://en.wikipedia.org/wiki/Levenshtein_distance

Memang ada banyak ukuran kesamaan string di luar sana:

• Levenshtein mengedit jarak;
• Jarak Damerau-Levenshtein;
• Kesamaan Jaro-Winkler;
• Jarak edit Common Subsequence Terpanjang;
• Q-Gram (Ukkonen);
• jarak n-Gram (Kondrak);
• Indeks Jaccard;
• Koefisien Sorensen-Dice;
• Kesamaan cosinus;
• ...

Anda dapat menemukan penjelasan dan implementasi java di sini: https://github.com/tdebatty/java-string-similarity

Anda dapat melakukannya dengan menggunakan java library apache commons . Lihatlah dua fungsi ini di dalamnya:
- getLevenshteinDistance
- getFuzzyDistance

Secara teoritis, Anda dapat membandingkan jarak edit .

Ini biasanya dilakukan dengan menggunakan pengukur jarak edit . Pencarian untuk "edit jarak java" menghasilkan sejumlah perpustakaan, seperti ini .

Kedengarannya seperti pencari plagiarisme bagi saya jika string Anda berubah menjadi dokumen. Mungkin penelusuran dengan istilah itu akan menghasilkan sesuatu yang bagus.

"Programming Collective Intelligence" memiliki bab tentang menentukan apakah dua dokumen serupa. Kodenya menggunakan Python, tetapi bersih dan mudah dipindahkan.

Terima kasih kepada penjawab pertama, menurut saya ada 2 perhitungan computeEditDistance (s1, s2). Karena menghabiskan waktu yang tinggi, memutuskan untuk meningkatkan kinerja kode. Begitu:

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


 }
}

Anda juga dapat menggunakan algoritma z untuk menemukan kesamaan dalam string. Klik di sini https://teakrunch.com/2020/05/09/string-similarity-hackerrank-challenge/