C#

レーベンシュタイン距離

2つの文字列が似ているかどうか調べるためにレーベンシュタイン距離を測ろうと思ったが、Wikipediaに掲載されているコードは、ちょっと使いづらい。多分わかりやすさを優先したのだろう。素直にC#に移植すれば、こんな感じになると思う。

public static int LevenshteinDistance(string str1, string str2)
{
    int[,] d = new int[str1.Length + 1, str2.Length + 1]; // ... (1)

    for (int i1 = 0; i1 <= str1.Length; i1++) // ... (2)
    {
        d[i1, 0] = i1;
    }

    for (int i2 = 0; i2 <= str2.Length; i2++)
    {
        d[0, i2] = i2;
    }

    for (int i1 = 1; i1 <= str1.Length; i1++) // ... (3)
    {
        for (int i2 = 1; i2 <= str2.Length; i2++)
        {
            int cost = (str1[i1 - 1] == str2[i2 - 1]) ? 0 : 1;
            d[i1, i2] = Math.Min(Math.Min(
                d[i1 - 1, i2    ] + 1,     // 文字の挿入
                d[i1    , i2 - 1] + 1),    // 文字の削除
                d[i1 - 1, i2 - 1] + cost); // 文字の置換
        }
    }

    return d[str1.Length, str2.Length];
}

このコードにはいくつか問題がある。まず(1)の箇所。比較する文字列が比較的短いうちは問題にならないが、例えば1000字の文字列同士を比較しようとすると、およそ1メガ要素の配列が必要で、メモリの確保が心配になる。

それから(2)のループの内容は(3)のループに組み込めるので、(2)のループを回す分だけ無駄になっている。中身のない空ループを書いているのと変わらない。

いろいろ整理すると、こんな感じになるかな。

public static int LevenshteinDistance(string str1, string str2)
{
    int n1 = 0;
    int n2 = str2.Length + 2;
    int[] d = new int[n2 << 1];

    for (int i = 0; i < n2; i++)
    {
        d[i] = i;
    }

    d[n2 - 1]++;
    d[d.Length - 1] = 0;

    for (int i = 0; i < str1.Length; i++)
    {
        d[n2] = i + 1;

        for (int j = 0; j < str2.Length; j++)
        {
            int v = d[n1++];

            if (str1[i] == str2[j])
            {
                v--;
            }

            v = (v < d[n1]) ? v : d[n1];
            v = (v < d[n2]) ? v : d[n2];

            d[++n2] = ++v;
        }

        n1 = d[n1 + 1];
        n2 = d[n2 + 1];
    }

    return d[d.Length - n2 - 2];
}

これで少し速くなり、メモリ的にも有利になると思うが、わかりにくいので、オリジナルのコードをコメントにして残しておくと良いかもしれない。

2つの文字列が似ているかどうかを調べるには、もうひと工夫必要。長いほうの文字列の文字数で割って比率を出せば良いらしい。

public static float LevenshteinRate(string str1, string str2)
{
    int len1 = (str1 != null) ? str1.Length : 0;
    int len2 = (str2 != null) ? str2.Length : 0;

    if (len1 > len2)
    {
        int tmp = len1;
        len1 = len2;
        len2 = tmp;
    }

    if (len1 == 0)
    {
        return (len2 == 0) ? 0.0f : 1.0f;
    }

    return LevenshteinDistance(str1, str2) / (float)len2;
}

戻り値は0～1の単精度浮動小数点値で、0ならまったく同じことを、1ならまったく違うことを意味する。やってみると比率0.5ぐらいでは、似てるかどうか判断がつかない感じで丁度良い。0.5未満なら似てると判断して良いだろう。こんな関数があったら、データベースで似ている名前を検索するのに便利だ。

このメソッドでは「A」と「a」は異なる文字と判定されるが、文字列が似ているかどうかを判断するときには、多分同じ文字と判定してほしいだろう。「あ」と「ア」なども同様。そうすると、距離や比率を測る前に、あらかじめ文字列の“ゆらぎ”みたいなのを統一（正規化）しておく必要がある。

(2020/01/01 初稿)

(2020/01/18 更新)