Succinct なトライをサポートする sumire-tries があるにもかかわらず，ここしばらく，大規模なトライ用のライブラリを開発しています．sumire-tries を何度も修正したのは，開発の途中でいろいろと気づいて，それらを反映させていたからです．いわゆるオマ…

…懲りることなく sumire-tries に変更を加えました．今回の変更では，select() 内のループによる計算を，テーブル参照に置き換えました．入力のパターンが少ないとき，全パターンあるいは一部パターンの計算結果を保存しておくことで高速化するという一般的…

sumire-tries の LoudsTrie に問題を見つけたため，修正しました．# 修正回数が多すぎますね，本当に…．申し訳ありません．修正版は既にアップロードしてあります． http://code.google.com/p/sumire-tries/ 今回の修正したのは，LoudsTrie の find_child() …

先日の修正（http://d.hatena.ne.jp/s-yata/20100117）に続いて，sumire-tries の select 関数を効率化しました．今回の変更点は，PopCount 関数の計算結果を有効利用するようにしたことです．※ このエントリにおいて，PopCount 関数とは，整数を引数として…

実験に用いた LoudsPlusTrie（LOUDS++）のソースコードにミスを発見しました．子ノードへの移動に用いる関数 child() において rank() を無駄に呼び出すという誤りにより，以前の実験結果（2009-10-29 - やた＠はてな日記, 2009-10-30 - やた＠はてな日記, 2…

LOUDS++ の実装にて，無駄に rank() を呼び出している箇所を見つけました．今日は眠たいので，明日にでも修正します．実験結果については，試した範囲では 5% くらい検索時間が短縮されるようです．こちらも修正版で計測しなします．