横着プログラミング 第9回: sary: Suffix Array のライブラリとツール

私にフローチャートだけを見せて、テーブルは見せないとしたら、
私はずっと煙に巻かれたままになるだろう。逆にテーブルが見せて
もらえるなら、フローチャートはたいてい必要なくなる。
-- Frederick P. Brooks Jr.

^*1

プログラミングにおいてはデータ構造が重要であり、正しいデータ 構造を選択すればアルゴリズムは自明なものとなる、という主張が ある。Rob Pike^*2 の "Notes on Programming in C" ^*3 によると、現実的なプログラムに必要なデータ構造は次の 4つであ るという。

• 配列 (array)
• 連結リスト (linked list)
• ハッシュテーブル (hash table)
• 2分木 (binary tree)

これらのデータ構造を組み合わせれば大抵のプログラムを書ける。 しかし、速度やメモリ効率を最優先としたプログラムの場合には、 特殊なデータ構造が必要なときがある。たとえば、連載第6回で紹 介した chatty では辞書のデータ構造として 2 分木を利用したが、 ダブル配列やパトリシア木、Suffix Array といったデータ構造を 使えばより高速に辞書を検索できる。

このうち Suffix Array は

• データ構造が極めて単純なため扱いやすい
• 辞書検索だけでなく巨大なテキストの検索にも適している

という特徴を持っている。今回は私が開発した Suffix Array のラ イブラリとツールである sary と、Suffix Array の仕組みについ て紹介する。

sary とは?

sary ^*4 は Suffix Array を扱う ためのライブラリとツールをセットにしたソフトウェアである。巨 大なテキストを高速に全文検索するために開発した。sary は次の 3つで構成される。

• mksary: Suffix Array を作成するツール
• sary: Suffix Array を用いてテキスト検索を行うツール
• libsary: Suffix Array を扱うための汎用ライブラリ

Suffix Array を扱うライブラリとツールとしては、sary を開発す る以前にも山下達雄氏による SUFARY ^*5 があった。しか し、SUFARY は性能の点では優れていたものの、ライブラリの API には馴染むことができなかった。そこで、SUFARY のコードを参考 にしつつ、API をオブジェクト指向にまとめ直したライブラリとし て sary を開発することにした。

sary のインストール

sary を利用するには次のソフトウェアをインストールする。

GLIB

GLIB は Cプログラミングに便利な関数を集めたライブラリである。 元々は GUIツールキット GTK+^*6 のために 開発されたが、現在では汎用的なライブラリとして GTK+ 以外のソ フトウェアでも広く利用されている。私は、伸縮可能な配列、連 結リスト、ハッシュテーブルといったデータ構造をオブジェクト指 向の API で扱える点が気に入って使っている。

sary では最新の GLIB 2.0 ではなく一世代前の GLIB 1.2 ^*7 を利用している。GLIB 1.2.x のインストールは次のように行う (原稿執筆時点での最新版 は 1.2.10)。

% gzip -dc glib-1.2.10.tar.gz | tar xvf - 
% cd glib-1.2.10
% ./configure
% make
% su
Password: (rootのパスワードを入力)
# make install

sary

sary のインストールは GLIB のインストールが完了した後に行う。 インストールは次のように行う (原稿執筆時点での最新版は 1.0.4)。

% gzip -dc sary-1.0.4.tar.gz | tar xvf -
% cd sary-1.0.4
% ./configure
% make
% su
Password: (rootのパスワードを入力)
# make install

sary の基本的な使い方

sary には sary と mksary という2つのツールが付属している。 sary コマンドは grep のようなテキスト検索を行う。巨大なテキ ストファイルも一瞬で検索できるのが特徴である。ただし、mksary コマンドであらかじめ検索対象のテキストファイルに対して Suffix Array を作成しておく必要がある。たとえば、テキストファ イル foo.txt に対して Suffix Array を作成するにはコマンドラ インから次のように実行すればいい。

% mksary foo.txt

mksary の実行が終了すると、Suffix Array である foo.txt.ary ができ上がる。作成した Suffix Array を用いて foo.txt を検索 するには sary コマンドを次のように実行すればいい。検索には foo.txt と foo.txt.ary の両方が必要である。

% sary keyword foo.txt

keyword には検索したいキーワードを指定する。検索結果は grep コマンドと同様に標準出力に表示される。

sary の基本的な使い方は以上である。次に mksary、 sary の各コ マンドの使い方を詳しく紹介する。

mksary コマンドの使い方

mksary コマンドは Suffix Array を作成するツールである。 mksary を実行すると処理の進行に従って次のようなメッセージが 表示される。

% mksary foo.txt
index:  100% |ooooooooooooooooooooooooooooooooooooooooo| Time: 00:00:07
sort:    10% |oooo                                     | ETA:  00:01:02

