C# Tips | 文字列処理：曖昧検索

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

はじめに 「曖昧検索」は“ちょっと間違っていても拾ってあげる”検索

業務システムで検索機能を作ると、こんなことが起きがちです。

「ユーザーが Yamda とタイプミスしても、本当は Yamada を出したい」
「ﾔﾏﾀﾞ（半角カナ）でも ヤマダ（全角カナ）でも、同じ人としてヒットさせたい」
「ｱｲｳｴｵ と アイウエオ を同じとみなしたい」

こういう「ちょっと違うけど、たぶんこれを探してるよね？」を拾うのが、曖昧検索です。

完全一致や単純な部分一致だけでは取りこぼしてしまうケースを、
“人間の感覚に寄せて”拾いにいくイメージです。

ここでは、プログラミング初心者向けに、

曖昧検索の考え方
代表的な指標「レーベンシュタイン距離（編集距離）」
シンプルな C# 実装
業務ユーティリティとしての使い方

を、順番にかみ砕いて説明していきます。

曖昧検索の基本イメージ

「どれくらい似ているか」を数値で表す

曖昧検索の多くは、「似ているかどうか」を Yes/No で決めるのではなく、
「どれくらい似ているか」を数値で表します。

例えば、次のような感覚です。

"Yamada" と "Yamda" → かなり似ている（1文字抜けているだけ）
"Yamada" と "Yamato" → そこそこ似ている（2文字違う）
"Yamada" と "Suzuki" → ほとんど似ていない

この「似ている度合い」を数値化する代表的な方法が、
レーベンシュタイン距離（編集距離）です。

レーベンシュタイン距離（編集距離）とは何か

ざっくりしたイメージ

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

「ある文字列を別の文字列に変えるために、
何回“挿入・削除・置換”の操作が必要か」

を数えたものです。

例えば、"Yamada" と "Yamda" を比べてみます。

Yamada
Yamda

a が1つ抜けているだけなので、「1回の削除」で変換できます。
つまり、レーベンシュタイン距離は 1 です。

"Yamada" と "Yamato" の場合。

Yamada
Yamato

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

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

C# でのシンプルなレーベンシュタイン距離実装

まずは完成形のコード

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

public static class FuzzySearchUtil
{
    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;

                d[i, j] = Math.Min(Math.Min(deletion, insertion), substitution);
            }
        }

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

少し長く見えますが、やっていることは「表を埋めていく」だけです。
順番にかみ砕いていきます。

レーベンシュタイン距離の中身をかみ砕く

距離を計算するための「表」を用意する

int[,] d = new int[n + 1, m + 1]; で、
(n+1) × (m+1) の二次元配列を用意しています。

ここで n は s の長さ、m は t の長さです。

この表の意味は、

d[i, j] = s の先頭 i 文字を、t の先頭 j 文字に変えるために必要な操作回数

です。

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

0 行目と 0 列目を初期化する

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

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

これは、「片方が空文字の場合」の距離を設定しています。

s の先頭 i 文字を空文字にするには、i 回削除が必要
空文字を t の先頭 j 文字にするには、j 回挿入が必要

なので、こうなります。

d[0, 0] = 0
d[1, 0] = 1
d[2, 0] = 2
…
d[0, 1] = 1
d[0, 2] = 2
…

という感じで、表の一番上と一番左が埋まります。

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

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;

        d[i, j] = Math.Min(Math.Min(deletion, insertion), substitution);
    }
}
C#

ここがアルゴリズムの心臓部です。

i と j を一歩ずつ進めながら、
「削除」「挿入」「置換」の3パターンを考え、
一番少ない回数になるものを選んでいます。

deletion は、「s の i 文字目を削除する」イメージです。
insertion は、「t の j 文字目を挿入する」イメージです。
substitution は、「s の i 文字目を t の j 文字目に置き換える」イメージです。

cost は、「その2文字が同じなら 0、違うなら 1」です。
同じ文字なら置換は不要なので、距離は増えません。

こうして表を全部埋め終わると、
右下の d[n, m] に「最小の操作回数」が入ります。

距離を使って「曖昧一致かどうか」を判定する

「距離がいくつ以下なら“似ている”とみなすか」を決める

距離が計算できるようになったら、
次は「どこまでを“許容範囲”とするか」を決めます。

例えば、「距離が 1 以下なら OK」と決めると、

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

という判定になります。

これをユーティリティメソッドにすると、こうなります。

public static bool IsFuzzyMatch(string s, string t, int maxDistance)
{
    int distance = GetLevenshteinDistance(s, t);
    return distance <= maxDistance;
}
C#

使い方の例です。

Console.WriteLine(FuzzySearchUtil.IsFuzzyMatch("Yamada", "Yamda", 1));  // True
Console.WriteLine(FuzzySearchUtil.IsFuzzyMatch("Yamada", "Yamato", 1)); // False
Console.WriteLine(FuzzySearchUtil.IsFuzzyMatch("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 = FuzzySearchUtil.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#

このように、「一番距離が小さいもの」を選ぶことで、
「たぶんこれを探してるよね？」という候補を提示できます。

ただし、距離が大きすぎる場合（例えば 5 以上など）は、
「どれも似ていない」と判断して、
「候補なし」とするのも大事です。

パフォーマンスに注意する

レーベンシュタイン距離は、
文字列の長さをそれぞれ n, m とすると、
計算量はおおよそ n × m です。

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

業務で使うときは、

対象文字列の長さをある程度制限する
候補数が多い場合は、まず簡単なフィルタ（先頭一致など）で絞る

といった工夫をするとよいです。

まとめ 「曖昧検索ユーティリティ」は“ユーザーのミスを優しく受け止めるクッション”

曖昧検索は、「ユーザーが完璧に入力してくれる」ことを前提にしないための仕組みです。
人間のミスや揺れを前提にして、システム側が少し歩み寄るイメージです。

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

曖昧検索は「似ている度合い」を数値化して、その数値で判定する考え方であること。
レーベンシュタイン距離（編集距離）は、「挿入・削除・置換の最小回数」で似ている度合いを測る代表的な指標であること。
C# では、二次元配列を使ったシンプルな実装で距離を計算できること。
距離がいくつ以下なら“似ている”とみなすか（閾値）を業務要件として決めること。
候補リストから「一番近いもの」を選ぶ、距離が大きすぎる場合は候補なしにする、といった使い方が実務的であること。

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

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