Nurmi Labs: Kirara

This entry will look at the indexing software written with Plan 9's rc and dialect of ANSI C, and implemented using unicode encoding.

http://plan9.bell-labs.com/sources/contrib/arisawa/
kirara-2.2b.tgz

~~http://plan9.aichi-u.ac.jp/kirara/~~ (dead link)

Japanese webpage

Kirara

Full Text Database for Plan 9

目次

1.0.0 サーチエンジン
1.1.0 デスクトップ・サーチエンジン
1.2.0 フルテキスト・サーチエンジン
1.3.0 Mac Spotlight
1.4.0 僕が欲しいデスクトップ・サーチエンジン
1.5.0 検索ツールに要求されるユーザーズインターフェース
1.6.0 オープンソース
1.7.0 Plan9
2.0.0 インデックス
2.1.0 フルテキストデータベースとインデックス
2.2.0 一意的な語の個数とテキストの関係
2.3.0 複数のファイルをまとめてインデックス化する
2.4.0 ファイルの読み取り速度
2.5.0 転置インデックスか grep か?
3.0.0 Plan9 ユーザとサーチ・エンジンとのインターフェース
3.1.0 ユーザの特徴
3.2.0 rio
3.3.0 acme
3.4.0 plumb
3.5.0 パイプと grep
4.0.0 Plan9 の特徴とサーチ・エンジンの設計
4.1.0 文字コード
4.2.0 ファイルシステム
4.3.0 ファイルシステムのファイルの変更イベントのログ
4.4.0 qid
4.5.0 unix 流プログラミング
4.6.0 C が一番早い?
5.0.0 Kirara
5.1.0 Kirara1 と Kirara2
5.2.0 Kirara1
5.3.0 Kirara2
6.0.0 Kirara で使われた新しいツール
6.1.0 rdline
6.2.0 trans
6.3.0 ffm
6.4.0 mkdict and lkdict
7.0.0 文献

2013/10/26
2013/12/07

今年の夏休みはデスクトップ・サーチエンジンを書いていた。Kirara と言うのは、そのサーチエンジンの名前である。日本的な古めかしい名前であるが、僕はこの名前が好きである。

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

サーチエンジン

2013/10/26

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

普通の人は「サーチエンジン」と言えば Google など検索企業のサーチエンジンを思い浮かべるであろう。彼らは巨大な設備を使ってネットに転がっている世界中の情報を集めて、検索サービスを行う。僕がこのまねごとなどできないのは明らかで対抗する気は毛頭にない。「デスクトップ・サーチエンジン」とは、個人が管理するコンピュータの中の情報を集めて検索可能にするソフトウェアのことである*。ここは Google の検索エンジンが入り込めないという意味で聖域であり、情報の整理はこちらで行わなくてはならない。
インターネットのサーチエンジンとデスクトップ・サーチエンジンとの中間のものとしてイントラネットのサーチエンジンが存在するが、僕は今のところ興味は無い。

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

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

注*: 「デスクトップ・サーチエンジン」は(学術的な意味では)あまり適切な言い方ではない。文献[14] では "Personal Information Retrieval" と表現している。この方が本質を的確に表している。
注**: 文献[1]では2009年となっているが、間違いであろう。

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

Kirara は Plan9 用に設計したフルテキスト・サーチエンジンである。unix には既にいろいろなサーチエンジンがあるので、いまさら新たに作らなくてもよいであろう。以前からサーチエンジンは Plan9 にも欲しいと思っていた*。そこで作る事にしたのである。フルテキスト・サーチエンジンとして設計したのは、僕がなまくらであり、検索キーワードの入力のために時間を割いて、ファイルの整理などできるはずがないからである。フルテキスト・サーチエンジンは、僕が何もしなくても、ファイルの中に含まれる語を自動的に抽出して検索可能にしてくれる。

