Kirara

Full Text Database for Plan 9

2013/10/26
2013/12/07

Kirara のソースコードは http://plan9.aichi-u.ac.jp/netlib/kirara/ で手に入る。

サーチエンジン

デスクトップ・サーチエンジン

デスクトップ・サーチエンジンがサーチエンジンの特殊なジャンルであり、研究対象として独自の内容を持っている事が 2010 年^**の ACM の SIG で確認されている(文献[1], 文献[2])。

例えば、
(1) インターネットの検索エンジンが、検索者にとって未知のファイルを探すのに対して、デスクトップ・サーチエンジンは、検索者にとって既知のファィルを探す。探索対象は彼がかって生成したり、修正したりしたファイルである。
(2) インターネットの検索エンジンが探索するファイルの種類は限られているのに対して、デスクトップ・サーチエンジンの場合には、電子メールやマルチメディアを含む多様なファイルが探索対象になる。

フルテキスト・サーチエンジン

Mac Spotlight

僕が欲しいデスクトップ・サーチエンジン

Spotlight のようなデモン型^注1は失格である。こういうのはウザイ。
「デモン型だからこそ、必要な時に必要な情報が集まっているのでは?」の声もあろう。もちろん、デモン型でない場合には、必要になった時に情報を更新することとなる。問題はそれに要する時間である。どの程度の時間であれば我慢できるか? せいぜい数分だね...

インデックスを作るためのディスクスペースが要求される。最近はハードディスクが安くなっているので、ここは気にする事はない。
しかしインデックスのためにあまりにも多くのディスクスペースが要求されると、最初のインデックスのために時間が取られすぎる。一晩かけても構わないと言う人もいるとは思うが....
一番の問題は、インデックスの更新に多くの時間が費やされることにある。この時間を小さくしたければ、大きなインデックスを持たない方が良い。

検索時間は1秒以内がイライラしないための要求水準らしい。もちろん膨大な量のファイルを表示する場合には時間がかかる。ここでは遅延時間(最初のレスポンスが表示されるのに要する時間)が問題になっている。(この点で Spotlight は素晴らしい)

検索ツールに要求されるユーザーズインターフェース

ユーザースインターフェースと言えば、ウィンドウとかボタンとかの GUI を連想するだろうが、あのように奇麗に飾ったものは決して使いやすいとは言えない。それによって非常に多くのものが犠牲になっているからである。機能性こそが要求される。こではその視点から要求を分析してみる。

ユーザは指定した「語」(1個あるいは複数)を含むファイルを見付けるために検索ツールを使う。僕の経験では、該当するファイルが数百に昇る事は珍しくない。この中から目標のものを効率良く探し出せる仕組みを持った検索ツールが欲しい。

検索結果を絞るには普通は AND 検索が使用される。我々が、検索すべきファイルの内容に関する知識を持っていれば、この方法が使える。しかし、(持たない事が多いので)この方法が役に立たない場合も多い。むしろファイルの置き場所(パス)が検索結果を絞るのに役に立つ。

ヒットするファイルが数十程度であれば、ヒットした行も表示されていれば、さらに絞りやすくなる。数個程度に絞り込めば、そのファイルをエディタに取り込み、検索で指定した語がどのような文脈で使われているかを吟味したくなる。

以上のような使い方に答えてくれる検索ツールが欲しいのである。

オープンソース

OS も同様ではあるが、悪意のコードが含まれ、それが明らかになった場合には OS メーカー(巨大企業である)に致命的なダメージを与えることになる。しかし、デスクトップ・サーチエンジンは個人、もしくは(無名の)小さな「企業」により作られ公表されることが多い。歯止めが掛かりにくいのである。実際 Windows 用の検索エンジンである Copernic Desktop Search は僕の Vista を潰した(文献[4])。(あれはマルウェアであると言う噂がある)

Plan9

ネットには Plan9 は成功しなかったと言う論者が居る^注1。Plan9 はビジネス的には成功していないし、成功する見通しもない。Linux もデスクトップの分野では同様であり、FreeBSDも Apple によるアレンジによってようやく Windows への(小さな)対抗勢力となっている。

