Double-Array Construction

ダブル配列は動的に更新できるデータ構造として提案されました． しかし，キーを追加するとき，衝突（ Collision ） という厄介な問題が発生します． そこでまず，キーの追加や削除を考慮せず， 登録するキーがすべて分かっている状態からの構築方法について説明します．

更新が遅いと評判のダブル配列ですが， 登録するキーの数が 10 万件くらいであれば， 1 秒以内で構築することができます． ただし，なぜか評価実験でよく使われている郵便番号のように， 網羅性の高いキー集合を対象とする場合は時間がかかります． なお，網羅性が高いという表現は，分岐数（節から出る枝の数）の平均が 大きいことを意味しています．

ダブル配列を構築する前に，マルチキークイックソート （ Multikey Quicksort ） などを使用してキー集合を整列します． マルチキークイックソートは基数ソートとクイックソートを合成したような手法で， 大量の文字列を高速に整列することができます． 論文（英語）が Fast Algorithms for Sorting and Searching Strings から手に入りますし， 検索エンジンで探せば日本語の解説も見つかりますので， 好きな資料を参考にしてみてください． 整列は構築時だけの処理ですから， 単純なクイックソートを利用しても問題ないと思います．

ダブル配列の構築における最初の手順は， 根のインデックス（ 0 or 1 ）と BASE の最小値を決定して， 文字から整数への変換テーブルを作成することです． 今回の説明では，根のインデックスを 0， BASE の最小値を 1 にして，文字については使用する文字コードをそのまま使うことにします． BASE の最小値を 1 にする理由は，あらゆる節 x と文字 c の組み合わせに対して， BC[x].BASE + CODE[c] が根と一致しないようにするためです．

なお，マルチバイト文字については， 同じ節からの遷移先が広範囲に配置されることを防ぐため， 1byte 毎に遷移を定義します． 直接 Unicode などに対して遷移を定義すると， 分岐がとても多くなる上に遷移先が広範囲に散らばりますので， 隙間なく要素を配置することはほぼ不可能になります． 節の数を減らすことができたとしても， 未使用要素がそれ以上に増えてしまっては意味がありませんから， やめておいた方がよいでしょう．

根の初期化については，BASE[0] = 1, CHECK[0] = 0 とすれば完了です．

根を初期化した後，他の節を深さ優先に配置していけば， ダブル配列の構築は終了となります．

まず，根の子を配置するために， キー集合の一文字目を参照します． キー集合は整列されているので，先頭の文字を順に参照していけば， 文字の種類と各文字の出現回数が求まります． キー集合が三つの文字列 "bird", "bison", "cat" により構成されている場合，以下に示すように， 文字 'b' が二回， 文字 'c' が一回となります．

図 1 ： "bird", "bison", "cat" の一文字目

次に，取得した文字の集合を用いて，子の節番号を決定します． 各節がダブル配列の未使用要素と対応するように， 根の BASE を設定しましょう． カウンタ base を BASE の最小値 1 で初期化し， 文字の集合に含まれているすべての文字 c に対して base + c が未使用要素になるまで， base をインクリメントしていきます． 条件を満たした base を根の BASE として採用すれば，子の節番号が決定します．

後は，配置された節を新しい根とみなして同様の処理を適用することにより， すべての節が再帰的に配置されていきます． 節の配置順序を以下に示します．

図 2 ： 静的なダブル配列の構築における節の配置順序

図 2 の例では， { 'b', 'c' }, { 'i' }, { 'r', 's' }, { 'd' }, { '#' }, { 'o' }, { 'n' }, { '#' }, { 'a' }, { 't' }, { '#' } という順に文字の集合が取り出されて，対応する節が配置されていきます． 文字コードとして ASCII を利用した場合， 以下のようなダブル配列が構築されることになります．

図 3 ： 静的に構築されたダブル配列（作成中）

静的にダブル配列を構築するとき，節を深さ優先に配置していけば， 親子関係にある節が近くに配置されることになります． 一方，幅優先に配置した場合，根の付近にある節は集中的に配置されますが， 親子関係にある節が同じキャッシュラインに配置される可能性が極めて低くなります． 実験では，深さ優先に節を配置したダブル配列の方が 高速な検索を実現できるという結果が得られています． ただし，動作環境や対象とする問題によっては，異なる結果になるかもしれません．

MP ダブル配列を構築する場合， 対応するキーが一つに絞り込まれた時点で， キーの後半部分を文字列として配列 TAIL に保存します．

To be continued．