注*: 僕が Kirara をアナウンスしたら、すぐに nemo さんからメールを頂いた。彼も Plan9 用のサーチエンジンを公表しているのだそうだ(文献[3])。でも彼のはプログラム中の tag のデータベースツールであり、フルテキスト型ではない。

Mac Spotlight

デスクトップ・サーチエンジンと言うものは滅多に使用しないものである。僕のゼミ生に聞いてみたが、Windows にもデスクトップ・サーチエンジンが存在する事を誰も知らない。知らなくても困らないような使い方しかしていないのである。Mac にも Spotlight と言う優秀なデスクトップ・サーチエンジンが存在する*。しかし僕は日常的に使う事はない。つまり無くてもよいようなものであるが、時に、「あのファイルはどこにあるのだろう」と悩む事があり、その時に役に立つ。つまり、デスクトップ・サーチエンジンと言うものは保険的なものに過ぎない。

誰でも保険に過度の支払いはしたくないであろう。Spotlight はバックグランドジョブとして絶えず情報を収集していて、その活動がウザイ。活動中には Mac の動きが悪くなるので、ネットには「Spotlight を止めたい」という悲鳴が結構聞こえてくる。でも最近の Spotlight は昔に比べて改良されて、ずいぶんと静かになったのだよ。

注*: 正確に言えば Mac のサーチエンジンは mds (Meta Data Server) であり、Spotlight はファインダーからの検索ツールである。

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

僕が理想とするデスクトップ・サーチエンジンとは、必要なときにだけ姿を現してくれる女神様のようなものである。普段は邪魔にならない。存在すら忘れてしまう。しかし、困った時の神頼みにはしっかりと答えてくれるサーチエンジンが欲しい。もちろん、これは理想論であるが、これにどこまで近づけられるかである。

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

注1: バックグランドジョブとして常に実行されているプログラムの事。サーバーとも言われる。Mac では mds(metadata server) が Spotlight へのサービスを行っている。

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

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

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

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

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

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

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

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

オープンソース

デスクトップ・サーチエンジンのソースはオープンであって欲しい。僕の技術的な興味と言うよりも、ユーザにとってのセキュリティの問題である。デスクトップ・サーチエンジンはファイルシステムを隈無く探すので、悪意のコードが含まれていても気付かれにくく被害が大きくなる。

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

Plan9

Kirara は Plan9 用に設計されたフルテキストのデスクトップ・サーチエンジンである。Plan9 とは unix を生み出した Bell 研究所が、unix をネットワーク時代にうまく適合するように unix を見直し、新たに開発した OS である。

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

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

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

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

注1: こうした論者は、Plan9 でやれる事は(ライブラリなどによって)アプリケーション側でやれるとも言う。そのようなケースもあるだろうが、アプリケーション側でやれない事もある。セキュリティに絡む問題が典型的な例である。そのために Pegasus のような Web サーバーは Plan9 でしか作れない。

インデックス

2013/10/29
2013/10/30
2013/11/15

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

フルテキストデータベースは、テキストに現れた「語」と、その場所の情報を格納したインデックスを持つ。「場所」と言うのは、ファイルへのパスであったり、ファイルの中の位置情報であったりする。僕が個人的に使用しているシステムでも、検索対象のファイルの個数は10万にも及ぶ。従って少なくとも「語」と、その「語」を含むファイルへのパスの関連情報を持たないと、遅くて実用にならない。「語」を基に「場所」を探せるように整理したインデックスを転置インデックスと言うが、以下では単にインデックスと言えば転置インデックスのこととする。

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

テキストのサイズと、そこに含まれる一意的な語の個数との関係は古くからよく研究されていて、追加すべき新たな内容を僕は持たない。学術的な研究には標準化されたテキストが使われており(例えば文献[13]に詳しい)、素人には分かりにくい。ここでは良く知られた小説を基に僕が計算した結果を紹介する。

