※この記事は情報検索・検索技術 Advent Calendar 2021 24日目の記事です。

デジタル事業情報サービスユニットで検索エンジニアをしている日當（@hinatades）と申します。

本記事では、検索フォームに検索演算子を導入するメリットと、導入の際に課題になりやすい演算子の優先順位付けを実現するアルゴリズムを日経テレコンの事例をもとにご紹介します。

検索演算子とは

本記事では検索条件を表現するための演算子（記号、コマンド）を検索演算子と呼びます。 代表的なものとしてAND、OR、NOTのような論理演算子が挙げられます。

例えば、Google検索では次のような検索演算子が利用できます。 検索演算子を使うことで、スペース区切りで単語を入力するだけでは表現できない検索条件を設定できます。

意味	演算子	使用例
検索を結合する	OR	マラソン OR レース
検索から語句を除外する	-	ジャガー 速さ -自動車
特定のサイトを検索する	site:	site:youtube.com
価格を検索する	$	カメラ $400
完全一致を検索する	""で囲む	"世界一高い建築物"

なぜ検索演算子が必要なのか

検索演算子を導入することで、ユーザーは検索の精度を高めることができます。

検索の精度を表す代表的な指標として、適合率（Precision）と再現率（Recall）があります。

• 適合率: 検索結果の中の正解数 / 検索結果数
• 再現率: 検索結果の中の正解数 / 検索対象の中の正解数

一般的に適合率と再現率にはトレードオフの関係があります。適合率を上げようと、検索結果からノイズを減らそうと結果を絞り込もうとすると、逆に正解の取りこぼしも増えて再現率が下がってしまうからです。

適合率と再現率の両方を向上したい場合、検索結果を絞り込む条件と拡げる条件を上手く組み合わせる必要があります。しかし、通常、ユーザーの求めている結果はユーザーしかわからず、つまり正解集合が何であるのかは、システム側ではわかりません。

このため、ノイズを減らしつつ、かつ正解を漏れなく拾うことを高い精度で行うには、ユーザー自身が検索結果を確認しながら、条件を更新（スクリーニング）することで、期待する結果に近づけていくことが求められます。

検索演算子は、検索フォーム上で自由に組み合わせることができるため、ユーザー自身が検索結果を柔軟にスクリーニングすることができます。スクリーニングにより適合率と再現率を両立して向上させることが可能になります。

日経テレコンでの導入事例

日経テレコンは、750以上の新聞・雑誌を中心に、国内外の企業データベース、人物プロフィルなど、幅広いビジネス情報を横断的に検索できる国内最大級のデータベースサービスです。

検索エンジンはElasticsearchを採用しています。詳細はこちらをご覧下さい。

日経テレコンの料金体系は、基本料金+従量課金 になっており、検索結果で記事の見出しや本文を画面に表示するたびに課金が発生します。 そのため、サービス上で柔軟な検索条件を設定可能にし、ユーザー自身が検索精度をできるだけ高められる仕組みが求められます。 日経テレコンでは、サービスに独自の検索演算子を導入しています。

以下は、各演算子の過去一年間（2018年8月1日〜2019年7月31日）の使用率を載せています。

意味	検索演算子	使用例	使用率
検索対象の拡大	OR	ビール OR ワイン	51.05%
検索対象の絞り込み	AND	半導体 AND 生産計画	44.75%
検索対象から除外	NOT	自動車 NOT 輸出	29.77%
本文文字数の指定	ZL=	ZL=500	5.28%
掲載日の指定	DA=	DA=19990401	4.09%
見出しの指定	HL=	HL=リーマンショック	0.44%
本文の指定	FT=	FT=売上高	0.01%
媒体略号の指定	BR=	BR=NKM	0.02%
ページの指定	PG=	PG=1	0.01%

検索演算子を一つ以上含んだ検索式は、全体の54.06%ほどに上りました。 チェックボックスなど、検索フォーム以外からも検索条件を指定できるにもかかわらず、検索演算子を使った検索が全体の半分以上ありました。

次のグラフは、クエリに含まれる検索演算子の数とヒット件数を可視化したものです。

横軸がクエリ含まれる検索演算子の数で、縦軸はヒット件数の平均値になっています。 検索演算子（スクリーニング条件）を増やすことで、検索結果を絞り込めることがわかります。

このように、日経テレコンでは検索演算子が精度の高い検索をする上で重要な役割を担っていることがわかります。

