これまで解説したように、N-gram方式は完全一致の検索結果が保証できるという点が優れています。ところが検索という用途では、厳密な検索結果が必要とされる一方、もう少し曖昧な表現も含めて検索したいという相反する要求もあります。このようなリクエストに応えたのが、FINDSPOTの曖昧検索と呼んでいる機能です。今回は曖昧検索機能とそのしくみについて紹介します。
曖昧検索
FINDSPOTでは、文字列を検索の際に指定文字列が完全に一致していなくても、曖昧な一致についても検索結果に含めることができます。この機能を曖昧検索と呼んでいます。曖昧検索を行うには、検索クライアントからサーバに対して曖昧検索のリクエストを送信します。CGIからの検索であれば、検索フォームに用意されている「曖昧検索」チェックボックスをチェックしておき、検索を行います。
曖昧検索では、検索語に対する、部分文字列、文字の挿入、文字の欠落、文字の置換、複合パターンに関するバリエーションも検索結果に含めることができます。それぞれのバリエーションについて例を挙げて説明します。
部分文字列
検索語の一部分である部分文字列が含まれた文書も検索結果に含める処理を行います。
文字の挿入
検索語に数文字の挿入が行われた文字列が含まれた文書も検索結果に含める処理を行います。
文字の欠落
検索語から数文字分欠落した文字列が含まれた文書も検索結果に含める処理を行います。
文字の置換
検索語から数文字分入れ代わった文字列が含まれた文書も検索結果に含める処理を行います。
複合パターン
上記の部分文字列、文字の挿入、文字の欠落、文字の置換が複合したパターンを含む文書も検索結果に含める処理を行います。
検索語に対して、どの程度の変化量までを許容値とするかが使いやすさの面で難しい所です。現在のFINDSPOTでは50％以上の合致を曖昧さの許容値としています。具体的には、検索文字列の半分以上のバイグラムが、検索文字列の倍の長さより小さい文字列の範囲に収まっているという判定条件で処理しています。
曖昧検索のしくみ
では次に、曖昧検索のしくみについて説明しましょう。FINDSPOTはN-gram方式の検索エンジンですので、N-gramの内部構造を利用して曖昧検索を実現しています。また、「第5回 N-gramのしくみ」で解説したように、各バイグラムの文字列片情報は文書中での出現位置の情報を保持していますので、この情報も曖昧検索機能の実現では活用しています。
部分文字列
部分文字列の説明として、検索文字列「台風の被害」で「台風の」を含む文書をヒットさせる例を取り上げます。
まず、「台風の」という文字列をバイグラムの文字列片に分けると次のようになります。*の付いた箇所が検索語に合致する部分です。
台風 n *
風の n+1 *
ここで、nはこの文書の「台風の」という文字列の出現位置を示します。
検索語である「台風の被害」をバイグラムの文字列片に照らしてみると、次のようになります。
台風 0 *
風の 1 *
の被 2
被害 3
バイグラムの右側の数字は、検索語の先頭からのバイグラムのオフセットです。*の付いた箇所が検索対象に合致する部分です。
4個のバイグラムに対して2個のバイグラムがマッチしており、検索文字列の半分以上の2個のバイグラムが、検索文字列の倍の長さ(10文字)より小さい文字列の範囲に収まっているという判定条件に適っています。
文字の挿入
文字の挿入の説明として、検索文字列「地震被害」で「地震の被害」を含む文書をヒットさせる例を取り上げます。
「地震の被害」という文字列をバイグラムの文字列片に分けると次のようになります。
地震 n *
震の n+1
の被 n+2
被害 n+3 *
検索語である「地震被害」のバイグラムに照らしてみると次のようになります。
地震 0 *
震被 1
被害 2 *
バイグラムの数としては、3個中2個に合致し50％以上の基準を満たしており、検索文字列の半分以上の2個のバイグラムが、検索文字列の倍の長さ(8文字)より小さい文字列の範囲に収まっているという判定条件に適っています。
文字の欠落
文字の欠落の説明として、検索文字列「中小企業雇用対策」で「中小企業対策」を含む文書をヒットされる例を取り上げます。
「中小企業対策」というバイグラムの文字列片に分けると、次のようになります。
中小 n *
小企 n+1 *
企業 n+2 *
業対 n+3
対策 n+4 *
検索語である「中小企業雇用対策」のバイグラムに照らしてみると次のようになります。
中小 0 *
小企 1 *
企業 2 *
業雇 3
雇用 4
用対 5
対策 6 *
バイグラムの数としては、7個中4個に合致しており、検索文字列の半分以上の4個のバイグラムが、検索文字列の倍の長さ(16文字)より小さい文字列の範囲に収まっているという判定条件に適っています。
文字の置換
文字の置換の説明として、検索文字列「アラビア語」で「アラビヤ語」を含む文書をヒットさせる例を取り上げます。
「アラビヤ語」という文字列をバイグラムの文字列片に分けると次のようになります。
アラ n *
ラビ n+1 *
ビヤ n+2
ヤ語 n+3
検索語である「アラビア語」のバイグラムに照らしてみると次のようになります。
アラ 0 *
ラビ 1 *
ビア 2
ア語 3
バイグラムの数としては、4個中2個に合致しており、検索文字列の半分以上の2個のバイグラムが、検索文字列の倍の長さ(10文字)より小さい文字列の範囲に収まっているという判定条件に適っています。
複合パターン
複合パターンの説明として検索文字列「首都の中心部」で「首都東京の中心」を含む文書をヒットさせる例を取り上げます。
「首都東京の中心」という文字列をバイグラムの文字列に分けると次のようになります。
首都 n *
都東 n+1
東京 n+2
京の n+3
の中 n+4 *
中心 n+5 *
検索語である「首都の中心部」のバイグラムに照らしてみると次のようになります。
首都 0 *
都の 1
の中 2 *
中心 3 *
心部 4
バイグラムの数としては、5個中3個に合致しており、50％以上の基準を満たしています。検索文字列の半分以上の3個バイグラムが、検索文字列の倍の長さ(12文字)より小さい文字列の範囲に収まっているという判定条件に適っています。
まとめ
バイグラムの文字列単位で照合して50％以上が合致し、かつ合致したバイグラムが検索文字列の倍の長さ以下の範囲に収まっているという数学的なルールは、人間の曖昧さの範疇をかなりうまく表現しているように思います。FINDSPOTではこの50%ルールをプログラムとして実装していますが、将来的には50％という閾値をパラメータで指定できるような機能拡張も計画しています。
実は、筆者はsedのようなUNIX関連のツールを長年使っているので、FINDSPOTで正規表現をサポートすることを最初に計画しました。しかし、一般の利用者には正規表現は理解しにくいし、知っていたとしても、検索式に入力するかとなるとはなはだ怪しいように思われました。
そこで、もっと別の使いやすい近似表現を見つけ出す方法としてたどり着いたのが、曖昧検索機能です。曖昧検索機能であれば、曖昧検索を指定するチェックボックスにチェックを入れるだけなので、正規表現のような難しい検索式を使いたくない人でも十分に使いこなせるのではないかと考えています。
