文字列の類似度を測定する - 生活を良くします-怠惰なプログラミング

自分と似ているツイートを探したい

文字の類似度を図る方法について

レーベンシュタイン距離、ジャロ・ウィンクラー距離、cos類似度、3-gramという方法があります。
今回はレーベンシュタイン距離を使って進めていきたいと思います。
twitter APIを使って自分と似ているツイートをするアカウントを探そうと考え、形態素解析による文字列の分割と類似度の検証が必要ということがわかりました。

レーベンシュタイン距離では形態素解析は必要がないため、実装のミスは少なそうというのも選んだ理由の一つです。

置き換えや置換が少ない方が、文字が似ているということになります。
つまり、レーベンシュタイン距離は値が小さい方が、類似度が高いということです。

レーベンシュタイン距離

レーベンシュタイン距離とは

二つの文字列Str1とStr2がどれくらい似ているのかを調べる方法で、Str2と同じ文字列にするためにどれくらいの回数だけStr1の1単語を追加・削除・置き換えすれば良いのかということを考える方法です。

太郎と次郎では1文字しか違わないため、置き換えが一度で済むためにレーベンシュタイン距離は1となります。

レーベンシュタイン距離：1.0
わたしは太郎です。
わたしは二郎です。

ただし、以下のように文字数が多くなった場合、レーベンシュタイン距離も追加・削除・置き換えの回数だけ大きくなっていくのでこのままでは比較に使用できません。

レーベンシュタイン距離：10.0
わたしは太郎です。
わたしは二郎と申すものでございます。

正規化レーベンシュタイン距離

正規化レーベンシュタイン距離とは、レーベンシュタイン距離で得られた値を、より文字数の多い方の文字数で割って出た値のことを示します。
これによって正規化レーベンシュタイン距離の値は、0.0~1.0の値におさまるため比較はしやすくなります。

正規化レーベンシュタイン距離でも、小さい値をとる方が文字列の類似度が高くなります。

正規化レーベンシュタイン距離：0.111111111111111
わたしは太郎です。
わたしは二郎です。

文字数が多くなっても正規化レーベンシュタイン距離は0.0~1.0の間で評価でき、比較することが可能になります。

正規化レーベンシュタイン距離：0.555555555555556
わたしは太郎です。
わたしは二郎と申すものでございます。

Javaでの簡単なサンプル

実際に計算を行う

Str1がStr2と同じ文字列になる前、追加・削除・置き換えを繰り返す
文字の追加・削除・置き換えの回数を数え、レーベンシュタイン距離を得る
Str1とStr2のうち、より大きい方の文字数でレーベンシュタイン距離を割る
正規化レーベンシュタイン距離を得て、比較する

public class Levenstein_distance {
 
    double LevensteinDistance(String array_left, String array_right) {
        int array_[][] = new int[array_left.length() + 1][array_right.length() + 1];
        int x = 0;
        String[] left = array_left.split("");
        String[] right = array_right.split("");
        int left_point = 0;
        int right_point = 0;
        int left_right = 0;
        int minimum = 0;
 
        for (int i = 0; i < array_left.length()+1; i++) {
            array_[i][0] = i;
        }
 
        for (int j = 0; j < array_right.length()+1; j++) {
            array_[0][j] = j;
        }
 
        for (int i = 1; i < array_left.length() + 1; i++) {
            for (int j = 1; j < array_right.length() + 1; j++) {

                left_point = array_[i - 1][j] + 1; 
                right_point = array_[i][j - 1] + 1;
 
                x = (left[i - 1].equals(right[j - 1])) ? 0 : 1;
 
                left_right = array_[i - 1][j - 1] + x;
 
                int min1 = Math.min(left_point, right_point);
                minimum = Math.min(min1, left_right);
                array_[i][j] = minimum;
            }
        }
        double max_string_num = Math.max(array_left.length(),array_right.length());
        double normalized_LD = array_[array_left.length()][array_right.length()] / max_string_num;
        return normalized_LD;
    }
 
 
    public static void main(String[] args) {
        
        String right = "ひつまぶし";//"ゴジラ";
        String left  = "ひまつぶし";//"キングゴジラ";
        
        Levenstein_distance LD = new Levenstein_distance();
        System.out.printf("%.15f",LD.LevensteinDistance(left,right));
     }
}

おそらく大きく間違えてはいないコードになったと思います。

出力結果

String right = "ひつまぶし";
String left  = "ひまつぶし";
レーベンシュタイン距離 : 0.400000000000000
 
String right = "ゴジラ";
String left  = "キングゴジラ";
レーベンシュタイン距離 : 0.500000000000000

最終結果として"ひつまぶし"："ひまつぶし"の方が、"ゴジラ"："キングゴジラ"のペアよりも類似度が高いということがわかった。
これを使っていろいろと進めていきたい。