著者	ファイルサイズ	総語数	一意的語数	一意的語数/総語数
Lincoln(G)	1531	272	145	53%
Obama(N)	4956	878	358	41%
Poe(B)	22209	4009	1246	31%
Shakespeare(M)	100243	18100	3195	18%
Shakespeare(H)	175221	32014	4533	14%
Doyle(A)	611011	104529	2141	2%
Dostoevsky(C)	1212802	220406	10620	5%
Tolstoy(W)	3226683	566318	17599	3%

Lincoln(G): Lincoln's Gettysburg Address
Obama(N): Obama's Nobel Prise speech
Poe(B): The Black Cat
Shakespeare(M): Macbeth
Shakespeare(H): Hamlet
Doyle(A): The Adventures of Sherlock Holmes
Dostoevsky(C): Crime and Punishment
Tolstoy(W): War and Peace

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

注1: Kiraraで採用された方法である。
注2: unix の wc で算出している。従って数字を含む。

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

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

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

size	ファイル数(usr)	ファイル数(sys)
~ 1KB	29725	10254
~ 10KB	40128	15263
~ 100KB	15331	5710
~ 1000KB	1509	313
~ 10000KB	220	12
~ 100000KB	17	4

表tab:stat>: 筆者のインデックス対象のファイルの分布

usr は、僕のホームディレクトリのインデックス対象

sys は、公式配布ファイルの中のインデックス対象

ファイル数は実際にインデックスされているテキストファイルのみ

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

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

注1: 複数のファイルをまとめ、grep を援用している。ただしディレクトリを単位としていない。3MB程度のサイズまで適当にファイルをまとめているようだ。Glimpse は上手にインデックスファイルを小さくしているようだが、インデックスファイルの更新は遅い。

ファイルの読み取り速度

ある本によると 7200rpm のハードディスクの計算上の読み取り速度の上限は 33MB/s 程度だと言う。この数字はキャシュされていない事を前提に計算されている。実際には様々な要因に支配される。ディスクアクセスを伴うプログラムの処理能力を調べるのは非常に難しい。ディスクからファイルを読み取ると、データがキャッシュされ、そのキャシュが追い出されない限り、ディスクからの読み取り速度ではなく、メモリーからの読み取り速度を基に計測していることになり、「処理能力」は数10倍も跳ね上がる。

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

次に示すのは 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 か?

フルテキストデータベースの話では、実装の方法として必ず採り上げられるのが、転置インデックスである。あるファイル F があったとする。ある「語」W を含む F の行を全て表示する問題は、転置インデックスを使って解決できる典型的な問題である。しかし、他方では grep を使っても簡単に解決できる。小さなファイルであれば grep の方が速い。しかし大きなファイルでは転置インデックスを参照した方が速い。転置インデックスを使う場合には3個のファイルが参照されるために小さなファイルでは効率が悪すぎる。他方では grep は、ファイルを初めから終りまで全て読み取るので、大きなファイルでは不利になるのである(図1)。僕の経験では 3MB 程度の所にクロスポイントがあるのではないかと思うが、厳格な実験に基づいてこの数字が主張されているわけではない。

図1: grep検索と転置インデックス検索との速度比較 (概念図)

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

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

2013/10/29

ユーザの特徴

応用プログラムの設計はユーザーニーズに合わせるべきである。
Plan9 のユーザは極めて特殊で、彼らの主たる関心はプログラミングである。またその方面に関しては十分な知識を持ち、訓練されている。シェルの使い方を知らないユーザは存在しないし、grep の使い方を知らないユーザも存在しないと考えて良い。見栄えには関心が無く、機能性が重視される。彼らはコマンド派である。またテキストファイルを好む。

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

rio