mksary の処理はインデックスポイントの割り当て (index) と、イ ンデックスポイントのソート (sort) という2段階に分かれている。

Suffix Array の作成にかかる時間は mksary に与えるオプション とテキストファイルの大きさによって変わる。Pentium III 1GHz × 2 + メモリ 1G バイトの計算機では、10Mバイトのテキストファ イルに対して、オプションなしで Suffix Array を作成するのに 1 分ほどかかる。

テキスト中の検索可能な位置

オプションなしで mksary を実行すると、テキスト中のすべての位 置で文字列の検索が可能な Suffix Array が作成される。このよう に作成された Suffix Array を用いると、sary コマンドは grep コマンドと同様に、テキストのどの位置に現われる文字列でも検索 できる。

mksary にオプションを指定すると、テキスト中の検索可能な位置 を制限できる。たとえば、 mksary に -l オプションを指定すると、 テキストの行頭からしか検索できない Suffix Array が作成される。 コマンドラインから次のように実行すると違いが分かる。

# 検索対象のテキストファイル (49バイト)
% cat abc.txt
apple   りんご
banana  バナナ
cherry  さくらんぼ

# -l オプションつきで Suffix Array を作成
% mksary -l abc.txt

# "apple" で検索すると見つかる (行頭ゆえ)
% sary "apple" abc.txt 
apple   りんご

# "りんご" で検索すると見つからない (行頭でないゆえ)
% sary "りんご" abc.txt 
%

# オプションなしで Suffix Array を作成
% mksary abc.txt

# "りんご" で検索しても見つかる
% sary "りんご" abc.txt 
apple   りんご

テキストの行頭からしか検索できない Suffix Array はサイズが小 さくなる。実際、オプションなしで作成した Suffix Array は 196 バイトなのに対し、-l オプションつきで作成した Suffix Array はたった 12バイトである。これは、テキスト中の検索可能な位置 が限定されたため、Suffix Array のデータが削減されたためであ る。

この「テキスト中の検索可能な位置」のことをインデックスポイン トと呼ぶ。オプションがない場合、インデックスポイントはテキス トのすべてのバイトごとに割り当てられる。-l オプションが指定 されたときは行頭ごとにインデックスポイントが割り当てられる。

Suffix Array のサイズ

Suffix Array のサイズは、インデックスポイントの数によっ て決まる。具体的には

Suffix Array のサイズ = インデックスポイントの数 × 4

で計算できる。4 は Suffix Array の表現に使っている 32ビット の整数型のデータサイズである。上の例では abc.txt は 49バイト であるため、オプションなしの Suffix Array は 49 × 4 = 196 バイトになる。一方、-l オプションつきの Suffix Array は、 3 行 × 4 = 12バイトとなる。Suffix Array のデータ構造について は後ほど詳しく紹介する。

日本語の問題

さきほどの abc.txt には日本語の文字列が含まれている。このファ イルは EUC-JP エンコーディングで保存されている。hexdump コマ ンドで覗くと次のように表示される。

% hexdump -c abc.txt
0000000   a   p   p   l   e             244 352 244 363 244 264  \n   b
0000010   a   n   a   n   a         245 320 245 312 245 312  \n   c   h
0000020   e   r   r   y         244 265 244 257 244 351 244 363 244 334
0000030  \n                                                            
0000031

8進数で表現された "244 352 244 363 244 264" が文字列「りんご」 に対応するバイト列である。オプションなしで作成された Suffix Array にはすべてのバイトごとにインデックスポイントが割り当て られているため、"352 244 363 244" という 1バイトずれたバイト 列でも検索できてしまう。これは EUC-JP で「蠅鵑」を表すバイト 列である。

# "蠅鵑" で検索しても見つかってしまう
% sary "蠅鵑" abc.txt 
apple   りんご

りんご・蠅鵑の問題

この問題を回避するには、日本語の文字の 1バイト目にだけインデッ クスポイントを割り当てて、 1バイトずれた位置からの検索を抑制 すればいい。EUC-JP エンコーディングのテキストに対してこのよ うな処理を行うには mksary に -c EUC-JP オプションを指定する。

# EUC-JPを配慮して Suffix Array を作成する
% mksary -c EUC-JP foo.txt

# "りんご" で検索すれば見つかるが、
% sary "りんご" abc.txt 
apple   りんご

# "蠅鵑" で検索しても見つからない
% sary "蠅鵑" abc.txt 
%

ここでの日本語の文字は 2バイトで1文字として扱われるため、 -c EUC-JP つきで作成された Suffix Array は 38文字 × 4 = 152 バ イトになる。

ところで、Namazu^*8 などの転置インデッ クス方式の全文検索システムでは、日本語の検索を行うために文を 単語に分割する処理を必要とする。この処理は茶筌 ^*9などの形態素解析システ ムによって行われる。たとえば、「日本語の検索」を茶筌で処理す ると「日本語」「の」「検索」の 3つに分割される。一方、Suffix Array を利用した全文検索システムではこのような単語分割の処理 は必要ない。