検索演算子を導入する

検索演算子の導入の難易度は、検索対象となるデータを格納しているリレーショナルデータベース（RDB）や検索エンジンの仕様に強く依存します。

論理演算子

論理演算子は多くのデータベースや検索エンジンがクエリとして受け付けていて、もっとも導入しやすい演算子のひとつです。

意味	検索演算子	使用例
検索対象の絞り込み	AND	半導体 AND 生産計画
検索対象の拡大	OR	ビール OR ワイン
検索対象から除外	NOT	自動車 NOT 輸出

検索フォームに論理演算子を導入したとして、

りんご AND みかん

というクエリが入力されたとすると、RDBであれば、likeを使って

SELECT * FROM articles WHERE body like '%りんご%' AND body like '%みかん%'

のに書き換えることで、同じ意味をもつクエリ（SQL）になります。

検索エンジンを利用してる場合は、さらに簡単になります。 ElasticsearchのQuery Stringクエリは、論理演算子を受け付けているため、

{
  "query":{
    "query_string":{
       "query": "りんご AND みかん",
       "fields": ["body"]
    }
  }
}

のように、ユーザーが入力した論理演算子を含んだクエリの文字列を、そのまま使うことができます。

論理演算子の優先順位付け

論理演算を導入する上で課題となりやすいのが、論理演算子の優先順位付けです。 論理演算子の優先順位は、括弧で括ることで表現可能ですがユーザーが括弧を付けてくれるとは限りません。例えば、

りんご AND みかん OR バナナ

というクエリをユーザー入力した場合、以下の２通りの解釈が可能です。

(りんご AND みかん) OR バナナ
りんご AND (みかん OR バナナ)

括弧を明示的に付けない場合、論理演算子の優先順位は、使用しているRDBや検索エンジンの仕様で決まることになります。 しかし、本来、論理演算子の優先順位はサービスの目的にそって定めるべきであり、使用しているRDBや検索エンジンの仕様に委ねるべきではありません。 このため、論理演算子を導入する場合、サービス側で適当な演算子の優先順位を決め、ユーザーが入力したクエリに対して適切な括弧をつける処理が必要になります。 一般的に、適合率重視のサービスであればAND優先、再現率重視のサービスであればOR優先にする必要があります。

参考までに、現時点で最新のElasticsearch v7.16.1では、論理演算子に優先順位について、括弧を明示的に書くことが推奨されています。Elasticsearch6のQuery Stringクエリは、NOT > AND > OR の優先順位でしたが、7からは明示的に括弧を書くことが推奨されるようになりました。

以下からは、日経テレコンで採用している演算子の優先順位付けアルゴリズムをご紹介します。

逆ポーランド記法とスタック

逆ポーランド記法（Reverse Polish Notation, RPN）とは、数式の記述方法で、演算子を被演算子の後に記述する表記法です。 日本語では後置記法とも呼ばれたりします。 この記法は演算の優先順位を指定する括弧が不要な点が特徴のひとつです。 例えば、見慣れた中間記法の式 (1+6) * (2+3) を、逆ポーランド記法で書くと

1 6 + 2 3 + *

と書け、括弧を用いずとも計算の順番を表現できます。

逆ポーランド記法で並んだ式を評価するにはスタックを使います。計算方法としては、先頭から順に

• 値であればスタックに追加
• 演算子であれば、スタックから値を２つ取り出してしその演算子を使って計算し、結果をスタックに追加

を繰り返し、最後にスタックに残ったひとつの値が解になります。

1
1 6
7     <- 1 + 6
7 2
7 2 3
7 5   <- 2 + 3
35    <- 7 * 5

ユーザーが入力したクエリであっても、キーワード間のスペースをどの論理演算子とするかを決め、置き換えることで中間記法の数式として考えることができます。 例えば、スペースをORとみなすと、

りんご みかん バナナ  ->  りんご OR みかん OR バナナ

となり、これは数字の間に演算子を書く中間記法そのものです。

中間記法で書かれたクエリを、論理演算の優先順位を決めて逆ポーランド記法に並び替えることで、元のクエリに括弧が明記されていなくとも、クエリを設定した論理演算子の順番に評価（括弧で括る）することができます。

操車場アルゴリズム

中間記法を逆ポーランド記法に書き換えるアルゴリズムとして、操車場アルゴリズムを紹介します。

