C# Tips | 文字列処理：Levenshtein距離

C# C#
スポンサーリンク

はじめに 「Levenshtein距離」は“どれくらい似ているか”を数字で教えてくれるもの

Levenshtein（レーベンシュタイン）距離は、
「ある文字列を別の文字列に変えるために、
何回“1文字の挿入・削除・置換”が必要か」を数えたものです。

距離が小さいほど「よく似ている」、
距離が大きいほど「似ていない」とみなせます。

例えば：

"kitten" → "sitting"
この変換に必要な操作はだいたい 3 回です（置換・置換・挿入）。
なので、Levenshtein距離は 3 です。

この「距離」を使うと、
曖昧検索、候補の自動補完、スペルチェックなどで
「どれが一番それっぽいか？」を機械的に判断できるようになります。

ここから、
考え方 → アルゴリズムのイメージ → C#実装 → 業務ユーティリティとしての使い方
という流れで、かみ砕いて説明していきます。

Levenshtein距離の考え方

3つの操作だけで考える

Levenshtein距離で使う操作は、たった3つです。

1文字削除（delete）
1文字挿入（insert）
1文字置換（substitute）

「ある文字列 s を、別の文字列 t に変えるために、
この3つの操作を何回すればいいか？」
その最小回数が距離です。

例えば "Yamada" と "Yamda"。

Yamada
Yamda

a が1つ抜けているだけなので、
「Yamada の 4文字目の a を削除する」1回で変換できます。
距離は 1 です。

"Yamada" と "Yamato"。

Yamada
Yamato

d を t に置き換え、
最後の a を o に置き換える、と考えると、
2回の置換で変換できます。
距離は 2 です。

このように、「どんな手順で変換するか」を考えたときの
最小の操作回数が Levenshtein距離です。

アルゴリズムのイメージ 「表を埋めていく」

距離を計算するための表を作る

Levenshtein距離は、
二次元の表（マトリクス）を一つ作って、
そこを少しずつ埋めていくことで計算します。

文字列 s の長さを n、
文字列 t の長さを m とします。

d[i, j] を
「s の先頭 i 文字を、t の先頭 j 文字に変えるために必要な操作回数」
と定義します。

最終的に欲しいのは、
「s 全体（長さ n）を t 全体（長さ m）に変えるための回数」なので、
答えは d[n, m] になります。

0行目と0列目の意味

s が空文字（長さ 0）で、t の先頭 j 文字にしたい場合、
j 回の挿入が必要です。

なので、d[0, j] = j です。

逆に、t が空文字で、s の先頭 i 文字から空文字にしたい場合、
i 回の削除が必要です。

なので、d[i, 0] = i です。

この2つを使って、
表の一番上の行と、一番左の列を初期化します。

残りのマスを「一歩ずつ」埋めていく

d[i, j] を求めるとき、
次の3パターンを考えます。

s の i 文字目を削除する（delete）
s の i 文字目の前に t の j 文字目を挿入する（insert）
s の i 文字目を t の j 文字目に置き換える（substitute）

それぞれのコスト（回数）はこうなります。

削除：d[i - 1, j] + 1
挿入：d[i, j - 1] + 1
置換：d[i - 1, j - 1] + cost

ここで cost は、
s[i - 1] と t[j - 1] が同じなら 0、違うなら 1 です。

3つのうち一番小さいものが、
「最小の操作回数」になるので、それを d[i, j] に入れます。

この計算を、i = 1..n、j = 1..m で繰り返していくと、
表が全部埋まり、右下の d[n, m] に答えが入ります。

C#でのLevenshtein距離実装

まずは完成形のコード

初心者でも追いやすいように、
できるだけ素直な実装を書きます。

using System;

public static class LevenshteinUtil
{
    public static int GetLevenshteinDistance(string s, string t)
    {
        if (s == null) throw new ArgumentNullException(nameof(s));
        if (t == null) throw new ArgumentNullException(nameof(t));

        int n = s.Length;
        int m = t.Length;

        if (n == 0) return m;
        if (m == 0) return n;

        int[,] d = new int[n + 1, m + 1];

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

        for (int j = 0; j <= m; j++)
        {
            d[0, j] = j;
        }

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                int cost = (s[i - 1] == t[j - 1]) ? 0 : 1;

                int deletion = d[i - 1, j] + 1;
                int insertion = d[i, j - 1] + 1;
                int substitution = d[i - 1, j - 1] + cost;

                int min = deletion;
                if (insertion < min) min = insertion;
                if (substitution < min) min = substitution;

                d[i, j] = min;
            }
        }

        return d[n, m];
    }
}
C#

ここから、実際に動かしてみて、
感覚をつかんでいきます。

動作例で距離の感覚をつかむ

英単語の例

Console.WriteLine(LevenshteinUtil.GetLevenshteinDistance("kitten", "sitting")); // 3
Console.WriteLine(LevenshteinUtil.GetLevenshteinDistance("Yamada", "Yamda"));   // 1
Console.WriteLine(LevenshteinUtil.GetLevenshteinDistance("Yamada", "Yamato"));  // 2
Console.WriteLine(LevenshteinUtil.GetLevenshteinDistance("abc", "xyz"));        // 3
Console.WriteLine(LevenshteinUtil.GetLevenshteinDistance("", "test"));          // 4
Console.WriteLine(LevenshteinUtil.GetLevenshteinDistance("test", ""));          // 4
C#

