データ構造

よく使うデータ構造の種類

Double Array

トライの一種。

LOUDS

• Double Array に比べてサイズが小さくなる。
• 速度は Double Array のほうが速い
• 動的更新可能な実装がない
  • 提案はされている

具体的な実装

TX

LOUDSの実装。

RX

LOUDSの実装。

RX は c string を利用するので、任意のバイナリを取り扱うことはできない。RBX は任意のバイナリを利用できるが、prefix search ができない。

MARISA

http://www.s-yata.jp/marisa-trie/docs/readme.ja.html

libmarisa により構築される辞書の書式はアーキテクチャに依存します．Little Endian な環境で構築した辞書は，Big Endian な環境では使えません．あらためて構築しなおす必要があります．また，Little Endian 形式の辞書は 32/64-bit 環境における互換性があるのに対し，Big Endian 形式の辞書は 32/64-bit 環境における互換性がありません．

高速で使いやすい。非常にコンパクトなファイルになる。

現在の Akaza では MARISA をメインで利用している。

daachorse

速いらしい。更新は遅いっぽい、システム辞書などにはよいかもしれない。

Key value store

sled

sled は pure rust のライブラリであり、よくできている。 一方で、普通にDBライブラリなので、複数ファイルに書いてしまう。 システム辞書の配布用途では、1ファイルのほうが管理がしやすい。

ユーザー言語モデルは sled でも良さそう。

cdb

かな漢字辞書については cdb などでも良さそうだが、システム辞書を cdb にするとやっぱりでかくなりすぎる。

ベンチマーク

TBD