読者です 読者をやめる 読者になる 読者になる

徒然なる日々を送るソフトウェアデベロッパーの記録(2)

技術上思ったことや感じたことを気ままに記録していくブログです。さくらから移設しました。

自作検索エンジンに and/or/not 機能を追加

昔作った Wikipedia タイトル専用検索エンジンに and/or/not 機能を追加してみた。
minosys.hateblo.jp

使い方は単語と単語の間に1文字以上スペースを空けて and, or, not と書く。
or, not は単独、または and 検索対象の後に書く必要がある。
(or, not の後ろに and を書いてはいけない。)
and, or, not の数に制限はないが、or, not はそれぞれ全文検索を行って
から結果集合を算出するため、遅くなる可能性がある。
and は実は省略可能。

指定例:

  1. "ガンダム ターン not ターンエー"
  2. "アルプス山脈 or ヒマラヤ山脈"

またなぜか FreeBSDコンパイルすると実行が SIGBUS でこけてしまうため、
Ubuntu 14.04LTS のサイトでテストを行った。

さて、中のロジックだが、入力文字列を空白区切りでトークン化し、単語間の区切り
文字列(つまり and, or, not)を左から順番に見つけていく。
各論理演算子に対して行う操作は以下のようになる。

  • A and B
    理論的は A の検索結果と B の検索結果の共通集合を算出すればよいが、
    それだと and が増えた時にとてつもなく遅くなるため、A を含むドキュメント
    が見つかった時に B も含むかチェックして、含まれていれば結果集合に
    追加するようにした。
  • A or B
    A の検索結果と B の検索結果を個別に求めて C++ の set_union() で
    結果集合を求める。
  • A not B
    A の検索結果と B の検索結果を個別に求めて、C++ の set_difference() で
    結果集合を求める。

"A or B", "A not B" は検索結果集合への演算なので素直にプログラミングできるが、
"A and B" は少し面倒臭い。

まず、A, B を N-gram の集合に分解し、各 N-gramについてドキュメントリストを
舐めてトークン文字列の存在を確認するのが基本的な流れとなるが、A, B が複数
N-gram から構成される場合、最初の key は文章のどこにあってもよいが、2番目
以降の key は最初の key の出現位置から文字位置の差分だけ離れたところに出現
しなければならない。(式で書くと、BM(key[0]) + n == BM(key[n])
ただし、BM()は key の出現位置を表すものとする。)

参照ドキュメントを更新するロジックは単純な単語認識で使用していたものが
そのまま利用できる。