yaskkserv とは?

C++ で書かれた、シンプル、高速で省メモリな独自形式の辞書 (変換にかかる時間は数秒です) を使用する SKK サーバです。 Linux/MacOSX/FreeBSD/OpenBSD/Cygwin で動作します。

バージョン 0.3.6 以降のライセンスは SKK と同じ GPL です。

current : yaskkserv-0.4.0.tar.bz2 (54060 bytes sha1sum:a38dfc1694c10b7040c0aa7351a2866399b81e4f) (2008年4月30日(水) 更新)

何かありましたら へのメイルや 電言板 まで、お気軽にどうぞ。 2ch UNIX 板の「SKK専用スレッド Part7」 も見てます。

SKK ML 「server completion の仕様の欠陥」で提案された 1 - 4 案について

yaskkserv では以下のような実装になっています。

News ログ

注意が必要な点

gcc3.3 系 + メモリが少ない環境でコンパイラのバグを踏む問題について

gcc3.3 系 + メモリが少ない環境で、コンパイラのバグを踏むためコンパイルできないという問題が確認されています。作者の環境ではメモリが 256M の機械でバグを踏みます。 512M の機械では問題ありません。この問題はオプティマイズレベルが高いと発生するようです。

yaskkserv-0.3.3 以降では configure でコンパイラバグを踏みそうな環境を検知し、自動的にオプティマイズレベルを下げます。

yaskkserv-0.3.3 より前のバージョンでは

• gcc4 系を使う
• メモリの多い機械でビルドする
• configure 内の -O4 を -O1 に置換する

といった対処をする必要があります。

ビルドについて

• GCC / GNU Make / Perl などが必要
• GCC は 3.3 以上が必要

その他

• 辞書の自動再読み込みはタイミングによって失敗することがある (更新チェック/再読み込みはサーバにアクセスがあった瞬間です。このとき辞書の状態が中途半端だと失敗することになります。)

なぜいまさら SKK サーバを書くの?

わざわざ書きおこしたのは

• 単に興味があった
• 組み込みを意識したものが欲しかった

といった理由からです。

特徴

• 辞書は同梱のツール yaskkserv_make_dictionary で独自形式に変換したものを使用
• データベースライブラリやスクリプト言語を必要としないシンプルな構成 (大抵の環境で ./configure && make 一発)
• それなりに省メモリ (作者の環境では SKK に附属の skkserv より大きく見える)
• それなりに高速 (最速クラスの cdb ものよりは遅い)
• 探索コアは組み込み (数十 kB 程度の RAM + 辞書ストレージといった構成) を意識した仕様
• 複数辞書に対応 (yaskkserv_normal または yaskkserv_hairy)
• server completion に対応 (yaskkserv_hairy のみ)
• 辞書の自動再読み込みに対応 (タイミングによっては不完全)
• 最近の元気ある動きに対応 (できるといいなぁ)

用途によって、いくつかのサーバを用意しています。

yaskkserv_simple

もっともシンプルなサーバ (skkserv から辞書再読み込み機能を除いたもの相当)

yaskkserv_normal

一般的なサーバ (skkserv + 複数辞書 + 辞書の自動再読み込み相当)

yaskkserv_hairy

なんでもありサーバになる予定 (yaskkserv_normal + server completion)

以下のような特徴があります。

• 見出し先頭の 1 文字により「通常エントリ」と「特殊エントリ」に分けて扱う
• 見出しとインデックスデータ中のひらがなは「ひらがなエンコード」でコンパクトに
• 「ブロック」という単位で管理され (セクタリードと相性が良くなるよう) アラインメントも可能
• エントリサイズは yaskkserv_make_dictionary による変換時に確定し、ブロックサイズとしてサーバ起動時に把握されるため安全

探索コアで必要なメモリサイズ

使用した辞書は 2005年10月12日(水) あたりの SKK-JISYO.total+zipcode です。(482220 エントリ 15930937 bytes)

「最小サイズ」はインデックスデータとブロックリードバッファを同じ領域に置くことでメモリを節約した場合のサイズです。(この場合は当然、インデックスデータを毎回ストレージから RAM へ読み込む必要があります。)

現在の実装ではインデックスデータとブロックリードバッファを別に確保するので、「合計サイズ」だけメモリを消費します。

