まだピクミン2をクリアしてないのでケジメ的に新作ゲームを買えないmikioです。今回は、Tokyo Cabinetを使って激烈簡単に特定サイトの専用の検索機能を設置する方法について説明します。クローリングから検索までを10分くらいの作業で可能にします。

特定サイトの検索エンジン

Web全体の検索機能を作るのは、途方もない技術力と設備を持っているGoogleやMicrosoftなどのビッグプレーヤでないと難しいのが現実です。でも、自分が気に入っているいくつかのサイトを対象とした検索エンジンを作るのであれば個人だってできます。また、インターネットから手が届かないイントラネットのコンテンツの検索機能は自分達で手がけないと構築できません。

ということで、企業用の検索システムが数多く売られていますし、LuceneやGroongaやHyper Estraierなどのオープンソース製品も世に多数存在します。それらに比べてTCによる検索システムが性能的あるいは機能的な観点で優れていると主張するつもりはありませんが、構築が簡単だという点はこの記事で伝わればいいかなと思っています。

実際にやってみる

はい、今から10分です。まずはこちらのコマンドをダウンロードして、wgettsv という名前で保存してください。それを実行します。例として、intra.example.com の全てのHTMLコンテンツを最大10000ファイルだけ収集してきてそれをTSVファイルに保存してみます。URLをあなたのオフィスのものに置き換えて動かしてみてください（もちろん自己責任でですが）。

$ ruby wgettsv -allow 'http://intra\.example\.com/' \
  -max 10000 'http://intra.example.com/' > intra.tsv

「-allow」オプションは、再帰的にコンテンツを取得する際に許容する飛び先のURLを指定します。example.comのイントラネットである intra.example.com ドメインのコンテンツのみを取得するようにしています。「-deny」オプションで禁止パターンを指定することもできます。「-max」オプションは最大取得数を指定します。最後の引数のURLはクロールのエントリポイントです。これは複数指定することもできます。

サイトの規模や回線の速度によりますが、小組織なら5分もあればクロールが終わると思います。ブログなどを再帰的に巡回させるとキリがないので、そういう場合は「-deny」で不要なクローリングを除外してください。クロールしてきたデータは文字コードをUTF-8に正規化した上で body や title や mtime などの属性を抽出し、それらを表現したTSVデータとして標準出力に流します。今回はそれを intra.tsv というファイルにリダイレクトして保存しています。このTSVファイルはTCのテーブルDBのインポートコマンドが期待する形式になっていますので、すぐにもインデックス作成を開始できます。

$ tctmgr importtsv tctsearch.tct intra.tsv
$ tctmgr setindex -it qgram tctsearch.tct title
$ tctmgr setindex -it qgram tctsearch.tct body

TSVファイルからインポートして tctsearch.tct というインデックスを作成して、titleコラムとbodyコラムにインデックスを張っています。5分でクロールしたくらいのレコード数であれば、この作業は数秒で終わると思います。

検索UIを設置します。Tokyo Cabinetのソースパッケージに example というディレクトリがあり、その中に検索UIのサンプルが含まれています。makeしてから、tctsearch.cgi と tctsearch.tmpl をCGIが実行できるディレクトリにコピーしてください。また、インデックスも同じディレクトリに移動してください。

$ cd tokyocabinet-1.4.29/example
$ make
$ cp tctsearch.cgi tctsearch.tmpl ~mikio/public_html
$ mv ~/mikio/tctsearch.tct ~mikio/public_html

あとは、設置した tctsearch.cgi にWebブラウザでアクセスするだけです。ここまで10分以内でできますよね？ UIをカスタマイズしたい場合は tctsearch.tmpl を適当に修正してください。インデックスを定期的に更新したい場合は、クロールとインデクシングの手順をシェルスクリプトに書いてcrondに実行させればよいでしょう。

Perl/Ruby/Javaで検索UIを作る

上記で設置したデモ用の検索用CGIスクリプトは、以前の記事で述べたTCのテンプレート直列化機能を用いてC言語で実装したものです。100行に満たないCのコードでここまで表現できるのは我ながら素敵だなと思うわけですが、しかしCプログラマの数は各種スクリプト言語のプログラマの数に比べてかなり少ないのが現実です。Cプログラマでも、UI層をCで書くなんて常軌を逸していると感じるかもしれません。私の趣味はさておき、CGIスクリプトと言えばスクリプト言語の出番ですよね。ということで、PerlとRubyとJavaでサンプルを実装してみました。いずれもロジック部分は50行以下で済んでいます。

Perlで書くとロジック部分は以下のようになります（完全なソースコードはこちら）。ロジック部分と表示部分を完全に分けて記述するのがCGIスクリプトを美しく書くコツです。この例では検索結果の主キーのリストをforeachで回して各々の文書情報をわざわざ@docsという配列に入れて、あとは@docsをforeachで回して表示するようにしています。metasearchとkwicというメソッドが謎な感じですが、それらについては後述します。

# CGI処理オブジェクトを作り、パラメータを受け取る
my $cgi = CGI->new();
my $scriptname = $cgi->script_name();
my $expr = $cgi->param("expr");

