BDDとZDDを下から読んで再帰アルゴリズムを作る

本記事は「データ構造とアルゴリズム Advent Calendar 2018」21日目の記事です。前後の記事は

• 20日目: @fuuki 氏による「メカニズムデザインのアルゴリズム（安定結婚問題）」
• 22日目: @MatsuTaku 氏による「Numbered Automaton による文字列の完全ハッシュ」

となっています。

本記事のタグにある「bdd」は、勝手に小文字になっているので気にしないでください。

はじめに

本記事では、集合族を圧縮表現するデータ構造である Binary Decision Diagram (BDD) ¹ と Zero-suppressed Binary Decision Diagram (ZDD) ² について、

• BDDとZDDの再帰構造
• その再帰構造を利用した再帰アルゴリズム

を解説します。この内容を選んだ理由は

• よくあるBDDとZDDの解説では上 (根節点) から読んで終わりがちであるため
• BDDとZDDの本質は下 (終端節点) から読まないとわからないという宗教を生やすため

です。知らんけど。

BDD は、論理関数を圧縮表現するものとして紹介されることが多いですが、ここでは集合族を表現するという文脈で話します。論理関数と集合族に対応関係があることは説明しません。

BDDとZDDの導入（上から読む）

一応は私の過去の記事を読むとわかるんですが、細かくて読むの面倒だと思うので改めて短く解説します。

今、集合 $S = \{s_1, \ldots, s_n\}$ 上の集合族を扱うとします。このとき、BDDとZDDは下図のようなラベル付きの階層的な有向グラフです。たまたま、各ラベルの節点が1つずつしかないですが、同じラベルの節点が複数存在していても構いません。

BDDとZDDは、1 つの根節点 $\rho$ と 2 つの終端節点 $\bot, \top$ を持ちます。上の図で言うと、1のラベルを持つ節点が $\rho$ です。このとき、非終端節点についているラベル $i$ は、その節点が $s_i$ に紐付いていることを表します。以下では、非終端節点 $\alpha$ のラベルを $\ell(\alpha)$ と書くことにします。各非終端節点は 2 つの出枝を持ち、 $\rho$ から終端へのパスを考えたとき、これらは以下の意味を持ちます。

• 0-枝（点線）： $s_{\ell(\alpha)}$ を「省く」
• 1-枝（実線）： $s_{\ell(\alpha)}$ を「含める」

このとき、「省く」とも「含める」とも言われない要素が存在し得ます。BDDとZDDでは、そのような要素の扱い方が以下のように異なります。

• BDDではドントケア（省いても含めてもよい）とする
• ZDDでは省いたことにする

そして、BDDとZDDが表す集合族は、 $\rho$ から $\top$ へのパスが表す部分集合からなります。すると、上図のBDDとZDDは、いずれも集合族 $\{\{s_1,s_2,s_3\},\{s_1,s_3\},\{s_3\}\}$ を表していることがわかります。

下から読む

では次に、BDDとZDDを下（ $\bot$ と $\top$ の側）から読んで見ましょう。

各節点 $\alpha$ について、 $\alpha$ から $\top$ へのパスで表される集合族を、BDDでは $\mathcal{B}(\alpha)$ と書き、ZDDでは $\mathcal{Z}(\alpha)$ と書くことにします。また、$\alpha$ の $x$-枝（$x \in \{0,1\}$）が指す節点を $\alpha_x$ と書くことにします。このとき、BDDとZDDを下から読むことは、

• $\mathcal{B}(\alpha)$ を $\mathcal{B}(\alpha_0)$ と $\mathcal{B}(\alpha_1)$ から構成する
• $\mathcal{Z}(\alpha)$ を $\mathcal{Z}(\alpha_0)$ と $\mathcal{Z}(\alpha_1)$ から構成する

ことです。

ZDDを下から読む

