• BPnet
  • ビジネス
  • IT
  • テクノロジー
  • 医療
  • 建設・不動産
  • TRENDY
  • WOMAN
  • ショッピング
  • 転職
  • ナショジオ
  • 日経電子版
  • PR

  • PR

  • PR

  • PR

  • PR

ITレポート(動向/解説)

作って理解するAjax --- No.3
インクリメンタル検索を実現 [サーバー編]

2005/12/16 ITpro
図1 インクリメンタル検索を実現<br>作成したサーバーCGIプログラムを使ってインクリメンタル検索する様子。計画通りに稼働しているのが分かります。
図1 インクリメンタル検索を実現<br>作成したサーバーCGIプログラムを使ってインクリメンタル検索する様子。計画通りに稼働しているのが分かります。
[画像のクリックで拡大表示]

この連載記事の目次へ

 前回は,インクリメンタル検索を実現するAjaxアプリケーションのクライアント・サイドの実装を紹介しました。今回は,サーバーとして稼働するCGIプログラムを作成します。このCGIプログラムは,クライアントから送られてきたクエリーに基づいてテキストを検索し,その結果を返送します。Ajaxアプリケーションは通常のWebアプリケーションに比べて,サーバー・アクセスが増加しがちです。このためサーバーをいかに効率よく実装できるかが,サービスを快適に提供できるかどうかを左右します。サーバー負荷を下げる手法についても考えてみましょう。

テキスト検索にsaryを使用

 みなさん,テキスト検索といえばどんな方法を思いつくでしょうか。単純なところではgrepコマンドの利用が考えられますし,データをMySQLやPostgreSQLなどのRDBMSで管理して,そのRDBMSの検索機能を利用する手もあります。また,Namazuのようないわゆる全文検索システムを利用しても良いでしょう。

 お手軽さという意味では,grepが一番簡単です。ただし,テキストを線形にサーチするだけなので,大量のテキスト検索には速度的な問題があります。RDBMSは,汎用性という意味では優れていますが手軽さに欠けます。さらに部分文字列検索に特化していないため,インクリメンタル検索においては必ずしも高速とは限りません。

 全文検索システムも実装によっては,部分文字列検索が不得意なものがあります。例えば,Namazuのように検索対象テキストを形態素解析するものでは,形態素よりも小さな文字列や,複数の形態素にまたがる部分文字列の検索は一般に不得手です。実装によっては検索漏れが発生する可能性があります。N-gram方式を採用するものはこうした問題はありませんが,CGIプログラムから手軽に呼び出せるフリーの実装が見当たらなかったため採用を見送りました。

 手軽で高速,かつ検索漏れのない方法として採用したのが「sary」です。saryは,「suffix array」というデータ構造を使ってテキストを高速検索するオープンソース・ライブラリです。suffix arrayとは,テキストの先頭からn文字目以降の部分文字列を「suffix」として順次切り出し,それを辞書順に並べ替えたものを配列(array)に格納したものです。例えば,「NIKKEIBP」というテキストからは次のようなsuffixが作成できます。最初の数字はテキストの先頭からの文字数で,これがsuffixの位置を示すポインタになります。

0 NIKKEIBP
1 IKKEIBP
2 KKEIBP
3 KEIBP
4 EIBP
5 IBP
6 BP
7 P

 これを辞書順に並べ替えると次のようになります。

6 BP
4 EIBP
5 IBP
1 IKKEIBP
2 KKEIBP
3 KEIBP
0 NIKKEIBP
7 P

 並び替えたsuffixのポインタの数字を配列に順次格納すれば,suffix arrayの出来上がりです。こうすることで,検索キーとして使われる任意の部分文字列の有無が,suffix array上の連続した一部分を検索するだけで高速に判別できます。例えば「KA」という文字列の有無は,「K」を先頭にする領域だけを調べればわかります(実際には2分探索などを使います)。

 このようにsuffix arrayは理解しやすく単純なデータ構造ですが,高速で漏れのない検索ができ,インデックス・サイズも小さいという利点があります。その半面,suffix arrayの作成に時間やメモリーを多量に消費します。ただし今回の用途では,頻繁にsuffix arrayを再作成しませんので,これは問題にはなりません。