分割ソート

Suffix Array の作成には配列をソートする処理が伴う。この処理 には、作成する Suffix Array のサイズに比例したメモリを必要と する。mksary でオプションなしで Suffix Array を作成する場合、 対象テキストのサイズの 5倍以上のメモリを積んでいることが望ま しい。このため、メモリの少ない計算機では巨大な Suffix Array を作成する際に、ソートの途中で Out of memory エラーで異常終 了することがある。

そこで、mksary にはメモリの少ない計算機で巨大な Suffix Array を作成するための分割ソートの機能が用意されている。分割ソート は、巨大な配列を細かいブロックに分割してソートし、最後にそれ らを 1つの配列にマージするというアルゴリズムで行われる。分割 ソートの機能を利用するには -b オプションを指定する。

% mksary -b foo.txt
index:  100% |ooooooooooooooooooooooooooooooooooooooooo| Time: 00:00:05
sort:   100% |ooooooooooooooooooooooooooooooooooooooooo| Time: 00:00:28
merge:   19% |ooooooo                                  | ETA:  00:00:12

分割された個々のブロックをソートする処理はマルチスレッドで並 列に行えるため、複数の CPU を積んだ計算機ではソートを一括し て行うよりも、分割ソートを行った方が速い。分割ソートをマルチ スレッド化するには -t オプションを用いる。2 つのスレッドを走 らせる場合には -t2 と指定する。

手元の Pentium III 1GHz × 2 + メモリ 1Gバイトの計算機では、 150Mバイトのテキストに対して Suffix Array を作成した場合、一 括ソートでは 1,378秒かかったのに対し、 -t2 -b オプションを指 定したときは 1,231秒で終了した。残念ながら、2つのスレッドを 走らせたからといって、2 倍速くなるわけではない。

その他の機能

mksary には他にも Shift_JIS, UTF-8 エンコーディングを扱う機 能や、空白区切りの単語単位でインデックスポイントを割り当てる といった機能を持っている。mksary のコマンドラインオプション を以下に示す。

Usage: mksary [OPTION]... FILE
  -a, --array=FILE     出力するファイル名を FILE に設定する
  -b, --block=[SIZE]   ブロックサイズ SIZE [4096] Kバイトで分割ソートを行う
  -i, --index          インデックスポイントを割り当ててファイルに書き出す
  -s, --sort           インデックスポイントのファイルをソートする
  -l, --line           インデックスポイントを行単位で割り当てる
  -w, --word           インデックスポイントを単語単位で割り当てる
  -c, --encoding=NAME, 文字単位の処理のエンコーディングを NAME に設定する
                       [バイト単位], ASCII, ISO-8859,
                       EUC-JP, Shift_JIS, UTF-8
  -L, --locale         locale のサポートを有効にする (mblen(3)関数を利用)
  -t, --threads=NUM    分割ソートのスレッド数を NUM に設定する
  -q, --quiet          黙って仕事する
  -v, --version        バージョン情報を表示する
  -h, --help           このヘルプを表示する

sary コマンドの使い方

sary コマンドは Suffix Array を用いてテキスト検索を行うツー ルである。検索にはテキストファイルと Suffix Array の両方を用 いる。。つまり、さきほどの abc.txt を検索する場合、abc.txt と abc.txt.ary の両方を必要とする。abc.txt に対してキーワー ド banana で検索するにはコマンドラインから次のように実行すれ ばいい。

% sary "banana" abc.txt
banana  バナナ

検索に正規表現を使えない、複数のファイルをまとめて検索できな いという制限を除けば、saryコマンドの使い方は grep コマンドと 同様である。大文字と小文字を区別しないで検索を行うには -i オ プションを指定する。

% sary -i "BaNaNa" abc.txt
banana  バナナ

テキスト中に含まれるキーワードを数えるには grep コマンドと同 様に -c オプションを指定する。次の例ではテキスト中に含まれる "a" を数えている。

% sary -c "a" abc.txt
4

自然言語処理では、巨大なテキスト (コーパス) から単語の出現頻 度を調べたいという場面が多いため、この機能は重宝する。

grep コマンドの -c オプションは、同じ行に複数のキーワードが 含まれている場合に 1 個としか数えないため、単語の出現頻度を 調べる用途には使えない。

% grep -c "a" abc.txt
2

キーワードが含まれる行の前後を含めて検索結果として表示するに は -A, -B, -C オプションを指定する。次の例ではキーワード banana で検索し、前後の行も表示している。

% sary -C "banana" abc.txt
apple   りんご
banana  バナナ
cherry  さくらんぼ

タグつきテキストの検索

