29

私は Java でレーベンシュタイン アルゴリズムを実装し、アルゴリズムによって行われた修正、つまりコストを取得しています。結果をパーセンテージで表示したいので、これは少しは役に立ちますが、あまり役に立ちません。

だから私はそれらの類似点を計算する方法を知りたいです。

また、皆さんがどのようにそれを行うのか、またその理由を知りたいです。

4

6 に答える 6

41

2 つの文字列間のレーベンシュタイン距離は、1 つの文字列を別の文字列に変換するために必要な編集の最小数として定義されます。許容される編集操作は、1 文字の挿入、削除、または置換です。(ウィキペディア)

  • つまり、レーベンシュタイン距離 0 は、両方の文字列が等しいことを意味します。
  • 最大レーベンシュタイン距離 (すべての文字が異なります) は max(string1.length, string2.length) です

したがって、パーセンテージが必要な場合は、これを使用してポイントをスケーリングする必要があります。例えば：

"Hello", "Hello" -> レーベンスタイン距離 1 この 2 つの文字列の最大レーベンスタイン距離は 5 です。したがって、20% の文字が一致しません。

String s1 = "Hallo";
String s2 = "Hello";
int lfd = calculateLevensteinDistance(s1, s2);
double ratio = ((double) lfd) / (Math.max(s1.length, s2.length));
于 2011-05-22T12:47:11.913 に答える
19

Apache Commons StringUtilsをダウンロードして、レーベンシュタイン距離アルゴリズムの実装を調査 (および使用) できます。

于 2011-05-22T11:35:58.933 に答える
2

レーベンシュタイン距離

Maven依存関係を介して使用できます

独自の実装を作成するよりも、この実装を使用する方がよいと思います。

<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-text</artifactId>
    <version>1.3</version>
</dependency>

例として、以下のコードを見てください

import org.apache.commons.text.similarity.LevenshteinDistance;

public class MetricUtils {
    private static LevenshteinDistance lv = new LevenshteinDistance();

    public static void main(String[] args) {
        String s = "running";
        String s1 = "runninh";
        System.out.println(levensteinRatio(s, s1));
    }

    public static double levensteinRatio(String s, String s1) {
        return 1 - ((double) lv.apply(s, s1)) / Math.max(s.length(), s1.length());
    }
}
于 2018-04-04T09:47:38.830 に答える
0

2 つのストリング間のレーベンシュタイン差の最大値は、2 つのストリングの長さの最大値になります。(これは、短い文字列の長さまでの各文字の記号の変更に対応し、さらに、短い文字列から長い文字列に移動するか、その逆に移動するかに応じて、挿入または削除します。)それを考えると、2 つの類似性文字列は、その最大値と、その最大値と実際のレーベンシュタイン差との差との比率でなければなりません。

レーベンシュタイン アルゴリズムの実装では、それらの編集がどうあるべきかを記録しない傾向がありますが、ウィキペディアのページにある抽象的なアルゴリズムを考えると、計算はそれほど難しくありません。

于 2011-05-22T12:05:27.110 に答える