はじめに

本記事では、あいまい検索の中でも比較的シンプルな実装について、ご紹介します。

また、住所一覧から住所を検索するUnityエディタ用の機能を用意して、動作を確認してみます。

参考情報

本記事を執筆するにあたり、以下を参考にいたしました。
有益な情報を公開していただき、ありがとうございます。

実装に関する参考情報

より高度な実装が知りたい方は、こちらをご参照ください。

住所一覧に関する参考情報

動作確認時に使用する住所一覧については、以下よりダウンロードした情報を元に作成しました。
https://postaladdress.jp

動作確認用の住所検索ウィンドウの実装

あいまい検索の動作確認用に、住所検索をおこなうウィンドウを実装します。

文字列を入力する欄を用意する
ここに入力された文字列を元に、住所一覧から一致率の高いものを検索します。
検索候補の住所一覧を表示する枠を用意する
有力な候補を最大10件表示するようにします。
各候補の末尾に選択ボタンを用意し、押下することで入力文字列を候補内容に置換します。

住所検索ウィンドウの見た目

検索対象の住所一覧は、改行区切りで Assets/addresses.txt に保存されている前提です。
住所は 漢字表記<カタカナ表記> のフォーマットで記述されています。
なお、今回用意した住所一覧の件数は、全部で118,891件となっています。

住所検索ウィンドウの実装は本題ではないので、スクリプトの記載のみに留めておきます。

住所検索ウィンドウの実装

Unity2022.3.54f1にて、動作を確認しています。

AddressSearchWindow.cs

using System;
using System.IO;
using System.Linq;
using UnityEditor;
using UnityEngine;

public sealed class AddressSearchWindow : EditorWindow
{
    private string[] _addresses = Array.Empty<string>();
    private string _inputText;

    [MenuItem("Window/住所検索ウィンドウを開く")]
    private static void Open()
    {
        GetWindow<AddressSearchWindow>();
    }

    private void OnGUI()
    {
        if (_addresses.Length == 0)
        {
            _addresses = File.ReadAllLines("Assets/addresses.txt");
        }

        _inputText = FuzzySearchField(_inputText, _addresses);
    }

    /// <summary>
    /// あいまい検索フィールドを描画する.
    /// </summary>
    /// <param name="inputText">入力文字列</param>
    /// <param name="candidates">検索対象の文字列群</param>
    /// <param name="viewCount">検索候補の最大表示件数</param>
    /// <returns></returns>
    private string FuzzySearchField(string inputText, string[] candidates, int viewCount = 10)
    {
        // 入力内容の更新.
        inputText = EditorGUILayout.TextField(inputText);
        if (string.IsNullOrWhiteSpace(inputText))
        {
            // 空なら, 候補は表示しない.
            return inputText;
        }

        // 入力内容を元に, 候補一覧をスコアリングして絞り込む.
        // ※ threshold を求める式は感覚で決めたものであり, 根拠はありません.
        var scores = candidates.Select(s => CalculateScore(s, inputText)).ToArray();
        var threshold = scores.Max() - viewCount;
        var targetIndexes = Enumerable.Range(0, scores.Length)
            .Where(i => scores[i] >= threshold)
            .OrderByDescending(i => scores[i])
            .Take(viewCount)
            .ToArray();

        // 絞り込まれた結果を表示.
        foreach (var index in targetIndexes)
        {
            using var horizontal = new EditorGUILayout.HorizontalScope();
            using (new EditorGUI.DisabledScope(true))
            {
                EditorGUILayout.TextField(candidates[index]);
            }

            if (GUILayout.Button("選択"))
            {
                inputText = candidates[index];
                EditorGUI.FocusTextInControl(string.Empty);
            }
        }

        return inputText;
    }

    /// <summary>
    /// あいまい検索用に一致率をスコアリングする処理.
    /// </summary>
    /// <param name="text"></param>
    /// <param name="pattern"></param>
    /// <returns></returns>
    private int CalculateScore(string text, string pattern)
    {
        // ここの実装が本題になります.
        return 0;
    }
}