rio とは Plan9 のウィンドウズシステムである。グラフィックスの扱いが良いとは言えないが、テキストの扱いは極めて良い(良くできている)。
rio の中に生成されるターミナルウィンドウは、それ自体テキストエディタのように、表示されているテキストを編集できる。それがコマンドであれば、その範囲をマウスで指定して実行できる。unix 系では Mac のターミナルが横幅を自由に変更でき扱いやすいが*、表示された結果が編集できないのが辛い。rio は、それを編集できるようにしたものだと思えばよい。

注*: Linux も横幅を変更できるが、表示は 80 文字に合わせられている。

acme

Plan9 の基本エディタ(テキストエディタ)は acme である。他に sam エディタもあるが、通常は操作がシンプルな(初等的な) acme が使われているようである。unix にある他のテキストエディタと比べると、飾りのようなものは無く、機能性重視であり、マルチファイルエディタである。また acme の中で Plan9 の任意のコマンドも実行できる。acme は unix の emacs に対するアンチテーゼであり、emacs 以上の機能を持たせながら、emacs のようには難しくはない。

plumb

ターミナルで語を指定して検索コマンドを打った時、結果がターミナル上に表示される。Kirara ではファイルへのパスと、その語を含む行の内容と、その行番号とが表示されるようになっている*。通常は多数のファイルが表示されるであろう。行も表示されるので、目的のファイルの見当が付きやすいが、目的の語がどのような文脈で使用されているか知りたい時には、Plan9 には plump と呼ばれる仕組みがあり、新たにコマンドを打たなくてもマウスだけで、そのファイルを acme に表示させ、しかも問題の行を選択状態にしてくれる。

注*: Mac の mdfind(Spoltlight) はファイルへのパスしか表示してくれない。なお Spotlight と言えば普通は Finder からの検索を意味するが、ああいうのははっきり言って実用にならない。該当するファイルの量が多すぎるのである。Apple は、これを絞り込む適切な方法を提供すべきであろう。

パイプと grep

結果の表示を絞るのに、パイプと grep が使える。パイプと grep は Plan9 のユーザは誰でも使い方を知っていると仮定してよい。サーチエンジンの検索インターフェースに、結果を絞るための特別なオプションを付けるよりも、パイプと grep に任せる方がユーザは理解しやすいだろうし、柔軟な利用が可能になる。

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

2013/10/27
2013/11/12

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

文字コード

Plan9 は UTF-8 発祥の地である。もちろん任意の文字コードのファイルを置けるが、全てのツールは UTF-8 を前提に作られている。従ってフルテキスト・サーチエンジンも UTF-8 を前提に設計してもよいだろう。

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

ファイルシステム

Plan9 ではファイルシステムはカーネルと分離している。そのためにファイルシステムのソースコードは見通しが良く、また動作を追いかけやすい。現在はサーバー用には主に fossil と cwfs が使われている。fossil は Russ Cox が実装し、cwfs は Geoff Collyer が Ken Thompson のコード注1を Plan9 カーネルの下で使えるようにしたしたものである。
マニュアルによれば、Plan9 のファイルシステムのディレクトリの mtime (修正時刻) は、そこに含まれているファイルの mtime が変更を受けた時に、同時に変更を受ける。fossil はこの点でマニュアル通りの動作をするが、cwfs は unix と同じ動作をしている。つまり変更を受けない。これは cwfs のバグであり、克服されるべき部分である。

注1: cwfs の下になったコードは Ken Thompson が書いたファイルサーバ専用機のコードである。この方法の欠点は、コンピュータが1個余計に必要な事と、ソースコードのメンテナンスが困難な事にある。

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

デスクトップ・サーチエンジンにとって、新たに作られたファイル、削除されたファイル、さらに更新されたファイルを知る事はインデックスの更新にとって不可欠である。いかにすばやくこの情報を手に入れるかが、更新時間を決める2大要素の一つである。
OSはこの情報を提供しないので、通常のデスクトップ・サーチエンジンは非常に非効率的な方法で、ファイルの変更情報を手に入れる。そのためにファイルシステムをくまなく探す。この間、CPU はこの仕事に追われ、また大量のディスクアクセスが発生する。ユーザのイライラの主な発生源である。

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

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

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

