実質上位互換な記事を書いてしまったのでこちらをどうぞ「BDDとZDDを下から読んで再帰アルゴリズムを作る」
本記事は「文字列アルゴリズム Advent Calendar 2017」10日目の記事です．前後の記事は以下の通りです．
- 9日目: @okateim 氏による「最短超文字列問題」
- 11日目: @yoshikyoto 氏による「PHPでしりとりをして Code Quest の連鎖ノ試練をクリアする」です．
えー、割と良くない体調の中で書いたので色々と多めにみていただきたく…
あ，図も書いてないですね…手元にいい感じに図を描けるものが無いので後日…とりあえず Wikipedia で代用…
はじめに
本記事で扱うトピックは Binary Decision Diagram (BDD) ，および Zero-suppressed Binary Decision Diagram (ZDD) というデータ構造です．これらはそれぞれ，計算機科学でしばしば議論されているブール関数，および集合族を効率良く扱うことができるデータ構造です．具体的には，
- 圧縮: ブール関数の主加法標準形，および集合族のリスト表現の長さよりも真に大きくはならず，指数的に小さくなる事例が多い (実メモリ的には定数倍を除いて考えています) ．
- クエリ応答: メンバーシップクエリ，要素数のカウント，ランダムサンプリング，ある種の確率に関する数値計算，ある種の目的関数に対する最適解探索，etc... を高速に処理できる．
- 演算: ブール関数，および集合族に関する様々な二項演算 (三項以上の演算もあり) を圧縮されたデータ構造上で計算する．これらの演算を総称して Apply 演算と呼ぶ．
などの性質，機能を備えたリッチなデータ構造となっています．
BDD はブール関数を圧縮処理することに特化しています．Bryant による効率的なアルゴリズム (圧縮技法，Apply 演算) の発見 [文献 1，1986] を期に大きく発展してきました．応用としては VLSI 設計，制約充足問題，システムの故障解析などが挙げられます．本記事では，構造の説明と BDD 上での Apply 演算の紹介，確率計算に関する解説をします．
ZDD は BDD の派生系で集合族を圧縮処理することに特化しています．湊により考案され [文献 2，1993] ， BDD の改良技術として注目を浴びています．特に，Knuth の著書 The Art of Computer Programming に，1つの章として取り上げられています．略記はもともと ZBDD だったらしいのですが，考案者が Knuth に ZDD の方が良いよと言われて以降，ほとんどの場合で ZDD と略されているようです．VLSI 設計，組合せ問題，データマイニングの分野などに応用があります．本記事では，構造の説明と ZDD 上での Apply 演算の紹介，組合せ最適化に関する解説をします．
準備
準備をしっかり書こうかなとも思いましたが，そんなに必要ない気がしたので簡潔に書きます．
-
ブール関数: 論理演算 $\lor, \land, \ldots$ を用いて記述でき，長さ $n$ の 0-1 ベクトルを入力とする関数 $f\colon \{0,1\}^n \rightarrow \{0,1\}$ を $n$ 変数ブール関数と呼びます．本記事では， $f$ への入力を $\boldsymbol{x} = (x_1,x_2,\ldots,x_n) \in \{0,1\}^n$ と表記し，各 $x_i~(i \in \{1,\ldots,n\})$ を変数と呼びます．また， $f$ のいくつかの変数に値を代入して得られるブール関数を $f$ の部分ブール関数と呼ぶことにします．
-
集合族: $n$ 要素からなる台集合 $U$ に対して， $\mathcal{X} \subseteq 2^U$ を $U$ 上の集合族と呼びます． $2^U$ は冪集合のことです．本記事では， $U = \{1,2,\ldots,n\}$ として考え，各 $i \in U$ をアイテム， $X \in \mathcal{X}$ を要素と呼び分けます．また，アイテムの集合のことを組合せと呼ぶこともあります．
続く 2 つの節では， BDD と ZDD それぞれの構造を淡々と説明します．
BDD
$n$ 変数ブール関数を表す BDD は，ノード集合 $N$ と 3 つの写像 $\ell,c_0,c_1$ を用いて $\mathcal{D} = (n,N,\ell,c_0,c_1)$ と書くことができます．本記事では，$\mathcal{D}$ が表現するブール関数を $f[\mathcal{D}]$ と書くことにしましょう．また，$\mathcal{D}$ のノード数について $S(\mathcal{D}) = |N|$ とします．$\ell \colon N \rightarrow \{1,\ldots,n+1\}$ は，ノード集合を $n+1$ 個の層 $N_i = \{\alpha \mid \ell(\alpha) = i\}~(i \in \{1,\ldots,n+1\})$ に分割します．根と呼ばれるノード $\rho \in N$ が 1 つ存在し， $r = \ell(\rho)$ としたとき $N_{i < r} = \emptyset,~N_r = \{\rho\}$ です．終端と呼ばれる 2 つのノード $\bot, \top \in N$ が存在し， $N_{n+1} = \{\bot,\top\}$ です．$c_b \colon N \setminus \{\bot,\top\} \rightarrow N~(b \in \{0,1\})$ は，終端を除く各ノードに対して $b$-子 と呼ばれるノードをただ 1 つ定めます．ここで， $\ell(\alpha) < \ell(c_b(\alpha))$ が成り立ちます．これらを図示すると有向非巡回グラフを成していることがわかります．また，どのような経路でも $\bot,\top$ のいずれかにたどり着くこともわかります．
長さ $k$ のノード列 $\boldsymbol{\pi} = (\pi_1,\ldots,\pi_k) \in N^k$ について， $\forall j \in \{1,\ldots,k-1\},~\exists b \in \{0,1\},~c_b(\pi_j) = \pi_{j+1}$ であるとき， $\boldsymbol{\pi}$ を $\mathcal{D}$ 上のパスと呼びます．このとき，パス $\boldsymbol{\pi}$ は $\forall j \in \{1,\ldots,k-1\}$ について $c_b(\pi_j) = \pi_{j+1}$ であるとき $x_{\ell(\pi_j)} = b$ となるような部分的な変数割当を表現します．ここで，ノード $\alpha$ から $\beta$ へのパスすべてからなる集合を $\mathit{PATH}(\alpha, \beta)$ とします．すると， $\mathit{PATH}(\rho, \top)$ は $f[\mathcal{D}]$ を真にする変数割当すべてを表現します．
BDD には次のような簡約化規則があります．
- 削除規則: $c_0(\alpha) = c_1(\alpha)$ であるようなノード $\alpha$ を削除します．削除手続きは， $\alpha$ の子を $\beta$ として， $c_b(\gamma) = \alpha$ であるようなすべての $b, \gamma$ の組に対して $c_b(\gamma) \leftarrow \beta$，および $N \leftarrow N \setminus \{\alpha\}$ とすることで行います．
- 共有規則: $\forall b \in \{0,1\}, c_b(\alpha) = c_b(\beta)$ であるような 2 つのノード $\alpha, \beta$ を共有します．共有手続きは， $c_b(\gamma) = \alpha$ であるようなすべての $b, \gamma$ の組に対して $c_b(\gamma) \leftarrow \beta$，および $N \leftarrow N \setminus \{\alpha\}$ とすることで行います．
[ここに図を入れる]
これらを任意の順序で適用し続けると，これ以上簡約化できない形になり，それを既約な BDD と呼びます．任意のブール関数に対して，変数順序を固定したとき，既約な BDD は一意に定まることが知られています． 既約か前の BDD を $\mathcal{D}$ として，これを既約にするためにかかる計算時間はなんと $O(S(\mathcal{D}))$ です．
ところで，あるノード $\alpha \in N$ について，あるパス $\boldsymbol{\pi} \in \mathit{PATH}(\rho, \alpha)$，および $\alpha$ を根とみなしそれ以下のノードからなる BDD $\mathcal{D}(\alpha)$ を考えると， $\mathcal{D}(\alpha)$ は $f[\mathcal{D}]$ に前述の変数割当規則に従って $x_{\ell(\alpha)-1}$ までを入力したときの部分ブール関数を表現しているとみなすことができます．つまり，共有規則は等価な部分ブール関数を 1 つのノードにまとめる規則に他なりません．また，削除規則は，部分ブール関数において 0-1 のいずれを代入しても出力に影響しない冗長な変数，すなわちドントケアな変数を削除することに対応します．これらは後々必要になる重要な性質です．
ZDD
BDD をブール関数を圧縮表現するデータ構造として紹介しましたが，ブール関数は集合族へ読み替えることが可能であるため，集合族を圧縮表現するデータ構造とも言えます．具体的には，ある変数割当 $\boldsymbol{x} = (x_1,x_2,\ldots,x_n) \in \{0,1\}^n$ について， $x_i = 0$ ならばアイテム $i$ を含まず，$x_i = 1$ ならばアイテム $i$ を含むと考えればよいです．しかし， BDD には集合族を表す上で冗長な表現が存在しています．これを解消したものが ZDD です．
$n$ アイテムからなる台集合上の集合族を表現する ZDD も同様の構造 $\mathcal{D}$ で記述できます．異なるのは，パスの読み方と削除規則です．本記事では， $\mathcal{D}$ が表現する集合族を $\mathcal{F}[\mathcal{D}]$ と書くことにしましょう．
ZDD におけるパスを表す長さ $k$ のノード列 $\boldsymbol{\pi}$ は，組合せ $U(\boldsymbol{\pi}) = \{i \in U \mid \exists j \in \{1,\ldots,k-1\},~\ell(\pi_j) = i,~c_1(\pi_j)=\pi_{j+1}\}$ を表現します．そして， $\mathit{PATH}(\rho, \top)$ は $\mathcal{F}[\mathcal{D}]$ を表現します．
ZDD の削除規則は以下の操作を行います．
- $c_1(\alpha) = \bot$ であるようなノード $\alpha$ を削除する．削除手続きは，
$\beta = c_0(\alpha)$ として，$c_b(\gamma) = \alpha$ であるようなすべての $b, \gamma$ の組に対して $c_b(\gamma) \leftarrow \beta$，および $N \leftarrow N \setminus \{\alpha\}$ とすることで行います．
[ここに図を入れる]
もちろん，既約な ZDD も存在します．任意の集合族に対して，アイテム順序を固定したとき，既約な ZDD は一意に定まることも知られています．
ZDD と BDD を比較したときに気になるのは，やはり削除規則でしょう． ZDD の削除規則は，集合族の表現にうまく特化したものになっています．どういうことかというと， ZDD において削除されるノード $\alpha$ は $c_1(\alpha) = \bot$ の条件を満たすので，あるパス $\boldsymbol{\pi} \in PATH(\rho, \alpha)$ により表現される組合せ $U(\boldsymbol{\pi})$ にそのアイテム $\ell(\alpha)$ を含めても， $\mathcal{D}$ が表現する集合族に現れない組合せしかできません．よって，ノード $\alpha$ は冗長であるというわけです．
たったこれだけの違いですが，疎な集合族 (各アイテムの出現頻度が低い) を BDD/ZDD それぞれで表現してみると， ZDD の方が 数百から数千倍も小さくなる事例があるということが経験的にわかっています．一方で， BDD とは逆にブール関数を表す上で冗長な変数，すなわちドントケアな変数が存在しているため，ブール関数の表現には向かない場合が多いです．
Apply 演算
BDD と ZDD はそれぞれ，ブール関数上の演算と集合族上の演算をサポートしています．だいぶ力尽きているので，ここは軽く紹介するだけにとどめます．BDD と ZDD は以下のような二項演算を $O(S(\mathcal{A})S(\mathcal{B}))$ 時間で計算します．
| 演算 | 入力 | 出力 |
|---|---|---|
| 論理和 | BDD $\mathcal{A}, \mathcal{B}$ | BDD $\mathcal{C}$: $f(\mathcal{C}) = f(\mathcal{A}) \lor f(\mathcal{B})$ |
| 論理積 | BDD $\mathcal{A}, \mathcal{B}$ | BDD $\mathcal{C}$: $f(\mathcal{C}) = f(\mathcal{A}) \land f(\mathcal{B})$ |
| 和集合 | ZDD $\mathcal{A}, \mathcal{B}$ | ZDD $\mathcal{C}$: $\mathcal{F}(\mathcal{C}) = \mathcal{F}(\mathcal{A}) \cup \mathcal{F}(\mathcal{B})$ |
| 積集合 | ZDD $\mathcal{A}, \mathcal{B}$ | ZDD $\mathcal{C}$: $\mathcal{F}(\mathcal{C}) = \mathcal{F}(\mathcal{A}) \cap \mathcal{F}(\mathcal{B})$ |
| 差集合 | ZDD $\mathcal{A}, \mathcal{B}$ | ZDD $\mathcal{C}$: $\mathcal{F}(\mathcal{C}) = \mathcal{F}(\mathcal{A}) \setminus \mathcal{F}(\mathcal{B})$ |
実は，これらの計算量が明らかにされたのは最近 [文献 3，2012] で，それまでは Bryant による $O(S(\mathcal{A}) + S(\mathcal{B}))$ という予想が信じられていました．とはいえ，このような予想がでるくらいですから，実用的な場面では $O(S(\mathcal{A})S(\mathcal{B}))$ よりかなり高速に動作する場合が多いです．多分，排他的論理和 $\oplus$ も同じ計算量になったと思うのですが，自信がないので表には入れていません．また，他にも高速な単項演算，二項演算は存在しています．
上記以外にも複雑な演算が多岐に渡ってサポートされているのですが，それらには綺麗な計算量保証が付いていない場合がほとんどで，実用的にもそれほど高速ではないです．しかし，便利なことに代わりはないので，応用で度々出現したり，現在でもたまに新しい演算が提案されたりしています．
確率計算と組合せ最適化
疲労がやばいんですが，頑張ります．まず，次のような問題を考えます．
- $n$ 変数ブール関数 $f$ の入力について，各変数 $x_i~(i\in\{1,\ldots,n\})$が 1 をとる確率 $p_i$ が与えられているとします．このとき， $f$ が真になる確率はいくらでしょうか．
このような計算は一般に #P-完全 と呼ばれる難しい計算複雑性のクラスに属します．しかし，$f$ を BDD で表現することさえできてしまえば， $O(S(\mathcal{D}))$ というシンプルな計算量で簡単に計算できてしまいます．
その仕組みは， BDD の各ノードが部分ブール関数を表現することと密接な関係があります．あるノード $\alpha$ が表す部分ブール関数が真になる確率を $P(\alpha)$ と書いて見ましょう．すると，以下の再帰式が浮かび上がってきます．
- $P(\top) = 1,\ P(\bot) = 0$
- $P(\alpha) = p_{\ell(\alpha)} \times P(c_1(\alpha)) + (1 - p_{\ell(\alpha)}) \times P(c_0(\alpha))$
これは，変数 $x_{\ell(\alpha)}$ に 1 を代入したときに真になる確率と 0 を代入したときに真になる確率を足し合わせたものになっています．すると， $f$ そのものを真にする確率は， $P(\rho)$ をこの再帰式に従って計算すれば求まります．これには動的計画法 (メモ化再帰) の技法により，一度計算したノードの計算結果を使い回せるので $O(S(\mathcal{D}))$ と高速に求められるわけです．
次に以下の問題を考えます．
- アイテム $i \in U$ が価値 $v_i$ を持つとします．このとき， $U$ 上の集合族 $\mathcal{X}$ の要素で，価値総和が最大となる要素はどれでしょうか．またその値はいくらでしょうか．
いわゆる組合せ最適化ですね．特に，目的関数が線形 (組合せ $X$ に対して $\sum_{i\in X} v_i$) である場合となっています．こちらも一般には NP-困難 であるような問題がたくさんあるわけですが， $\mathcal{X}$ を表現する ZDD があれば同様に $O(S(\mathcal{D}))$ で計算できてしまいます．そして，その仕組みもまた再帰式で簡単に記述できます．ノード $\alpha$ が表す集合族の中での最大コストを $V(\alpha)$ と書くことにすると，式は以下のとおりです．
- $P(\top) = 0,\ P(\bot) = -\infty$
- $V(\alpha) = \max\{v_{\ell(\alpha)} + V(c_1(\alpha)), V(c_0(\alpha))\}$
これは，アイテム $\ell(\alpha)$ を取るときの最大値と取らないときの最大値の大きい方を選択する，ということをしています．すると， $V(\rho)$ が最適値であり，そこまでの経路を復元すれば最適解を 1 つ取り出すことができます．これも動的計画法 (メモ化再帰) で簡単に計算できます．ちなみに， Apply 演算を駆使すると，最適値を持つ解すべてを表現する ZDD を取り出すこともできます (ここの計算量は最近ちょっと気にしている) ．
おわりに
ここまで読んでいただきありがとうございます．文字列アドベントカレンダーなので，本記事を通して BDD/ZDD がオートマトンぽいとか，文字列版の Decision Diagram はないのかとか思ってくれると嬉しいかもしれません．で，実は文字列版の Decision Diagram として Sequence Binary Decision Diagmra (SeqBDD) があります．気になる人は調べてみてください．
最後に身分を明かしますが，私は ZDD 考案者である湊先生の下で研究指導を受けている博士課程学生です． ZDD の誕生年が 1993 年で，私の誕生年が 1992 年なので惜しいなあとか思ったりしています．ところで，こんな記事を書いていて怖くないわけがないので，本記事は広めないでくださいね．約束です．
参考文献
- Randal E. Bryant. "Graph-Based Algorithms for Boolean Function Manipulation", IEEE Transactions on Computers, C-35(8):677–691, 1986.
- Shin-ichi Minato. "Zero Suppressed BDDs for Set Manipulation in Combinatorial Problems", 1993.
Ryo Yoshinaka, Jun Kawahara, Shuhei Denzumi, Hiroki Arimura and Shin-ichi Minato. "Counterexamples to the long-standing conjecture on the complexity of BDD binary operations", Information Processing Letters, 2012.