ny23の日記

レコード付き動的ダブル配列の実装も公開

研究 |

以前 トライ（ダブル配列，簡潔データ構造）と STL コンテナ - ny23の日記で比較に使った自作のレコード付き動的ダブル配列 (dda) の実装も公開．以下の論文のアルゴリズムを実装したもの．

矢田晋, 田村雅浩, 森田和宏, 泓田正雄, 青江順一．ダブル配列による動的辞書の構成と評価, 情報処理学会第71回全国大会, 1-263-1-264頁, 2009年3月.

レコード付き動的ダブル配列 - ny23の日記から始まり， レコード付き動的ダブル配列 - ny23の日記, レコード付き動的ダブル配列 - ny23の日記, レコード付き動的ダブル配列 - ny23の日記 と二週間かかって書いた僅か360行の c++ ヘッダファイル．動的ダブル配列は上の分類器の学習手法で素性の重みの管理に使っているので，学習手法の実装に同梱した．std::tr1::unordered_map ベースのトライに比べると，分類器の学習速度・分類速度が2倍程度高速になる（ レコード付き動的ダブル配列 - ny23の日記, やっと出たのか - ny23の日記）． 動的ダブル配列を使って Wikipedia のテキスト処理を高速化 - ny23の日記 でも使っているけど，上の比較にもあるように，TAIL を「うまく」実装しないとサイズ面では静的ダブル配列に比べて明らかに不利（それでも葉に近づくに従い分岐数が減るような普通のキー集合なら追加順序によらず darts よりはうまく詰めてくれる）なので，静的な辞書を構築するのには明らかに不向き．キーの動的な追加（＋レコードの更新）の高速性を最優先した実装になっているので，トライをコンテナ的に使いたいときには有用．あと，int / uint / float など，4 bytes のデータなら（例外値を指定することで）何でもダブル配列内に保存できるようになっているのは便利かもしれない．

これで ソフトウェアの名前 - ny23の日記で書いてたプログラムは全部公開終了．この中では動的ダブル配列のコードが一番ましだと思う．やっていることは，最もややこしいので読むのは一番骨が折れるだろうけど．

ツイートする