Apple の MacOS は mds (Meta Data Server) にファイルの変更情報を送っていると思われる。そうでなければ、あれほど素早く、ファイルの変更を mds に反映させる事はできない。

qid

qid と言うのは、ディレクトリやファイルを識別するための ID であり、unix の inode のようなものである。ただし inode と異なり、ディレクトリやファイルごとに、ユーザ ID などの情報と一緒になっている。詳しくは筆者の記事「 cwfs の研究」の中に解説されている。
Plan9 の qid は 8B の情報であり、これを使ってデータベースの「語」とファイルの関係を表せば、パスを使うよりも簡潔になる。その場合には、もちろん、qid とパスとの対応表が必要になる。

unix 流プログラミング

Plan9 のシェル rc は非常によくできていて、Plan9 の全てのファイルを扱える。サーチエンジンはシステムに許される全てのファイルを扱えなくてはならない。その中には、ファイル名に二重引用符(")やシングルの引用符(')、それから * や ? など、通常は使わないような文字を含むものがあり得る。こちらが、そのようなファイルを作らないように気をつけていても、よそから持って来たファイルには様々な文字がファイル名に含まれている。

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

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

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

C が一番早い?

現在では全てのプログラムの源流は C だから、C で書くのが一番速いと考えがちである。しかし僕が Kirara を書いた経験から言えば、微妙である。なぜか?

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

Plan9 の正規表現はシンプルで、他のスクリプト言語に見られる正規表現のようには、多彩なオプションを備えていない。多彩なオプションの陰で支払われた代償に関しては Russ Cox のネットの記事が参考になる(文献[5])。

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

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

Kirara

2013/10/29
2013/11/04

Kirara1 と Kirara2

現在のところ Kirara には性格の異なる2つのバージョンがある。

Kirara1(ver.1.x) および Kirara2(ver.2.x) である。
Kirara1 はディレクトリを単位にインデックスしている。世の中にいろいろなサーチエンジンがあるが、このような方法を採用しているのは、Kirara1 だけではないかと思う。Kirara2 はオーソドックスにファイルを単位にインデックスしている。どちらが良いかとは簡単には言えない。それぞれに一長一短があり、ユーザの選択に任せた方が良いと判断している。

*	Kirara1	Kirara2
初期インデックス時間	速い	遅い
インデックス更新時間	速い	遅い
インデックススペース	小さい	大きい
検索時間	遅い	速い

Kirara1 の検索時間は「遅い」としたが、通常の検索においては両者の違いは殆どない。ここで言う「通常」とは、「語」(1つあるいは複数)を指定して、それらを含むファイルを見付ける検索である。これは Mac の Spotlight が行える検索のレベルでもある。

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

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

注*: Mac の mdfind には残念ながら、この機能は無い。欲しいなら、ユーザの手で、これを行うツールを作る事はできるであろう。
(3) 検索語が、ヒットしたファイルの中でどのように使用されているかを調べたい事がある。第2ステップの表示は Plan9 の plumb のメカニズムとの連携が考慮されているので、plumb を使って、素早く該当ファイルをエディタにロードし、該当行に辿り着ける**。

注**: Mac では難しいであろう。

Kirara1

Kirara1 の最新バージョンは ver.1.3 である。ver.1.2 から大きな変更を受けているが、基本的なアルゴリズムには変更はない。変更の理由は Kirara2 とプログラムパーツを共有することにあった。(2つのバージョンの同時サポートは大変である。)

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

kfind1 'snoop&htm|html'

とすると、「snoop」を含み、かつ、「htm」または「html」を含むディレクトリが表示される。また

kfind1 'snoop&htm*'

とすると、「snoop」を含み、かつ、「htm」で始まる語を含むディレクトリが表示される。
検索で使える演算子は、' '(空白) と '&' と '|' と '*' だけである。空白 ' ' は、ファイルの同じ行に含む事を探す場合に指示する注1。含まないを指示する記号はニーズが低いと思えるのでサポートされていない。(そのような必要があれば、grep を使えばよい)

注1: 実装上の理由から、これらの任意の組み合わせが許されている訳ではない。空白と '&' は同時には使えない。(検索の目標からして当然)
また '|' と '*' は grep の正規表現が使われている。そのためにこれらは、空白や '&' に比べて、論理演算子としての結合強度は高い。

さて、ディレクトリの中から、指定された語を含むファイルを探し、その行を表示するコマンドは 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/
...

である。この最初の行を実行すると、/lib/ の中のファイルから、snoop または htm または html を含む行を見付け、そのファイルのパスとともに表示される。

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

Kirara2

Kirara2 の最新バージョンは ver.2.0 である。
Kirara2 は Kirara1 と異なり、指定された語を含むファイルを探す。使える演算子は Kirara1 と同じである。例えば

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
...

のようなものが表示される。G2 は Kirara2 用のコマンドであり、その役割は G1 と同じであるが、引数が既にファイルになっている所が異なる。これらを実行すると、

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%

のように検索条件にマッチする行が、パス名、行番とともに表示される。この形式で出力しておけば、plumb の仕組みを使って、マウスだけで簡単にエディタの中にファイルをロードし、問題の行が選択状態になる。このへんの事情は Kirara1 の G1 でも同じである。なお「maia%」はプロンプトである。

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

kfind2 'snoop htm|html' |rc

を実行すればよい。

kfind2 'snoop htm|html'

だと(通常は)非常に多くの行が表示され、そのうち、実際に同じ行に含まれるのは極く僅かである。従って、1つ1つを個別に実行して確認するよりも、シェルである rc に渡して全てを一挙に実行させる方が効率が良い。このへんの事情は Kirara1 の G1 も同じである。

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

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

2013/11/05
2013/11/06
2013/11/07

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

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

rdline

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

注1: fopen() が使う標準バッファサイズは驚く程小さい。このサイズは /usr/include/stdio.h の中の BUFSIZ を見れば分かるが、Linux の場合には 8KB、Mac の場合には、たった1KBである。従って高速化を図る場合には関数 setvbuf() を使ってバッファサイズを大きくとる必要がある。詳しくは黒田久泰氏の解説(文献[8])を見よ。

関数 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 を入れ替える。もしもテーブルが

alice   bob
bob     carol
carol   alice

であれば、ファイルの左の文字列を右の文字列に入れ替え、その結果巡回置換が行われる。
実際の応用としては大きなテーブル*が想定されているので、効率の良いアルゴリズムが要求される。

注*: 僕のシステムの Kirara2 では10万行に及んでいる。
このようなツールは 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

grep は便利なツールであるが、フィールドの概念を持たないために、フィールドを指定して文字列のマッチングを調べる問題には適さない。ffm はフィールドを指定し、その文字列が、ファイルの中に一覧として与えられた文字列のどれかに一致した行を表示する。例えば patter_file に

alice
bob

と書かれていると、

ffm -f3 pattern_file target_file

で、target_file の中の第3フィールドに alice または bob があれば、その行を表示する。

この例では完全一致であるが、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 が生成するファイルは、比較的オーソドックスな内容になっており*、いわゆる辞書(ファイルの中の一意語の一覧ファイル)とリスト(語の位置情報を一意語ごとに整理し圧縮したファイル)から構成される。
また大きな辞書に対しては、辞書の目次を作成しておくと、効率良く語にアクセスできるので、そのための機能も持たせてある。

注*: 文献[12]にそうした技法が解説されている。可変バイトに関しては少し変形されている。

文献

[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~~ (dead link)

[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~~ (dead link)

[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~~ (dead link)

[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)

QUICK GUIDE

25 October 2015

Kirara