# 検索語が入力されていれば検索を行う
my @docs;
if(defined($expr) && length($expr) > 0){

  # データベースを開く
  my $tdb = TokyoCabinet::TDB->new();
  $tdb->open(DBPATH);

  # クエリオブジェクトを作る
  my $tqry = TokyoCabinet::TDBQRY->new($tdb);
  $tqry->addcond("title", $tqry->QCFTSEX, $expr);
  $tqry->setorder("title", $tqry->QOSTRASC);
  $tqry->setlimit(30, 0);
  my $bqry = TokyoCabinet::TDBQRY->new($tdb);
  $bqry->addcond("body", $bqry->QCFTSEX, $expr);
  $bqry->setorder("title", $bqry->QOSTRASC);
  $bqry->setlimit(30, 0);

  # 検索する
  my $res = $tqry->metasearch([ $bqry ], $tqry->MSUNION);

  # 該当文書の情報を取り出して表示用の配列に入れる
  foreach my $pkey (@$res){
    last if(@docs >= 30);
    my $cols = $tdb->get($pkey);
    if(defined($cols)){
      my $kwic = $bqry->kwic($cols, undef, 20, $bqry->KWMUCTRL);
      $cols->{kwic} = $kwic;
      push(@docs, $cols);
    }
  }

  # データベースを閉じる
  $tdb->close();

}

Rubyで書くとロジック部分は以下のようになります（完全なソースコードはこちら）。Perlと全く同じ流れです。

# CGI処理オブジェクトを作り、パラメータを受け取る
cgi = CGI::new
scriptname = cgi.script_name
expr = cgi.params["expr"][0]

# 検索語が入力されていれば検索を行う
docs = []
if expr && expr.length > 0

  # データベースを開く
  tdb = TDB::new
  tdb.open(DBPATH)

  # クエリオブジェクトを作る
  tqry = TDBQRY::new(tdb)
  tqry.addcond("title", TDBQRY::QCFTSEX, expr)
  tqry.setorder("title", TDBQRY::QOSTRASC)
  tqry.setlimit(30, 0)
  bqry = TDBQRY::new(tdb)
  bqry.addcond("body", TDBQRY::QCFTSEX, expr)
  bqry.setorder("title", TDBQRY::QOSTRASC)
  bqry.setlimit(30, 0)

  # 検索する
  res = tqry.metasearch([ bqry ], TDBQRY::MSUNION)

  # 該当文書の情報を取り出して表示用の配列に入れる
  res.each do |pkey|
    break if(docs.length >= 30)
    cols = tdb.get(pkey)
    if cols
      kwic = bqry.kwic(cols, nil, 20, TDBQRY::KWMUCTRL)
      cols["kwic"] = kwic
      docs.push(cols)
    end
  end

  # データベースを閉じる
  tdb.close()

end

Java（JSP）で書くとロジック部分は以下のようになります（完全なソースコードはこちら）。PerlやRubyと全く同じ流れです。

// サーブレットリクエストからパラメータを受け取る
request.setCharacterEncoding("UTF-8");
response.setCharacterEncoding("UTF-8");
String expr = request.getParameter("expr");

// 検索語が入力されていれば検索を行う
List docs = new ArrayList();
if(expr != null && expr.length() > 0){

  // データベースを開く
  TDB tdb = new TDB();
  tdb.open(dbpath, TDB.OREADER);

  // クエリオブジェクトを作る
  TDBQRY tqry = new TDBQRY(tdb);
  tqry.addcond("title", TDBQRY.QCFTSEX, expr);
  tqry.setorder("title", TDBQRY.QOSTRASC);
  tqry.setlimit(30, 0);
  TDBQRY bqry = new TDBQRY(tdb);
  bqry.addcond("body", TDBQRY.QCFTSEX, expr);
  bqry.setorder("title", TDBQRY.QOSTRASC);
  bqry.setlimit(30, 0);
  TDBQRY[] oqrys = { bqry };

  // 検索する
  List res = tqry.metasearch(oqrys, TDBQRY.MSUNION);

  // 該当文書の情報を取り出して表示用の配列に入れる
  Iterator resit = res.iterator();
  while(docs.size() < 30 && resit.hasNext()){
    byte[] pkey = (byte[])resit.next();
    Map cols = tdb.get(new String(pkey, "UTF-8"));
    if(cols != null){
      String[] kwic = bqry.kwic(cols, null, 20, TDBQRY.KWMUCTRL);
      cols.put("kwic", kwic);
      docs.add(cols);
    }
  }

  // データベースを閉じる
  tdb.close();

}

3言語ともほとんど同じ構造になるあたり、tokyocabinet.idlの威力を感じていただけたのではないかと思います。各種言語の良さを100%引き出すインターフェイスにはなっていませんが、どれかひとつでの書き方を知っていれば他の言語でもサクっと仕上げて定時に帰れるというのが素敵ポイントです。

メタ検索

Webコンテンツの全文検索においては、「タイトルもしくは本文のいずれかに検索文字列を含む」という条件を指定するのが普通です。言い換えれば、「検索文字列をタイトルに含む」文書群と「検索文字列を本文に含む」文書群の和集合を提示するということです。TCのテーブルデータベースでは、ひとつのクエリオブジェクトに複数の条件をaddcondメソッドで追加していくことで論理積（AND条件：積集合）を表現することができますが、その方法では論理和（OR条件：和集合）を表現することはできません。それだとWeb検索の典型的なユースケースであるタイトルと本文を対象とした検索では困ったことになります。

