アルゴリズム
bdd
データ構造
ZDD
sdd

本記事は「データ構造とアルゴリズム Advent Calendar 2018」16 日目の記事です(が,遅刻しました.すみません...)

15 日目は @goonew 氏による「SLPとCDAWG,RLBWTからString Attractorsが作れることを見る」,

17 日目は @matsu7874 氏による「2次元の凸包を求めるアルゴリズムと応用について」です.


はじめに

Sentential Decision Diagram (SDD)1 は 2011 年に提案された論理関数を表すデータ構造です.

従来,論理関数を表すデータ構造として Binary Decision Diagram (BDD)2 が知られていましたが,SDD は BDD の一般化であり,BDD より小さく論理関数を表現できうることや,BDD で行える様々な操作が SDD でも同様に行えることがわかっています.

そんな SDD ですが,BDD よりも一見複雑な構造をしているためか,まだあまり広まっていないように思います(私見です).

そこでこの記事では SDD の「読み方」を理解すること目標として,SDD を紹介したいと思います.

BDD を知らない人も多いと思うので,まずさっと BDD を紹介したのちに,SDD の紹介をします.

書ききれなかったので,わからないところがあったら @yurahuna に聞いてください


ポイント

SDD にせよ BDD にせよ,基本原理は場合分けによって論理関数を再帰的に分割するというところにあります.

SDD と BDD は場合分けの方法が違うだけということがわかっていると,SDD が理解しやすくなると思います.


Binary Decision Diagram (BDD)

BDD は論理関数を表現するデータ構造です.

この記事では軽く触れるに留めますが,

詳細な定義については昨年のアドベントカレンダーの @tsukasa_diary 氏の記事をご参照ください.

以下,写像 $f \colon \{0, 1\}^N \to {0, 1}$ を($N$ 変数)論理関数とします.

また,英大文字(例:$X$)で変数の集合を,英小文字(例:$x$)で変数を表すことにします.

BDD は以下の Shannon 分解に基づいて,論理関数を再帰的に分割します.

$$ f = (\neg x \land f_{x=0}) \lor (x \land f_{x=1})$$

$x$ は変数を,$\neg x$ はその否定を表し,$\land, \lor$ はそれぞれ論理積・論理和を表します.

$f_{x=0}, f_{x=1}$ はそれぞれ $f$ において $x$ に $0, 1$ を代入したものを表します.

つまり,Shannon 分解とは変数を1つ選び,それが0か1かで場合分けする操作とみなすことができます.

BDD を作るときは,変数間に適当に線形順序を定め3,その順序に従って Shannon 分解を再帰的に適用していきます.

すると最後の変数を処理し終えるまでには必ず,論理関数は恒真関数 $\top$ または恒偽関数 $\bot$ となります.

この過程を表現したものが BDD です.

たとえば,論理関数 $f = (a \land b) \lor (b \land c) \lor (c \land d)$ を表す BDD4 は,変数順序を $a < b < c < d$ と定めたとき,次の図1のように描けます.

図1において,ラベル $x$ を持つ丸いノードから出る点線の指す先が $f_{x=0}$ を,実線の指す先が $f_{x=1}$ を表します.

s_図1.png

図1を見ると,各ノードで,そのノードに対応する変数が0か1かで2つに分岐することがわかります.

これが BDD の "Binary Decision Diagram" と言う名前の表すところです.

結局 BDD とは,変数を1つずつ見て,それが0か1かで場合分けしていく構造であると言うことができます.


Sentential Decision Diagram (SDD)

SDD も BDD と同じく論理関数を表すデータ構造です.

BDD では Shannon 分解に基づいて論理関数を再帰的に分割しましたが,

SDD では Shannon 分解を一般化した $(X, Y)$-partition によって論理関数を再帰的に分割します.

$(X, Y)$-partition を定義するために,まずは $(X, Y)$-decomposition を定義します.

$X, Y$ を互いに素な変数集合とします.論理関数 $f(X, Y)$ が

$$ f(X, Y) = (p_1(X) \land s_1(Y)) \lor \dots \lor (p_n(X) \land s_n(Y))$$

と書けるとき,$\{(p_1, s_1), \dots, (p_n, s_n)\}$ を $f$ の $(X, Y)$-decomposition と言います.

各 $(p_i, s_i)$ を decomposition の element といい,各 $p_i$ を prime, 各 $s_i$ を sub と言います.

$f$ の $(X, Y)$-decomposition $\alpha = \{(p_1, s_1), \dots, (p_n, s_n)\}$ が次のすべての条件を満たすとき,それを $(X, Y)$-partition と言います.


  • $\forall i \in [n], p_i \neq \bot$

  • $\forall i, j \in [n], i \neq j \Rightarrow p_i \land p_j = \bot$

  • $\bigvee_{i=1}^{n} p_i = \top$

つまり,prime による場合分けが「空な場合を含まず,互いに排反かつすべてを満たしている」という意味です(この意味で "partition" と言うのでしょう).

Shannon 分解は,変数を1つ選び,それが0か1かで場合分けするのでした.

一方で,$(X, Y)$-partition は,変数の集合 $X$ を選び,$X$ に属する変数たちがどのような値を取るかで場合分けする操作 であると言えます.

Shannon 分解よりも,分解の仕方がざっくりしているわけです.

この意味で,$(X, Y)$-partition は Shannon 分解の一般化であると言えます.

$(X, Y)$-partition において,$X$ がちょうど1つの変数からなる場合が Shannon 分解に対応しています.

