データ構造

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

Double Array

トライの一種。

LOUDS

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

具体的な実装

TX

LOUDSの実装。

RX

LOUDSの実装。

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 をメインで利用している。

ベンチマーク

TBD