索引ファイルを作る
Ｃ言語で開発を行っている時、簡単な索引ファイルを作りたいことがあります。 例えば、電話番号文字列から、レコード番号を求めたりする場合です。 今のトレンドでは、「ＳＱＬにクエリー投げて・・・」ということになるのでしょうが、 そこそこの速度がだせて、簡単に実装できるものを考えます。
キー検索とは？
２分岐検索や、バランス木などについては、多くのアルゴリズム本がありますので、そちらを参照してください。 ここでは、問題の解き方を掘り下げながら、新しいファイルフォーマットを考えます。
データがレコード形式で保存されていて、ある文字列をキーに、レコードを探したいというのは、よくある需要です。
他にも、特定条件に一致するレコードをを全部抽出したいという需要もありますが、ここでは、キー検索にまとを絞って考えます。
この問題を単純化すると、ある文字列と特定の数値を登録しておいて、その文字列から数値を求めるということになります。
それほど難しくなさそうなのですが、挿入、削除しても、高速に調べるようにするには、ちょっとした工夫が必要です。
簡単なアルゴリズムを考える
今回の目的は、文字列から数値を求めることです。
すると当然、数値をファイルのどこかに記録しておく必要があります。
そして、その「どこか」を高速に検索できればいいわけです。
これを簡単にするために、文字列そのもので分岐していく場所を決定することを考えます。
１バイトは８ビットですが、これを上位４ビットと下位４ビットに分けます。
すると、"0123"という文字列は、0x3,0x0,0x3,0x1,0x3,0x2,0x3,0x3という４ビットのデータ８個に分解できます。
この１つ１つで、分岐テーブルを作り、データを検索します。
４ビット単位なんて時代錯誤のように見えるかもしれませんが、これを８ビット単位で行うと、
分岐テーブルは２５６組必要になり、１組のデータが３２ビットですので、１０２４バイト必要になります。
これが文字列の各部分で確保されていくことになり、元データファイルに比べて、かなり大きいファイルになります。
実は、４ビットで行ってもファイルサイズは、かなり大きくなります。
でも、８ビットで行うよりはマシであろうということで、今回は４ビットで行うことにします。
#define U32 unsigned int
#define M_BR 0xfffffffc // 分岐テーブルマスク
#define M_ST 0x00000003 // ステータスマスク
#define S_NL 0 // データなし
#define S_BR 1 // 本情報は分岐テーブルへのオフセット
#define S_DT 2 // 本情報はデータへのオフセット
#define S_RS 3 // （予約）
typedef struct _abr // 分岐テーブル構造体
{
U32 up; // 上位へのリンク
U32 me; // 自分自身へのリンク
U32 br[16]; // １６分岐テーブル(4bit分)
} ABR;
こんな構造体を作ってみました。Ｕ３２は、符号なし３２ビットの整数です。
他のデータを含め、データは４バイトアラインで登録するものとします。
構造体の各メンバーは、ファイル上のオフセットを表しています（結果４ギガバイトまでのファイルしか扱えません）
すると、ファイルオフセットは、４バイトアラインされているため、下２ビットは必ず０になります。
この部分に、「分岐先の情報」を詰め込みます。
詰め込みを行うため、分岐先データオフセットを取り出すマスク(M_BR)と
分岐先情報を取り出すマスク(M_ST)を用意します。
詰め込むといっても、分岐先データがない（＝０）分岐した先も、分岐テーブル（＝１）分岐先はデータ（＝２）という３つの情報だけです。（なので２ビットで入ります）
typedef struct _det // データエントリ構造体
{
U32 len; // データ部長さ
int sval; // 戻り値
} DET;
分岐先がデータであった場合、上のような構造体をファイル上に設け、この部分に続いて、データそのものを４バイト単位に拡張して登録することにします。この構造体にあるsvalこそ、今回の答え（求めるべき値）を格納しておく場所です。
この構造（フォーマット）のよいところ悪いところ
このデータそのものを分岐先のアドレスにしようというアイデアが、よそにあるのかはわかりません。 データはそれぞれ内容が違うので、この分岐による木は、ある程度の形に成長するはずです。 もちろん、電話番号であれば、先頭はほとんど"0"ですので、最初の２節くらいは、１本しか分岐しないことになり、 効率が悪い部分がでるのも事実です。
ただ、全体の中央付近など、挿入するデータの大小関係について、一定のルールでバランスする木は、
木のバランスを維持するための動作を、挿入時点で行うものがほとんどであり、
これが、データ登録時の時間的コストを押し上げています。
今回の「木」はバランス調整を行いません。
行わなくても、「そこそこ」維持されるハズですし、
そもそもバランスとれるような（調整可能な）フォーマットになっていません。
バランスをとることなく、データが冗長になったとしても、ある程度の検索速度がでるのであれば、
プログラムコードは、小さくなって、見やすくなるハズです。
キー検索open/closeの実装
typedef struct _atree
{
int fd; // ファイルディスクプリタ
ABR ab; // 最終参照ABR
ABR ab2; // 新規作成用ABR
int pt; // 最終参照ABR内分岐P
DET de; // データエントリ実体
unsigned char bx[AR_MAXLEN]; // 検索文字列の比較用バッファ
} ATREE;
まず、このライブラリ全体を通して使う構造体を定義します。
１つの索引ファイルを扱うためには、この構造体が必要です。
fdは、索引ファイルをopenしたファイルディスクプリタで、
これを使ってread/writeします。
前述のABR（ブランチ用のテーブル）は、新規作成時（分割時）には、
２つ必要ですので、これも確保しておきます。
ptは、ＡＢＲ内のポインタというか、４ビットごと（１６通りごと）
で検索する際のポインタです。
deは、データエントリ構造体で、読み書き用に１つバッファとして確保しています。
bxは、検索文字列そのものの比較用バッファです。
//
// 検索ファイルをオープンする
//
int ar_open(ATREE* a, char *filename)
{
int i;
char buf[256];
memset(a,0x00,sizeof(ATREE)); // 構造体をクリア
a->fd = open(filename,O_RDWR | O_CREAT,0600);
if (a->fd < 0) return ARE_OPEN;
i = lseek(a->fd,0,SEEK_END);
if (i == 0) // 作成直後
{
memset(buf,0x00,256);
strcpy(buf,AR_SIGN); // 先頭２５６バイトに適当なサイン
write(a->fd,&buf,256);
memset(&(a->ab),0x00,sizeof(ABR)); // 分岐の大本を作成
a->ab.me = 256; // 自らのoffsetは２５６
write(a->fd,&(a->ab),sizeof(ABR));
}
return 0;
}
//
// 検索ファイルをクローズする
//
int ar_close(ATREE* a)
{
if (a->fd) close(a->fd);
a->fd = 0;
return 0;
}
まず、利用プログラム側で、ATREE構造体を確保し、そのアドレスと、索引ファイル名を指定して、
ar_open()を呼び出します。使用が終われば、ar_close()を呼び出します。
ファイル先頭２５６バイトは、これがAtreeファイルであることを確認するために、サインを記述していますが、
チェックしていません。チェックが必要な場合、lseekの戻り値が０のif文にelseをつけて、
先頭から256バイト読み込んで検証してください。
新規作成の場合、ファイルサイズが０となりますので、これを検出して、
先頭２５６バイトをサイン用に確保した直後に、検索開始ポイントとなる、
分岐テーブルを１つ確保します。
まだ、索引データは何も登録されていないので、全部０にしておき、
meというメンバーに、自らのファイルオフセットである２５６をセットします。
キーデータ登録部分の実装
//
// 登録する
// str:検索すべき文字列
// sval:登録すべき番号(0以上を渡す)
// 戻り値:0=成功,0未満=なんらかのエラー
//
int ar_regist(ATREE* a,unsigned char* str,int sval)
{
int btp,ofs,len,i,dst,st,pt2,dfs=0;
ofs = PROOT; // 最初の分岐テーブル位置(=256)を代入しておく
len = strlen(str) * 2 + 2; // 検索文字列の長さ (\0込み,4bit単位)
a->bx[0] = '\0'; // データ実体バッファをクリア
for(btp = 0;btp < len;btp++)
{
a->pt = str[btp/2]; // 今回の４ビットを取り出す
if ((btp%2) == 0) a->pt /= 16; // バイト内前半は上位４ビット
a->pt &= 0x0f; // ４ビットでマスク
lseek(a->fd,ofs,SEEK_SET); // offset位置にシークして
st = read(a->fd,&(a->ab),sizeof(ABR)); // ABR構造体を読み込む
if (st != sizeof(ABR)) return ARE_BROKEN; // 読めない=壊れている
dst = a->ab.br[a->pt] & M_ST; // ステータスを取り出す
ofs = a->ab.br[a->pt] & M_BR; // オフセットを取り出す
if (dst == S_NL) // データが存在しないのでエントリ登録
{
a->de.len = (strlen(str) + 4) & M_BR; // \0込み4バイトアライン
if (a->de.len >= AR_MAXLEN) return ARE_TOOLONG;
a->de.sval = sval; // sval登録
memset(a->bx,0x00,a->de.len); // データ実体バッファクリア
strcpy(a->bx,str); // 登録文字列をコピー
a->ab.br[a->pt] = lseek(a->fd,0,SEEK_END) | S_DT; // 分岐テーブル更新
write(a->fd,&(a->de),sizeof(DET)); // DET書き込み
write(a->fd,&(a->bx),a->de.len); // データ実体書き込み
lseek(a->fd,a->ab.me,SEEK_SET); // 分岐テーブル自身に移動
write(a->fd,&(a->ab),sizeof(ABR)); // 分岐テーブルを更新書き込み
return 0;
}
if (dst == S_DT) // データ一致 or データ衝突
{
// 衝突したデータとDETを読み込む
if (a->bx[0] == '\0') // 衝突は１候補と確定しているので、読み込んでない場合だけ
{
dfs = ofs; // DETのオフセットを控えておく
lseek(a->fd,ofs,SEEK_SET); // offset位置にシークして
st = read(a->fd,&(a->de),sizeof(DET)); // DET構造体を読み込む
if (st != sizeof(DET)) return ARE_BROKEN+1; // DETが読めなかった
if (a->de.len >= AR_MAXLEN) return ARE_BROKEN+2; // 登録されている長さがおかしい
st = read(a->fd,&(a->bx),a->de.len); // データ実体を読む
}
// データは完全に一致した = sval更新して終了
if (btp+1 == len)
{
a->de.sval = sval;
lseek(a->fd,dfs,SEEK_SET);
write(a->fd,&(a->de),sizeof(DET));
return 0;
}
// まだ完全に一致していないデータが衝突したので、新しい分岐テーブルを作成する
memset(&(a->ab2),0x00,sizeof(ABR)); // ab2をクリア
a->ab2.up = a->ab.me; // 新しい分岐テーブルの親は今読んだテーブル
a->ab2.me = lseek(a->fd,0,SEEK_END); // 新しい分岐テーブルはファイル終端
pt2 = a->bx[(btp+1)/2]; // 衝突したデータの分岐先を計算する
if (((btp+1)%2) == 0) pt2 /= 16; // 新しい分岐データ登録位置を求める
pt2 &= 0x0f;
a->ab2.br[pt2] = a->ab.br[a->pt]; // 新しい分岐データを登録
st = write(a->fd,&(a->ab2),sizeof(ABR)); // 書き込み
// 元の分岐テーブルを修正する
a->ab.br[a->pt] = S_BR | a->ab2.me; // 新分岐テーブルを指すようにする
lseek(a->fd,a->ab.me,SEEK_SET); // 自分の位置にシークして
write(a->fd,&(a->ab),sizeof(ABR)); // ABR構造体を更新する
ofs = a->ab.br[a->pt] & M_BR; // 次回に備えてオフセットを取り出す
}
}
return ARE_BROKEN+4;
}
さて、いよいよデータ登録です。 索引ファイルにデータを登録する処理としては、短い部類だとは思うのですが、 見通しは悪いですね。少しづつ解説します。
ofs = PROOT; // 最初の分岐テーブル位置(=256)を代入しておく
len = strlen(str) * 2 + 2; // 検索文字列の長さ (\0込み,4bit単位)
a->bx[0] = '\0'; // データ実体バッファをクリア
この部分で、検索に入る前段階の処理をしています。
変数ofsには、次に読み込むべき分岐テーブル（またはデータヘッダ）のファイル上オフセットが入ってることになっていますので、最初の分岐テーブル（検索対象データ１バイト目の上位４ビットに対応）のアドレスである256が代入されています。
また、４ビットごとに検索しますので、検索ループ回数は文字列長さの２倍（文字列長さには、文字列終端の0x00が入っていませんので、その分２を足しています）そしてデータ実体バッファをクリアして準備完了です。
(書きかけ）
キーデータ検索部分の実装
//
// 検索する
// str:検索すべき文字列
// 戻り値:0未満=何らかのエラー,0以上=登録番号
//
int ar_search(ATREE* a,unsigned char* str)
{
int btp,ofs,len,i,dst,st;
ofs = PROOT; // 最初の分岐テーブル位置を代入しておく
len = strlen(str) * 2 + 2; // 検索文字列の長さ (\0込み,4bit単位)
for(btp = 0;btp < len;btp++)
{
a->pt = str[btp/2]; // 今回の４ビットを取り出す
if ((btp%2) ==0) a->pt /= 16; // 上位4ビットが先
a->pt &= 0x0f;
lseek(a->fd,ofs,SEEK_SET); // offset位置にシークして
st = read(a->fd,&(a->ab),sizeof(ABR)); // ABR構造体を読み込む
if (st != sizeof(ABR)) return ARE_BROKEN; // 読めない=壊れている
dst = a->ab.br[a->pt] & M_ST; // ステータスを取り出す
ofs = a->ab.br[a->pt] & M_BR; // オフセットを取り出す
if (dst == S_NL) return ARE_NOTFOUND; // データが存在しないので未発見確定
if (ofs < PROOT) return ARE_BROKEN; // 壊れている
if (dst == S_DT) // データ候補を発見した
{
lseek(a->fd,ofs,SEEK_SET); // offset位置にシークして
st = read(a->fd,&(a->de),sizeof(DET)); // DET構造体を読み込む
if (st != sizeof(DET)) return ARE_BROKEN; // DETが読めなかった
if (a->de.len >= AR_MAXLEN) return ARE_BROKEN; // 登録されている長さがおかしい
st = read(a->fd,&(a->bx),a->de.len); // データ実体を読む
if (st != (int)a->de.len) return ARE_BROKEN; // データが読めなかった
if (strcmp(a->bx,str) != 0) return ARE_NOTFOUND; // データ不一致＝未発見
return a->de.sval; // 発見したので、svalを返す
}
}
return ARE_BROKEN;
}
検索は登録に比べれば簡単です。（書きかけ）
無作為研究所トップページに戻る