locatedb - ファイルのフォーマットと規約の説明 - Linux コマンド集 一覧表

locatedb - 前置圧縮されたファイル名データベース

このマニュアルページは GNU 版 locate で用いるファイル名データベースのフォーマットについて記述したものである。 ファイル名データベースには、最後に更新された時点において、 特定のディレクトリツリー下に存在していたファイルのリストが含まれている。

複数のデータベースを共存させることもできる。 環境変数やコマンドラインオプションを指定すれば、 ユーザーは locate に検索させるデータベースを選択することができる。 詳しくは locate (1L)を見よ。 システム管理者はデフォルトで用いられるデータベースの名前や、 データベースの更新頻度、 またデータベースに入れるディレクトリなどを選択することができる。 通常ファイル名データベースの更新は updatedb プログラムを定期的に実行させることによって行なう (夜間が良いだろう)。詳細は updatedb (1L)を見よ。

updatedb は frcode というプログラムを呼び出して ファイル名のリストを前置圧縮 (front compression) する。 これによってデータベースのサイズは 1/4 から 1/5 になる。 前置圧縮 (インクリメンタルエンコーディングとも呼ばれる) は以下のような動作をする。

データベースのエントリはソートされたリストからなっている (ユーザーの利便性のため、大文字小文字は区別していない)。 従って、各々のエントリは直前のエントリと最初の数文字が一致していることが多い。 それぞれのデータベースエントリには、 まずオフセット差分カウントという 1 バイトのデータが入っている。 これは現在のエントリと直前のエントリの共有部分の文字数から、 直前のエントリとそのもうひとつ前のエントリの共有文字数を引いたものである (従ってこの数値は負になることもある)。 カウントの後には共有部分の文字列以降の残りが ASCII 文字列で与えられる。 これはヌル文字で終端するとみなされる。

もしオフセット差分カウントがバイトデータで与えられる範囲 (+/-127) を越えた場合は、バイトデータ 0x80 がカウントに代入され、 2 バイトのワードデータがその後に続く。 このワードデータでは高位バイトが先に来る (ネットワークバイトオーダー)。

すべてのデータベースは、 ファイルエントリの最初に `LOCATE02' というダミーのエントリを持つ。 これは locate によってチェックされ、 このデータベースが正しいフォーマットであることを確認するために用いられる。 実際の検索においてはこのエントリは無視される。

複数のデータベースを連結することはできない。 最初の (ダミー) エントリを結合するデータベースから取り去れば良さそうだが、 これは正しくない。 なぜなら後に続くデータベースの最初のエントリにおける オフセット差分カウントは正しい値を取り得ないからである。

Unix 版 locate および find や、以前の GNU 版で用いられていた古いデータベースフォーマットも存在している。 この古い形式のデータベースを作成する場合には、 updatedb は bigram と code というプログラムを呼び出す。 古いフォーマットが上に述べた記述と異なる点を以下に示す。 それぞれのエントリがオフセット差分カウントのバイトデータで始まり ヌル文字で終わる代わりに、 0 から 28 までのバイトデータが -14 から 14 までのオフセット差分カウントとして用いられ、 これがエントリ区切りを兼ねることになる。 この範囲外の長いオフセット差分カウントを示すデータには、 0x80 ではなく 0x1e (30) が使われる。 長いカウントを保有するデータにはホストのバイトオーダが用いられ (これはネットワークバイトオーダと等しいとは限らない)、 またホストの integer のワードサイズ (4 バイトのことが多い) が用いられる。 またここにストアされるデータは実際の値から 14 を引いた値になる。 データベースの各エントリには終端バイトが無く、 30 以下の値を持つバイトデータが次のエントリの始まりであると認識される。

さらに古いデータベース形式では、 ダミーエントリの代わりに先頭に 256 バイトのテーブルがあり、 ファイルリストでもっとも頻繁に用いられている bigram が並べてある。 bigram とは隣接した二つのバイトデータをインデックス付けしたものである。 データベースに現われるバイトデータのうち、 最高位ビットがセットされているものは (残りの 7 ビットをインデックスとして) bigram テーブルのデータと置換される。 この bigram とオフセット差分カウントを用いることで、 データベースの大きさは新しいフォーマットより 20-25% 小さくなっている。 しかし 8 ビットクリーンでないという欠点を併せ持つ。 ファイル名に含まれるバイトデータのうち、 スペシャルコードに属するものは、 データベース中ではすべてクエスチョンマークで置き換えられる。 これは任意の一文字を表わすシェルのワイルドカードなので、 実際のファイル名に現われることはない。

frcode への入力が以下のようなものとする（ヌル文字は改行に置き換えて ある）:

/usr/src
/usr/src/cmd/aardvark.c
/usr/src/cmd/armadillo.c
/usr/tmp/zoo

直前のエントリとの最長一致部分の長さは:

0 /usr/src
8 /cmd/aardvark.c
14 rmadillo.c
5 tmp/zoo

frcode からの出力は、最後のヌル文字を改行に代え、カウントバイト を数字に代えると以下のようなものになる:

0 LOCATE02
0 /usr/src
8 /cmd/aardvark.c
6 rmadillo.c
-9 tmp/zoo



(6 = 14 - 8 また -9 = 5 - 14)

find (1L), locate (1L), updatedb (1L), xargs (1L)
Finding Files (on-line in Info, or printed)