しかし他の面ではどうか? Plan9 が生み出した文字コード方式である UTF-8 は現在では Internet の標準文字コードとして不動の地位にある。また現在では Linux も Mac も採用しているユーザレベルのファイルシステムの考え方も Plan9 研究の産物である。Plan9 は OS 研究の成果として、現実世界に大きな影響を与えた点では成功したのである。

Plan9 がクライアントマシンの OS としてユーザーに受け入れられるためには、欠けているものが多すぎる。僕でさえ、クライアントマシンは Mac であり、そこで動いている OS は MacOS である。

他方では Plan9 はサーバとしては実用になっている。僕は、一番使いやすく、安心して使えるサーバーは Plan9 だと思っている。コンパクトで、ソースがオープンで、(他の OS のように)パッチワークではない。そのために動作が理解しやすく、必要に応じてユーザのレベルで手を入れやすい。そうしたことが使いやすく、安心して使えるための必要な条件なのである。

インデックス

フルテキストデータベースとインデックス

一意的な語の個数とテキストの関係

ここにおける一意的語数は、2文字以上の語に限定している^注1。総語数は1文字以上の語であり、空白で区切られたものを単位としている^注2。
一般論としては、総語数に対する一意的語数の割合は、総語数が増えると減少する。Doyle はこの割合が小さい。少年少女を相手にした小説なので、彼らの辞書にも無いような難しい語は使わないのであろう。
小説を、与えられた辞書に含まれる語のみを使って書くとすれば、小説のサイズがどれほど大きくなっても、そこに現れる一意的語の個数には上限が存在する。従って、(一意的語数/総語数) は、総語数が大きくなると 0 に収束する。

複数のファイルをまとめてインデックス化する

大きなインデックスファイルは3重の意味で不利である。1つ目は、インデックスのためのディスクスペースが大きくなり、それ自体嫌われる。2つ目は、インデックスファイルの更新に時間がかかる。3つ目は、検索時のインデックスの読み取りに時間がかかる。

僕の場合もそうであるが、多数のメモ的な小さなファイルを持っている(表1)。小さなファイルをそのままインデックス化すると、インデックスファイルのサイズは大きくなりがちである。そこで、複数のファイルをまとめてインデックス化するアイデアが出てくる。その場合、実際のファイルを探すのに grep の助けを借りる。

まとめる自然な単位はディレクトリであろう。作業はディレクトリを単位として行われており、1日の内で1つのディレクトリしか使わない事も多い。またディレクトリの中のファイル検索は grep と極めて相性が良い。Kirara の最初のバージョン(現在の Kirara1)はこのアイデアを基に作られた。

Kirara を完成させてから、ネットを調べてみると、Glimpse(文献[6]) も良く似たアイデアで作られている事が分かった^注1。

ファイルの読み取り速度

ファイルが非常に大きい場合には、小さな主記憶のコンピュータの場合には十分にキャッシュされない。従ってキャッシュを利用して速度を稼ごうとする場合には不利である。インデックスファイルは結構大きくなるので、筆者の環境ではインデックスファイルのサイズは検索速度にかなり大きな影響を与える。

次に示すのは 212MB のファイル(main)を 3 回読み取り、その時間を調べている。

term% ls -l
...
--rw-rw-r-- M 149 arisawa arisawa 212272271 Oct 20 15:31 main
...
term% time wc main
7217248 14434496 212272271 main
1.15u 0.22s 48.63r 	 wc main
term% time wc main
7217248 14434496 212272271 main
0.66u 0.18s 1.22r 	 wc main
term% time wc main
7217248 14434496 212272271 main
0.75u 0.18s 1.22r 	 wc main
term%

2回目からの読み取り速度が40倍に跳ね上がっているが、これはキャッシュの効果である。しかし、同じコンピュータの下でのもっと大きなファイル(これも main ではあるが異なるディレクトリにある)では次に見るように、キャッシュの効果は小さい。

