Compact Directed Acyclic Word Graphを定義する

これは「文字列アルゴリズム Advent Calendar 2017」４日目の記事です．

３日目の記事は@itomomotiによる「周期性補題」でした．
５日目の記事は@kazu0x17による「木の同型性判定」です．
昨年の文字列アルゴリズム Advent Calendar では「Suffix Tree + Suffix Array = Suffix Tray」という記事を書きました．

はじめに

文字列アルゴリズム，特に文字列に対する索引が好きです．

古典的な全文索引であるCompact Directed Acyclic Word Graph (以下CDAWG)を紹介するのがこの記事です．この記事の内容は基本的に以下の論文内で示されています．

• Anselm Blumer, Janet Blumer, David Haussler, Andrzej Ehrenfeucht, M. T. Chen, and Joel I. Seiferas. The smallest automation recognizing the subwords of a text. Theoretical Computer Science, 40:31–55, 1985.

• Anselm Blumer, Janet Blumer, David Haussler, Ross M. McConnell, and Andrzej Ehrenfeucht. Complete inverted files for efficient text retrieval and analysis. Journal of the ACM, 34(3):578–595, 1987.

• Mathieu Raffinot. On maximal repeats in strings. Information Processing Letters, 80(3):165–169, 2001.

• Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa, Giancarlo Mauri, Giulio Pavesi. On-line construction of compact directed acyclic word graphs. Discrete Applied Mathematics, 146(2):156-179, 2005.

おおよそ30年前に提案されたデータ構造ですが，理論的には今現在もいろいろ研究されています．

CDAWGはsuffix trieと呼ばれるデータ構造から定義する方法と，部分文字列の同値関係から定義する方法があり，今回はその２つをやっていきます．

全文索引問題

テキスト$T$の中からパターン$P$を探す問題をパターンマッチングと呼びます．
以下のテキスト$T$からパターン$P = $ "鰛鰯魦" を探してください．

テキスト$T = $ "鯆鰯鰻鰯鰻魦鰛鰯魞魞鰛魦鰛魦鰛魦鰛魦魦鰯鰯鯆鰯鰻鰯鰻魦鰛鰯魞魞鰛魦鰛魦鰛鰯魦鰛魦魦鰯鰯"

見つかりましたか？ こういう感じの問題です．

テキスト$T$の長さを$n$，パターン文字列$P$の長さを$m$とすると，KMPのようなテキストをすべて舐めるアルゴリズムで$O(n + m)$時間で解くことができます．

入力テキスト$T$に対し前処理を行い，全文索引と呼ばれるデータ構造を作成することで，このパターンマッチングをより高速に解くことができます．この記事を通して，長さ$n$の文字列$T$に対して全文索引を構築することを考えます．

準備

議論の前に，いくつかの記法を導入します（面倒だったら読み飛ばしてください）．基本的に初日の記事や昨日の周期性補題の記事で用いられたものと同じです．

• 文字の集合$\Sigma$をアルファベットとよびます¹．文字列は$\Sigma^*$の要素です．$\Sigma$の要素数を$\sigma$と書きます．また，長さ0の文字列を空文字列と呼び$\varepsilon$で表します．
• 長さ$n$の文字列$T$全体を$T[1..n]$と書くことにします．$|T|$で文字列$T$の長さを表します．$T[i]$で$T$の$i$番目の文字を表し，$T[i .. j]$で$T$の$i$番目の文字から$j$番目までの部分文字列を表します($i \leq j$)．
  • 例: T = ababcのとき，T[2] = b, T[1..3] = aba