そこで、複数のクエリオブジェクトを使って積集合、和集合、差集合を表現するためのメタ検索という機能が提供されています。例えば、qry1.metasearch([qry2,qry3], TDBQRY.MSISECT); とすると、qry1とqry2とqry3の検索結果の積集合（つまり全てクエリの結果に含まれる主キーの集合）を問い合わせることができます。また、qry1.metasearch([qry2,qry3], TDBQRY.MSUNION); とすると、qry1とqry2とqry3の検索結果の和集合（どれかのクエリの結果に含まれる主キーの集合）を問い合わせることができます。qry1.metasearch([qry2,qry3], TDBQRY.MSDIFF); とすると、qry1と「qry2とqry3の和集合」の差集合（つまりqry1に含まれるがqry2にもqry3にも含まれない主キーの集合）を問い合わせることができます。

単純な検索エンジンとしての効率を求めるならば、タイトルと本文を連結した文字列を単一のコラムとして格納しておいて、それを対象とした検索をすればいいでしょう。ただ、そうしてしまうと「タイトルのみに含む」という条件や「本文のみに含む」という条件を指定することができなくなってしまうので、痒いところに手が届かなくなってしまいます。効率を求めるか機能性を求めるかはユースケースに応じて決定すべきなわけですが、後者を選択する場合にはメタ検索機能を重宝することになるでしょう。

メタ検索機能の嬉しい副作用として、複数のデータベースにまたがった検索ができるということが挙げられます。メールを格納したデータベースと接続したクエリオブジェクトとチャットログを格納したデータベースと接続したクエリオブジェクトに対して論理和のメタ検索を行えば、メールとチャットログの統合検索が可能となります。メーリングリスト毎に別個のデータベースを作っておいて、それらをチェックボックスで選択して統合検索するようなUIも簡単に作ることができます。

スケーラビリティの観点からも、メタ検索機能は重要です。いわゆるリアルタイム検索を想定した場合、更新の負荷を下げることが重要となりますが、そのためにはデータベースを細かく分割することが必要となります。すなわち、主キーにハッシュ関数などを適用して格納先のデータベースを決定する、いわゆる水平分散（sharding）という手法です。大規模な文書群を対象とした検索機能を構築する場合にも水平分散は重要となるでしょう。分割数を上げるほどに検索の負荷は上がりますが、更新の負荷はその分だけ下げることができます。よって、分割数を調整することで検索負荷と更新負荷のバランスポイントに近づくことができるわけです。単体のホスト内でもデータベースを分けて水平分散を行い（必要であればマルチスレッドで並列処理を行い）、ホスト間でも水平分散してさらなる性能向上を図るという二段階の視点がスケーラビリティ向上には重要です。ホスト間の分散についてはTCの領域ではありませんのでアプリ層で頑張ってくれというスタンスですが。

KWIC

検索に多数の文書がヒットした場合、文書内のどこに検索語が含まれるかと、その検索語がどんな文脈で使われているかを提示することで、実際にどの文書が欲しいものなのかを判断する手助けをするのが普通です。KWIC（KeyWord In Context）とかスニペットとか呼ばれるような、本文から検索語の周辺部分を抜き出した文字列を提示するということです。Googleとかでも検索結果に太字の検索語とともに周辺文が提示されますよね。

このKWICですが、アプリ側で実装しようとすると意外に大変なのです。材料として検索語のリストと本文の文字列があればよいのですが、処理内容は著しく複雑です。正規表現でやろうとすると周辺文を領域を指定するのが厄介ですし、何より普通の正規表現では検索語をきちんと表現できないのです。というのも、全文検索においては正規表現よりも強烈に文字列の正規化をしているからです。例えば、TCでは検索対象の文字列に以下のような正規化を施しています。

• 全角英数字を半角英数字にする。
• 半角カタカナを全角カタカナにする。
• ウムラウトやセディーユなどのアクセント記号を外す。
• 英字やギリシャ文字やスラブ文字の大文字を小文字にする。
• タブや改行やその他の空白文字および制御文字を通常の空白文字にする。

これらの正規化をするだけなら各種のライブラリを使えばよく、正規化した後なら一般的な正規表現の実装で検索語に該当する部分を特定することができるでしょう。しかし、ハイライトさせる文字列は正規化する前のものでないといけないため、正規化した後で正規表現をかけるという方法は通用しないのです。例えば「I’m Mikio Hirabayashi」を「I’m <strong>Mikio</strong> Hirabayashi」としたいとしましょう。正規化して「i’m mikio hirabayashi」にしてから正規表現をかける方法だと、「mikio」の「M」が大文字だったという情報が失われてしまうのでダメです。正規表現のi（ignore-case）オプションを使えばいけそうですが、アクセント記号などを含んでいる場合にはそれもダメです。したがって、インデックス内の文字列の正規化方法を知っている動作主体が、その知識を使って部分文字列の検出および周辺文の抽出を一括で行うことが必要となります。