"kitten" → "sitting" が 3 なのは、
k → s（置換）、e → i（置換）、最後に g を挿入、
といったイメージで 3 回の操作が必要だからです。

"Yamada" と "Yamda" は 1。
"Yamada" と "Yamato" は 2。
直感ともだいたい一致しているはずです。

日本語でも同じように使える

Console.WriteLine(LevenshteinUtil.GetLevenshteinDistance("やまだたろう", "やまだたろ"));   // 1
Console.WriteLine(LevenshteinUtil.GetLevenshteinDistance("ヤマダタロウ", "やまだたろう")); // 4 くらい
C#

日本語も「1文字単位」で見ているので、
ひらがな・カタカナの違いなどは「別の文字」として扱われます。

「ひらがなとカタカナを同じとみなしたい」場合は、
事前にひらがな→カタカナ変換などの正規化をしてから距離を計算する、
という一工夫が必要になります。

距離を使って「似ているかどうか」を判定する

閾値（しきい値）を決める

距離そのものは「どれくらい違うか」の数字です。
これを「似ている／似ていない」に変えるには、
「どこまでを許容するか」という閾値を決めます。

例えば、「距離が 1 以下なら似ている」と決めると：

"Yamada" と "Yamda" → 距離 1 → 似ている
"Yamada" と "Yamato" → 距離 2 → 似ていない

「距離が 2 以下なら似ている」と決めると：

"Yamada" と "Yamda" → 似ている
"Yamada" と "Yamato" → 似ている

という判定になります。

これをユーティリティにすると、こう書けます。

public static bool IsSimilar(string s, string t, int maxDistance)
{
    int d = LevenshteinUtil.GetLevenshteinDistance(s, t);
    return d <= maxDistance;
}
C#

使い方の例です。

Console.WriteLine(IsSimilar("Yamada", "Yamda", 1));  // True
Console.WriteLine(IsSimilar("Yamada", "Yamato", 1)); // False
Console.WriteLine(IsSimilar("Yamada", "Yamato", 2)); // True
C#

「maxDistance をいくつにするか」が、
業務要件（どこまで許すか）になります。

業務・実務での使いどころ

曖昧検索の心臓部として使う

ユーザーが入力した文字列と、
マスタに登録されている候補を比べて、
「一番近いもの」を探す、という使い方が典型です。

public static string? FindBestMatch(string input, IEnumerable<string> candidates)
{
    string? best = null;
    int bestDistance = int.MaxValue;

    foreach (var c in candidates)
    {
        int d = LevenshteinUtil.GetLevenshteinDistance(input, c);

        if (d < bestDistance)
        {
            bestDistance = d;
            best = c;
        }
    }

    return best;
}
C#

使い方の例です。

var names = new[] { "Yamada", "Yamamoto", "Suzuki", "Sato" };

string? best = FindBestMatch("Yamda", names);

Console.WriteLine(best); // Yamada
C#

さらに、「距離が 3 以上なら“どれも似ていない”とみなして候補なしにする」
といったルールを足せば、
「それっぽい候補があるときだけ提案する」こともできます。

スペルチェックや入力補助

英語の入力補助や、
コード値のタイプミス検出などにも使えます。

例えば、「ユーザーが入力したコードがマスタに存在しないとき、
一番近いコードを“もしかしてこれ？”として表示する」
といった機能です。

パフォーマンスと実務上の注意点

計算量のイメージ

Levenshtein距離の計算量は、
文字列の長さを n, m とすると、おおよそ n × m です。

短い文字列（名前、コード、短いキーワード）なら問題ありませんが、
長い文章や、大量の候補に対して毎回計算すると、
処理が重くなることがあります。

実務では、次のような工夫が有効です。

比較する文字列の長さをある程度制限する
候補が多い場合は、まず先頭一致や部分一致でざっくり絞ってから距離を計算する
距離がある程度大きくなった時点で「これ以上計算しても意味がない」と打ち切る

初心者の段階では、
「長い文章に対して大量にやると重くなるかも」
くらいの感覚を持っておけば十分です。

まとめ 「Levenshtein距離ユーティリティ」は“似ている度合いを数字でくれる物差し”

Levenshtein距離は、
「どれくらい似ているか」を客観的な数字で教えてくれる、
とても強力な“物差し”です。

押さえておきたいポイントは、

Levenshtein距離は「挿入・削除・置換」の最小回数で定義されること。
二次元配列を使って、「s の先頭 i 文字」と「t の先頭 j 文字」の距離を順番に埋めていくアルゴリズムで計算できること。
C#では、素直な実装でも十分実務で使えること。
距離そのものだけでなく、「距離がいくつ以下なら似ているとみなすか」という閾値を決めることで、曖昧検索や候補提案に使えること。
長い文字列や大量の候補に対しては、パフォーマンスに気をつける必要があること。

ここまで理解できれば、
「Levenshtein距離って名前だけ難しそう」から一歩進んで、
“ユーザーの入力ミスや揺れをうまく受け止めるための、実務で使えるユーティリティ”として、
自分の C# コードの中に自然に組み込めるようになっていきます。

スポンサーリンク
タイトルとURLをコピーしました