term% ls -l
...
--rw-rw-r-- M 149 arisawa adm 464183117 Oct 26 22:03 main
...
term% time wc main
17106350 34212700 464183117 main
2.05u 0.37s 100.08r 	 wc main
term% time wc main
17106350 34212700 464183117 main
1.74u 0.35s 11.46r 	 wc main
term% time wc main
17106350 34212700 464183117 main
1.44u 0.28s 11.43r 	 wc main
term%

転置インデックスか grep か?

デスクトップ・サーチエンジンと言うのは、扱う対象によって実装方法を柔軟に考える必要があるのだろう。教科書的な方法が巧く働くのは、大きなファイルに対してだけであり、僕のシステムのように、大部分が小さなファイルの場合には(表1を見よ)、殆どのファイルについては grep の方が効率が良い。しかし大きなファイルも存在するので、検索時にファイルのサイズに応じて方法を切り替えた方が良い。

Plan9 ユーザとサーチ・エンジンとのインターフェース

ユーザの特徴

筆者の場合、検索の主な対象はプログラムである。Plan9 のマニュアルは丁寧に書かれてはいるが、機能を論理的に説明されただけでは、なかなか理解できない事がある。プログラムのサンプルが欲しいのである。幸い Plan9 はオープンなシステムなので、ソースコードが添えられている。こうしたソースコードがプログラミングの効率を上げ、陥りがちな誤りを防いでくれる。生きたコードの中からライブラリ関数の使用例に容易にアクセスできる全文検索型のテキストデータベースは役に立つはずである。

rio

acme

plumb

パイプと grep

Plan9 の特徴とサーチ・エンジンの設計

Plan9 で動く Desktop Search Engine を設計するとすれば、Plan9 のどのような特徴が活用できるだろうか?

文字コード

多様な文字コードが混在する環境下でのソフトウェア開発は地獄である。幸いな事に Plan9 では、この問題から解放されている。

ファイルシステム

ファイルシステムのファイルの変更イベントのログ

ファイルシステムのファイルの変更イベントをうまく手に入れるメカニズムが存在すれば、インデックスの更新時間を大幅に節約できる。

Plan9 以外の OS では、これを実現するためにはカーネルの修正が要求される。例えば Linux 用に書かれたサーチエンジンである Wumpus(文献[10]) では、そのためのカーネルパッチが提供されている(文献[11])。しかし、カーネルパッチが要求されるようなツールは使われないであろう。カーネルパッチは敷居が高すぎるのと、頻繁に行われるカーネルのアップデートにユーザも開発者も付いて行けないのである。

Plan9 はこの点で非常に柔軟で、ファイルの変更イベントを手に入れる仕組みをユーザレベルで簡単に追加できる。カーネルの修正は不要で、ファイルシステムへの修正すら必要はない。ファイルの変更イベントを手に入れるには単に1つのプログラムを追加すればよい。これを使うと、インデックスの更新に必要な情報は数秒で(場合によっては瞬間的に)手に入る。

qid

unix 流プログラミング

unix ではどうだろう? ファイル名にシングルの引用符が含まれている可能性があれば、sh や bash はもうお手上げである。つまり、ファイルを一般的に扱う場合には、ちゃんとしたプログラミング言語を使わないと、バグる。

unix と言うのは、大きなプログラムを作って問題を解決するのではなく、既存の小さなプログラム(ツール)を組み合わせて、問題を解決できるようにした OS である。シェルがプログラムとプログラムを繋ぎ合わせる役割を果たしている。もちろん、既存のツールだけではやっていけない事もあろう。その場合には不足している部分だけを補ってやる。これが unix 流のプログラミングである。しかし、実際にはシェルに問題があって、うまく行かない場合がある。

結局、unix においても、大きなプログラムが横行するようになった。現在においては、unix 流プログラミングの理念は Plan9 の中でしか実現できない。

C が一番早い?