ということで、KWICを出力するのはインデクサのライブラリの仕事にするのが現実的です。データストレージや情報検索を担当するライブラリとしては異色の機能ですが、仕方ないのです。クエリオブジェクトにkwicメソッドが実装されています。第1引数に文書データのハッシュ、第2引数に本文を格納したコラムの名前（undef/nil/nullの場合はクエリに指定した最初の条件のコラムを自動選択）、第3引数に周辺文の文字数、第4引数にオプションをとります。オプションには、KWMUTAB（検索語をタブでマークアップ）、KWMUCTRL（検索語を0×02と0×03でマークアップ）、KWMUBRCT（検索語を [ ] でマークアップ）、KWNOOVER（周辺文のオーバーラップを禁止）、KWLEAD（文書の先頭を強制的に選択）のビット論理和を指定することができます。いわゆる普通のKWICが欲しい場合は、qry.kwic(cols, nil, 20, TDBQRY.KWMUCTRL) で得た文字列内の制御文字を出力用のマークアップに置換するのが定石でしょう。

まとめ

任意のWebコンテンツを簡易クローラで収集してインデクシングする方法と、そうしてできたインデックスを対象とした検索用ユーザインターフェイスを各種言語バインディングを用いて簡単に実装する方法について説明しました。付属のUIを設置するだけなら10分くらいでできそうだと思っていただければ幸いです。

検索UIの実装ってなかなか楽しいですよね。メタ検索やKWIC生成などの面倒な部分はTCが担当してくれるので、適切なロジックを実現するための業務分析と使いやすいインターフェイスを実現するための情報設計に工数を割くことができます。実装言語が選択できるというところも素敵ポイントかなと思っている今日この頃です。ぜひお試しあれ。

相対性理論のボーカルが頭から離れないmikioです。熱いわっふるの声に応えて今回はTokyo Cabinetのテーブルデータベースにおける検索機能の実装について語ってみたいと思います。とても長いのですが、最後まで読んだあかつきには、自分でも全文検索エンジンを作れると思っていただければ嬉しいです。

デモ

モチベーションをあげていただくために、100行のソースコードで検索UIのデモを作ってみました。Java 6の日本語文書を対象としているので、「stringbuffer」とか「コンパイル」とか「倍精度浮動小数」とかそれっぽい用語で検索してみてください。

インデックスがちゃんとできていれば、たった100行で某検索エンジン風味の検索機能をあなたのデータを対象にして動かすことができます。ソースコードはこちら（テンプレートはこちら）です。

でも、今回はUIの話ではないのです。ものすごく地味に、全文検索システムの核となる転置インデックスの設計と実装について説明します。最初に設計から入り、インデックスを構築するアルゴリズムとそれに対する検索を行うアルゴリズムを擬似コードで解説します。

概要設計

以前の記事でも述べましたが、テーブルデータベースは、ハッシュデータベースとして主キーとレコード本体のデータを関連付けて管理します。各レコードのデータは、名前と値からなるコラムの集合として記録され、ハッシュ（連想配列）と同様のインターフェイスで操作されます。

コラムインデックスを張れるというのがテーブルデータベースの最大の特徴です。全てのレコードにおける特定の名前のコラムを対象としたインデックスを管理するのです。新規に追加したレコードが該当のコラムを持っている場合や、既存のレコードの該当のコラムが更新された場合には、コラムインデックスも自動的に更新されなければなりません。コラムインデックスはB+木の外部データベースとして実現されます。処理の流れに基づいて整理すると、レコードの追加と削除については以下のデータベース操作が必要となります。

• レコードを挿入する（tctdbputkeep）
  1. レコード本体をメインのデータベースに挿入する（tchdbput）
  2. コラムの値をキー、レコード本体の主キーを値にしたデータをインデックスに挿入する（tcbdbput）

• レコードを削除する（tctdbout）
  1. レコード本体をメインのデータベースから取得する（tchdbget）
  2. コラムの値をキーとして、インデックスからデータを削除する（tcbdbout）
  3. レコード本体をメインのデータベースから削除する（tchdbout）

• レコードを更新する（tctdbput）
  1. レコード本体をメインのデータベースから取得する（tchdbget）
  2. 既存のコラムと新しいコラムを比較して異なる場合、上記のインデックス削除操作（tcbdbout）とインデックス挿入操作（tcbdbput）を行う。
  3. レコード本体をメインのデータベースに上書きで挿入する（tchdbput）

削除操作の際には既存のレコードを使ってインデックスを元に戻すということと、更新操作の際には削除を行ってから挿入を行うというところがポイントです。MySQLの各種ストレージエンジンでも、CouchDBのストレージエンジンでも、たいていのインデックス付きストレージは上記の枠組みを踏襲しているはずです。

インデックスの型による実装の分岐

文字列型や数値型といった、比較によって探索範囲を絞り込むような操作はツリー系のインデックスで高速化することができるので、実装としてB+木データベースをそのまま使えばよいでしょう。コラムの値をキーにして、該当レコードをメインデータベースから取り出すための主キーを値として関連付けてB+木に入れるのです。コラムの値は複数のレコードで重複する可能性があるので、B+木の実装は重複キーを許容するタイプのものでなければいけません。文字列型と数値型は比較方法の違いでしかないので、B+木の比較関数を文字列用と数値用で切り替える以外はほとんど同じ実装を使いまわせます。

