Darts のデータ構造

darts-clone

Darts はダブル配列を構築するためのライブラリであり，ダブル配列はトライという木構造を表現するためのデータ構造です．以下のサイトに解説があるので，ここでは概要のみを述べます．

トライ (Trie)

トライは文字列を格納できる木構造です．木を構成するノードに文字列を関連付ける二分探索木や B-木とは異なり，トライでは文字をノード（あるいは枝）に関連付けます．トライを根から葉へと辿り，関連付けられている文字（ラベル）を後ろにつなげていけば文字列を復元できるようになっています．

例えば，``ABC'' という文字列を検索する場合，

  1. 根の直下にラベル `A' を持つノードがあれば，そのノードに移動する．
  2. 現在のノード直下にラベル `B' を持つノードがあれば，そのノードに移動する．
  3. 同様に，ラベル `C' を持つノードに移動する．

という手順で ``ABC'' がトライに登録されているかどうかを確認します．

文字列を登録するとき，何らかのデータを関連付ける必要があれば，その文字列の終端と対応するノードに関連付けるようにします．このとき，各ノードが文字列の終端と対応しているかどうかを判別できるようにするため，各ノードに終端フラグを持たせたり，各文字列に終端文字を付け加えたりします．文字列の終端と対応するノードは，終端ノードなどと呼びます．このとき，葉ノードは終端ノードになりますが，終端ノードが葉ノードであるとは限りません．Darts では，文字列の終端として使われることの多い `\0' を終端文字として用いています．

ダブル配列

ダブル配列は，トライを表現するデータ構造の一種です．トライをシンプルな配列として表現するデータ構造で，検索がとても高速なことで知られています．検索が高速な理由は，ラベルを条件として子ノードを探すとき，線形探索や二分探索を必要とせず，時間計算量 O(1) で移動先を簡単に見つけることができるからです．平均時間計算量 O(1) の探索を実現するデータ構造としてはハッシュ表もありますが，トライの実装においては，最悪時間計算量を O(1) にできる上に 100% 近い充填率を維持できるという特徴を持つダブル配列の方が優秀なデータ構造といえるでしょう．

ダブル配列は，BASE, CHECK という配列に加えて，TAIL という配列を用いるデータ構造として提案されています．BASE, CHECK の要素は，トライのノードと対応します．TAIL の要素もトライのノードと対応しますが，トライの葉から根に向かって，最初の分岐が見つかるまでのノードと対応します．TAIL を用いる目的は，根から遠くにあるノードを文字で置き換え，辞書のサイズを抑えることにあります．単純な実装では，BASE, CHECK の要素を各 4 bytes で表現し，TAIL の要素を 1 byte で表現することになります．

Darts では，検索時間，実装の難易度，登録する文字列（キー）と値（レコード）の関連付けなどを考慮した結果だと思いますが，TAIL を使用していません．初期に提案されたダブル配列と比べると，以下のような違いがあります．

  • Darts では，TAIL を使用せず，すべてのノードを BASE, CHECK により表現しているため，
    • 辞書のサイズが大きくなるものの，
    • 検索時間が短くなり，
    • 整数をレコードとして終端ノードに格納できるようになっています．

初期のダブル配列において，BASE と CHECK に格納される値は，以下の条件を満足するものとされています．

  • ノード s からノード t への枝があり，ノード t のラベルが c のとき，
    • t == BASE[s] + c
    • s == CHECK[t]

そして，この条件に従ってトライを探索するため，CHECK[i] にアクセスした直後に BASE[i] にアクセスすることが多く，BASE と CHECK を別々の配列にするより，base と check というメンバを持つ配列にする方が，アクセスの局所性を高めることができます．Darts::DoubleArray では，以下のような構造体の配列を用いています．

struct unit_t
{
  int base;
  unsigned int check;
};

base が符号ありの整数になっている理由は，終端ノードかどうかを判断するフラグとして base の符号を利用しているからです．BASE[i] < 0 のとき，ノード i は終端ノードであり，-(BASE[i] + 1) がレコードとして関連付けられています．