Darts clone の辞書構築

darts-clone

トライをダブル配列で表現する Darts では，文字列の集合から一息に辞書を構築することができます．しかし，DAWG をダブル配列で表現する Darts clone では，最初に DAWG を構築し，その DAWG をダブル配列に変換するという手順が必要になるため，Darts と比べると，辞書構築に時間がかかります．ここで説明する内容は，DAWG を構築する方法と，ダブル配列への変換を効率化するための工夫です．

DAWG の構築

DAWG は，トライと同じように，文字列を辞書式昇順に一つずつ追加していく方式で構築できます．ただし，文字列を登録するとき，子ノードの配置が確定し，兄弟ノードがすべて分かったノードについては，確定済みのノードに対するマージを試みます．このとき，マージの条件はラベルと子ノードがすべて同じことであり，マージ対象の検索にはハッシュ表を使っています．トライから DAWG への変換として見ると，帰りがけ順（Post-order）に子ノードをマージもしくは確定する処理になります．

DAWG の構築において，未確定のノードと確定済みのノードでは必要な情報が異なるため，格納に用いるクラスは別々になっています．未確定のノードについては，それほど数が大きくならないので，単純なクラスを用いて実装しています．一方，確定済みのノードについては，メモリ消費を抑えるために，ビット単位で割り当てを変更したり，ラベルやフラグを別々に管理したりするという工夫をしています．

入力となる文字列の集合に含まれる文字の総数を n，文字の異なり数を m，入力に対するトライのノード数を k とおくと，トライの構築にかかる時間計算量は O(n) になり，DAWG の構築にかかる時間計算量は O(n + m・k) になります．m・k の部分は，ハッシュ表でマージ対象を検索した後で子ノードを比較する処理と対応しています．実際にかかる時間は，ハッシュ関数の性能やハッシュ表の充填率，子ノードの数などに依存します．

DAWG からダブル配列への変換

Darts clone では，構築した DAWG を深さ優先で探索し，各ノードと対応する要素をダブル配列に配置します．そして，DAWG からダブル配列への変換で問題となるのは，要素の配置を決定する方法と共通部分木のマージを反映する方法です．以下，それぞれについて説明します．

要素の配置

ダブル配列において，新しい要素の配置を決める単純な方法は，線形探索により未使用の要素（配置先として使用できる要素）を見つけることです．しかし，この方法では，最終的な要素の数を n とおくと，時間計算量が O(n^2) となり，ダブル配列の構築にとても時間がかかります．そこで，要素の配置を高速化する手法として，スキップ法とリンク法が提案されています．

  • スキップ法
    • 概要
      • ダブル配列の末尾付近には未使用の要素が多いという特徴を利用し，末尾から一定の範囲のみを探索の対象とすることで，最悪時間計算量を抑えます．
    • 欠点
      • 探索範囲を狭くすると未使用要素が多く残り，探索範囲を広くすると時間がかかるというトレードオフが発生します．
  • リンク法
    • 概要
      • 未使用の要素を連結リストに保存し，未使用の要素のみを探索の対象とすることで，平均時間計算量を抑えます．
    • 欠点
      • 最悪時間計算量を抑えることができず，登録する文字列によって，構築にかかる時間が大きく悪化する可能性があります．

Darts clone では，スキップ法とリンク法を組み合わせて利用しています．すなわち，ダブル配列の末尾から一定の範囲にある未使用の要素を連結リストに保存します．この組み合わせにより，スキップ法を単独で利用するよりも探索範囲を広く取りやすくなり，さらにリンク法を単独で利用する場合の欠点を解決できます．

マージの実現

DAWG からダブル配列への変換では，DAWG の深さ優先探索において，各ノードがマージによる合流地点になっているかどうかを調べ，対応する要素が既に配置されていれば，その要素を直前のノードの移動先として使用することになります．そのため，各ノードがマージによる合流地点かどうか，および対応する要素はどれかを保存しておく必要があります．そこで，Darts clone では，ビットベクトルの簡潔表現（Succinct data structures）を利用しています．すなわち，前者をビットベクトルにより表現し，後者の ID を rank() で求めるようにしています．単純・高速・コンパクトと三拍子揃った便利な方法です．

DAWG における共通部分木のマージをダブル配列に反映するとき，注意点があります．それは，対応する要素が存在しても，適切な offset の設定ができない場合，その要素を移動先として使用できないことです．このような場合，要素を新たに配置することになります．offset の設定に失敗する原因は，要素圧縮と大規模化の両立により，offset で表現できる値に隙間が発生していることです．