検索対象テキストの準備

 suffix arrayは1つのテキストを対象に作成します。このため検索対象のテキストが複数ある場合は,事前にそれらを連結して1つのファイルを作成しておかなければなりません。今回は,青空文庫で公開されている夏目漱石の『こころ』と『三四郎』をダウンロードし,それらをひとつのテキスト・ファイルにまとめ,「sample.txt」という名前で保存しておくことにします。ご自分のblogや日記,メールなどを1つのテキスト・ファイルに結合したものを用意しても良いでしょう。例えば「Movable Type」にはblogをテキストとしてエクスポートする機能があります。これを使ってみるのも一つの手です。この際,ファイルをUTF-8エンコーディングで保存してください。

 なお,このサンプル・テキストは約1Mバイトの小さなものですが,数十~数百Mバイトといった大きなファイルを用意した方がsuffix arrayの効果を体感できると思います。10Mバイト程度までのファイルであれば,grepでも十分高速に検索できるからです。ただし,saryの制限で2Gバイト以上のファイルは利用できません。

saryのインストール

 saryは,GLibライブラリ(バージョン2.0以降)が導入されているUNIX系OSで動作します。また,ソース・アーカイブ形式で配布されていますので,利用にはGCCなどのCコンパイラが必要です。ここでは,これらが既に導入されているUNIX系OSでのインストール手順を紹介します。

 saryのソース・アーカイブは,公式ダウンロード・ページから入手できます。執筆時点(2005年12月12日)の最新バージョンは1.2.0です。

 このソース・アーカイブからのsaryのインストール手順は下記の通りです。これにより,suffix array構築用コマンド「mksary」や,検索用コマンド「sary」がインストールされます。

% tar zxfv sary-1.2.0.tar.gz
% cd sary-1.2.0
% ./configure 
% make
% su 
# make install

 早速,簡単なテキスト検索をやってみましょう。まず,検索対象のテキスト・ファイル「sample.txt」のsuffix arrayインデックスを作成します。 これにはmksaryコマンドを実行します。-cオプションでファイルのエンコーディング(文字コード)を指定します。

% mksary -c utf-8 sample.txt

 処理が完了すると「sample.txt.ary」という名前のsuffix arrayインデックス・ファイルが作成されます。

 インデックス・ファイルが作成できれば,saryコマンドを使った検索ができます。saryコマンドの使い方は,grepコマンドと変わりません。「sary キーワード 検索対象ファイル」と実行します。sample.txtに「先生」という文字列が含まれているかどうかを検索する場合は,次のように実行します。このとき,OSのロケールはUTF-8にしておきます。

% sary 先生 sample.txt
  上 先生と私
 私(わたくし)はその人を常に先生と呼んでいた。だからここでも
ただ先生と書くだけで本名は打ち明けない。
これは世間を憚(はば)かる遠慮というよりも、その方が私にとって
自然だからである。私はその人の記憶を呼び起すごとに、すぐ「先生
」といいたくなる。筆を執(と)っても心持は同じ事である。よそよ
そしい頭文字(かしらもじ)などはとても使う気にならない。
...

libsaryを使った検索CGIの作成

 saryパッケージには,オブジェクト指向設計の優れたライブラリ「libsary」が含まれています。先ほどのmksaryコマンドやsaryコマンドも,このlibsaryを使って実装されています。 今回作成するCGIプログラムでも,このlibsaryのAPIを通じてsuffix arrayを使った検索を実現させます。

 なお,CGIプログラムはCで作成します。サーバー・サイドの実装には通常,PHPやPerlといったスクリプト言語が用いられます。しかしAjaxアプリケーションはサーバーと頻繁に通信しますから,サーバーには高速なレスポンスが求められます。Cで開発するのは,少しでも動作速度を向上させるためです。Cといっても,大半の処理はlibsaryのAPIを通じて実施しますから難しくありません。他の検索用CGIプログラムにも簡単に応用できると思います。

●処理の流れを確認
 さて,CGIプログラムの全体の処理は,以下の流れになります。それぞれ順に説明していきます。
  • suffix arrayインデックスのオープン
  • 検索の実行
  • 検索結果を前後の文脈付きで表示(KWIC 表示)
  • suffix arrayインデックスのクローズ

●suffix arrayインデックスのオープン/クローズ
 まず,sary_searcher_new関数を使って既存のインデックスをオープンします。引数には検索対象のテキスト・ファイル名を与えます。成功すると,SarySearcherクラスのインスタンス変数(ポインタ)が返ってきます。検索処理や検索結果の取得は,この変数を通じて実施します。なお,すべての処理を終えたら,プログラム終了前にインデックスをクローズします。これには,sary_searcher_destroy関数を使います。