Plan9 の基本ツール(grep,awk,...)は恐ろしく速い^注*。正規表現ライブラリを使って僕が書く grep もどきは、とてもあれだけのスピードは出ない。基本ツールはプログラムの達人が、磨きをかけて完成している、いわば芸術品である。コードを見ると、スピードを上げるために普通ではない書き方がされている。

我々が全てを C で新たに書こうとすると、達人達が行った以上の高度な技を駆使しなくてはならないだろう。そうしなければ効果が上がらない場合がある。そして大抵はそれはできない。

そうであるから、使えるものは使う、この方が速度においても良い結果が得られる。

Kirara

Kirara1 と Kirara2

違いが顕著に現れるのは、指定した複数の語を1つの行に含むファイルを検索する場合である。Mac の Spotlight はこれをサポートしていない。他のデスクトップ・サーチエンジンも同様だと思われる。

検索では通常、膨大な数のファイルがヒットする。我々の目標は、その中から目的に合致するものを選び、場合によっては、検索対象の語がテキストの中でどのように使用されているかを調べる事である。この点で、Kirara1 も Kirara2 も共に設計には以下の点が配慮されている。
(1) 第1ステップでは、Kirara1 ではヒットしたディレクトリへのパス、Kirara2 ではヒットしたファイルへのパスが表示される。必要とあれば出力を grep に渡して、パス情報を基に表示をマスクできる。この点は unix 系の検索エンジンでであれば、どれも同じである。そして、多くの検索エンジンはここで止まっている。
(2) 第2ステップでは、第1ステップで得られた結果を基に、該当ファイルのパスと、ヒットした行の内容と行番号が表示される^*。

Kirara1

さて Kirara1 は指定された語を含むディレクトリを探す。例えば

kfind1 'snoop&htm|html'

kfind1 'snoop&htm*'

さて、ディレクトリの中から、指定された語を含むファイルを探し、その行を表示するコマンドは G1 である。

kfind1 'snoop&htm|html'

G1 'snoop|htm|html' /lib/
G1 'snoop|htm|html' /sys/lib/linux/var/lib/apt/lists/
G1 'snoop|htm|html' /sys/src/cmd/mothra/
...

なお、指定された条件の語が含まれるディレクトリが存在したとしても、指定された条件のファイルが存在するとは限らない。つまり G1 による検索が空振りになる可能性がある。このことが Kirara1 が Kirara2 よりも検索時間が遅くなる理由である。

Kirara2

kfind2 'snoop&htm|html'

G2 'snoop|htm|html' /sys/src/cmd/mothra/mkfile
G2 'snoop|htm|html' /usr/arisawa/doc/rfc/1rfc_index.txt
G2 'snoop|htm|html' /usr/arisawa/netlib/9fans/9fans.0006
...

maia% G2 'snoop|htm|html' /sys/src/cmd/mothra/mkfile
/sys/src/cmd/mothra/mkfile:6: 	snoop.c \
/sys/src/cmd/mothra/mkfile:9: 	html.syntax.c \
/sys/src/cmd/mothra/mkfile:11: 	rdhtml.c \
/sys/src/cmd/mothra/mkfile:15: HFILES=mothra.h html.h libpanel/panel.h libpanel/rtext.h
maia%

snoop と、htm または html を同じ行に含むファイルを探すには

kfind2 'snoop htm|html' |rc

kfind2 'snoop htm|html'

Kirara は通常のデスクトップエンジンと異なり、そのアウトプットを(パイプを通じて)他のプログラムに渡せるように配慮されている。決して、Kirara だけで全てを行うようには考えられていない。

Kirara で使われた新しいツール

Kirara は Plan9 のシェルスクリプト rc をベースにして、速度が要求される部分、あるいは rc が適さない部分(文字単位の処理が要求される部分)は C で開発されている。この方が見通しが良く、また柔軟に仕様を変更できる。Plan9 の grep や awk などの基本ツールは素晴らしく速く、それらを使いたいと言うのも、rc をベースにした理由でもある。

