追加・削除をサポートしたレコード付きダブル配列の実装を公開
線形分類器のライブラリに同梱して公開した動的ダブル配列に削除機能と登録キー／値のダンプ機能を追加実装して，別パッケージとして公開した．標準的な静的ダブル配列のライブラリのインターフェスに加えて，追加，削除，登録キーのダンプを実装してある．自分では使わない共通接頭辞検索が派手にバグっていたのでついでに修正．
主な特徴は，
- 高速な追加: 整列したキーの追加は std::unordered_map*1の2倍速．ランダム順だと同程度．
- 高速な検索: ノードの探索に局所性があれば std::unordered_map の4倍速．なければ同程度．
- 高速な削除: 検索と同程度の時間で登録キーを削除可．
- 省メモリ: レコード込みで登録キーの3-4倍程度の消費メモリ．静的に構築したトライには負けるが std::unordered_map と同程度．
- 短いコード: ヘッダファイル一つで構成，500行程度．
- 4-byte の任意の型のレコードをネイティブサポート（BASE に埋め込み，高速）．
ダブル配列といえば静的に構築するライブラリが多いので，追加・削除まで実装したライブラリは少ないと思う．コンテナとしての利用を念頭に置いた速度重視，サイズ軽視の実装*2．
ダブル配列では文字単位で配列へのランダムアクセスが発生するため，キー長が長く，格納するキー数が極端に多い場合には std::unordered_map に比べて追加・検索速度が劣化しやすい．逆に言うと，キーのサイズが中規模程度，また大規模でも（テキストから頻出単語を列挙する場合など）トライ中のノードへのアクセスに局所性がある場合には std::unordered_map の代替としても十分使える．
キーを追加するときは（最大メモリ消費を抑えるため）空き要素無くきっちり詰めるようにしてあるが，削除するときは削除時間を重視して空いたスペースは放置する仕様になっている．追加・削除を連続して行うような状況だと削除で空いたスペースはどうせ使われるし*3，保存するトライのファイルサイズが問題になるような状況なら静的に再構築した方が良いはずなので，高機能な削除を実装するのはコストに見合わないと判断した．その代わりに，再構築を支援するため登録キー／値をダンプする関数を用意した．
二年以上前に書いたコードなので，別パッケージで公開するにあたって簡単にリファクタリングしたのだけど，ちょっといじっただけで簡単にトライが壊れるので難儀した．なんだか，薄氷の上を渡るような実装になっている．関数は用途ごとに綺麗に分かれているのだけど，共通して操作する（ダブル配列の）BASE や CHECK，ノードリンクやブロック単位で管理された空き要素などが複雑に相互依存していて，煩雑．削除機能は20行程度の追加で実装できたが，自分の書いたコードの理解に思いの外時間を取られた．厄介なデータ構造だ．頭の体操にはいいけど，当分触りたくないな．
[追記] 今回実装を見送った機能としては補完（予測検索）がある．ノードリンクを利用すれば高速な予測検索を実装できるが，現在の実装ではダブル配列を保存する際にノードリンクを破棄してしまうので，読み込んだダブル配列では予測検索（更新も）できない．登録キーのダンプ機能は当初は根ノードからの予測検索として実装されていたが，上記の理由から葉ノードから辿って登録キーを復元するというノードリンク不要な実装に変更した（その際，予測検索の実装も削除）．
予測検索については，返り値をどう返すかも悩ましい．共通接頭辞検索と同じにするなら，文字列を保存する領域を動的に確保しないといけないし（#include
[追記; 01/12] 電車の中で座れて時間があったので予測検索を実装してみた．結局，共通接頭辞検索のインタフェースを参考に，レコードのみ，レコードと接尾辞の長さ，レコードと接尾辞の長さとノード番号の3種類の形式で結果を受け取れるようにした．接尾辞が必要な場合は別途復元する関数を呼ぶ必要がある．最終確認に色々なデータセットで実験していたら，キーの追加時に無限ループに陥るバグがあることが分かり，gdb でデバッグ．案の定，リファクタリング時に変更した箇所（while 節の条件部）に原因があることが分かって凹んだ．
[追記; 01/13] Judy Array や HAT-trie の実装と比較してみた．HAT-trie の Nikolas Askitis さんのサイトにあるデータセットを使ってみたところ，データ構造自体のサイズは HAT-trie より大きく Judy Array と同じぐらい，検索速度は1.3-2.1倍程度高速だった．
[追記; 01/14] ついでに C で実装されたスプレー木*4とも比較してみた．データ構造自体のサイズは（レコードを保持しない）スプレー木の半分ぐらい（オーバーヘッドを入れたプロセスサイズで見てもやや少なめ）で挿入・検索共にスプレー木の2.7倍程度高速だった．STL の連想コンテナもそうだけど，キー単位でメモリ確保行う場合，16バイトアラインメントの影響が深刻．
[追記; 02/08] 論文にも載せられるぐらいしっかりしたベンチマークプログラムを書いて，実験した結果を公開した．ついでに，Google sparsehash, cpp-btree などとも比較したので後で追記する．テキストデータで Google densehash より挿入が遅いことを除いて，挿入も検索もメモリ使用量もダブル配列の方が全然良かった．特に，検索は3-10倍ぐらい速い．こちらは明日ぐらいに結果を公開しよう．
[追記; 02/24] ベンチマークに比較する実装をさらに色々追加した．
- 挿入速度は Judy Array が最速で，その後ダブル配列や std::unordered_map，ternary search tree などが続く．
- 検索速度はダブル配列が最速．HAT-trie や Judy Array が続く．その次は ternary search tree や splay tree が続く．
- 消費メモリは HAT-Trie が最も少ない．それに続くのが，Judy Array, ダブル配列．静的な簡潔データ構造の実装は，構築時にダブル配列の2,3倍のメモリが必要．なんだか残念に感じる．
ダブル配列で HAT trie 並の消費メモリを達成するにはTAIL を実装するか，衝突の効率的な回避を諦めて check を 1-byte にするしか無さそう．更新速度を Judy Array 並にするのだと TAIL を実装する方向かなぁ．