sary コマンドに --start=TAG, --end=TAG オプションで、開始タ グと終了タグを指定すると、タグに囲まれた部分を単位として検索 結果を表示できる。たとえば、次のようにタグづけされたテキスト があるとき、

% cat books.txt
<book>
  <title>Programming Pearls</title>
  <author>Jon Bentley</author>
  <publisher>Addison Wesley</publisher>
</book>

<book>
  <title>The Mythical Man-Month</title>
  <author>Frederick P. Brooks Jr.</author>
  <publisher>Addison Wesley</publisher>
</book>

sary コマンドに --start="<book>", --end="</book>" オプション を指定すれば、<book> ... </book> を単位として検索結果を表示 できる。高度な検索はできないものの、XMLデータベースのちょっ とした検索には役に立つ。

# Suffix Array を作成
% mksary books.txt

# 普通に検索すると行単位で表示される
% sary -i "pearls" books.txt
  <title>Programming Pearls</title>

# 開始タグと終了タグを指定するとその範囲の単位で表示される
% sary -i --start="<book>" --end="</book>" "pearls" books.txt
<book>
  <title>Programming Pearls</title>
  <author>Jon Bentley</author>
  <publisher>Addison Wesley</publisher>
</book>

検索結果の辞書順表示

通常、検索結果はテキスト先頭からの出現位置順に表示される。 sary コマンドに -l オプションを指定すると、検索結果の表示を 辞書順 (ABC順) に変更できる。この機能は辞書の検索に使うと便 利である。たとえば、次のようなテキストに対して mksary -l で Suffix Array を作っておけば、テキストの中身は辞書順に並んで いなくても、検索結果を辞書順に表示できる。

% cat dict.txt
cons    公司
eval    威張る
apply   適用する
cdr     くだを巻く
car     車

# 行頭のみにインデックスポイントを割り当てる
% mksary -l dict.txt

# 普通に検索すると出現位置順に表示される
% sary "c" dict.txt
cons    公司
cdr     くだを巻く
car     車

# -l オプションを指定すると、辞書順に表示される
% sary -l "c" dict.txt
car     車
cdr     くだを巻く
cons    公司

Suffix Array を用いたテキスト検索では、アルゴリズムの性質上、 検索結果は出現位置順よりも辞書順に表示した方が速い。

sary コマンドのコマンドラインオプションを以下にまとめておく。

Usage: sary [OPTION]... PATTERN FILE
  -c, --count               出現頻度を数えて表示する
  -i, --ignore-case         大文字・小文字を区別しない
  -l, --lexicographical     検索結果を辞書順に表示する
  -A, --after-context=NUM   後の NUM 行も出力する
  -B, --before-context=NUM  前の NUM 行も出力する
  -C, --context=[NUM],      前後 NUM 行も出力する
  -s, --start=TAG,          タグに囲まれた領域を出力する。開始タグをTAGに設定
  -e, --end=TAG,            タグに囲まれた領域を出力する。終了タグをTAGに設定
  -v, --version             バージョン情報を表示する
  -h, --help                このヘルプを表示する

grep との速度比較

ここでは実際に巨大なテキストを用いて、grep と検索の速度を比 較する。実験には RFC^*10 を加工して作成した 150 Mバイトのテキストファイルを利用した。

# rfc*.txt をまとめて巨大なファイルを作る
% cat rfc*.txt > rfc-all.txt

# rfc-all.txt の Suffix Array を作る
% mksary rfc-all.txt

このテキストに対して Pentium III 1GHz × 2 + メモリ1Gバイト の計算機でgrep と sary コマンドのそれぞれの検索速度を測定し た。grepコマンドには GNU grep^*11 2.4.2 を用いている。実験結果は以下の通りである。コマンドの実行時間 を 3回計測して最も速かった結果を採用した。

% time grep "http" rfc-all.txt > /dev/null
0.60s total : 0.29s user 0.33s system 102% cpu

% time sary "http" rfc-all.txt > /dev/null
0.02s total : 0.01s user 0.01s system 99% cpu

この結果から、grep コマンドは 150Mバイトのテキストの検索に 0.6 秒かかるのに対し、sary コマンドでは 0.02秒で検索できるこ とがわかる。なお、Suffix Array の作成には 20分かかった。

この実験では「grep では遅すぎて巨大なテキストの検索には使い 物にならない。sary なら高速である」と主張したいところだった が、最近の計算機では 150M バイトくらいのテキストなら、一度メ モリにキャッシュされてしまえば grep でも 1秒以内に検索できる ことがわかった。そこで、Pentium MMX 266 MHz + メモリ 64MB と いう一昔前の計算機でも同じ実験を行ってみた。

% time grep http rfc-all.txt > /dev/null
49.04s total : 11.94s user 2.52s system 29% cpu

% time sary http rfc-all.txt > /dev/null
0.16s total : 0.12s user 0.06s system 112% cpu