以下では Kirara で使われた(あるいは Kirara のために開発された)筆者のツールをいくつか紹介する。これらは汎用のツールなので、他のアプリケーションへの応用が利く。

rdline

ファイルから1行を読み取るのに、unix では関数 fgets() が使われる。この関数は読み取った行を格納するバッファを与え、そこにストリームから読み取ったデータ(これも 関数 fopen() によってバッファリングされている^注1)をコピーする。

関数 fgets() は2つの点で問題がある。1つは、ストリームバッファから読み取るためのバッファを指定する必要があり、この必要サイズが前もって分からない事が多い事。2つ目は、バッファからバッファへの無駄なコピーが発生しており、そのために遅くなる事である。

第1の点に関しては、関数 getline() によって柔軟な対応ができるが、やはり無駄なコピーが発生している点では違いは無い。

Plan9 では、bio ライブラリの関数 Brdline() や Brdstr() が直接バッファを参照する事によって無駄なデータのコピーを防ぎ、高速化を図っている。関数 Bopen() が大きなバッファを確保するので、Brdline() が扱える1行の最大サイズは Bopen() の大きなバッファサイズに一致する。まあ、余程変なテキストファイルでない限り、このサイズを超える事はないでしょう。

さて、残念な事に、Brdline() はファイルの末尾が改行で終わらないファイルの読み取りに問題を抱えている。unix の由緒正しいテキストファイルは改行で終わる。Plan9に携わる全ての人々は、正しいテキストファイルしか扱ってこなかったのだと思う。しかし、コンピュータユーザの層が広がったために、近頃ではファイルの末尾が改行で終わらないテキストファイルが当たり前のように転がっている。もしも Brdline() がそのようなファイルを読むとどうなるか? 最後の行が読み取れないのである!

テキストファイルの読み取りは、殆どの場合、行単位なので、Brdline() がそのような問題を抱えていれば、非常に困る。Brdstr() は Brdline() の代わりに使う事が可能であるが、以下に見るように遅い。(Brdline() の2倍以上時間がかかる)

Kirara では、行読み取り専用の関数 rdline() を開発し、それが使われている。この関数はファイルの末尾が改行で終わっていなくても、全ての行を正しく読み取る。もっともファイルの末尾が改行で終わっていない事を判定する方法を提供していないので、rdline() を使ってテキストファイルをコピーすると、ファイルの末尾が改行で終わっていないファイルの場合、生成されたファイルは由緒正しいテキストファイルになり、末尾に改行が追加される。

以下は実験である。読み取る対象は212MBのテキストファイルである。

--rw-rw-r-- M 149 arisawa arisawa 212272271 Oct 20 15:31 /n/other/kirara1/usrdb/main

(十分にキャッシュされた後の)実行時間は次の通りである。

term% time 8.rdline_demo -f Brdstr /n/other/kirara1/usrdb/main
1.25u 0.35s 2.03r 	 8.rdline_demo -f Brdstr /n/other/kirara1/usrdb/main
term% time 8.rdline_demo -f rdline /n/other/kirara1/usrdb/main
0.46u 0.12s 0.86r 	 8.rdline_demo -f rdline /n/other/kirara1/usrdb/main
term% time 8.rdline_demo -f Brdline /n/other/kirara1/usrdb/main
0.27u 0.21s 0.80r 	 8.rdline_demo -f Brdline /n/other/kirara1/usrdb/main

ここに -f のオプションは、使用する関数を指定している。計測に使用したソースコードを以下に示すが、rdline() の使い方もこれから分かる。

#include <libc.h>
#include <bio.h>
#include "misc.h"

char *func;
Biobuf bout;

void
usage(void)
{
	fprint(2,"usage: rdline_demo -f func file\n");
	exits("usage");
}

void
doit_rdline(int fd)
{
	char *p;
	Rdbuf *rb;
	rb = RdbufNew(fd, 32*1024);
	while((p = rdline(rb))){/* assign = */
		;
	}
}