まずは、わかりやすいと思われる、ZDDから見ていきます。$\bot$ だけのZDDでは、$\top$ に至るパスがないので、 $\mathcal{Z}(\bot) = \emptyset$ であることが容易にわかります。 $\top$ だけのZDDでは、枝がないパスがただ 1 つ存在するとみなせるので、 $\mathcal{Z}(\top) = \{\emptyset\}$ であることが容易にわかります。

では、 一般に $\mathcal{Z}(\alpha)$ はどう表せるでしょうか？これには、 $\mathcal{A} \subseteq 2^S$（集合族） および $s_i \in S$ （要素）に対する次の演算子を定義します。

\mathcal{A} \Join s_i := \{A \cup \{s_i\} \mid A \in \mathcal{A}\}

このとき、 $\mathcal{Z}(\alpha)$ は以下の再帰式で定まります。

\mathcal{Z}(\alpha) = \left\{
\begin{array}{}
\emptyset & (\alpha = \bot)\\
\{\emptyset\} & (\alpha = \top)\\
\mathcal{Z}(\alpha_0) \cup \bigl(\mathcal{Z}(\alpha_1) \Join s_{\ell(\alpha)}\bigr) & (otherwise)
\end{array}
\right.

0-枝側の集合族をそのままに、1-枝側の集合族に $s_{\ell(\alpha)}$ を結合して併合するだけの簡単なお仕事です。上から読むときの規則からもそれはそうだろうとなります。図で書くと以下のようになります。根の再帰部分だけ色を付けています。

BDDを下から読む

次に、BDDを下から読みます。 $\bot$ だけのBDDでは、ZDDと同様に、 $\mathcal{B}(\bot) = \emptyset$ であることが容易にわかります。 $\top$ だけのBDDでは、任意の要素がドントケアになり、$\mathcal{B}(\top) = 2^S$ となります。

では、 一般に $\mathcal{B}(\alpha)$ はどう表せるでしょうか？
これには、 $\mathcal{A} \subseteq 2^S$（集合族） および $s_i \in S$ （要素）に対する次の 2 つの演算子を定義します。

\mathcal{A} \Delta^+ s_i := \{A \in \mathcal{A} \mid s_i \in A\}

\mathcal{A} \Delta^- s_i := \{A \in \mathcal{A} \mid s_i \notin A\}

このとき、 $\mathcal{B}(\alpha)$ は以下の再帰式で定まります。

\mathcal{B}(\alpha) = \left\{
\begin{array}{}
\emptyset & (\alpha = \bot)\\
2^S & (\alpha = \top)\\
\bigl(\mathcal{B}(\alpha_0) \Delta^- s_{\ell(\alpha)}\bigr) \cup \bigl(\mathcal{B}(\alpha_1) \Delta^+ s_{\ell(\alpha)}\bigr) & (otherwise)
\end{array}
\right.

0-枝側からは $s_{\ell(\alpha)}$ を持たないやつを引っ張り出し、1-枝側からは $s_{\ell(\alpha)}$ を持つやつを引っ張り出し、それらを併合します。節点 $\alpha$ に来たときに、 $s_{\ell(\alpha)}$ のドントケアが解除されることがポイントです。それ以前は、必ず $s_{\ell(\alpha)}$ はドントケアです。図で書くと以下のようになります。根の再帰部分だけ色を付けています。

これらの再帰式こそ、BDDとZDDの本質だという宗教を筆者は生やしたいです。知らんけど。

BDDとZDDの再帰アルゴリズム

上で示した再帰式から、BDDとZDDを用いた様々な再帰アルゴリズムを考えることができます。ここでは、 4 つの例を示します。

数え上げ

BDDとZDDが表現する集合族の大きさを求めます。すなわち、$\bigl|\mathcal{B}(\rho)\bigr|$ と $\bigl|\mathcal{Z}(\rho)\bigr|$ を求めます。これは、上の再帰式と対応を取り、うまく再帰式を導出することで達成されます。

ZDDに対しては、以下の再帰式が簡単に導出されます。

\bigl|\mathcal{Z}(\alpha)\bigr| = \left\{
\begin{array}{}
0 & (\alpha = \bot)\\
1 & (\alpha = \top)\\
\bigl|\mathcal{Z}(\alpha_0)\bigr| + \bigl|\mathcal{Z}(\alpha_1)\bigr| & (otherwise)
\end{array}
\right.

それはそう。
そして、BDDに対しては、以下の再帰式を導出できます。

\bigl|\mathcal{B}(\alpha)\bigr| = \left\{
\begin{array}{}
0 & (\alpha = \bot)\\
2^{|S|} & (\alpha = \top)\\
\frac{\bigl|\mathcal{B}(\alpha_0)\bigr| + \bigl|\mathcal{B}(\alpha_1)\bigr|}{2} & (otherwise)
\end{array}
\right.

0-枝側と1-枝側から半分ずつ持ってくるのでこうなる。

よって、これらの再帰式に従って、終端から値を生めていくアルゴリズムを作ればOKです。

生起確率の計算

各要素の出現確率を表す関数 $p \colon S \rightarrow [0,1]$ が与えられたとき、部分集合 $A \subseteq S$ に対して

p(A) := \prod_{s_i \in A} p(s_i)

とします。また、集合族 $\mathcal{A} \subseteq 2^S$ に対して

p(\mathcal{A}) := \sum_{A \in \mathcal{A}} p(A)

とします。$p(\mathcal{A})$ は $S$ から $p$ に従ってランダムサンプリングした部分集合が $\mathcal{A}$ に含まれている確率です。このとき、 $p(\mathcal{B}(\rho))$ および $p(\mathcal{Z}(\rho))$ を簡単に求めることができます。

これも再帰式を書きます。ZDDでは、どーーーーーーーーーーーーーーーーーーん！！！（そろそろ雑になってきましたね？？？）

p(\mathcal{Z}(\alpha)) = \left\{
\begin{array}{}
0 & (\alpha = \bot)\\
\prod_{s_i \in S} (1 - p(s_i)) & (\alpha = \top)\\
p(\mathcal{Z}(\alpha_0)) + p(\mathcal{Z}(\alpha_1)) \frac{p(s_{\ell(\alpha)})}{(1 - p(s_{\ell(\alpha)}))} & (otherwise)
\end{array}
\right.

はじめは誰もいない。そこに誰かをいたことにしていく。そんなイメージになります。

BDDでは、どーーーーーーーーーーーーーーーーーーん！！！

p(\mathcal{B}(\alpha)) = \left\{
\begin{array}{}
0 & (\alpha = \bot)\\
1 & (\alpha = \top)\\
p(\mathcal{B}(\alpha_0)) \bigl(1 - p(s_{\ell(\alpha)})\bigr) + p(\mathcal{B}(\alpha_1)) p(s_{\ell(\alpha)}) & (otherwise)
\end{array}
\right.

はじめは皆いる。その後は、自分がいない確率を 0-枝側に、自分がいる確率を 1-枝側にかける。ね、簡単でしょ？

これもまた、これらの再帰式に従って、終端から値を生めていくアルゴリズムを作ればOKです。

最大化

各要素の重みを表す関数 $w \colon S \rightarrow N$ が与えられたとき、部分集合 $X \in \mathcal{B}(\rho)$ または $X \in \mathcal{Z}(\rho)$ であって、以下を最大化するものを求めよ。

w(X) := \sum_{s_i \in X} w(s_i)

宿題にします！！！（は？？？）
例を示すといったがアレは嘘だ。疲れたもん。

和集合演算

2 つのBDD $\mathcal{B}$ と $\mathcal{B}'$ またはZDD $\mathcal{Z}$ と $\mathcal{Z}'$ が与えられたとき、 $\mathcal{B}(\rho) \cup \mathcal{B}'(\rho')$ または $\mathcal{Z}(\rho) \cup \mathcal{Z}'(\rho')$ を表す BDD、ZDDを求めます。

面倒になってきたし、ここは長くなりそうなので、ZDDの場合だけ再帰式を示します。
2つのZDDが表す集合族の再帰式を $\cup$ で併合すれば、以下の再帰式を得ます (終端部分はもう少し工夫できます）。ここで、再帰対象となる節点のラベルが異なる場合だけ注意が必要です。

\mathcal{Z}(\alpha) \cup \mathcal{Z}'(\alpha') =
\left\{
\begin{array}{}
\emptyset & (\alpha = \alpha' = \bot)\\
\{\emptyset\} & (両方終端で一方が\top)\\
\bigl(\mathcal{Z}(\alpha_0) \cup \mathcal{Z}'(\alpha')\bigr) \cup \bigl(\mathcal{Z}(\alpha_1) \Join s_{\ell(\alpha)}\bigr) & (\ell(\alpha) < \ell(\alpha'))\\
\bigl(\mathcal{Z}(\alpha_0) \cup \mathcal{Z}'(\alpha'_0)\bigr) \cup \bigl((\mathcal{Z}(\alpha_1) \cup \mathcal{Z}'(\alpha'_1)) \Join s_{\ell(\alpha)}\bigr) & (otherwise)
\end{array}
\right.

ただし、$\ell(\alpha) \leq \ell(\alpha')$ となるように、毎回適宜 swap をしてください。

ここで、$Cup(\alpha, \alpha')$ を $\mathcal{Z}(\alpha) \cup \mathcal{Z}'(\alpha')$ のZDDを生成しその根を返す関数とし、
$MakeNode(\alpha_0, \alpha_1, i)$ を 0-枝の先に $\alpha_0$ を 1-枝の先に $\alpha_1$ を持つようなラベル $i$ の新しい節点を生成する関数とします。
このとき、上記の再帰式からZDDを構築する以下の再帰関数を得ます。

Cup(\alpha, \alpha') =
\left\{
\begin{array}{}
return~\bot & (\alpha = \alpha' = \bot)\\
return~\top & (両方終端で一方が\top)\\
return~MakeNode(Cup(\alpha_0, \alpha'), \alpha_1, \ell(\alpha)) & (\ell(\alpha) < \ell(\alpha'))\\
return~MakeNode(Cup(\alpha_0, \alpha'_0), Cup(\alpha_1, \alpha'_1), \ell(\alpha)) & (otherwise)
\end{array}
\right.

この関数に従ってメモ化したアルゴリズムを使うと、2つのZDDの任意の節点ペアに対して高々1回だけ $Cup$ が評価されるので、2つのZDDの節点数の積に依存した計算時間で、和集合をとった新たなZDDが構築できます。

おわりに

本記事では、BDDとZDDの再帰構造を説明し、そこからいくつかの再帰アルゴリズムを導出しました。本記事で挙げた再帰式はかなり有用だと思うので、BDDやZDDを使う時には思い出してあげて欲しいです。

また、BDDとZDD上での演算は今回紹介した和集合以外にもたくさんあるので、それらを調べてみたり自分で設計してみたりするのも面白いと思います。

ところで、BDDとZDDの再帰アルゴリズムの導入にあたって、BDDとZDDが表す集合族の再帰式から入る文献ってほぼ見たことがないんですよね。2018/12/25に最終提出を控えている僕のD論（頭が無理無理言ってる）では演算以外の再帰アルゴリズムにそこそこ触れているので、もし使うことがあればリファーしていただけるとすごく嬉しいけど恥ずかしいですね（ダイレクトマーケティング）。だけど、僕のD論では「BDDとZDDを上から作るの最高！」という立場なので、今回の話はお供として添えるだけです。

参考文献

1. Randal E. Bryant. "Graph-Based Algorithms for Boolean Function Manipulation", IEEE Transactions on Computers, C-35(8):677–691, 1986. ↩

2. Shin-ichi Minato. "Zero Suppressed BDDs for Set Manipulation in Combinatorial Problems", 1993. ↩