「--short-block」は辞書サイズを大きくすることでインデックスデータを小さくする形式です。

辞書サイズ

SKK-JISYO.total+zipcode (482220 エントリ 15930937 bytes) をコンバートした場合のサイズです。

「ひらがなエンコード」について

文字列がひらがなまたは ASCII だけで構成されていれば下位バイトのみ使用し、それ以外の文字が存在する場合は先頭に \x1 を追加するエンコード形式です。

ex.)
ああああ → \xa2\xa2\xa2\xa2 (下位バイトのみ)
ひらがな漢字 → \x1ひらがな漢字 (先頭に \x1)
LIFEFORCE → LIFEFORCE (ASCII のみ)
ぐらでぃうす2 → \xb0\xe9\xc7\xa3\xa6\xb9\x32 (下位バイト + ASCII)
沙羅曼蛇 → \x1沙羅曼蛇 (先頭に \x1)

見出しやインデックスデータ中の文字列でこのエンコード形式を採用しています。

「インデックスデータ」について

インデックスデータは一般に RAM 上へ置かれます。ここでストレージ上にある辞書の読み込むべきブロックが確定するため、ストレージへのアクセスは 1 度の探索あたり必ず 1 回以下 (運が良ければキャッシングされ 0 回) になります。

インデックスデータをストレージに置いておき、ブロックリードバッファと同じ領域に読み込んでから使うこともできます。この場合メモリは節約できますが、ストレージへのアクセスが 1 度の探索あたり必ず 2 回 (インデックスデータの読み込み + 辞書のブロック読み込み) になります。

インデックスデータは以下の要素から構成されます。 (詳しくはソースコード skk_jisyo.hpp のコメントをごらんください。)

• struct FixedArray の固定長配列 (256 個)
• struct Block の可変長配列
• 文字列格納領域

struct FixedArray は「通常エントリ」の探索に使用します。「ひらがなエンコード」された先頭 1 バイトが添字となります。「特殊エントリ」は struct FixedArray を参照せず、直接ブロックを探索します。

struct FixedArray には struct Block の開始インデックス、長さとブロック終端文字列へのオフセットが含まれています。ここで指定されたどこかのブロックに探索文字列は存在することになります。どのブロックに含まれるかは、ブロック終端文字列と探索文字列を比較することで判定します。

                                            文字列を比較して
                        +---------+         「探索文字列」が「終端文字列」以下ならば
                        |Block N-1|         そのブロックに存在
+----------+   index=N  +---------+         探索文字列が "あい" ならば Block N+1 に存在
|FixedArray|--+-------->|Block N  |
+----------+  |    ^    +---------+---"ああああ" Block N の 終端文字列
              |    |    |Block N+1|
              |  len=4  +---------+---"あいいいいい" Block N+1 の 終端文字列
              |    |    |Block N+2|
              |    v    +---------+---"あかかかか" Block N+2 の 終端文字列
              +-------> |Block N+3|
                        +---------+---"あさささ" Block N+3 の 終端文字列
                        |Block N+4|
特殊エントリ開始        +---------+
ブロック -------------> |Block N+5|
index = N+5             +---------+
                        |Block N+6|
                        +---------+

struct Block の個数と文字列格納領域は 2005年10月12日(水) あたりの SKK-JISYO.total+zipcode の値です。

「ブロック」について

ブロックサイズが大きいとインデックスデータサイズは小さくなりますが、ブロックの読み込みに時間がかかり、ブロックリードバッファ内での探索時間が少し増えます。

ブロックサイズが小さいとインデックスデータサイズは大きくなりますが、ブロックの読み込み時間とブロックリードバッファ内での探索時間は減ります。しかし同一の struct FixedArray に含まれる struct Block が増え、ここでの探索時間が少し増えます。

yaskkserv は以下の環境で動作確認しています。

基本戦略

• シンプルな構造で、ベンチマーク性能は無視。おいしい落としどころを狙う。
• コンバータなどで使う class SkkJisyo は cstdio/mmap などの潤沢なリソースを要求。
• サーバで使う class SkkDictionary は C++ の (C / assembler への置き換えも簡単な) コードのみ。

めも