こちらの結果は grep で 49.04秒、 sary で 0.16秒と大きな差が 開いた。メモリが少なくキャッシュが効かないのが大きな要因であ る。grep がテキスト全体を走査する必要があるのに対し、sary は テキストと Suffix Array の一部分にしかアクセスする必要がない ため、少ないディスクアクセスで高速に検索が行える。

libsary の使い方

libsary は Suffix Array を扱うための汎用的なライブラリである。 mksary と sary コマンドは libsary を用いて実装している。 ここでは libsary を使った簡単なサンプルプログラムを紹介する。

簡単版 mksary

次のサンプルプログラムは、mksary と同様に、指定されたファイ ルの Suffix Array を作成するものである。

  #include <stdlib.h>
  #include <errno.h>
  #include <sary.h>
  
  int
  main (int argc, char **argv)
  {
      char *file_name;
      SaryInt ipoints;
      gboolean status;
      SaryBuilder *builder;
  
      if (argc != 2) exit(2);
      file_name = argv[1];
  
      builder = sary_builder_new(file_name);
      // EUC-JP でインデックスポイントを割り当てる
      sary_builder_set_ipoint_func(builder, sary_ipoint_char_eucjp);
  
      ipoints = sary_builder_index(builder);
      if (ipoints == -1) {
          g_print("error: %s(.ary): %s\n", file_name, g_strerror(errno));
          exit(2);
      }
  
      // インデックスポイントをソートして Suffix Array を作成
      status = sary_builder_sort(builder);
      if (status == FALSE) {
          g_print("error: %s(.ary): %s\n", file_name, g_strerror(errno));
          exit(2);
      }
      sary_builder_destroy(builder);
      return 0;
  }

サンプルプログラムをコンパイルするにはコマンドラインから次の ように実行する。`sary-config --libs` と `sary-config --

cflags` はlibsary を使うのに必要なオプションを Cコンパイラ に渡すためおまじないである。

% cc -o sample1 sample1.c `sary-config --libs` `sary-config --cflags`

作成された sample1 コマンドを用いて sample1.c の Suffix Array を作るには次のように実行する。

% ./sample1 sample1.c

# sample1.c.ary という Suffix Array が作成された
% ls sample1.c*
sample1.c  sample1.c.ary

簡単版 sary

次のサンプルプログラムは、sary と同様に、Suffix Array を用い たテキスト検索を行うものである。

  #include <stdlib.h>
  #include <errno.h>
  #include <sary.h>
  
  int
  main (int argc, char **argv)
  {
      Saryer *searcher; // Saryer は SarySearcher の短縮形
      char *pattern;
      char *file_name;
  
      if (argc != 3) exit(2);
      pattern = argv[1];
      file_name = argv[2];
  
      searcher = saryer_new(file_name);
      if (searcher == NULL) {
          g_print("error: %s(.ary): %s\n", file_name, g_strerror(errno));
          exit(2);
      }
  
      if (saryer_search(searcher, pattern)) {
          gchar *line;
  
          // 検索結果を出現位置順にソート
          saryer_sort_occurrences(searcher);
  
          while ((line = saryer_get_next_line(searcher))) {
              g_print("%s", line);
              g_free(line);
          }
      }
      saryer_destroy(searcher);
      return 0;
  }

サンプルプログラムをコンパイルするにはコマンドラインから次の ように実行する。

% cc -o sample2 sample2.c `sary-config --libs` `sary-config --cflags`

作成された sample2 コマンドを用いて、さきほどの sample1.c を 検索するには次のように実行する。

# sample1.c を "file_name" で検索
% ./sample2 "file_name" sample1.c
    char *file_name = argv[1];
    SaryBuilder *builder = sary_builder_new(file_name);
        g_print("error: %s(.ary): %s\n", file_name, g_strerror(errno));
        g_print("error: %s(.ary): %s\n", file_name, g_strerror(errno));

このように、 libsary を用いれば Suffix Array を Cプログラム から手軽に扱うことができる。sary の Webサイトでは libsary を Perl やRuby から利用するためのバインディング^*12 も公開されている。libsary の詳しい使 い方についてはリファレンスマニュアル ^*13 を参照して いただきたい。

Suffix Array とは?

これまで Suffix Array のデータ構造の詳細には触れずに sary を 紹介してきた。ここでは Suffix Array のデータ構造を詳しく説 明する。

Suffix Array とはテキストを高速に検索するためのデータ構造で ある。 Suffix とはテキスト中のある位置からテキスト末尾までの文字列 のことをいう。たとえば、"abracadabra" というテキストの場合、 1 文字目からの Suffix は "abracadabra"、 2 文字目からの Suffix は "bracadabra"、 3 文字目からの Suffix は "racadabra"、 ...、 9 文字目からの Suffix は "bra"、 10文字目からの Suffix は "ra"、 11文字目からの Suffix は "a" のようになる。 下の図は、すべての Suffix を図で表したものである。