BDD は変数を 1 つずつ選んで場合分けしていくので,変数順序は線形順序でした.

一方,SDD の変数順序は vtree5 という木構造で表されます.

vtree は根付きの二分木で,葉が論理変数と1対1に対応します.

ただし vtree は順序木です.つまり,左の子と右の子を区別します.

SDD を作るときは,vtree を根からたどって,今いる vtree の頂点の左の子の部分木の葉にある変数たちを $X$, 右の子の部分木の葉にある変数たちを $Y$ として $(X, Y)$-partition を構成することを再帰的に繰り返します.

例として,論理関数 $f = (a \land b) \lor (b \land c) \lor (c \land d)$ を表す SDD と,その変数順序を定める vtree を図2に示します.

s_図2.png

図2(a)は vtree を表していて,葉には対応する変数,葉以外の頂点には頂点番号を記しています.

図2(b)は丸ノードが1つの $(X, Y)$-partition を表していて,四角形が2つ並んだやつが $(X, Y)$-partition の element を表しています.左の四角が prime, 右の四角が sub に対応しています.

また,丸ノードに書かれた整数は対応する vtree の頂点番号を意味します6

図2の SDD が $f = (a \land b) \lor (b \land c) \lor (c \land d)$ を表していることを確かめてみましょう.

まず,下の段の丸ノードから読むと,一番左の丸ノードはラベルが 2 なので,vtree の頂点 2 に対応しています.

vtree の頂点 2 は左の子が $b$, 右の子が $a$ なので,$(\{b\}, \{a\})$-partition を作れと言っています.

結局,一番左の丸ノードは $(b \land a) \lor (\neg b \land \bot) = a \land b$ を表しています.

同様に,中央の丸ノード(ラベル2)は $(\neg b \land \bot) \lor (b \land \neg a) = \neg a \land b$ を表します.

次に,一番右の丸ノードはラベルが 3 なので,vtree の頂点 3 に対応しています.

vtree の頂点 3 は左の子が $d$, 右の子が $c$ なので,$(\{d\}, \{c\})$-partition を作れと言っています.

結局,一番右の丸ノードは $(d \land c) \lor (\neg d \land \bot) = c \land d$ を表しています.

最後に,一番上の丸ノードはラベルが 1 なので vtree の頂点 1 に対応しています.

vtree の頂点 1 は左の子の部分木に変数 $a, b$ があり,右の子の部分木に変数 $c, d$ があるので,$(\{a, b\}, \{c, d\})$-partition を作れと言っています.

結局,一番上の丸ノードは $((a \land b) \land \top) \lor ((\neg a \land b) \land c) \lor (\neg b \land (c \land d))$ を表しています.

これは確かに $f = (a \land b) \lor (b \land c) \lor (c \land d)$ の $(\{a, b\}, \{c, d\})$-partition になっています.

結局7,一番上のノードは変数の集合 $X = \{a, b\}$ に対し,$X$ が $a \land b$ であるか,$\neg a \land b$ であるか,$\neg b$ であるかで場合分けしていたわけです.

これが SDD が "Sentential(文による?)Decision Diagram" と呼ばれる所以のようです.


おわりに

この記事では,論理関数を表すデータ構造である SDD を(読み方だけですが)紹介しました.

この記事では紹介しませんでしたが,2016 年には BDD の親戚である ZDD を SDD-like な構造に拡張した Zero-suppressed Sentential Decision Diagram (ZSDD)8 が提案されています.

SDD が BDD の一般化であるのと同様に,ZSDD は ZDD の一般化です.

また,文字列集合を表現する Sequence Decision Diagram (SeqBDD)9 を拡張した Sequence Sentential Decision Diagram10 も提案されています.

SeqBDD は昨年のアドベントカレンダーの @shu-den 氏の記事で紹介されています.

本当は SDD の Apply 演算や,ZSDD の implicit partitioning が zero-suppress そのものであることも書きたかったのですが,それはまたの機会ということで...11





  1. Adnan Darwiche. SDD: A new canonical representation of propositional knowledge bases. In IJCAI Proceedings-International Joint Conference on Artificial Intelligence, volume 22, page 819, 2011. 



  2. Randal E Bryant. Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers, 100(8):677–691, 1986. 



  3. 変数順が定まっている BDD を特に OBDD ということもあります. 



  4. 変数順が定まっているだけだと1つの論理関数に対して BDD は一意に定まらず,図1の BDD はあくまで例です.いくつか追加のルールを課すと一意になります. 



  5. おそらく variable(変数)tree の略 



  6. vtree の頂点と SDD の頂点が紛らわしいので,vtreeに対しては「頂点」,SDDに対しては「ノード」と言うことにします. 



  7. 結局って言いすぎだけど便利なので使ってしまう 



  8. Masaaki Nishino, Norihito Yasuda, Shin-ichi Minato, and Masaaki Nagata. Zero-suppressed sentential decision diagrams. In AAAI, pages 1058–1066, 2016. 



  9. Elsa Loekito, James Bailey, and Jian Pei. A binary decision diagram based approach for mining frequent subsequences. Knowledge and Information Systems, 24(2):235–268, 2010. 



  10. Shuhei Denzumi. Sequence sentential decision diagrams. In proceedings of the 12th International Conference on Combinatorial Optimization and Applications, COCOA 2018, pages 592–606, 2018. 



  11. そもそもマニアックすぎるので需要があるのかという説もあります.