●検索の実行
 検索は,sary_searcher_search関数を使って実施します。引数は2つあり,一つは最初に作成したSarySearcherクラスのインスタンス,もう一つはクエリー文字列(検索キーワード)です。検索に成功すると「1」が返ってきます。 インデックスのオープンから検索の実行,そしてインデックスのクローズまでのコード例を以下に示します。
#include <stdio.h>
#include <string.h>
#include <sary.h>

int main(int argc, char **argv) {
  SarySearcher *searcher;
  const char *query;
  int length;

  if (argc != 2) return -1;
  query = argv[1];
  printf("Content-Type: text/html; charset=\"UTF-8\";\n\n");

  /* suffix array のオープン */
  searcher = sary_searcher_new("sample.txt");
  if (searcher == NULL) {
    printf("cannot open index");
    return -1;
  }

  /* 長さのチェック */
  length = strlen(query);
  if (length == 0) return -1;
  if (length > 50) {
    printf("query is too long");
    return -1;
  }

  /* 検索 */
  if (! sary_searcher_search(searcher, query)) 
    printf("[%s] is not found", query); /* マッチするものがな
かった */
  else 
    print_result(searcher, query); /* 検索結果の表示処理 (後ほ
ど説明) */

  /* suffix array のクローズ */  
  sary_searcher_destroy(searcher);

  return 0;
}
 実際のコードでは,インデックスのオープン/クローズ時のエラー処理や,クエリー文字列の長さチェックなどの処理も記述しています。それについては,後述する実コードを参照してください。

●検索結果を前後の文脈付きで表示
 検索結果の表示には,print_result関数を使います。今回検索結果の表示形式として採用したKWIC形式は,検索結果を前後の文脈付きで表示する形式です。そのため,この関数を使う前に,少なくとも「クエリー文字列のテキスト中での出現位置」,「各出現位置の前後の文脈」の2つの情報を取得する必要があります。

 libsaryには,クエリー文字列のテキスト上での出現位置を抽象化したクラス「SaryText」があります。通常,以下のようにsary_searcher_get_next_occurrence関数を繰り返し呼ぶことで,出現位置を順に取得できます。

SaryText *text;
while (text = sary_searcher_get_next_occurrence(searcher)) {
  /* text を使った 実際の処理 */
}
 SaryTextオブジェクトの操作用に,以下の3つの関数が用意されています。
  • char *sary_text_get_cursor(SaryText *);
  • char *sary_text_get_bof(SaryText *);
  • char *sary_text_get_eof(SaryText *);
 それぞれ,クエリー文字列の出現位置へのポインタ,テキストの先頭位置へのポインタ,テキストの終了位置へのポインタを返します。この3つを使えば,現在の位置から前後の文脈を抜き出せます。
 実際のコードは,以下のようになります。
void print_result(SarySearcher *searcher, const char *query)
{
  SaryText *text;
  int num_result = 0;

  /* 出現順にソート */
  sary_searcher_sort_occurrences(searcher);
     
  printf("<table>");
  
  /* 各出現位置に対しての処理 */
  while ((text = sary_searcher_get_next_occurrence(searcher)) && 
         num_result++ < 30) {
    const char *bof   = sary_text_get_bof(text);
    const char *eof   = sary_text_get_eof(text);
    const char *stext = sary_text_get_cursor(text);
    const char *etext = stext + strlen(query);
    const char *end   = seek_forward(etext, eof, 20);
    const char *start = seek_backward(stext, bof, 20);

    /* start .. end の範囲を出力 */
    printf("<tr><td style=\"text-align:right\">");
    for (; start < end; ++start) {
      if (start == stext)
        printf ("</td><td style=\"background:yellow\">");
      if (start == etext) printf ("</td><td>");
      switch (*start) {
      case '>': printf("&gt;");  break;
      case '<': printf("&lt;");  break;
      case '&': printf("&amp;"); break;
      default:  putchar(*start);
      }
    }
    printf("</td></tr>");
  }
  
  printf("</table>");
}
 このコードでは,それぞれの検索結果(SaryTextインスタンス)から,以下の4つの情報を取得しています。
  • bof: テキストの先頭ポインタ
  • eof: テキストの終了ポインタ
  • stext: クエリのテキスト上での開始位置ポインタ
  • etext: クエリのテキスト上での終了位置ポインタ
 さらに後述するseek_forward関数を使って,etextからeofの範囲まで長さ20の文脈,seek_backward関数を使ってstextからbofの範囲まで長さ20の文脈を取得しています。前後の文脈は最終的にstartからendの範囲となります。
 seek_fowardとseek_backwardは,UTF-8エンコーディングの元で与えられた長さだけポインタを進める/戻す関数です。この処理は繁雑であるため説明は割愛します。具体的な実装は最終的なコードをご覧下さい。
 sary_searcher_sort_occurrencesは,クエリー文字列の各出現位置を,実際のテキスト中での出現位置に従って並び替える関数です。また,検索結果の数は最大30に限定しています。
 最後にstart~endの範囲の文字列を出力するコードを書けば完成です。検索結果表示中で,クエリー文字列を中央にハイライト表示するようにHTMLのtableタグを使っています。 全体のコードは,こちらにあります。インデックス・ファイルの名前などの定数はマクロにして,メンテナンス性を高めています。