"abracadabra" のすべての Suffix

これらの Suffix を辞書順にソートして、「 n文字目からの Suffix」の nの部分 (図では Index の部分) を並べると Suffix Array ができあがる。

Suffix を辞書順にソートして Suffix Array を作る

テキストの検索は、Suffix が辞書順にソートされているという性 質を利用して 2分探索のアルゴリズムで行う。"ra" で検索する過 程を下の図に示す。数字つきの矢印は、2分探索の順序を表してい る。

2分探索で検索

図の説明では、"abracadabra", "bracadabra", "racadabra", ..., "bra", "ra", "a" とたくさんの Suffix が並んでいるが、プログ ラムを書くときには、

• 元のテキスト: "abracadabra"
• Suffix Array: [11, 8, 1, 4, 6, 9, 2, 5, 7, 10, 2]

の 2つのデータだけがあればいい。すべての Suffix は元のテキス トとインデックスポイントだけで表現できる。たとえば、"adabra" という Suffix にアクセスするには「"abracadabra" の 6文字目か ら始まる文字列」というように表せばいい。

mksary コマンドの説明の中で「テキスト中の検索可能な位置」の ことをインデックスポイントと呼んだ。上の例では、すべて文字に インデックスポイントを割り当てている。子音のみにインデックス ポイントを割り当てると、テキストの子音の位置からしか検索が行 えない Suffix Array を作成できる。

子音の位置からしか検索できない Suffix Array

Suffix Array についてより詳しく知りたい方は文献[1,2] ^*14 を参照していただきたい。

サンプルプログラム

テキスト "abracadabra" の Suffix Array を作成する C 言語のサ ンプルプログラムを以下に示す。図で説明されるよりコードを見た 方がよくわかる、という読者は多いと思う。

  #include <string.h>
  #include <stdio.h>
  #include <stdlib.h>
  
  void show           (const int *array, int len);
  int  suffixcmp      (const void *p1,  const void *p2);
  
  char *text = "abracadabra"; 
  
  int 
  main (int argc, char **argv)
  {
      int i, len = strlen(text);
      int *array = malloc(sizeof(int) * len);
      if (array == NULL) exit(2);
  
      // [0, 1, 2, ... len - 1] という配列を作る
      for (i = 0; i < len; i++)
          array[i] = i;
  
      // インデックスポイントと Suffix の対応を表示
      show(array, len);
  
      // Suffix Array を作成
      qsort(array, len, sizeof(int), suffixcmp);
  
      // ソート後のインデックスポイントと Suffix の対応を表示
      show(array, len);
      return 0;
  }
  
  void
  show (const int *array, int len)
  {
      int i;
      for (i = 0; i < len; i++)
          printf("array[%2d] = %2d, text + %2d = %s\n", 
                 i, array[i], array[i], text + array[i]);
      printf("\n");
  }
  
  // qsort用の比較関数
  int
  suffixcmp (const void *p1, const void *p2)
  {
      char *suffix1 = text + *((int *)p1);
      char *suffix2 = text + *((int *)p2);
      return strcmp(suffix1, suffix2);
  }

サンプルプログラムのコンパイル方法と実行結果は次の通りである。

% cc -o sample3 sample3.c

% ./sample3                     
array[ 0] =  0, text +  0 = abracadabra
array[ 1] =  1, text +  1 = bracadabra
array[ 2] =  2, text +  2 = racadabra
array[ 3] =  3, text +  3 = acadabra
array[ 4] =  4, text +  4 = cadabra
array[ 5] =  5, text +  5 = adabra
array[ 6] =  6, text +  6 = dabra
array[ 7] =  7, text +  7 = abra
array[ 8] =  8, text +  8 = bra
array[ 9] =  9, text +  9 = ra
array[10] = 10, text + 10 = a

array[ 0] = 10, text + 10 = a
array[ 1] =  7, text +  7 = abra
array[ 2] =  0, text +  0 = abracadabra
array[ 3] =  3, text +  3 = acadabra
array[ 4] =  5, text +  5 = adabra
array[ 5] =  8, text +  8 = bra
array[ 6] =  1, text +  1 = bracadabra
array[ 7] =  4, text +  4 = cadabra
array[ 8] =  6, text +  6 = dabra
array[ 9] =  9, text +  9 = ra
array[10] =  2, text +  2 = racadabra

作成される Suffix Array は、さきほどの図にあった

[11, 8, 1, 4, 6, 9, 2, 5, 7, 10, 2]

ではなく、

[10, 7, 0, 3, 5, 8, 1, 4, 6, 9, 2]

と、各要素が 1づつ小さい値になっている。これは、C言語の文字 列の先頭は 0 から始まるという仕様に合わせているためである。

検索用サンプルプログラム