一方で、今回のトピックである転置インデックスは、文字列型や数値型とは一線を画します。B+木を使うところは一緒なのですが、検索キーの作り方が全く違うのです。コラムの値をさらに分解して、転置インテックス用のトークンを抽出し、各トークンをキーにして、該当レコードをメインデータベースから取り出すための主キーを値として関連付けてB+木に入れるのです。

とはいえ、インデックスの型にかかわらず、各インデックスに対して「主キーとコラムの値をパラメータとして渡してインデックスを更新する」という部分は共通です。すなわち、以下のような共通インターフェイスを介して個々の実装に分岐すれば、その上層は綺麗に実装できそうです。

// インデックスにコラムの値を追加する
bool tctdb_index_insert_column(TCTDB *tdb, INDEX *idx,
  const char *pkey, const char *value);

// インデックスからコラムの値を削除する
bool tctdb_index_remove_column(TCTDB *tdb, INDEX *idx,
  const char *pkey, const char *value);

ここまでの設計を注意深く行っておけば、それより下の層はコーディングテクニックのみの世界になります。すなわち、決まった仕様をアルゴリズムに落とし込んで、そのバグのない実装をそこそこ最適化しながら書きまくるという職人芸の世界です。それでは、トークン転置インデックスおよびq-gram転置インデックスの2つの実装を見ていきましょう。

トークン転置インデックスの正直な実装

トークン転置インデックスは簡単です。コラムの値を空白とカンマで区切った文字列をトークン（検索キー）にしてB+木に入れまくるだけです。擬似コードで書くとこんな感じでしょうか。

-- トークンの区切り文字
separators = " ,"

-- インデックスにコラムの値を挿入する
index_insert_column(tdb, idx, pkey, value)
  -- トークンを分割
  tokens = split(value, separators)
  -- 各トークンをDB上のposting listに追加
  foreach token in tokens do
    idx.db.add(token, pkey)
  end
end

-- インデックスからコラムの値を削除する
index_remove_column(tdb, idx, pkey, value)
  -- トークンを分割
  tokens = split(value, separators)
  -- 各トークンのDB上のposting listを更新
  foreach token in tokens do
    -- 既存のposting listを取得
    old_pkeys = idx.db.get(token)
    -- 新しいposting listを生成
    new_pkeys = []
    -- 既存のposting listで、該当レコード以外の主キーを移行
    foreach old_pkey in old_pkeys do
      if old_pkey != pkey then
        new_pkeys.add(old_pkey)
      end
    end
    -- 新しいposting listでDBを上書き
    idx.db.replace(token, new_pkeys)
  end
end

削除処理で、既存のposting listを取得してから該当レコードの主キーのみを削って書き戻すというところがポイントです。アルゴリズム的にダサいことこの上ないこの削除処理ですが、現実的にはこのような実装が最善です。posting listを予め整列させておいて計算量が O(logN) である二分探索を摘要するという手も考えられますが、それでも削除分を詰める処理はO(N)ですし、そもそもDBに書き戻すデータ量は変わらないので全く意味がありません。上位層でデータベースやインデックスを分割するのが計算量削減には有効なのですが、それはこのモジュールの実装には関係ないことですので、このままのアルゴリズムを最適化して実装すればよいでしょう。

q-gram転置インデックスの正直な実装

q-gram転置インデックスはちょっと複雑になります。コラムの値における一定の文字数の連続した部分文字列を、1文字ずつずらしながら、全ての組み合わせを抽出したものをトークン（検索キー）とします。例えば、「abcdef」をtri-gramで処理すると「abc」「bcd」「cde」「def」「ef」「f」が抽出されます。「ef」と「f」は3文字に満たないのですが、抽出しておかないと後で検索できないので無理やり仲間に入れてあげます。トークンに対応づけて格納するposting listには、そのトークンが何番目に現れたかというオフセット情報も加える必要があります。3文字以上の検索語で検索された場合に、トークン同士が並んでいるかの隣接判定を行うためです。ということで、擬似コードはこんな感じになります。

-- q-gramの単位文字数
qgunit = 3

-- インデックスにコラムの値を挿入する
index_insert_column(tdb, idx, pkey, value)
  -- トークンを分割
  tokens = qgram_split(value, qgunit)
  -- 各トークンをDB上のposting listに追加
  offset = 0
  foreach token in tokens do
    idx.db.add(token, [pkey, offset])
    offset += 1
  end
end

-- インデックスからコラムの値を削除する
index_remove_column(tdb, idx, pkey, value)
  -- トークンを分割
  tokens = qgram_split(value, qgunit)
  -- 各トークンのDB上のposting listを更新
  foreach token in tokens do
    -- 既存のposting listを取得
    old_pairs = convert_to_pairs(idx.db.get(token))
    -- 新しいposting listを生成
    new_pairs = []
    -- 既存のposting listで、該当レコード以外の主キーのペアを移行
    foreach old_pair in old_pairs do
      if old_pair[0] != pkey then
        new_pairs.add(old_pair)
      end
    end
    -- 新しいのposting listでDBを上書き
    idx.db.replace(token, new_pairs)
  end