• 組み込みではブロックごとに圧縮しておくと良いかも (でも、思ったより縮まないなぁ)
• ブロックにヘッダを付ければサーチの高速化が可能 (だが、そこまですべき?)
• EUC 以外の文字コードが扱えると便利かもしれない (けど面倒だなぁ)
• ひらがなエンコードは "ー" を特殊扱いにすればもうちょい縮むんだけど、主目的はインデックスデータ側なので、あまり意味は無さげだなぁ
• yaskkserv では SKK の辞書を jisyo 、 yaskkserv 専用の辞書を dictionary と呼ぶ。 (skkserv.c だと jisho だったりするのよね。)
• yaskkserv では (「見出し」" "(半角スペース) の直後にある '/' からはじまり '/' で終わる) candidate の固まりを「変換文字列」と呼ぶ。

辞書変換時間

コマンド yaskkserv_make_dictionary の実行にかかる時間を time で適当に計測してみました。

使用した辞書は 2005年10月12日(水) あたりの SKK-JISYO.total+zipcode です。(482220 エントリ 15930937 bytes)

"0"

サーバへコネクションを切断するよう要求します。

"1eee "

「見出し」 eee に対する「変換文字列」を要求します。 " " (スペース)でターミネートされていることに注意が必要です。

サーバから返される「変換文字列」は / で区切られた "1/foo/bar/baz/\n" のような形式です。

サーバから返される文字列の末尾には "\n" が必要なことに注意が必要です。

「見出し」が存在しない場合は入力の先頭の "1" を "4" に変換したものをそのまま返します。 (実はプロトコル的には 4 で始まる文字列ならば何でも良いらしいですが、一部のクライアントで問題が出るとのことです。)

"2"

サーバへ「バージョンナンバー」を要求します。

サーバから返される「バージョンナンバー」は "A.B " のような形式です。 " " (スペース)でターミネートされていることに注意が必要です。

skkserv/skkserv.c に A はメジャーバージョン B はマイナーバージョンのような記述がありますが、 skkserv 自体 "A.B.C " のような形式で返していますし、他のサーバではサーバ文字列を返しているものもあるので、バージョンナンバーというよりバージョン情報と表現すべきなのかもしれません。

"3"

サーバへ「サーバのホスト名と IP アドレスのリスト」を要求します。

サーバから返される「サーバのホスト名と IP アドレスのリスト」は "hostname:addr:[addr...:] " のような形式です。 " " (スペース)でターミネートされていることに注意が必要です。

yaskkserv では未実装です。(ダミー文字列が返されます。)

"4eee "

「見出し」 eee で始まる見出しを要求します。" " (スペース)でターミネートされていることに注意が必要です。

サーバから返される「見出し」は / で区切られた "1/foo/bar/baz/\n" のような形式です。

サーバから返される文字列の末尾には "\n" が必要なことに注意が必要です。

これは新しいプロトコルで、今のところきちんとした定義は無いようです。

あいまいな点としては

• 「送りなし」エントリと「abbrev」エントリのみ返され、「送りあり」エントリは一般に返されない?
• 複数の辞書を探索する場合、同じ「見出し」が複数存在することがあるけれど、重複チェックは必要ないのかしら?
• 出現順は?
• 「見出し」が存在しない場合は入力をそのまま返す?
• サーバから返される「見出し」に完全一致の (要求した) 「見出し」を含める?

といったものが挙げられます。

yaskkserv では

• 返す「見出し」は「送りなし」と「abbrev」のみ
• 「見出し」の重複チェックあり
• 「見出し」の出現順は内部的な出現順 (内部的なソート順 + dictionary 指定順)
• 「見出し」が存在しない場合は入力をそのまま返す
• サーバから返される「見出し」に完全一致の「見出し」を含める

といった実装になっています。

上記以外の不正な入力について

skkserv/skkserv.c ではデバッグモード時にエラーメッセージをコンソールへ出力するだけのようです。

yaskkserv-0.3.0 以降では "0\n" を返します。 yaskkserv-0.3.0 より前は何も返しません。

SKK に関するメモ

• 2ch UNIX 板の SKK専用スレッド Part7
• SKK Openlab
• SKK 辞書 Wiki SKK 辞書 Wiki 内の SKK 用語集

戻る