LOUDS関連メモ

LOUDS関連で調べたものをメモしておく。

各種操作を高速に保ったままでデータサイズを情報理論的な下限近くまで圧縮できるデータ構造。
基本は簡潔ベクトルで、疎なベクトルをビット列と密なベクトルに変換し、xビット目までの0または1の数を返すrank()と、x番目の0、または1の位置を返すselect()で操作する。

簡潔データ構造の木構造版(簡潔木とも呼ばれる)のひとつ。簡潔木には他にBP(Balanced Parentheses)やDFUDS(Depth First Unary Degree Sequence)というものもある。

darts等に比べて作業領域が1/4〜1/10

tx-trieの後継。圧縮率が上がっている

ux::Mapのサンプルコード
https://gist.github.com/1476764

ux-trieよりも圧縮率に優れた実装。多層TRIEやパトリシアTRIEの併用で圧縮率と速度の向上を図っている。

ベンチマークを見るかぎり、速度・圧縮率でmarisa-trieが優秀な模様。

WebService::Blog->new( user => ’hide_o_55’ )