はじめに
本記事では、あいまい検索の中でも比較的シンプルな実装について、ご紹介します。
また、住所一覧から住所を検索するUnityエディタ用の機能を用意して、動作を確認してみます。
参考情報
本記事を執筆するにあたり、以下を参考にいたしました。
有益な情報を公開していただき、ありがとうございます。
実装に関する参考情報
より高度な実装が知りたい方は、こちらをご参照ください。
住所一覧に関する参考情報
動作確認時に使用する住所一覧については、以下よりダウンロードした情報を元に作成しました。
動作確認用の住所検索ウィンドウの実装
あいまい検索の動作確認用に、住所検索をおこなうウィンドウを実装します。
- 文字列を入力する欄を用意する
ここに入力された文字列を元に、住所一覧から一致率の高いものを検索します。 - 検索候補の住所一覧を表示する枠を用意する
有力な候補を最大10件表示するようにします。
各候補の末尾に選択ボタンを用意し、押下することで入力文字列を候補内容に置換します。
住所検索ウィンドウの見た目
検索対象の住所一覧は、改行区切りで Assets/addresses.txt に保存されている前提です。
住所は 漢字表記<カタカナ表記> のフォーマットで記述されています。
なお、今回用意した住所一覧の件数は、全部で118,891件となっています。
住所検索ウィンドウの実装は本題ではないので、スクリプトの記載のみに留めておきます。
住所検索ウィンドウの実装
Unity2022.3.54f1にて、動作を確認しています。
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