What's fskkserv

skkserv[1] の代替品です。

SKK の辞書に含まれる見出し語には以下のような性質があります。

これらの性質を利用して索引の構造を工夫すると、外部のデータベースライブ ラリに頼らずとも高速な検索が実現できそうです。fskkserv では、索引に二 進トライの一種である、パトリシア木を採用することで高速化を図っています。

特長

ダメなところ

How to use

1. make します。コンパイルには Objective Caml[2] が必要です。

  $ make

native code を生成するには "make opt" とします。

2. 辞書ファイルから索引を生成します。

  $ ./mkpat /usr/local/share/skk/SKK-JISYO.M

カレントディレクトリに SKK-JISYO.M.pat というファイルができるはずです。

"-c" オプションを付けて起動すると、圧縮した索引を出力します。 この場合、生成される索引のファイル名は、SKK-JISYO.M.pacb となります。

3. tcpserver や nc を使って、サーバとして起動します。

  $ tcpserver 127.0.0.1 1178 \
        ./fskkserver /usr/local/share/skk/SKK-JISYO.M ./SKK-JISYO.M.pat

Benchmark

ckskkserv[3] を用い、SKK-JISYO.L の全見出し語を変換し、一単語あたりの 平均所要時間を求めました。実験は各 skkserv 毎に三回行いました。

最初の一単語の検索には初期化処理が含まれるので、ckskkserv を改造して、 二回目以降の単語変換のみ計算に入れるようにしてあります。

実行環境は以下の通りです：

1. fskkserv

  185.678090, 188.390796, 180.536258

2. rskkserv

  1582.044346, 1566.993461, 1546.381771

3. 改造版 skksearch (Berkeley DB 4.1 対応)

Algorithm

1. キーコードの割り当て

見出し語を一文字ずつ切り分け、リストに収めます。 次に、以下のルールで各文字に 1 から 283 までの数値(キーコード)を割当てます。

加えて、見出し語文字列の終端を表すために 0 をリストの末尾に加えます。

2. ハフマン符号化による圧縮

辞書中の全見出し語における文字の出現頻度から、ハフマン符号化を行い、 1. で求めたリストを可変長のビット列に変換します。

3. パトリシア木の構築

2. で求めたビット列をキーに、元の辞書ファイル中の位置との対応をパトリ シア木に挿入します。

4. 索引の保存

以下の二種類の対応表をシリアライズしてファイルに保存します。

License

GPL2 or later.

Authors

Daiki Ueno <ueno@unixuser.org>

Footnotes:

Converted by allout-html.el.