mixi engineer blog

＊＊＊ 引っ越しました。最新の情報はこちら → https://medium.com/mixi-developers ＊＊＊ ミクシィ・グループで、実際に開発に携わっているエンジニア達が執筆している公式ブログです。様々なサービスの開発や運用を行っていく際に得た技術情報から採用情報まで、有益な情報を幅広く取り扱っています。

オレオレ検索窓を設置しよう

algorithm mixi

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

wgettsv

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

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行以下で済んでいます。

tctsearch

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（検索語を0x02と0x03でマークアップ）、KWMUBRCT（検索語を [ ] でマークアップ）、KWNOOVER（周辺文のオーバーラップを禁止）、KWLEAD（文書の先頭を強制的に選択）のビット論理和を指定することができます。いわゆる普通のKWICが欲しい場合は、qry.kwic(cols, nil, 20, TDBQRY.KWMUCTRL) で得た文字列内の制御文字を出力用のマークアップに置換するのが定石でしょう。

まとめ

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

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