21日目の記事は@tsukasa_diary氏による「BDDとZDDを下から読んで再帰アルゴリズムを作る」でした．
23日目の記事は@okateim氏による「Shortest Unique Substring Query」です．
こんにちは．Qiita初投稿の@MatsuTakuです．
本記事では，文字列集合の各文字列に一意のIDを割り当てるNumbered Automatonというグラフ構造について紹介します．
はじめに
文字列集合を効率的に表現する方法の一つとして，グラフ表現により文字列を扱うオートマトンがあり，代表的なものとしてTrieやDAWGなどが知られています．
Trieは文字列集合の接頭辞を併合して構築される木構造で，本記事に関連する重要な特徴として，検索文字列により到達する状態は一意である事が挙げられます．この特徴により，各文字列により到達する状態に一意のIDを割り当てることで，文字列とIDの対応表を簡単に表現することができます．
DAWGは文字列集合の接頭辞と接尾時を併合して表現されるグラフで，文字列集合を表現する最も状態数の少ないグラフを指して用いられます．
Trieより小さいグラフで表現できるという利点がある反面，任意の状態に対し複数の検索文字列で到達する可能性があり，Trieと同様の方法では前述した対応表を表現できません．
タイトルで紹介したNumbered Automaton1は，Trieに限らず一般の非巡回決定性有限オートマトンにおいて，表現した文字列と対応するIDを保存するグラフ構造になります．本記事では，オートマトンをNumbered Automatonに拡張する方法と，Numbered Automatonにおいて文字列とIDを双方向に検索するアルゴリズムについて紹介します．
文字列に対する完全ハッシュ
本記事の主な課題は，要素数$n$の有限文字列集合 $K = \{k_1, k_2, ..., k_n\}$ はアルファベット順辞書順に並んでいると想定し，$k_i \in K$ と $i \in \{1, 2, ..., n\}$ を対応付けることとします．
任意のID集合$V=\{v_1, v_2, ..., v_n\}$を$K$と対応付ける場合，$i$と$v_i$の対応表の準備により，$i$を介して$k_i$と$v_i$の対応付けを行うことになります．
Numbered Automaton
Trieは，入力$k_i$により到達する各状態に$i$を保存することで簡単に対応付が可能でしたが，DAWGを始めとする経路が集合するオートマトンにおいては同様の方法を用いることができませんでした．
Numbered Automaton では，オートマトンの遷移にある数値を保存することで，任意の受理状態までの経路に対して一意のIDを割り振ることができます1．本記事では，遷移に与える数値をワード数2と呼ぶことにします．
ワード数は，オートマトンのすべての遷移に対して与えられる自然数です．この値は，任意の遷移より後に出現する受理状態までのすべての経路の数を表します．言い換えると，任意の状態に注目したとき，その状態より右側に保存されている文字列のパターン数を表しています．$"\rm{abc}"$により到達する状態より右側に現れる文字列のパターンは $\{\epsilon (空文字), "\rm{de}"\}$ の2種類なので，$"\rm{abc}"$の$'\rm{c}'$に対応する遷移のワード数は２ということになります．
オートマトンの遷移にワード数を与えてNumbered Automatonに拡張する操作は，DFSにより発見した受理状態の数を親に伝播することで実現できます．
文字列からIDの復元
まず準備として，カウンター$C = 0$を用意します．入力文字列を一文字ずつ与えて探索しながら，到達したすべての状態で以下に示す操作を行います．
- 子の遷移の内，遷移ラベルが入力文字より小さい全ての遷移のワード数を$C$に加算
- 受理状態を通過した場合，$C$に$1$を加算
この操作を入力文字列を受理するまで行い最後に$C$を報告することが，文字列からIDの復元操作になります．
入力文字列を$k_3 = "\rm{abdef}"$とし，$i = 3$を復元する操作を例示しながら説明します．オートマトンに入力する文字は，順に$\{'\rm{a}', '\rm{b}', '\rm{d}', '\rm{e}', '\rm{f}'\}$です．初期状態から$"\rm{a}"$の入力による経路上の状態においては，入力文字より小さいラベルを持つ遷移は見つからず，受理状態も通過しなかったため，$C=0$のままで通過します．$”\rm{ab}”$により到達した状態は，$\{'\rm{c}', '\rm{d}'\}$のラベルを持つ遷移が存在します．次に入力される文字は$'\rm{d}'$であるため，ラベル$'\rm{c}'$に対応する遷移のワード数$2$を$C$に加算し，$C=2$となります．同様の操作を行い，$"\rm{abdef}"$の入力により受理状態に到達したため，$C$に$1$を加算し$C=3$となります．ここで入力文字を受理したため，$C=3$を報告することで，$"\rm{abdef}"$から$3$が復元されたことになります．
IDから文字列の復元
$i$から$k_i$を復元する場合，$C=i$を準備します．続いて以下に示す操作により，探索経路を決定しながら$C=0$になるまで探索を行い，それまでにたどった経路上の遷移ラベルを報告することが，IDから文字列の復元操作になります．
- 受理状態に到達した場合，$C$から$１$を減算する
- 到達した状態で，子の遷移を遷移ラベルのアルファベット順に確認し，以下の操作を行う．
- $ワード数 < C$の場合， $C$からワード数を減算する
- $ワード数 \geq C$の場合，現在確認している経路で遷移を実行する．
$i=3$の入力から$k_3 = "\rm{abdef}"$を復元する操作を例示します．最初に発見する$'\rm{a}'$の遷移のワード数は4であり, $4 \geq C (= 3)$であるため，現在の遷移を実行します．同様に次の$'\rm{b}'$に該当する遷移も実行します．次の状態でアルファベット順に最初に見つかる$'\rm{c}'$の遷移のワード数は2であり，$2 < C ( = 3)$であるため，$C$から$2$を減算し$C=1$となり，次の兄弟の遷移を確認します．次の$'\rm{d}'$の遷移のワード数は$1$であり，$1 \geq C (=1)$であるため，現在の遷移を実行します．同様の操作で$"\rm{ef}"$のラベルを遷移することで受理状態に到達したため，$C$から1を減算し$C = 0$となります．以上で$C=0$となったため，これまでに辿った経路上のラベル$"\rm{abdef}"$を報告することで，$3$から$"\rm{abdef}"$が復元されました．
おわりに
Numbered Automaton 自体は古くから知られたアルゴリズムではありますが，実際に使われているケースは殆ど無いように思います．文字列集合表現と完全ハッシュのタスクにおいてTrieとDAWG+Numbered Automatonを比較する場合，データ構造に落とし込んだ際の記憶量と検索時間が主な比較項目になります．DAWGは接尾辞の併合によりTrieより小さいグラフで文字列集合を表現できますが，すべての遷移に整数値を割り当てるための記憶量のコストをいかに抑えるかが肝になります．また，Trieは簡潔データ構造表現が提案されいたり，データ構造に関してかなり研究が進んでいるため，単純なグラフサイズだけでは記憶量を比較することはできません．検索時間においても，Numbered Automatonのアルゴリズムはすべての状態において子の遷移すべてを確認する必要があります．そのため，実際の時間オーダーはデータ構造に依存するものの，Trieより非効率であることは否めません．
数少ない実用例として，今年の9月にNumbered Automatonを利用した圧縮文字列辞書をTrie辞書と同程度の性能で実現する方法を提案しましたので，ご興味ありましたらご参照下さい3 4．
もちろんタスク設定によってはNumbered Auromatonが日の目を見る可能性はあります．もし応用例などをご存知の方がいらっしゃいましたら，ぜひコメントしていただければと思います．
ここまで読んでいただき，ありがとうございました．