• 文字列$x,y,z \in \Sigma^*$に対して，文字列$w$が$w = xyz$であるとき，$x,y,z$をそれぞれ$w$の接頭辞（prefix），部分文字列（factor, substring），接尾辞（suffix）といいます．$w$の接頭辞の集合と部分文字列の集合，接尾辞の集合をそれぞれ，$\mathit{Prefix(w)}$，$\mathit{Factor(w)}$，$S\mathit{uffix(w)}$と書きます．
  • 例: $\mathit{T = ababc}$に対して， $\mathit{Prefix(T)} = \{ \varepsilon, a, ab, aba, abab, ababc\}$， $\mathit{Factor(T)} = \{ \varepsilon, a, b, c, ab, ba, bc, aba, abc, bab, abab, babc, ababc\}$, $\mathit{Suffix(T)} = \{ \varepsilon, c, bc, abc, babc, ababc\}$
• $x \in \mathit{Factor(T)}$が繰り返し（repeat）であるとは，$x$が$T$中に２回以上出現することと定義します．また，任意の$a \in \Sigma$に対して$T$中の出現回数が$xa \in \mathit{Factor(T)}$と$ax \in \mathit{Factor(T)}$の出現回数よりも真に多いrepeatを極大繰り返し（maximal repeat）と定義します．（グラフ理論の"極大"の感覚と少し違うようです）

Suffix trie & suffix tree

最も基本的な全文索引はsuffix trieと呼ばれるものです．
その名の通り，全ての接尾辞をTrie構造（根付き木で，各枝は１文字のラベルをもつ．ノードが持つ子供への枝ラベルは全て異なる）の根から格納したものです．以下の図を見てください．

テキスト中の全ての部分文字列が根からのパスで表現されています．パターンマッチングは根からパターン文字列で遷移できるかどうかを見るだけでよく，$O(m)$時間¹で解くことができます．（特に，パターンが存在するか否かをyes/noで返す問題はmember queryと呼ばれます．他に，出現回数を返すcountや出現位置をすべて返すlocateなどがあります．以降は簡単のためmember queryを考えます．）

Suffix trieのノード数は$O(n^2)$個なので，どうにかしたい気持ちになります．

分岐のないノードを取り払い，枝のラベルを１文字だけから複数文字持てる様にすればノード数が減らせそうです（path compactionと呼びます）．こうしてできるのがSuffix treeです．以下の図を見てください．

テキストの末尾にユニークな文字（図の場合だと文字cは末尾以外に出現していないので，ユニークな文字）が付いている場合，葉ノードの数はちょうど$n$個になります．内部ノードは全て分岐しているので，その個数は最大$n-1$個になり，Suffix treeのノード数は合計$O(n)$です．
枝ラベルの文字数は$O(n^2)$ですが，全てのラベルはテキスト中の部分文字列なので，その開始位置と終了位置の整数2つを持っておけばよいです．

Suffix link

突然ですが，suffix trieとsuffix treeにはsuffix linkと呼ばれるノードからノードへのポインタが定義でき，これが便利なので導入します．雑にいうと，ノードが表す文字列の先頭１文字を削ったものへのポインタです．
Suffix treeのあるノード$v$を考えます．“ノード$v$が表す文字列”を根から$v$へのパス上のラベル文字列を連結したものと定義し，$\mathit{label(v)}$と書くことにします．面倒なので，ノード$v$をノード$\mathit{label(v)}$と書いてもいいことにしましょう．

ノード$v$を根を除く内部ノードが文字$a \in \Sigma$と文字列$x \in \Sigma^*$に対し，$\mathit{label(v)} = ax$だとすると，$\mathit{label(u)} = x$となるノード$u$が存在します．
この時，ノード$v$のsuffix linkを$\mathit{suflink(v)} = u$と定義します．以下の図を見てください．破線がsuffix linkです．テキストの末尾がユニークだと葉ノードにも定義できます．

DAWG & CDAWG

suffix trieやsuffix treeを眺めていると，同型な部分木がよく出現することがわかります．これを一つにまとめ，DAGにするとさらにノード数＆枝数が減らせそうです．Suffix trieのDFA最小化がDAWG，suffix treeの最小化がCDAWGです．例のごとく以下の図を見てください．同じ色のノードは同じ部分木を持っているのでマージします．