以下が処理の流れになります。

前処理として、

• スペースをどの演算子とみなすか決め、置き換える
  • りんご　みかん -> りんご OR みかん
• スペース区切りでクエリ文字列を分割してリスト化する
  • りんご OR みかん -> ["りんご", "OR", "みかん"]

ことが必要になります。

操車場アルゴリズムは次の流れで進んでいきます。キューとスタック(演算子のみが入る)が必要です。

• トークンがキーワードの場合
  • キューに追加
• トークンが演算子の場合
  • スタックから演算子を取り出して、トークンの優先順位と比較する
    • スタックから取り出した演算子の優先順位が、トークンの優先順位と同じ、もしくは高い場合
      • 演算子をキューに追加し、トークンをスタックに追加する
    • スタックから取り出した演算子の優先順位が、トークンの優先順位より低い場合
      • 演算子をスタックに追加し、トークンをスタックに追加する
• トークンが左括弧の場合
  • スタックに追加
• トークンが右括弧の場合
  • スタックのトップにあるトークンが左括弧になるまで、スタックから演算子を取り出し、キューに追加する。左括弧になったら取り出して捨てる

すべてのトークンの読み込みが終わったら、最後の処理として

• オペレータスタックが空になるまで、スタックから演算子を取り出し、キューに追加する
• キューを返す

このアルゴリズムをPythonを使ったサンプルコードにすると次のようになります。

def shunting_yard_algorithm(tokens: List[str]) -> List[str]:
    """
    引数:
        tokens(List[str]): トークナイズされたトークン
    戻り値:
        queue(List[str]): 逆ポーランド記法で並んだキュー
    """
    stack: List[str] = []
    queue: List[str] = []
    LOGICAL_OPERATORS: List[str] = ["OR", "AND", "NOT"]

    for token in tokens:
        if token in LOGICAL_OPERATORS:
            while len(stack) > 0:
                opr = stack.pop()
                if _get_rank(opr) >= _get_rank(token):
                    queue.append(opr)
                else:
                    stack.append(opr)
                    break
            stack.append(token)
        elif token == '(':
            stack.append(token)
        elif token == ')':
            while len(queue) >= 0:
                try:
                    opr = stack.pop()
                except:
                    raise ParseException()
                if opr == '(':
                    break
                queue.append(opr)
        else:
            queue.append(token)

    while len(stack) > 0:
        opr = stack.pop()
        if opr in ['(', ')']:
            raise ParseException()
        queue.append(opr)
        return queue

_get_rank() はオペレータの優先順位を返す関数です。

次に紹介する関数は、逆ポーランド表記法に並んだトークン対して、正しく括弧付けを行います。 同じ演算子が並んだ場合に余計な括弧を付けたくないので、結合するキーワードから、get_operator_in_combined_token() で括弧に囲まれていない論理演算を抜き出しています。

get_operator_in_combined_token("りんご AND ( みかん OR バナナ)")
>> {"AND"}

def create_query_with_tokens_in_rpn(tokens_in_rpn: List[str]) -> str:
    stack: List[str] = []
    query_string: str = ""
    LOGICAL_OPERATORS: List[str] = ["OR" , "AND", "NOT"]

    for i, token in enumerate(tokens_in_rpn):
        if token not in LOGICAL_OPERATORS:
            stack.append(token)
            continue
        try:
            b = stack.pop()
            a = stack.pop()
        except IndexError:
            raise ParseException()
        if not {token} >= get_operator_in_combined_token(a):
            a = "( {0} )".format(a)
        if not {token} >= get_operator_in_combined_token(b):
            b = "( {0} )".format(b)
        query_string = "{0} {1} {2}".format(a, token, b)
        stack.append(query_string)
    return query_string

まとめ

検索演算子を導入するメリットと、導入の際に課題になりやすい演算子の優先順位付けを実現するアルゴリズムを日経テレコンの事例をもとにご紹介しました。

日経テレコンの事例からわかるように、検索演算子は検索が主の機能であるサービスであるほど、ユーザーの検索条件に対する要望が高度化するため、導入のメリットがあると考えています。 検索演算子を導入することで、検索条件の幅が広がり、適合率と再現率を両立した検索が可能になります。導入はサービス画面に手を加えること無く、検索フォームだけあれば導入できます。

サービスの検索体験の向上をご検討の際に、ご参考になれば幸いです。