ダブル配列の資料（更新に関する内容）
ダブル配列の資料にスターが付いているようなので，関連する資料も公開することにしました．今回の資料は，情報処理学会第 71 回全国大会で使用したスライドで，ダブル配列の更新に関する内容となっています．
- ダブル配列による動的辞書の構成と評価
提案手法自体は，従来手法における最悪ケースに対処するための手法なので，使いどころが難しいと思います．でも，どういう手法があるのかを見る程度には役立つのではないでしょうか．
実験結果については，従来手法でうまくいかない状況を想定した内容になっています．同じコーパス（Google n-gram の 1-gram）を使っても，辞書順に登録する場合，これほど大きな差はありません．TAIL を用いない場合も，試していませんが，これほどの差は発生しないはずです．
ダブル配列は更新を苦手とするデータ構造ですが，std::set
さらに細かい話として，http://code.google.com/p/darts-clone/wiki/Evaluation では TAIL を使わない方が前方一致検索が高速になっているものの，動的に構築した場合，この限りではないかもしれません．キーの追加で衝突が起きる度に要素が移動されるので，キャッシュは徐々に効きにくくなります．TAIL を用いる場合，少なくとも，サフィックスはメモリ上に連続して配置されます．
