プログラム 技術

C#のあいまい検索について<N-gram + ひらがな正規化ver.>

今回はシステムを作るうえで時々ある『あいまい検索』についてです。あいまい検索の中でも日本語に焦点を当てています
そのため、要件によっては合わない可能性があるので注意してください。また、今回は追加のライブラリ等をしようしないため自身で調整が必要な場合があります

名称バージョン
C#.Net 8.0

N-gram について

簡単に説明すると文字列をN個ずつとしての単語に分けて検索する方法となります。詳しくは以下のサイトが参考になるかと思います

参考サイト
https://omomuki-tech.com/archives/6286
初心者でもわかる！N-gramとは？自然言語処理の基本を解説

参考サイトへ

実際に実装する

N-gramについて理解したところで実際に実装していきます

正規化する

まず初めにN-gramを実施する前に文字列を正規化します

public static string Normalize(string input)
{
    if (string.IsNullOrEmpty(input))
        return string.Empty;

    var sb = new StringBuilder(input.Length);

    foreach (char c in input)
    {
        char normalized = c;

        // カタカナ（ァ-ヶ）をひらがな（ぁ-ゖ）に変換
        if (c >= 'ァ' && c <= 'ヶ')
        {
            normalized = (char)(c - 0x60);
        }
        // 全角英大文字 → 半角小文字
        else if (c >= 'Ａ' && c <= 'Ｚ')
        {
            normalized = (char)(c - 'Ａ' + 'a');
        }
        // 全角英小文字 → 半角小文字
        else if (c >= 'ａ' && c <= 'ｚ')
        {
            normalized = (char)(c - 'ａ' + 'a');
        }
        // 全角数字 → 半角数字
        else if (c >= '０' && c <= '９')
        {
            normalized = (char)(c - '０' + '0');
        }
        // 半角英大文字 → 小文字
        else if (c >= 'A' && c <= 'Z')
        {
            normalized = char.ToLower(c);
        }

        sb.Append(normalized);
    }

    return sb.ToString();
}

N-gram用の関数を作成する

次にN-gram用の関数を作成します

// 文字列からN-gramを生成
public static List<string> GetNGrams(string text, int n = 2)
{
    var ngrams = new List<string>();

    if (string.IsNullOrEmpty(text) || text.Length < n)
    {
        // 文字列がN未満の場合は文字列自体を返す
        if (!string.IsNullOrEmpty(text))
            ngrams.Add(text);
        return ngrams;
    }

    for (int i = 0; i <= text.Length - n; i++)
    {
        ngrams.Add(text.Substring(i, n));
    }

    return ngrams;
}

// N-gramベースのJaccard類似度を計算
public static double CalculateNGramSimilarity(string text1, string text2, int n = 2)
{
    // 正規化
    var normalized1 = Normalize(text1);
    var normalized2 = Normalize(text2);

    // N-gram生成
    var ngrams1 = GetNGrams(normalized1, n).ToHashSet();
    var ngrams2 = GetNGrams(normalized2, n).ToHashSet();

    if (ngrams1.Count == 0 && ngrams2.Count == 0)
        return 1.0;

    if (ngrams1.Count == 0 || ngrams2.Count == 0)
        return 0.0;

    // Jaccard係数を計算
    int intersection = ngrams1.Intersect(ngrams2).Count();
    int union = ngrams1.Union(ngrams2).Count();

    return union == 0 ? 0.0 : (double)intersection / union;
}

// N-gramベースのDice係数を計算（Jaccardより部分一致に強い）
public static double CalculateDiceSimilarity(string text1, string text2, int n = 2)
{
    var normalized1 = Normalize(text1);
    var normalized2 = Normalize(text2);

    var ngrams1 = GetNGrams(normalized1, n).ToHashSet();
    var ngrams2 = GetNGrams(normalized2, n).ToHashSet();

    if (ngrams1.Count == 0 && ngrams2.Count == 0)
        return 1.0;

    if (ngrams1.Count == 0 || ngrams2.Count == 0)
        return 0.0;

    int intersection = ngrams1.Intersect(ngrams2).Count();

    return (2.0 * intersection) / (ngrams1.Count + ngrams2.Count);
}

検索関数を作成する

最後にこれまで作成した関数たちを使用して判定するための関数を作成します

// リストから類似する項目を検索
public List<SearchResult> Search(string query, IEnumerable<string> items)
{
    var results = new List<SearchResult>();

    foreach (var item in items)
    {
        double similarity = CalculateNGramSimilarity(query, item, _ngramSize);

        if (similarity >= _threshold)
        {
            results.Add(new SearchResult
            {
                Text = item,
                Similarity = similarity
            });
        }
    }

    return results.OrderByDescending(r => r.Similarity).ToList();
}

