Darts clone のデータ構造

darts-clone

トライをダブル配列で表現する Darts に対して，Darts clone は，基礎のデータ構造として Directed Acyclic Word Graph (DAWG) というグラフ構造を採用し，DAWG をダブル配列で表現するようになっています．

Directed Acyclic Word Graph (DAWG)

トライの共通部分木を併合することで得られるグラフ構造が DAWG です．トライからDAWG への変換では，登録するキーの末尾に共通性があるほど，多くのノードを取り除くことができます．これまでの実験により，日本語や英語の単語をたくさん登録する場合であれば，全体の 60 〜 70% 程度のノードを取り除けることが分かっています．特に有効なデータの例として，日本の郵便番号を DAWG に登録すると，そのサイズはトライの約 1/10 になります．

DAWG はトライを圧縮したデータ構造として有用ですが，レコードとダブル配列に関して，以下のような問題があります．

  • レコードに関する問題
    • レコードの重複率が低ければ，ほとんど圧縮できません．
  • ダブル配列に関する問題
    • 初期のダブル配列では，同じノードに向かう複数の枝を表現できません．

レコードに関する問題は，終端ノードにレコードを関連付けるため，異なるレコードを持つキーを併合できないことが原因です．この問題により，すべてのキーに固有のレコードを持たせる場合，共通部分木が一つも存在しないため，DAWG への変換による圧縮効果は得られなくなります．

ダブル配列に関する問題は，移動元と移動先のノードを 1 対 1 で対応させていることが原因です．この問題については，ダブル配列の要素を圧縮する手法により解決できます．

ダブル配列の要素圧縮

初期のダブル配列では，トライを 2 つの配列 BASE, CHECK により表現することになっていて，実装においては，2 つの整数 base, check をメンバとする配列を用います．そして，トライの規模や扱いやすさを考えると，Darts::DoubleArray のように，base, check それぞれに 32-bit の整数を割り当てることになります．このとき，ダブル配列のサイズは，ノード数 n に対して 8・n bytes です．

ダブル配列の要素を圧縮する手法では，各要素に割り当てる領域を 4 bytes に削減するべく，BASE と CHECK の代わりに BASE' と CHECK' を用います．それぞれに格納される値は，以下の条件を満足するものとします．

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

重要な変更点は，CHECK が移動元のノード番号を格納するのに対し，CHECK' には移動先のラベルが格納されることです．この変更により，CHECK' の各要素に対する割り当てを 1 byte に減らすことができます．後は，BASE' の各要素に対する割り当てを 3 bytes にすれば，ダブル配列の各要素を 4 bytes で表現できるようになります．また，要素を圧縮したダブル配列では，移動元と移動先のノードを 1 対 1 で対応させる必要がなくなり，同じノードに向かう複数の枝を表現できるようになります．結果として，ダブル配列のサイズは 1/2 になり，さらに，ダブル配列による DAWG の実装が可能となります．

上述のように，要素の圧縮には，サイズ面と機能面での利点があります．しかし，BASE' の各要素に対する割り当てを減らすことは，ノード数の上限が小さくなるという欠点につながります．具体的には，2^23 ≒ 840 万程度がノード数の上限になります．この上限があっても，一般的な形態素辞書など，登録する文字列が短く，語彙数が 100 万件に満たない程度であれば，十分に対応できます．ただし，登録する文字列が長かったり，語彙数が 200 万件を超えたりする場合，ノード数が上限に到達することがあります．そのため，Darts clone では，要素の圧縮とダブル配列の大規模化を両立するための工夫をしています．

なお，新しい条件式で + の代わりに XOR を用いている理由は，ダブル配列の拡張をブロック単位にして，例外処理を減らすためです．オーバーフローやアンダーフローが発生しないという XOR の特徴は魅力的です．

要素圧縮と大規模化の両立

ダブル配列の要素圧縮において，BASE' の各要素に対する割り当てを 3 bytes にするという単純なアプローチを採用すると，ノード数の上限やレコードの最大値が小さくなってしまいます．そこで，Darts clone では，ダブル配列の要素を以下のようなクラスで表現します．

class DoubleArrayUnit
{
public:
	bool has_leaf() const { return ((unit_ >> 8) & 1) == 1; }
	int value() const { return static_cast<value_type>(unit_ & ((1U << 31) - 1)); }
	unsigned int label() const { return unit_ & ((1U << 31) | 0xFF); }
	unsigned int offset() const { return (unit_ >> 10) << ((unit_ & (1U << 9)) >> 6); }

private:
	unsigned int unit_;
};

各メソッドの動作と役割は，以下のようになっています．

  • has_leaf()
    • 終端ノードでなければ，子ノードに終端ノードが存在するかどうかを返します．
      • has_leaf() を提供している理由は，終端ノードの候補にアクセスすることなく終端ノードの有無を確認できるようにするためです．特に，commonPrefixSearch() の高速化に有効です．
  • value()
    • 終端ノードであれば，関連付けられているレコードを返します．
      • 終端ノードのラベルは終端文字に限定されるため，終端フラグとして使用している Most Significant Bit (MSB) 以外，31 bits をレコードの格納に使用しています．
  • label(): check の代替
    • 終端ノードでなければ，ラベルを返します．
    • 終端ノードであれば，不正なラベルを返します．
      • 検索における終端ノードに対する例外処理をなくすため，MSB が 1 になっている 32-bit 符号なし整数を不正なラベルとして返します．
  • offset(): base の代替
    • 子ノードの相対オフセットを返します．
      • 右から 10 番目の bit は，オフセットの値域を拡張するかどうかを表します．拡張する場合，格納されているオフセットを 256 倍にして返します．この拡張により，最大で 2^(21+8) ≒ 5.4 億という大きな値を表現できるようになっています．

これらのメソッドが返す値は，以下のようになります．

  • ノード s からノード t への枝があり，ノード t のラベルが c のとき，
    • t == s XOR s.offset() XOR c
    • c が終端文字であれば，
      • s.has_leaf() == true
      • t.value() が有効
      • c ≠ t.label()
    • c が終端文字でなければ，
      • s.has_leaf() == false
      • t.value() の動作は未定義
      • c == t.label()