void
doit_Brdline(int fd)
{
	char *p;
	Biobufhdr bin;
	uchar biobuf[32*1024];
	if(Binits(&bin, fd, OREAD, biobuf, sizeof(biobuf)) < 0)
		sysfatal("input not open: %r");
	while((p = Brdline(&bin, '\n'))){ /* assign = */
		;
	}
}

void
doit_Brdstr(int fd)
{
	char *p;
	Biobufhdr bin;
	uchar biobuf[32*1024];
	if(Binits(&bin, fd, OREAD, biobuf, sizeof(biobuf)) < 0)
		sysfatal("input not open: %r");
	while((p = Brdstr(&bin,'\n',1))){ /* assign = */
		;
	}
}

void
main(int argc, char *argv[])
{
	int fd;

	ARGBEGIN{
	case 'f': func = EARGF(usage());
		break;
	default: usage();
	}ARGEND

	if(*argv == nil)
		usage();

	if(!func)
		usage();

	Binit(&bout, 1, OWRITE);

	fd = open(*argv,OREAD);
	if(fd < 0)
		sysfatal("%s not open: %r",*argv);

	if(strcmp(func,"rdline") == 0)
		doit_rdline(fd);
	else
	if(strcmp(func,"Brdline") == 0)
		doit_Brdline(fd);
	else
	if(strcmp(func,"Brdstr") == 0)
		doit_Brdstr(fd);
	else
		usage();

	close(fd);
	Bterm(&bout);
	exits(nil);
}

このプログラムの中の関数 doit_XXXX(int fd) の中の、変数 p が、行への参照ポインタである。通常は、この p を使って何かが行われる。

trans

unix のツールの中に tr コマンドがある。tr はファイルの中の文字を変換する。あるいは与えられた文字を削除する。trans ツールは(文字ではなく)文字列の変換テーブルを与えて、テキストファイルを変換する。簡単な例を挙げると、テーブルが

alice	bob
bob	alice

alice	bob
bob	carol
carol	alice

このようなツールは unix の中に存在しても良さそうに思えるが、存在しない。そこで作る事にした。(もっとも Kirara のためではなく、その前に作った Mac 用の u9fs のためであった。)

まずテキストファイルをスキャンしたときに、テーブルの第1列目の文字列を効率良く見付ける必要がある。unix にはそのためのツールとして fgrep (現在では grep の1つのオプションとなっている) があるが、僕は fgrep のコードは見ていない。多分、僕が考えたものよりも効率が良いと思う。(僕のはもう少し改善の余地があるから)

trans は fgrep のように、単に見付けるのではなく、テーブルの第2列目の文字列に変換する点で fgrep よりも複雑である。そして別の応用があり得る。

Kirara の中ではアルゴリズムが異なる2つの trans コマンドが使われている。KR_trans と eKR_trans である。KR_trans では文字列を見付けるのに Karp-Rabin アルゴリズムが使われている。このアルゴリズムはもともと1個の文字列の検索法として提唱されたが、Karp-Rabin アルゴリズムの素晴らしい点は、マルチパターン検索に使える可能性がある事である。Trie 法を使った場合もマルチパターン検索が可能であるが、メモリーを食いすぎる。

Karp-Rabin アルゴリズムをそのままパターン検索に使った場合には制約が強く、検索文字列の長さが全て同じ場合にだけに利用できる。この方法は Kirara の中では、qid をパスに変換するのに使われている。eKR_trans は Karp-Rabin アルゴリズムを、固定長文字列ではない場合にも使えるように僕が拡張したもので、これはイベントログを分析するのに使われている。先に僕が改善の余地があると述べたのは eKR_trans の方である。

文献[9]には、マルチパターン検索の最近の研究の成果が簡単に説明されている。

ffm

alice
bob

ffm -f3 pattern_file target_file

この例では完全一致であるが、ffm にオプション -m を与えれば、第3フィールドの先頭からの部分文字列が alice または bob と一致する行を表示する。もちろん最長マッチングである。
さらに、(awk と組み合わせて)一致した行を加工するのに適したオプションも存在する。

