検索エンジンを作る

第18回 プロパティ検索式の最適化ポイント

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

論理演算の最適化

もう1つFINDSPOTの内部処理で,プロパティ検索に関して最適化を行った点があります。それはヒット結果集合に対する論理演算の方法です。

FINDSPOTの1つの文書に対する検索結果は,これまでの連載でも説明したように,次のように4つの情報で構成されています。

1つの文書に対する検索結果

  • 文書ID
  • 文中での検索語の出現位置
  • 文中での出現回数
  • 検索結果のソート用のキー情報(複数)

なお,全文検索対象として指定されていないプロパティ(書誌データベースに保存されたプロパティ)に対するプロパティ検索の場合には,文中での検索語の出現位置と文中での出現回数はセットされません。

この4つの情報を1要素として,複数の検索結果を格納したものがヒット結果集合です。ヒット結果集合に対するAND, OR, NOTなどの論理演算がどのように実現できるかを見ていきましょう。

まず,論理演算は検索結果の情報のうち,文書IDを対象に集合演算を行う点に着目してください。文書ID以外の検索結果情報は論理演算の場面では関係がないので,以下の説明では省略します。

たとえば,次のようなヒット結果集合のAとBが存在したとします。

表2

ヒット結果集合 文書ID
1, 4, 6, 12
2, 3, 4, 5, 6

「A AND B」の集合演算は,ヒット結果集合Aとヒット結果集合Bの両方に存在する文書IDを求める操作になります。ここでの「A AND B」の答は共通に存在する文書IDということで「4, 6」になります。

このAND演算のアルゴリズムをPerlで表現してみましょう(FINDSPOTは実際にはC++で記述していますが,ここでは説明を簡単にするためPerlで解説します)⁠

リスト1 Pealで記述したAND演算

my @a = ( 1, 4, 6, 12 );  ← ヒット結果集合A
my @b = ( 2, 3, 4, 5, 6 );  ← ヒット結果集合B
my @ans;

foreach my $unit_a (@a)
{
  foreach my $unit_b (@b)
  {
    if ($unit_a == $unit_b)
    {
      push @ans, $unit_a; 
    }
  }
}

foreach my $x (@ans)
{
  print "$x\n";
}

リスト1内のif文の箇所は,集合Aの要素の数と,集合Bの要素の数のかけ算の回数実行されます。つまり,この方法によると,集合Aの要素の数をN,集合Bの要素の数をMとすると,O(MN)の計算量が必要になります。この例では,集合Aの要素数が4, 集合Bの要素数が5なので,20回の比較となります。

一般に集合は順序を持っていませんが,FINDSPOTのヒット結果集合はリストの形をしているため順序があります。また,リストの要素は文書IDの順で並んでいるという特徴があります。この特徴を論理演算のアルゴリズムに生かして,次のように二分検索を使って合致集合Bの要素を求めることができます。

リスト2 二分検索を使った最適化

my @a = ( 1, 4, 6, 12 );
my @b = ( 2, 3, 4, 5, 6 );
my @ans;

foreach my $unit_a (@a)
{
  my $match = bsearch($unit_a, \@b);
  if ($match != -1)
  {
    push @ans, $unit_a; 
  }
}

foreach my $x (@ans)
{
  print "$x\n";
}

sub bsearch($)
{
  my ($unit, $ref_list) = @_;
  my @list = @$ref_list;
  return bsearch_x($unit, 0, $#list, $ref_list);
}

sub bsearch_x($)
{
  my ($unit, $from, $to, $ref_list) = @_;
  my @list = @$ref_list;
  if ($from > $to)
  {
    return -1;
  }
  my $pos = int(($from + $to) / 2);
  my $x = $list[$pos] - $unit;
  if ($x == 0)
  {
    return $unit;
  }
  elsif ($x > 0)
  {
    return bsearch_x($unit, $from, $pos - 1, $ref_list);
  }
  else
  {
    return bsearch_x($unit, $pos + 1, $to, $ref_list);
  }
}

この工夫で,比較は9回に減らすことができます。O記法ではO(M log 2 N)と遙かに少ない演算で同じ結果が得られます。Mが4個,Nが5個の場合には20回から9回への減少ですが,前回のようにMが15万個,Nが96万個の場合には,総当たりの方法では1440億回もの比較が必要ですが,最適化後の方法では150000×log 2 960000を計算すると約298万回の比較と,遙かに少ない計算量で同じ処理を行えます。

FINDSPOTの初期実装では,前述の総当たりの方法で論理演算を行っていましたが,現在は後述のアルゴリズムで論理演算を済ます工夫を取り入れています。

著者プロフィール

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

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

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

著書

コメント

コメントの記入