大事な部分は以下の部分なので、以降はここの実装に絞って話を進めていきます。

/// <summary>
/// あいまい検索用に一致率をスコアリングする処理.
/// </summary>
/// <param name="text"></param>
/// <param name="pattern"></param>
/// <returns></returns>
private int CalculateScore(string text, string pattern)
{
    // ここの実装が本題になります.
    return 0;
}

最初の実装

前述の参照情報にある記事に、以下のような記述があります。

あいまい一致は、順序通りに各文字を一致しようとする。

こちらを参考にしつつ、実装してみます。
順序通りに各文字が一致するか判定し、一致した数をスコアとします。

/// <summary>
/// あいまい検索用に一致率をスコアリングする処理.
/// </summary>
/// <param name="text"></param>
/// <param name="pattern"></param>
/// <returns></returns>
private int CalculateScore(string text, string pattern)
{
    var ti = 0;
    var pi = 0;
    while (ti < text.Length && pi < pattern.Length)
    {
        if (text[ti] == pattern[pi])
        {
            ++pi;
        }
        ++ti;
    }

    // 一致した文字数をスコアとして返す.
    return pi;
}

この実装で、動作を確認してみましょう。

住所検索ウィンドウを開いて "元悪王子町" で検索してみます。

候補欄の一番上に "京都府京都市下京区元悪王子町<..." が表示されている

処理速度は申し分なく、文字の入力完了後にすぐに表示されます。
結果を見る限り、機能としても問題なさそうです。

"最初の実装"の問題点

このシンプルな実装でも十分かもしれませんが、困ることもあります。
住所一覧にはカタカナ表記も含んでいるので、今度は "モトアクオウジチョウ" で検索してみます。

候補一覧の一番上に "愛知県豊川市御津町下佐脇／..." が表示されている

この場合は目的の住所が二番目に表示されており、一番上には別のものが表示されています。

少し改良する

最初の実装では、文字の出現順序は影響するものの、連続して一致しているかどうかは影響しません。

単純に文字が含まれているかではなく、連続して一致していたらスコアを加算するようにしてみます。

/// <summary>
/// あいまい検索用に一致率をスコアリングする処理.
/// </summary>
/// <param name="text"></param>
/// <param name="pattern"></param>
/// <returns></returns>
private int CalculateScore(string text, string pattern)
{
    var score = 0;
    var consecutiveMatchCount = 0;
    var ti = 0;
    var pi = 0;
    while (ti < text.Length && pi < pattern.Length)
    {
        // 文字が連続で一致している数をカウントする.
        if (text[ti] == pattern[pi])
        {
            ++consecutiveMatchCount;
            ++ti;
            ++pi;
            continue;
        }

        // １文字しか一致しなかったなら, 一致は無かったことにする.
        if (consecutiveMatchCount == 1)
        {
            consecutiveMatchCount = 0;
            --pi;
            continue;
        }

        // ２文字以上連続で一致していたなら, 一致した数をスコアに加算する.
        if (consecutiveMatchCount > 1)
        {
            score += consecutiveMatchCount;
            consecutiveMatchCount = 0;
        }

        ++ti;
    }

    // まだスコアに加算していない分があるなら, 加算する.
    if (consecutiveMatchCount > 1)
    {
        score += consecutiveMatchCount;
    }

    return score;
}

改めて "モトアクオウジチョウ" で検索してみましょう。

候補一覧の一番上に "京都府京都市下京区元悪王子町<..." が表示されている

期待した結果になりました。
判定処理は少し複雑になりましたが、体感上は速度への影響はなさそうです。

その他の問題点

"京都府" で検索してみましょう。

一覧には "東京都府中市..." が並び、"京都府..." は一つも表示されない

この場合はそもそも "京都府" ではじまるものはひとつも表示されず、追加の入力が必須となります。

このように、まだまだ改善の余地はありそうですが、今回はここまでにしたいと思います。

おわりに

改めてのご案内となりますが、より高度な実装は前述の参照情報にある記事をご参照ください。

今回の実装では不十分な部分もあるかと思いますが、なにかのお役に立てば幸いです。

Discussion