java - Javaでの類似性文字列の比較

Question

いくつかの文字列を互いに比較して、最も類似している文字列を見つけたいと思います。どの文字列が他の文字列により類似しているかを返すライブラリ、メソッド、またはベストプラクティスがあるかどうか疑問に思いました。例えば：

「キツネがジャンプした」->「キツネがジャンプした」
「クイックキツネがジャンプした」->「キツネ」

この比較は、最初のものが2番目のものより類似していることを返します。

私は私が次のようないくつかの方法が必要だと思います：

double similarityIndex(String s1, String s2)

どこかにそんなものはありますか？

編集：なぜ私はこれをしているのですか？MSProjectファイルの出力をタスクを処理するレガシーシステムの出力と比較するスクリプトを書いています。レガシーシステムのフィールド幅は非常に限られているため、値が追加されると説明が省略されます。生成されたキーを取得できるように、MSProjectのどのエントリがシステムのエントリに類似しているかを半自動で見つける方法が必要です。手動でチェックする必要があるため、欠点がありますが、多くの作業を節約できます。

score 179 · Accepted Answer

多くのライブラリで使用されているように、2つの文字列間の類似性を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()`：

上記の関数は、2つの文字列間の編集距離editDistance()を計算することが期待されています。このステップにはいくつかの実装があり、それぞれが特定のシナリオにより適している場合があります。最も一般的なのはレーベンシュタイン距離アルゴリズムであり、以下の例で使用します（非常に大きな文字列の場合、他のアルゴリズムの方がパフォーマンスが向上する可能性があります）。

編集距離を計算するための2つのオプションは次のとおりです。

ApacheCommonsTextのレーベンシュタイン距離の実装を使用できます。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"

score 88 · Accepted Answer

はい、次のような多くの十分に文書化されたアルゴリズムがあります。

コサイン類似性
ジャッカードの類似性
ダイス係数
一致する類似性
重複の類似性
などなど

良い要約（ "Sam's String Metrics"）はここにあります（元のリンクが無効になっているため、インターネットアーカイブにリンクしています）

これらのプロジェクトも確認してください。

score 16 · Accepted Answer

レーベンシュタイン距離アルゴリズムを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];
};

score 13 · Accepted Answer

確かに、文字列の類似性の尺度はたくさんあります。

レーベンシュタイン編集距離;
ダメラウ・レーベンシュタイン距離;
ジャロ・ウィンクラー類似性;
最長共通部分列編集距離。
Q-グラム（ウッコネン）;
n-グラム距離（コンドラク）;
ジャッカード係数;
ソーレンセン-ダイス係数;
コサイン類似性;
..。

これらの説明とJava実装はここにあります： https ：//github.com/tdebatty/java-string-similarity

score 11 · Accepted Answer

レーベンシュタイン距離を使用して、2つの弦の差を計算できます。 http://en.wikipedia.org/wiki/Levenshtein_distance

score 11 · Accepted Answer

これは、 apachecommonsjavaライブラリを使用して実現できます。その中のこれらの2つの関数を見てください：
-- getLevenshteinDistance
--getFuzzyDistance

score 5 · Accepted Answer

最初の回答者のおかげで、computeEditDistance（s1、s2）の計算は2つあると思います。時間がかかるため、コードのパフォーマンスを向上させることにしました。それで：

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


 }
}

score 3 · Accepted Answer

3

理論的には、編集距離を比較できます。

于 2009-06-05T09:59:28.230 に答える

score 3 · Accepted Answer

これは通常、編集距離メジャーを使用して行われます。「editdistancejava」を検索すると、このような多くのライブラリが見つかります。

score 3 · Accepted Answer

あなたの文字列が文書に変わった場合、私には盗作ファインダーのように聞こえます。たぶん、その用語で検索すると、何か良いものが見つかるでしょう。

「集合知プログラミング」には、2つのドキュメントが類似しているかどうかを判断するための章があります。コードはPythonですが、クリーンで簡単に移植できます。

score -1 · Accepted Answer

zアルゴリズムを使用して、文字列の類似性を見つけることもできます。ここをクリックhttps://teakrunch.com/2020/05/09/string-similarity-hackerrank-challenge/

java - Javaでの類似性文字列の比較

11 に答える 11

計算editDistance()：

実例：

Related

Reference

計算`editDistance()`：