Suffix treeが与えられた時，どのようにして同型な部分木を見つければいいのか？これにsuffix linkが使えます．いまノード$v$を根とする部分木と$u$を根とする部分木が同型だとしましょう．そのとき，テキスト$T$中の$v$と$u$の出現の終了位置集合は同じになります．すなわち$v$から$u$（もしくは$u$から$v$）にsuffix linkを用いて遷移できます．下図のように同じ色のノードがsuffix linkで結ばれているのがわかります．

そんな感じで，Suffx trieからsuffix tree，DAWG，CDAWGを定義しました．以下はまとめの図です．

DAWGが与えられたときCDAWGを線形時間で構築する方法²や文字列から直接CDAWGを線形時間で構築する方法³，オンラインで構築する方法⁴が知られています．

さて，こうしてできたCDAWGの枝数はどれくらいでしょうか？Suffix treeの枝数が$O(n)$なので，多くとも$O(n)$本であることは間違いありませんが，もう少し厳密に見積もれそうです．

部分文字列の同値関係を定義して，CDAWGのノードと枝を定義することで解析してみたいと思います．

同値関係で定義する

（右/左）出現同値類

長さ$n$の文字列$T$と長さ$m$の文字列$x$が与えられたとき，$T$中に出現する$x$の位置集合を考えます．

$T$における$x$の出現開始位置集合を$\mathit{start\_ pos_T(x)} = \{ i \;|\; x = T[i..i+m-1]\}$
$T$における$x$の出現終了位置集合を$\mathit{end\_ pos_T(x)} = \{ i \;|\; x = T[i-m+1..i]\}$
とします．

これらの出現位置集合を使って，文字列Tの部分文字列に左同値と右同値という関係を定義します．

文字列$T$の部分文字列$x$と$y$において，$\mathit{start\_ pos_T(x)} = \mathit{start\_ pos_T(y)}$のとき$x$と$y$は左同値関係にあるといい，$x \equiv^L_T y$と書くことにします．
同様に，$\mathit{end\_ pos_T(x)} = \mathit{end\_ pos_T(y)}$のとき$x$と$y$は右同値関係にあるといい，$x \equiv^R_T y$と書きます．
また，$\equiv^L_T$における$x$の同値類を$[x]^L_T$，$\equiv^R_T$における$x$の同値類を$[x]^R_T$と書くことにします．
$[x]^L_T$の最長の要素を$[x]^L_T$の代表元とし$\overrightarrow x$と書くことにします．同様に$[x]^R_T$の最長の要素を$[x]^R_T$の代表元とし$\overleftarrow x$と書きます．

関係$\equiv^L_T $と$\equiv^R_T $には以下が成り立ちます．

• (a) $x \equiv^R_T y$のとき，$|x|\geq |y|$ならば，$y$は$x$の接尾辞である．（$x \equiv^L_T y$のとき，$|x|\geq |y|$ならば，$y$は$x$の接頭辞である．
• (b) $x \equiv^R_T y$なら$xz \equiv^R_T yz$である（右不変な同値関係といいます）（同様に$x \equiv^L_T y$は左不変な同値関係）
• (c) $xy \equiv^R_T y$のとき，$y$はかならず$x$の直後に出現する．（$yx \equiv^L_T y$なら$y$は必ず$x$の直前に出現する）
• (d) $x \in \mathit{Factor(x)}$が$[x]^R_T$の最長の要素である（すなわち$x = \overleftarrow x$） ．$\Leftrightarrow$ $x$が$T$の接頭辞，もしくは$ax,bx \in \mathit{Factor(T)}$となる文字$a,b\in\Sigma$が存在する.
• (e) (d)の左同値類版．$x$が$[x]^L_T$の最長の要素である（すなわち$x = \overrightarrow x$）． $\Leftrightarrow$ $x$が$T$の接尾辞，もしくは$xa,xb \in \mathit{Factor(T)}$となる文字$a,b\in\Sigma$が存在する.

これらを使ってこれまで紹介した全文索引のノード集合と辺集合を定義していきたいと思います．

Suffix trieとsuffix tree，DAWG，CDAWGを定義する．