Suffix Array を用いてテキストの検索を行うサンプルプログラム を以下に示す。テキスト "abracadabra" に対して "ra" から始ま るすべての Suffix を検索して表示する。

  #include <string.h>
  #include <stdio.h>
  #include <stdlib.h>
  #include <assert.h>
  
  int  searchcmp      (const void *p1,  const void *p2);
  void *bsearch_first (const void *key, const void *base, size_t nmemb,
                       size_t size, int (*compar)(const void *, const void *));
  
  char *text = "abracadabra";
  int textlen = 11;
  int array[] = {10, 7, 0, 3, 5, 8, 1, 4, 6, 9, 2};
  
  int 
  main (int argc, char **argv)
  {
      char *key = "ra";
      int keylen = strlen(key);
      int *first, *cursor;
  
      // key から始まる最初の Suffix を検索
      first = bsearch_first(key, array, textlen, sizeof(int), searchcmp);
      if (first == NULL)
          exit(2);
  
      // 検索結果 (keyから始まるすべての Suffix) を表示
      cursor = first;
      while (strncmp(key, text + *cursor, keylen) == 0) {
          printf("text + %d = %s\n", *cursor, text + *cursor);
          cursor++;
      }
      return 0;
  }
  
  // bsearch用の比較関数
  int
  searchcmp (const void *p1, const void *p2)
  {
      char *key    = (char *)p1;
      char *suffix = text + *((int *)p2);
      return strncmp(key, suffix, strlen(key));
  }
  
  // 最初の要素を返す bsearch(3)
  void *
  bsearch_first (const void *key, const void *base, size_t nmemb,
                 size_t size, int (*compar)(const void *, const void *))
  {
      int low, high, mid;
  
      assert(key != NULL && base != NULL && compar !=NULL);
  
      low = -1;
      high = nmemb;
      assert(low < high);
  
      while (low+1 != high) {
          mid = (low + high) / 2;
          if (compar(key, base + mid * size) > 0) {
              low = mid;
          } else {
              high = mid;
          }
      }
      if (high >= nmemb || compar(key, base + high * size) != 0) {
          return NULL;
      }
      return (void *)(base + high * size);
  }
  

Suffix の 2分探索は bsearch_first() 関数を用いて行う。Unix の Cライブラリ (libc) には 2分探索を行う bsearch 関数が標準 で用意されているのに、なぜ bsearch_first 関数を自作している かというと、bsearch 関数の仕様に不都合があるからである。man 3 bsearch で調べると、次のような記述が見つかる。

返り値
       bsearch() 関数は、配列のメンバーのうち、一致したものへのポ
       インタを返す。見つからなかったときは NULL を返す。 key  と
       一致したメンバーが複数あるとき、そのうちのどのメンバーが返
       されるかはわからない。

Suffix Array を用いた 2分探索では、キーに前方一致でマッチす る最初の Suffix を見つける必要がある。よって、bsearch 関数の 「一致したメンバーが複数あるとき、そのうちのどのメンバーが返 されるかはわからない」という仕様では困る。そこで、「一致した メンバーが複数あるとき、そのうちの最初のメンバーを返す」ため にbsearch_first 関数を定義している。この、最初のメンバーを返 す2分探索アルゴリズムについては Jon Bentley の『珠玉のプログ ラミング』^*15 で詳しく解説されている。

サンプルプログラムの実行結果は次の通りである。

% ./sample4 
text + 9 = ra
text + 2 = racadabra

高速化のための技術

sary は Suffix Array を高速に処理するために、 mmap と pthread という 2つの特徴的な技術を利用している。ここでは両者 の使い方を簡単に紹介する。

mmap

mmap はファイルやデバイスをメモリにマップするシステムコール である。mmap したファイルはメモリと同じようにアクセスできる。 sary では、テキストと Suffix Array の両方のファイルを mmap で扱っている。

次のサンプルプログラムは、コマンドラインで指定されたファイル を mmap して小文字を大文字に変換しながら出力するものである。 fread や fgets といったファイル読み込みの関数は一切用いていない。

  #include <stdio.h>
  #include <stdlib.h>
  #include <ctype.h>
  #include <fcntl.h>
  #include <unistd.h>
  #include <sys/stat.h>
  #include <sys/mman.h>
  
  size_t  get_file_length  (const char *file_name);
  char    *map_file  (const char *file_name, size_t len);
  
  int 
  main (int argc, char **argv)
  {
      char *file_name, *map;
      size_t len;
      int i;
  
      if (argc != 2) exit(2);
      file_name = argv[1];
  
      len = get_file_length(file_name);
      if (len < 0) exit(2);
  
      map = map_file(file_name, len);
      if (map == NULL) exit(2);
  
      // メモリと同じようにファイルの中身にアクセスできる
      for (i = 0; i < len; i++)
          printf("%c", toupper(map[i]));
      
      return 0;
  }
  
  size_t
  get_file_length (const char *file_name)
  {
      struct stat st;
      if (stat(file_name, &st) < 0)
          return -1;
      return st.st_size;
  }
  
  char *
  map_file (const char *file_name, size_t len)
  {
      int fd;
      char *map;
  
      // 読み込み専用で開く
      fd = open(file_name, O_RDONLY);
      if (fd < 0)
          return NULL;
  
      // 読み込み可能なページとしてマップする
      map = mmap((void *)0, len, PROT_READ, MAP_SHARED, fd, 0);
      close(fd);
      if (map == MAP_FAILED)
          return NULL;
      return map;
  }
  