end

追加処理では主キーとオフセットのペアをDBに入れています。なので、削除処理では、DBから取得したposting listをペアのリストに変換した上で扱うことになります（実際にはポインタをゴニョゴニョすればいいのでわざわざ変換はしませんが）。qgram_splitをどう実装するかも結構深い課題なのですが、文字エンコーディングをUTF-8やUTF-16/32に正規化してゴニョゴニョすればよいでしょう。TCではUTF-8の入力を前提としつつUTF-16に変換してから各種の正規化を施しています。

キャッシュの活用

ここまでの説明は、「正直な実装」についてです。アルゴリズムとしては最善を尽くしていますが、これをそのまま実装すると、ディスクがガリガリ音立てまくってちょっと悲しい気持ちになるだけです。トークンを検出する度にDBの読み書きを行っているのではI/Oの負荷が高すぎるので、キャッシュを活用して性能を改善を図るのが普通です。そのためには、擬似コードにおける idx.db に対する操作を全てキャッシュに対して行うようにすればよいのです。そしてキャッシュがメモリ容量を圧迫した時にデータベースにフラッシュ（flush＝吐き出す）するようにします。TCではTCMAP（オンメモリマップ）を使ってキャッシュを実現しています。

キャッシュをフラッシュするにあたっては、キャッシュ内のレコードをインデックスのB+木の比較関数と同じ順序でソートしてから、その順番でインデックスに書き込みます。B+木はランダムアクセスよりシーケンシャルアクセスの方が圧倒的に高速だからです。それを踏まえると、キャッシュをフラッシュする戦略には2種類の解が導かれます。キャッシュ内の全レコードを一度にフラッシュする方法と、LRUなどで判定したヒット率の低いレコードのみをフラッシュする方法です。前者の戦略だとB+木のアクセスが完全にシーケンシャルになるので、スループットを最大化することができます。その反面、ソートや書き出しのために関連するリソースを長い時間ロックすることになり、レイテンシのばらつきが大きくなってしまいます。後者の戦略は全く逆の特性で、ロックの粒度が低いのでレイテンシは低く抑えられますが、B+木のアクセスパターンが悪化するので、スループットは低くなります。

冒頭のデモで用いたJava6 SDKの日本語文書約1万ファイルのインデックスを私の開発環境で作成した場合、全体を一気にフラッシュする戦略だと21秒で完了しましたが、フラッシュに最大1.78秒のロックがかかりました。ロック時間はそのままレイテンシに直結していまいます。一方でLRUの1%をちょびちょびフラッシュする戦略だと、最大0.05秒のロックで済んだ代償として、処理時間は49秒に伸びてしまいました。どちらの戦略が望ましいかはユースケースによるので、実装としてどちらを採用するかは悩ましいところです。ベンチマーク野郎達に気に入ってもらうには前者だし、SIのシーンの多くで要求されるのは後者でしょう。悩んだ末、とりあえずTCのテーブルデータベースはリアルタイム的な使い方を重視しているので、レイテンシ最低化のために後者をデフォルトにしました。ただし、インデックスを張らずにDBを作ってから後でインデックスを張る場合にのみ、一気にフラッシュする戦略で動作するようになっています。バルクでインデクシングしてリードオンリーで検索させるようなユースケースではこの方式が便利でしょう。

トークン転置インデックスを使った検索

テーブルデータベースに対してクエリが発行された際には、クエリオプティマイザによって、クエリに含まれる条件に合ったインデックスが探されて、適切なものがあればそれが使われます。トークン転置インデックスはSTRAND演算子（空白区切りトークンの完全一致AND検索）とSTROR演算子（空白区切りトークンの完全一致OR検索）の際に利用されます。いずれにせよ、クエリの式から抽出したトークンをもとにキャッシュとデータベースからposting listを取得し、それに含まれる主キーのリストを返します。STRANDの実装を擬似コードで示すと以下のようになります。

index_search_strand(tdb, idx, tokens)
  -- 最初のトークンだけ特別扱い
  res = {}
  token = tokens.shift()
  -- posting list内の主キーを結果のプールに入れる
  pkeys = idx.db.get(token)
  foreach pkey in pkeys do
    res.set(pkey)
  end
  -- 残りのトークンはAND条件で処理
  foreach token in tokens do
    nres = {}
    -- 既に取り出した集合にある主キーのみを選ぶ
    pkeys = idx.db.get(token)
    foreach pkey in pkeys do
      if res.exists(pkey) then
        nres.set(pkey)
      end
    end
    -- 結果の置き換え
    res = nres
  end
  res
end

とても簡単ですね。検索エンジンというと何だか凄い技術のように思っている人も多いかと思いますが、分かち書き方式（タグ検索方式）であれば上記のような短いコードで実装できてしまうものなのです。もちろん大規模なインデックスを扱うならばそれなりの工夫は必要になりますが、q-gram方式に比べるとインデックスも小さいし実装も単純だし、天国です。

q-gram転置インデックスを使った検索

