大規模トライ用ライブラリの開発状況

かなり大きなキー集合を使って実験してみたところ，作業領域量（メモリ消費）に関する問題がいくつか見つかりました．

• なんとなく分かっている問題点
  • LOUDS や PLOUDS の構築において，トライ→トライ変換をおこなうとき，幅優先探索用の待ち行列（std::queue）が大きくなり，メモリ不足になるようです．
  • BP や DFUDS の構築において，findclose() 用の補助データ構造を作成するとき，メモリ消費が大きくなり，メモリ不足になるようです．

現状でも，それなりに大きなサイズのトライを構築できるのですが，開発目標が「32GB のメモリで Google n-gram コーパスをトライ化すること」なので，もう少し頑張ってみようと思います．

# 実のところ，LOUDS や LOUDS++ はトライ→トライ変換をしなくても，深さ別にビット列を保存しておくことで，インクリメンタルに構築できます．でも，頻度降順に並べ替える上手い方法が思いつかなかったので，トライの変換で対応するようにしました．

追記（2010-02-05）：BP や DFUDS についての問題は，使っていたライブラリの制限によるものでした．とりあえず，現状で分かっている問題点については，解決策が見つかりました．でも，まとまった時間が確保できないので，しばらくかかると思います．ぐぬぬ…．