検索エンジンを作る

第8回 検索と論理式

この記事を読むのに必要な時間:およそ 2 分

文書集合

ここで「文書集合」という概念が出てきました。文書集合はFINDSPOTのしくみを理解するのに欠かせない概念なので,もう少し詳しく解説しましょう。

FINDSPOTの全文検索インデックスの中には,連載第5回で解説したように,文書IDとN-gramの文字列素の文中での出現位置情報が入っています。

N-gramによる文字列の検索結果として,文書IDと,文字列の文中での出現位置が得られます。同じ文書中に検索文字列が複数箇所に出現することがあるので,検索結果は文書ごとにいったん次のように集計を行います。

  • 文書ID
  • 文中での出現位置(複数出現した場合には一番文頭に近い位置)
  • 文中での出現回数
  • 検索結果のソート用のキー情報(複数)

これが1つの文書に対する検索結果です。この情報をFINDSPOTでは「ヒットユニット」という名前で呼んでいます。文中での出現位置の情報をヒットユニットに入れているのは,検索結果の一覧を表示する際に,文書中のヒットした箇所の近傍を表示するためです。また,文中での出現回数や,ソート用のキー情報は,検索結果を表示する際の表示順を決定するのに用います。

文書集合はヒットユニットを複数集めたものになっています。文書集合は別の文書集合との間で,AND(論理積)の集合演算ができる他,OR(論理和),NOT(否定)などの集合演算ができるしくみになっています。

非常に複雑な検索式で検索を行う場合には,検索式の部分部分の文書集合が大きいと,それだけ検索エンジンにかかる負荷が大きくなり,検索時間もかかってしまいます。検索式のチューニングを行う場合には,この文書集合の大きさに着目して,文書集合がなるべく小さくなるように検索式を工夫すると効率の良い検索が行えます。

検索式の最適化は大きなテーマなので,別の機会に詳しく解説したいと思います。

パーサジェネレータ Lemon

C/C++言語用のパーサジェネレータといえば伝統的にyacc, bisonという感があります。ところが出力するコードを見ると静的変数が多用されており,リエントラントになっていません。つまり,yacc, bisonで作成したパーサは,マルチスレッドでの利用用途には使えないのです。

このような理由からFINDSPOTの初期の実装では,LL(1)文法のパーサをすべて手書きで記述し,検索エンジンのパーサがマルチスレッドで動作しても問題がないようにしていました。ところが,だんだんと機能が増えて検索式の構文が複雑になってくると,さすがにすべて手書きでパーサを記述するのは厳しくなってきます。そこで,このような利用用途に合ったパーサジェネレータを探していて見つけたのがLemonというパーサジェネレータです。Lemonは最近利用が増えているSQLiteというオープンソースのデータベースのソースコードに含まれています。また,LemonはSQLiteのプロジェクトの一部としてメンテナンスされています。

Lemonの本家
Lemonのチュートリアルの日本語訳

FINDSPOTの検索式を解析するパーサは,このLemonというパーサジェネレータを用いて書き直して現在に至っています。秀逸なパーサジェネレータであり,yacc, bisonの経験があればあまり苦もなく使いこなせるのではないかと思います。一点,難があるとすれば,あまり知られていないためか,ドキュメントやサンプルが少ないという点でしょうか。今後,CPUの複数コア化が進むことが見込まれているので,この傾向に併せてマルチスレッドのソフトウェア開発が増えてくるはずです。マルチスレッド用途に利用できるLemonは今後の注目株です。

著者プロフィール

工藤智行(くどうともゆき)

有限会社サイパック取締役社長。システム構築・管理のコンサルティング,ローカライゼーション,文書処理や障害者向けソフトウェアを中心とするプログラミングを長年手がける。 近著『UNIXプログラミングの道具箱』『システム管理現場の鉄則FreeBSD編』等

URLhttp://www.cypac.co.jp/

著書