前回は，インクリメンタル検索を実現する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 *);
実際のコードは，以下のようになります。
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(">"); break;
case '<': printf("<"); break;
case '&': printf("&"); break;
default: putchar(*start);
}
}
printf("</td></tr>");
}
printf("</table>");
}
このコードでは，それぞれの検索結果（SaryTextインスタンス）から，以下の4つの情報を取得しています。
- bof: テキストの先頭ポインタ
- eof: テキストの終了ポインタ
- stext: クエリのテキスト上での開始位置ポインタ
- etext: クエリのテキスト上での終了位置ポインタ
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 -lpthreadFedora 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 -lpthreadpkg-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年には自然言語処理学会年次大会優秀発表賞を受賞。 |