サンプルプログラムのコンパイル方法と実行結果は次の通りである。

% cc -o sample5 sample5.c
% ./sample5 sample5.c | head -3
#INCLUDE <STDIO.H>
#INCLUDE <STDLIB.H>
#INCLUDE <CTYPE.H>

mmap の使い方についてはRichard Stevens の『詳解UNIXプログラ ミング』 ^*16 が詳しい。

pthread

pthread は POSIX ^*17 のスレッド APIである。1 つのプロセス内で複数のスレッドを並列に実行できる。sary では pthread を用いて分割ソートのマルチスレッド化を行った。

次のサンプルプログラムは、下のような 2つのスレッドを並列に実 行するものである。

• スレッド1: 標準入力から 1文字づつ読み込む
• スレッド2: 何文字読み込まれたかを1秒ごとに表示する (5秒で終了)

  #include <stdio.h>
  #include <stdlib.h>
  #include <unistd.h>
  #include <pthread.h>
  
  void reader     (void *dummy);
  void reporter   (void *dummy);
  
  int count = 0;
  
  int 
  main (int argc, char **argv)
  {
      pthread_t thread1, thread2;
  
      pthread_create(&thread1, NULL, (void *)reader,   NULL);
      pthread_create(&thread2, NULL, (void *)reporter, NULL);
  
      pthread_join(thread2, NULL); // thread2 の終了を待つ
      return 0;
  }
  
  void 
  reader (void *dummy)
  {
      char byte;
      while (1) {
          // 標準入力から1文字づつ読み込む
          // こんな風にシステムコールを呼びまくると大変遅い
          if (read(0, &byte, 1) <= 0)
              break;
          count++;
      }
  }
  
  void 
  reporter (void *dummy)
  {
      int i;
      for (i = 0; i < 5; i++) {
          sleep(1);
          printf("%d bytes\n", count);
      }
  }
  

サンプルプログラムのコンパイル方法と実行結果は次の通りである。

% cc -o sample6 sample6.c -pthread

% ./sample6 < /dev/zero
1328655 bytes
2689596 bytes
4046096 bytes
5421934 bytes
6796633 bytes

pthread を使った実際のプログラミングでは、複数のスレッドが同 時に変数の値を書き換えるといった競合を回避するための排他制御 が必要になる。pthread を使ったプログラミングについては Bradford Nicholsらによる『Pthreadsプログラミング』^*18 が詳しい。

おわりに

今回は私が開発した Suffix Array のライブラリとツールである sary と Suffix Array の仕組みについて紹介した。sary を開発し たのは 2年前ほど前になる。当初は、巨大なテキストの検索を活用 していろんな便利なツールを作ろうと張り切っていたのだが、しば らくすると巨大なテキストを検索したいという場面はそれほど多く ないことに気づいた。結局、Emacs 上で英文の用例検索をする安直 なツールを作った程度で熱が冷めてしまった。

Emacs上で用例検索

とはいうものの、 Suffix Array の応用範囲は他にももっと考えら れるはずである。本記事を読んで Suffix Array を使って何か新し いソフトウェアを作ってみようと思ってもらえるとうれしい。

なお、本連載で作成したプログラムのソースコードは筆者のページ ^*19 から入手可能である。

謝辞

今回の原稿を執筆するにあたって、Suffix Array の技術内容につ いて山下達雄氏から多くの助言をいただいた。ここに記して感謝す る。

参考文献

1. 山下達雄: 『用語解説 「Suffix Array」』, 人工知能学会誌 Vol. 15 No. 6 p. 1142.
2. Udi Manber, Gene Myers: "Suffix Arrays: A New Method for On-line String Searches", 1st ACM-SIAM Symposium on Discrete Algorithms, pp. 319-327, 1990.
3. Jon Bentley著, 小林健一郎訳: 『珠玉のプログラミング』 , ピアソン, 2000.
4. Richard Stevens, 大木敦雄訳: 『詳解UNIXプログラミング』 , ピアソン, 2000.
5. Bradford Nichols, Dick Buttlar, Jacqueline Proulx Farrell, 榊正憲訳: 『Pthreadsプログラミング』 , オライリー・ジャパン, 1998.