一方で、q-gram転置インデックスは、地獄です。文字数と同じ数だけトークンが作られ、しかもposting listにオフセット情報も含めるので、インデックスのサイズが莫大になります。そして、主キーとオフセットを使ってトークンの隣接判定を行う必要があるため、実装もかなり複雑になってしまいます。q-gram転置インデックスはFTSPH演算子（フレーズ検索）とFTSAND演算子（空白区切りトークンの中間一致AND検索）とFTSOR演算子（空白区切りトークンの中間一致OR検索）とFTSEX演算子（Web検索エンジン風検索クエリ）の際に利用されます。ここではそれらに共通で呼び出される、トークンの隣接判定を伴う文字列中間一致について擬似コードを示します。

index_search_fts(tdb, idx, tokens)
  -- 隣接判定をするための全オカレンス情報の配列
  ocr = []
  -- 全トークンのposting listをオカレンス配列に入れる
  for i = 0, tokens.length do
    pairs = idx.db.get(token)
    foreach pair in pairs do
      -- そのオカレンスのトークン番号をペアに加える
      pair.push(i)
      ocr.push(pair)
    end
  end
  -- オカレンス配列をソート。主キーが第1キーでオフセットが第2キー
  sort_occrrence(ocr)
  -- 結果の主キーのセット
  res = {}
  -- オカレンス配列の全要素をスキャン
  i = 0
  while i < ocr.length do
    -- 要素を取り出す。主キーとオフセットとトークン番号のトリオ
    trio = ocr[i]
    i += 1
    -- トークン番号が0のものに着目
    if trio[2] == 0 then
      id = trio[0]
      off = trio[1]
      seq = 1
      -- 後続のオカレンスを調べる
      for j = i, ocr.length do
        ntrio = ocrs[j]
        -- 主キーが違っているかオフセットが進みすぎていたら抜ける
        if ntrio[0] != id or ntrio[1] > off + qgunit then
          break
        end
        -- 主キーが同じでトークン番号とオフセットが整合していた場合には
        if ntrio[2] == seq and ntrio[2] == off + qgunit then
          -- 現在のオフセットとトークン番号を進める
          off = ntrio[2]
          seq += 1
        end
      end
      -- 現在のオフセットがクエリの長さまで到達していたら結果セットに加える
      if off == trio[2] + tokens.length * qgunit then
        res.set(id)
        -- 次の主キーまで飛ばす
        while i < ocrs.length and ocrs[i][0] == id do
          i += 1
        end
      end
    end
  end
end

上記の処理に渡すトークンリストは、クエリの文字列からq-gramのq文字数毎にずらして切り出したものを用います。例えば、tri-gramで「abcdef」の場合は、「abc」と「def」になります。じゃあq文字の倍数でなかった場合はどうするかと言うと、最後のトークンだけ前に端数の文字数分を前にずらします。例えば「abcde」の場合、「abc」と「cde」を用います。その場合はposting listから取り出したオフセットもオカレンス配列に入れる際にずらしておくことで、隣接判定の処理で余計なことをせずに済ませます。

クエリの文字列がq文字以下だった場合には、クエリの文字列に前方一致する全てのトークンを調べる必要があります。その際には隣接判定は不要ですから、タグ検索の処理とほぼ同じようにposting listをそのまま結果セットに入れるような処理になります。

カウンティングソート

隣接判定の計算量を削減するためにオカレンス配列をソートしておくことが重要なわけですが、ソートするのってどうなのよと思いませんか。馬鹿正直過ぎます。ところで、オカレンス配列に求められる条件は次のものです。

• 主キーが同じオカレンス情報が連続している
• 主キーが同じ中ではオフセット毎にソートされている

もちろん全体をソートすればこの条件は達成されますが、冷静に考えてみると、全体を一気にソートしなくても達成できます。まず思いつくのは、オカレンス情報の各々を主キー毎に作った別々のリストに加えていく方法ですが、これには弱点があります。候補の数が多すぎる場合にリストの数が増えすぎて空間も時間も使いすぎてしまうのです。そこで、リストの数を一定にするために、主キーのハッシュ値を使うことを考えます。さらに、リストオブジェクトを新たに作るための空間と時間のオーバーヘッドがリストの数を制限することになるため、元の配列と同じ領域を使いたくなります。そこで気づくのが、主キーのハッシュ値を使ってカウンティングソート（分布数え上げソート）を行うことです。カウンティングソートの前提条件は比較する値の変域が予め分かっていることですが、ハッシュ値を使うとまさにそれを達成できます。

ということで、65536通りのハッシュ値を使ってカウンティングソートをした上で、同一ハッシュ値の要素群にはクイックソートをかけるようにしました。これによって、65536*(4=sizeof(int))で256KBの空間を使うかわりに、全体をクイックソートした場合よりもlog2(65536)=16で16倍高速化するかもしれない実装になったわけです。まあ実際には分布を数えるためのオーバーヘッドがかかるしオカレンスのハッシュ値が均等に分布するわけでもないため、速度は2倍程度にしかなりませんが。メモリに余裕があれば65536よりでかい変域を使ってもよいですが、細かく努力してもあまり成果がでないというのもまた現実です。