ffm は正規表現をサポートしていない。pattern_file には膨大な(例えば数万の)検索文字列が存在する事が想定されており、そのようなケースでは、正規表現はあまり役に立たないんだよね。本当に必要なった場合にはサポートするけど...

Kirara のスクリプトを見れば分かるけど、ffm は非常にたくさん使われている。結構便利なツールなのである。

mkdict and lkdict

mkdict と lkdict は英辞郎を Plan9 でも使えるようにするために開発されたが、Kirara2 では大きなファイルをインデックスし検索するのに使われている。英辞郎は 200MB もあり、これを grep で検索すると(キャッシュされていない場合には)ひどく時間がかかり使い物にならない。mkdict はインデックスファイルを作り、lkdict は語を与えて検索する。いずれも1つのファイルを対象としている。lkdict では複数の語を与えてもよく、その場合には、与えられた全ての語を含む行を出力する。正規表現に基づく or 検索も可能である。
mkdict が生成するファイルは、比較的オーソドックスな内容になっており^*、いわゆる辞書(ファイルの中の一意語の一覧ファイル)とリスト(語の位置情報を一意語ごとに整理し圧縮したファイル)から構成される。
また大きな辞書に対しては、辞書の目次を作成しておくと、効率良く語にアクセスできるので、そのための機能も持たせてある。

文献

[1] David Elsweiler, Gareth Jones, Liadh Kelly and Jaime Teevan (2010)
Workshop on Desktop Search
http://www.sigir.org/forum/2010D/sigirwksp/2010d_sigirforum_elsweiler.pdf

[2] David Elsweiler, Gareth Jones, Liadh Kelly and Jaime Teevan (2010)
SIGIR 2010 DESKTOP SEARCH
Workshop of the 33rd Annual International ACM SIGIR Conference
http://www.cdvp.dcu.ie/DS2010/DesktopSearchProceedings.pdf

[3] Francisco J Ballesteros (2007)
File indexing and searching for Plan 9
4th International Workshop on Plan9
http://4e.iwp9.org/papers/tags.pdf

[4] Kenji Arisawa (2013)
Virus にやられたらしい
http://ar.aichi-u.ac.jp/blog/virus.html

[5] Russ Cox (2007)
Regular Expression Matching Can Be Simple And Fast
http://swtch.com/~rsc/regexp/regexp1.html

[6] Udi Manber and Sun Wu (1993)
GLIMPSE: A Tool to Search Through Entire File Systems
http://webglimpse.net/pubs/glimpse.pdf

[7] Udi Manber, Burra Gopal and Sun Wu (1998)
Glimpse Documentation
http://webglimpse.net/gdocs/glimpsehelp.html

[8] 東京大学情報基盤センター 黒田久泰 (2006)
C言語におけるファイル入出力の高速化
http://www.cc.u-tokyo.ac.jp/support/press/news/VOL8/No5/data_no1_0609.pdf

[9] Leena Salmela (2007)
Multi-Pattern String Matching with Very Large Pattern Sets
http://www.dcc.uchile.cl/~gnavarro/workshop07/lsalmela.pdf

[10] Stefan Büttcher (2007)
Wumpus — File System Search
http://www.wumpus-search.org/

[11] Stefan Büttcher (2007)
fschange – Linux File System Change Notification
http://stefan.buettcher.org/cs/fschange/index.html

[12] Stefan Büttcher, Charles L. A. Clarke and Gordon V. Cormack
Information Retrieval Implementing and Evaluating Search Engines
(The MIT Press, 2010)

[13] Ricardo Baeza-Yates and Berthier Ribeiro-Neto
Modern Information Retrieval -- the concept and technology behind search -- second edition
(Addison Wesley, 2011)

[14] Christopher D. Manning, Prabhakar Raghavan, Hinnrich Schütze (訳者: 岩野和生, 黒川利明, 濱田誠司, 村上明子)
情報検索の基礎 (Introduction to Information Retrival)
(共立出版, 2012)