$(V,E)$をノード集合$V$と辺集合$E \subseteq V \times \Sigma^+ \times V$からなる辺ラベル付きグラフとします．($E$の要素$(v, x, u)$はノード$v$から$u$へのラベル$x$をもつ辺を表します．）

Suffix trie

Suffix trieから始めたいと思います．

Suffix trieのノード集合は簡単です．
各ノード$v$は根から$v$へのパスラベルで部分文字列を表現しています．
よって，
$V = \{ x \;|\; x \in \mathit{Factor(T)}\}$ です．
辺集合は，ノードからノードへ１文字で遷移するので，
$E = \{ (x, a, xa) \;|\; x, xa \in \mathit{Factor(T)}, a \in \Sigma\}$
と書けます．

Suffix tree

次にsuffix treeです．
Suffix trieの内部ノードから子を2つ以上持たないノードを取り除くと，Suffix treeのノード集合になります．
逆に言うと，suffix treeの（根を除く）内部ノードは必ず2つ以上の子を持つので，内部ノード$v$に対して$\mathit{label(v)} = x$だとすると，$xa$と$xb$が$T$中に出現するような文字$a,b\in\Sigma$が存在することになります．また，葉ノードと根は$T$の接尾辞を表現しています（根は空文字列を表現）．

これは左同値類の特徴(e)，

• (e) $x$が$[x]^L_T$の最長の要素である（すなわち$x = \overrightarrow x$）． $\Leftrightarrow$ $x$が$T$の接尾辞，もしくは$xa,xb \in \mathit{Factor(T)}$となる文字$a,b\in\Sigma$が存在する.

に当てはまるので，suffix treeのノード集合$V$は

$V = \{ \overrightarrow x \;|\; x \in \mathit{Factor(T)}\}$

と書けます．

すなわちsuffix treeの辺は，左同値類の代表元から別の代表元への遷移です．次のように書けます．

$E = \{ (\overrightarrow x, ay, \overrightarrow {xa}) \;|\; x, xa \in \mathit{Factor(T)}, a \in \Sigma，y \in \Sigma^*，\overrightarrow {xa} = xay, \overrightarrow x \neq \overrightarrow {xa}\}$

代表元$\overrightarrow x$は$[x]^L_T$の“最長の要素”なので，$\overrightarrow x$の末尾に文字$a$をつけたものは同値類$[x]^L_T$に含まれません．$ \overrightarrow {xa} = xay$だとすると，辺ラベル$ay$で$\overrightarrow x$から$\overrightarrow {xa}$に遷移します．

まとめると，部分文字列$x$に対して左同値類の代表元を取る行為は，分岐のないノードを取り払うこと（path compaction）と対応しています．

DAWG

次にDAWGです．DAWGの定義は，suffix trieの同型な部分木をまとめたものでした．

復習すると，Suffix trieのノード$v$を根とする部分木と$u$を根とする部分木が同型ならば，$v$から$u$（もしくは$u$から$v$）にsuffix linkを（１回以上）用いて遷移できます．suffix linkは先頭１文字を削ったものへのポインタです．すなわち$1\leq k$に対して$v$からの$k$回suffix link遷移を$suflink^k(v) = u$とすると，$end\_ pos_T(v) = end\_ pos_T(u)$の場合は$v$を根とする部分木と$u$を根とする部分木が同型であり，$end\_ pos_T(u) \subset end\_ pos_T(u)$の場合はそうでないことになります．
これは$T$の部分文字列の右同値類に対応します．

よって，ノード集合$V$は
$V = \{ [x]^R_T \;|\; x \in \mathit{Factor(T)}\}$，
と書けます．

DAWGの辺は，右同値類の元の末尾に文字$a$を付け加えて別の同値類へ遷移することになります．
右同値類は出現終了位置が全て同じものがまとまっているので，$[x]^R_T$のどの元に文字$a$を加えても末尾が変化し$[x]^R_T$とは別の同値類になります．

よって，
$E = \{ ([x]^R_T, a, [xa]^R_T) \;|\; x, xa \in \mathit{Factor(T)}, a \in \Sigma\}$
と書くことができます．

部分文字列$x$に対して右同値類を取る行為は，同型な部分木をまとめること（minimization）と対応しています．

CDAWG

Suffix trieとsuffix tree，DAWGを同値関係のもとで定義しました．

復習すると，suffix treeではsuffix trieから分岐のないノードを取り除くことを左同値類の代表元を取ることで表現し，DAWGではsuffix trieの同型な部分木をまとめることを右同値類を取ることで表現しました．

CDAWGはsuffix treeの同型な部分木をまとめたものです．
suffix treeのノード集合は$\{ \overrightarrow x \;|\; x \in \mathit{Factor(T)}\}$だったので，これに右同値類をかければ，同型な部分木をまとめることになります．したがって，CDAWGのノード集合$V$は，

$V = \{[\overrightarrow x]^R_T \;|\; x \in \mathit{Factor(T)}\}$，

と書けます．

辺集合も，suffix treeのときと同様です．

$E = \{([\overrightarrow x]^R_T, ay, [\overrightarrow {xa}]^R_T) \;|\; x, xa \in \mathit{Factor(T)}, a \in \Sigma，y \in \Sigma^*，\overrightarrow {xa} = xay, \overrightarrow x \neq \overrightarrow {xa}\}$

と書くことができます．$ [\overrightarrow {xa}]^R_T = \overrightarrow xay$だとすると，辺ラベル$ay$で$[\overrightarrow {x}]^R_T $から$[\overrightarrow {xa}]^R_T$に遷移します．

それで結局，CDAWGのノード・辺は何を表しているか？

CDAWGのノード集合
$V = \{ [\overrightarrow x]^R_T \;|\; x \in \mathit{Factor(T)} \}$
についてもう少し詳しく見ていきます．

まずsuffix treeの葉ノードはCDAWGのsink（出次数0のノード）にまとまります．$T$の末尾がユニークなら，sinkは長さ１以上の全ての接尾辞を表現しています．

次にCDAWGの内部ノードですが，結論から言うと，文字列の極大繰り返し(maximal repeat)に対応しています．

maximal repeatの定義は，$T$中に２回以上出現しており，左右どちらに文字を付け加えても出現回数が減少する部分文字列です．もう少し書くと

• $x \in \mathit{Factor(T)}$が繰り返し（repeat）であるとは，$x$が$T$中に２回以上出現することと定義し，任意の$a \in \Sigma$に対して$T$中の出現回数が$xa \in \mathit{Factor(T)}$と$ax \in \mathit{Factor(T)}$の出現回数よりも真に多いrepeatを極大繰り返し（maximal repeat）と定義する．

です．

Suffix treeの各ノードは必ず分岐しているので，それらが表す部分文字列は少なくとも２回以上出現しています．なのでCDAWGの内部ノードが表す文字列も必ず２回以上出現します．すなわちrepeatであることはわかります．

CDAWGの内部ノード$[\overrightarrow x]^R_T$の代表元$\overleftarrow{\overrightarrow x}$はsource（入次数0のノード）から$[\overrightarrow x]^R_T$への最長パス上のラベルを連結した文字列になります．右・左同値類の定義より，$\overleftarrow {\overrightarrow x}$の先頭もしくは末尾に文字を追加すると$T$中の出現回数が減ることがわかります．すなわち，$\overleftarrow {\overrightarrow x}$は$T$のmaximal repeatです．

辺はmaximal repeatの末尾に文字を追加したものなので，その本数はmaximal repeatの右拡張数と呼ばれます．各maximal repeat $\overleftarrow {\overrightarrow x}$に対し，$\overleftarrow {\overrightarrow x} a \in \mathit{Factor(T)}$となるような文字$a$の種類だけ枝が必要です．

この枝数がどれくらいかというと，$T = aa\ldots aac$のような文字列に対して最悪の$O(n)$（具体的には$2n-2$）になり，Fibonacci文字列のとき最良の$O(\log n)$になります．maximal repeatの個数が少ないほどいいので，文字列中に長い部分文字列の繰り返しが多く含まれているとCDAWGのサイズは小さくなります．例えば全人類のゲノムシーケンスを集めて高速な全文索引を構築するようなことがあった場合，人間のDNAはほとんど変わらないので長い繰り返しが多く出現し，maximal repeatの個数が少なくなるのでCDAWGは効率のいい索引になります⁵．なるはずですが，領域を$O(n)$から減らすにはまだ問題があります．

ラベル文字列の問題

文字列$T$のmaximal repeatの右拡張数を$e^R_T$と書くことにします．
CDAWGはsuffix treeと比べて辺数が$O(n)$から$O(e^R_T)$になりましたが，辺ラベルの文字数を$O(e^R_T)$で抑えることはできず最悪時$O(n^2)$文字必要になります（例: $\mathit{T = abcdefg} \ldots$）．suffix treeと同様にCDAWGの辺ラベルは元文字列$T$の部分文字列なので，$T$を保持しておき，辺ラベル$T[i..j]$の代わりに整数$i,j$を各辺に持たせておけばよさそうです．

これを使うとCDAWGの領域計算量はbit換算で$n \log \sigma + O(e^R_T \log n) bits$ になります．（元文字列（$n$文字）に必要なbit数 + $O($枝数個のポインタ$)$です．）

元文字列を保持しない，すなわち$n \log \sigma$bits必要ないCDAWGが最近になって提案されています⁶⁷⁸．これを使えばsuffix treeよりもさらに小さい全文索引にすることができます．

まとめ

そんなわけでCDAWGを紹介したり，定義したりしました． ここで扱わなかった内容として，各索引の構築方法，DAWGとsuffix treeの関係，Myhill–Nerode定理，いろいろな補題の証明などがあります．どれも面白い内容なので誰かが書いてくれると思います．

文字列アルゴリズムAdvent Calendarは執筆者を現在も募集中です．文字列アルゴリズムという名前とは裏腹に，その実態はアルゴリズムとデータ構造Advent Calendarになっているので，どなたもお好きな内容で気軽に参加できます．よろしくお願いします．

---

1. 文字列大好き人間のためにいっておくと，この記事通して整数アルファベットを仮定します． ↩

2. Anselm Blumer, Janet Blumer, David Haussler, Ross M. McConnell, and Andrzej Ehrenfeucht. Complete inverted files for efficient text retrieval and analysis. Journal of the ACM, 34(3):578–595, 1987. ↩

3. Mathieu Raffinot. On maximal repeats in strings. Information Processing Letters, 80(3):165–169, 2001. ↩

4. Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa, Giancarlo Mauri, Giulio Pavesi. On-line construction of compact directed acyclic word graphs. Discrete Applied Mathematics, 146(2):156-179, 2005. ↩

5. LZやBWT，文法圧縮ほど小さくなるわけではないですが．．． ↩

6. Djamal Belazzougui, Fabio Cunial, Travis Gagie, Nicola Prezza, and Mathieu Raffinot. Composite repetition-aware data structures. In Proceedings of the 26th Annual Symposium on Combinatorial Pattern Matching (CPM 2015), volume 9133 of LNCS, pages 26–39. Springer, 2015. ↩

7. Takuya Takagi, Keisuke Goto, Yuta Fujishige, Shunsuke Inenaga, Hiroki Arimura. Linear-Size CDAWG: New Repetition-Aware Indexing and Grammar Compression. In Proceedings of the 24th International Symposium on String Processing and Information Retrieval (SPIRE 2017), volume 10508 of LNCS, pages 304-316. Springer, 2017. ↩

8. Djamal Belazzougui, Fabio Cunial. Fast Label Extraction in the CDAWG. In Proceedings of the 24th International Symposium on String Processing and Information Retrieval (SPIRE 2017), volume 10508 of LNCS, pages 304-316. Springer, 2017.  ↩