ビットマスク

あれ、さっきの説明だとインデックスから取得してきたposting listを全部オカレンス配列にぶち込んでいるけども、全部ソート処理に回されて効率悪いのはどうなのよと思いませんか。馬鹿正直過ぎます。ところで、隣接しているか確かめなくてもトークンがコラム内にあるかないかを調べるだけである程度は絞り込めます。つまりフィルタをかけて不要なオカレンス情報を予め振り落とすことによって、後で行うソート等の処理の計算量を減らすのです。例えば、「sakura」というクエリの場合、「sak」のposting listはオカレンス配列にそのまま入れるのですが、「ura」のposting listでは「sak」を処理した際に出てきた主キーのもののみをオカレンス配列に入れるのです。

そこで考えつくのが、トークン毎にハッシュを作って、オカレンス毎に主キーを登録していって最後に論理積をとるという方法です。でも、どっちみち後で完全なテストをするのだから、完全なハッシュを作らなくてもよいでしょう。主キーのハッシュ値を使ってビットマスクを作るだけでもよさそうです。そういえばカウンティングソートの時にハッシュ値を作っているのだから、それを流用してしまえばよさそうです。

ということで、クエリから切り出した第1のトークンのオカレンス情報はそのままオカレンス配列に格納しますが、第2トークン以降を処理する際には、第1トークンで作ったビットマスクでフラグが立っているものだけをオカレンス配列に格納することにします。ハッシュ値なので疑陽性になることがありますが、疑陽性のオカレンスも連接判定の際に削られるので問題ありません。いわずもがな、ビットマップによるハッシュ表はバケット1個あたり1ビットしか使いませんので、100万個のバケットのハッシュ表を作っても125KBしか空間を使わないで済むのです。

第2トークン以降のオカレンス情報がフィルタで削れるのはいいとして、じゃあ第1トークンのオカレンス情報はどうやって削りましょうか。オカレンス配列を作った後で、その配列全体をスキャンして、最終トークンの主キーとオフセットに着目してビットマスクを作った上で、もう一度配列全体をスキャンして、最終トークン以外のオカレンス情報をビットマスクを使ってフィルタすることにします。配列全体を2度もスキャンするのは効率悪い気もしますが、あくまで計算量はO(N)なのでソートのO(N log N)の前処理としては効率的とも言えます。

主キーの表現

単純化のために、主キー（文書ID）が数値であることを前提として今までの説明をしてきました。しかし、TCのテーブルデータベースは任意のバイト列を主キーに指定できるので、数値以外のデータもposting list内の文書IDとして指定できる必要があります。多くの検索エンジンでは文書IDが数値であることを利用して効率的な符号化を行っているのですが、任意のバイト列だとそのような効率化ができません。効率が悪いインデックスは存在価値がありませんから、ここはうまいこと方法を考えないといけません。悩んだ末、主キーが数値であることを前提にインデックスの構造を設計し、そうでない場合はエスケープ文字を使って表現することにしました。すなわち、主キーが数値である場合には効率的に処理ができ、数値でない場合にもそれなりに動くという特性になります。

主キーが自然数で10進数の正規形である場合は、つまり ‘0′ から ‘9′ までの文字のみから構成されて先頭が ‘0′ ではなく全体が正の値である場合は、それを数値として扱い、デルタ符号を用いて直列化したデータを記録します。そうでない場合には、先頭にゼロコード（’\0′) を接頭させてそのままのバイト列を記録します。インデックスからposting listを読み出す際には、先頭がゼロコードか否かで数値か任意バイト列かを判定します。数値である場合には10進数の正規形としてバイト列に復元します。

重複キーレコード方式と連結方式

インデックスはB+木のデータベースなのですが、B+木にposting listを格納するには大きく分けて2種類の方法があります。ひとつは、個々のオカレンス情報を別々のレコードとして扱い、キーが重複したレコードを格納できるというB+木の性質を利用して複数のレコードとして格納する方法です。もうひとつは、同一トークンの全てのオカレンス情報を単一のバイト列に直列化して、単一のレコードとして格納する方法です。前者はカーソルを使って特定の文書IDのオカレンス情報を取り出すといった効率化ができる半面、レコード数が多くなるので、個々のレコードのメタデータの分だけ空間効率が悪化します。後者はその逆の性質で、posting listの取得操作や更新操作にあたって全体を一括して処理しなければならない反面、空間効率は高まります。

結論としては、TCでは後者の一括方式を採用しています。検索の際には結局posting list全体をゴニョゴニョするので、個々のオカレンス情報をピンポイントで処理できるという性質はそれほど利点にならないからです。更新を高速化させるには前者の方が有利なのですが、更新操作の効率に関してはキャッシュに頑張らせて稼ぐと割り切って、現在の設計に落ち着いています。

まとめ

長々と説明しましたが、多分、実際のソースコードを読んでもらった方がわかりやすいです。tctdb.cをちょっと覗いてみてください。他のライブラリに全く依存せず、BoostもSTLも使っていないのに、6000行にも満たないコードで全文検索機能付きのテーブルデータベースを実現できています。よくぞここまで簡潔にまとめたものだなと我ながら感心している次第です。