// リストから類似する項目を検索（セレクター使用版）
public List<SearchResult<T>> Search<T>(string query, IEnumerable<T> items, Func<T, string> selector)
{
    var results = new List<SearchResult<T>>();

    foreach (var item in items)
    {
        string text = selector(item);
        double similarity = CalculateNGramSimilarity(query, text, _ngramSize);

        if (similarity >= _threshold)
        {
            results.Add(new SearchResult<T>
            {
                Item = item,
                Text = text,
                Similarity = similarity
            });
        }
    }

    return results.OrderByDescending(r => r.Similarity).ToList();
}

// 部分一致を含む検索を行う
public List<SearchResult> SearchWithPartialMatch(string query, IEnumerable<string> items)
{
    var results = new List<SearchResult>();
    var normalizedQuery = Normalize(query);

    foreach (var item in items)
    {
        var normalizedItem = Normalize(item);
        double similarity;

        // 完全一致
        if (normalizedItem == normalizedQuery)
        {
            similarity = 1.0;
        }
        // 部分一致（クエリがアイテムに含まれる）
        else if (normalizedItem.Contains(normalizedQuery))
        {
            similarity = 0.9 * ((double)normalizedQuery.Length / normalizedItem.Length);
        }
        // N-gram類似度
        else
        {
            similarity = CalculateNGramSimilarity(query, item, _ngramSize);
        }

        if (similarity >= _threshold)
        {
            results.Add(new SearchResult
            {
                Text = item,
                Similarity = similarity
            });
        }
    }

    return results.OrderByDescending(r => r.Similarity).ToList();
}

実際に動かしてみる

上記で作成したコードをサンプルとして動かしてみます

// 検索対象のデータ
var products = new List<string>
{
    "東京タワー",
    "とうきょうタワー",
    "トウキョウタワー",
    "東京スカイツリー",
    "大阪城",
    "おおさかじょう",
    "名古屋城",
    "富士山",
    "ふじさん",
    "フジサン",
    "Microsoft Office",
    "マイクロソフト オフィス",
    "ＭＩＣＲＯＳＯＦＴ　ＯＦＦＩＣＥ"
};

// 検索インスタンスを作成（N-gram=2, 閾値=0.2）
var fuzzySearch = new JapaneseFuzzySearch(ngramSize: 2, threshold: 0.2);

// テスト1: カタカナ・ひらがな混在検索
Console.WriteLine("【検索1】「とうきょう」で検索:");
var results1 = fuzzySearch.Search("とうきょう", products);
foreach (var result in results1)
{
    Console.WriteLine($"  {result}");
}

// テスト1結果 : ひらがな・カタカナどちらも同じ数値でヒットしている
//【検索1】「とうきょう」で検索:
//  とうきょうタワー (類似度: 57.1%)
//  トウキョウタワー (類似度: 57.1%)

// テスト2結果 : 半角・全角・大文字・小文字が含まれていても同じ数値でヒットしている
//【検索2】「microsoft」で検索:
//  Microsoft Office (類似度: 61.5%)
//  ＭＩＣＲＯＳＯＦＴ　ＯＦＦＩＣＥ (類似度: 61.5%)

問題なく動作することがわかりましたが、精度などは調整しつつ使用する必要があると感じました。そのため、今度はライブラリを使用したバージョンについて記載したいと思います。また、いつものように上記サンプル含め、いつも通りGitHubにアップしていますので参考にしてください

サンプルコード
BlogSampleCodeProjects/JapaneseFuzzySearch at main · nasuton/BlogSampleCodeProjects · GitHub
BlogSampleCodeProjects/JapaneseFuzzySearch at main · nasuton/BlogSampleCodeProjects · GitHub

Project for sample code used in the blog.(Blogで記載しているサンプルコード ...

GitHubへ

会社紹介

私が所属しているアドバンスド・ソリューション株式会社(以下、ADS)は一緒に働く仲間を募集しています

会社概要
「技術」×「知恵」＝顧客課題の解決・新しい価値の創造

この方程式の実現はADSが大切にしている考えで、技術を磨き続けるgeekさと、顧客を思うloveがあってこそ実現できる世界観だと思っています
この『love & geek』の精神さえあれば、得意不得意はno problem！
技術はピカイチだけど顧客折衝はちょっと苦手。OKです。技術はまだ未熟だけど顧客と知恵を出し合って要件定義するのは大好き。OKです
凸凹な社員の集まり、色んなカラーや柄の個性が集まっているからこそ、常に新しいソリューションが生まれています

ミッション
私たちは、テクノロジーを活用し、業務や事業の生産性向上と企業進化を支援します

ホームページ
アドバンスド・ソリューション株式会社｜ADS Co., Ltd.
アドバンスド・ソリューション株式会社｜ADS Co., Ltd.

Microsoft 365／SharePoint／Power Platform／Azure による DX コンサル・シス ...

サイトへ移動

PR

-プログラム, 技術
-