●作成したCGIプログラムのコンパイル
 ソース・コードをコンパイルし,「search.cgi」という実行バイナリを作成します。これには,次のような手順でGCCを実行します。なお,「glib-config --cflags」と「glib-config --libs」は,引用符ではなくバックスラッシュで囲んでください。
% gcc -Wall -O2 `glib-config --cflags` search.c -o search.cgi 
`glib-config --libs` -lsary -lpthread
 Fedora CoreのようにGLibバージョン2.0系列が「glib2」という別パッケージになっている環境では,glib-configコマンドはglib2の情報を取得できず,上記の手順ではコンパイルに失敗します。このような環境では,下記のどちらかの手順を試してみてください。
% gcc -Wall -O2 `pkg-config glib-2.0 --cflags` search.c -o sear
ch.cgi `pkg-config glib-2.0 --libs` -lsary -lpthread
 pkg-configコマンドがインストールされていない場合は,下記を試します。
% gcc -Wall -O2 -I/usr/include/glib-2.0 -I/usr/lib/glib-2.0/in
clude search.c -o search.cgi -lglib-2.0 -lsary -lpthread

CGIプログラムの動作チェック

 実際に検索を実施して,CGIプログラムの動作をチェックしてみましょう。検索対象のテキスト「sample.txt」とそのsuffix arrayインデックス「sample.txt.ary」を作成した「search.cgi」を同じディレクトリに置き,search.cgiをコマンド・ラインから実行します。実行時にはクエリー文字列を指定します。例えば,「先生」というキーワードで検索する場合は次のようにします。

% ./search.cgi 先生
Content-Type: text/html; charset="UTF-8";

<table><tr><td style="text-align:right">ころ夏目漱石  上</td>
<td style="background:yellow">先生</td>
<td>と私
...

 正しく動作するようでしたら,前回作成したクライアント側のHTMLファイルをWebブラウザで表示させ,クエリーを送ってみましょう。入力するたびに検索結果が更新されていけば成功です(図1[拡大表示])。

 なお,今回は単純に「sample.txt.ary」と「sample.txt」を,CGIプログラムと同一のディレクトリに置きました。このままでは,インデックスの内容を直接参照される可能性があるなど,セキュリティ的な問題があります。Webサーバーの設定を修正するか,そもそもWeb経由では見えないディレクトリにファイルを置くなど,実運用には注意が必要です。

この連載記事の目次へ

工藤 拓(くどう たく)

1976年生まれ。奈良先端科学技術大学院大学 情報科学研究科 松本研究室にて自然言語処理学,機械学習を研究。在学中に、次世代形態素解析エンジン「MeCab」や、係り受け解析器「CaboCha」など多数のソフトウエアを開発する。平成14年には自然言語処理学会年次大会優秀発表賞を受賞。

あなたにお薦め

連載新着

連載目次を見る

今のおすすめ記事

  • 【速報】

    Uberが5700万の個人情報を漏洩、1年間知らせず

     米ウーバー・テクノロジーズ(ウーバー)は米国時間2017年11月21日、2016年10月に約5700万件の個人情報漏洩を起こしていたと発表した。同社のWebサイト上でダラ・コスロシャヒCEOの執筆記事として公開している。

ITpro SPECIALPR

What’s New!

経営

アプリケーション/DB/ミドルウエア

クラウド

運用管理

設計/開発

サーバー/ストレージ

クライアント/OA機器

ネットワーク/通信サービス

セキュリティ

もっと見る