Yusuke TABATA
yusuk****@w5*****
2005年 11月 20日 (日) 02:05:33 JST
田畑です。 変換エンジンのデータの扱いについてちょっと書いてみました。 -- いくつかの変換エンジンの構成を次のように分類できると思います。 (1)入力された文字列を解析する部分 (2)(1)の処理で必要なデータを辞書などから収集する部分 この文書では(2)の部分について扱います。 この手の議論をする場合、基本的には既存のコードを再利用することを 考えるべきです。特に変換エンジンの場合はデータの収集および上位層の 開発にリソースを割きたいところですので重要なポイントですが、往々に して自分で作成することが必要になってしまいます。 車輪の最発明は変換エンジンだけに限ったものではないですが、とりあえず 使えそうな車輪を列挙してみます。 1. SQLサーバ 2. BerkeleyDBの類 3. 専用ライブラリ 4. 変則的な技 5. まとめ 1. SQLサーバ まず、データベースと言えばSQLサーバがあります。特にPostgreSQLや MySQLは参考資料やユーザ数も多く、使い勝手に問題があるというような 話を聞くことも無さそうです。実際にsumibiはMySQLを使って実装され、 実用的な機能と性能を実現しています。 しかし、anthyのようにデスクトップのユーザがインストールして使う ことを前提としている場合、SQLサーバを動かすことを要求するのは困難 なように思います。 これに対する別解としては各ユーザの権限で動かすことのできるsqliteを 使うという選択肢もあります。sqliteはソースコードを自分のソフトに 組み込んで使うことを想定して作ってあるため、別途インストールを要求 ようにすることが可能です。 変換エンジンでSQLサーバを使わない理由としては、上記のような インストールや運用の問題の他に、速度の問題、ディスクやメモリ効率の 問題があるのですが、忘れてはならない理由として何人かの変換エンジン 書きはSQLサーバのことをよく知らない、あるいはSQLサーバのことを 知っている人はあまり変換エンジンを書こうと思わないという状況が あるように思います。 もしかすると、現行のSQLサーバでは文節区切りまで行なう変換エンジンを 作るのに必要な性能は出ないかもしれないのですが、私はそれを判断できる 経験を持ってないです。 2. BerkeleyDBの類 SQLサーバを避けるとすると、BerkeleyDBの類を使うのが便利かもしれません。 これも色々なバリアントがあります。選択する際の重要な特性としては (a)普通にインストールされているか？ 変換エンジンのためだけにユーザに珍しいものをインストールさせるのは 辛いところです。この点では純正のdbもしくはgdbmが選択肢になると 思います。 (b)データの書き込みを許すかどうか？ 一般に、DBの構築時に入れたデータに追加することを許さないものの方が 検索が高速であったり、ファイルサイズの無駄が小さいものになります。 一部のSKKサーバで使われているcdbがこれにあたると思います。 (c)複数プロセスからのアクセスを許すかどうか？ 変換エンジンの個人辞書などに使う場合、変換エンジンのインスタンス 同士、あるいは辞書ツールとの同時アクセスがあるので、それを考慮した ものが望ましいです。 sambaの関連プロダクトであるtdbがこれをサポートしています。tdbは 非常にコンパクトなので、その点でもお勧めです。 #LGPLかBSDライセンスのtdbがあれば便利ですが... 上記の他にqdbmが高速だといった話も聞いています。 3. 専用ライブラリ テキスト処理の専用のライブラリとして、次のようなものが有名です。 Suffix Arrayを使ったsary http://sary.sourceforge.net/ Double Array Trieを使ったDarts、manaで使われています。 http://www.chasen.org/~taku/software/darts/ 同じくdatrie http://linux.thai.net/~thep/datrie/datrie.html 内容についてはそれぞれのページに詳しく説明があるので、それを 参照してください。単にキーから文字列を得るだけではなく、キーの 文字列を含む文字列を探したり、キーの文字列の先頭から共通部分を 持つ文字列を探すということができます。 ただし、実際に使おうとすると生成されるファイルサイズが大きい とか微妙な不満が出てきます。 anthyの場合、単語の検索部分では(1)hash値で単語の有無を判断する→ (2)バイナリサーチで辞書ファイル中のだいたいの場所を探す→ (3)リニアサーチで単語の情報の場所を探す という手の込んだ方法で速度とファイルサイズの両立を図っています。 もし、今からanthyを書き直すとしたら先頭の数文字をDouble Array Trie に入れて後ろの文字列をリニアサーチするようにするのかなと考えています。 このようなアルゴリズムのコードをライブラリとして出せたら、今から 変換エンジンを書く人にとって便利だとは思うのですが、手を動かせてません。 4. 変則的な技 gettextを使ったSKKサーバ http://www.kmc.gr.jp/~tak/sources/misc.html#gtskkserv この手のハックを思いつく柔軟性と実際にやってしまうパワーは重要だと 思います。実際の性能もそんなに悪くないようです。 gettextへ依存してはいますが「日本語使いたいならgettextぐらい入れとけ」と 言ってしまうのは間違ってはいないと思います。 #ちなみにgtskkservの作者はanthyの初期の共同開発者です 5. まとめ 結局、既存のコードを利用せずに手書きしてしまうことも多いのですが、 時代によって変化するトレードオフを見て、時には奇策を使い、開発者& ユーザ共に負担の低いソフトを作っていければ良いのではないかと思います。 -- -- CHAOS AND CHANCE! Yusuke TABATA
