私のブックマーク
決定グラフを用いたデータ構造
科学技術振興機構 ERATO湊離散構造処理系プロジェクト 研究員
川原 純
はじめに
BDD (Binary Decision Diagram、二分決定グラフ) はn変数0/1論理関数を効率良く表現するデータ構造である。
BDDは80年代から90年代後半にかけて盛んに研究されており、
主にLSI回路設計やモデル検査の分野において広く使われる技術となった。
2000年代以降は、BDDやその派生形を、
データマイニングや知識発見、確率推論、列挙アルゴリズム設計、バイオインフォマティックス等、
情報科学の様々な分野に適用する動きが広がっている。
また、組合せ集合（集合族）を表現する ZDD（Zero-Suppressed BDD）や、文字列集合を表現する SeqBDD (Sequence BDD)、
置換の集合を表現する πDD (PiDD, Permutation DD) 等、
離散構造を処理するための、決定グラフを用いた種々のデータ構造が提案されている。
これらは対象を圧縮して表現するのみならず、
各種の集合演算や代数演算が圧縮表現のまま効率良く行えるという特徴をもつ。
本稿では決定グラフを用いたデータ構造に関して、新しい話題を中心にWeb上のリソースを紹介する。
解説記事・書籍
- BDD/ZDDを基盤とする離散構造と演算処理系の最近の展開, 電子情報通信学会 基礎・境界ソサイエティ Fundamentals Review, Vol. 4, No. 3, pp. 224–230, 2011.
湊 真一先生による解説記事（日本語）。BDD/ZDDの概要や最近の話題について解説されている。
http://w2.gakkai-web.net/gakkai/ieice/vol4no3pdf/vol4no3_224.pdf - The Art of Computer Programming Volume 4, Fascicle 1: Bitwise tricks & techniques; Binary Decision Diagrams, Addison-Wesley Professional, 2009. (書籍)
D. Knuth 先生による書籍。1節がBDD/ZDDに充てられている。数百問の演習問題と解答付き。
ドラフトが
http://www-cs-faculty.stanford.edu/~knuth/fasc1b.ps.gz
に公開されている。
The Art of Computer Programming のページ
http://www-cs-faculty.stanford.edu/~uno/taocp.html
に正誤表やその他の情報が掲載されている。 - An Introduction to Binary Decision Diagrams
H. Andersen 先生によるレクチャーノート。BDDに関する基礎的な事項を理解できる。
http://www.configit.com/fileadmin/Configit/Documents/bdd-eap.pdf - An Introduction to Zero-Suppressed Binary Decision Diagrams
A. Mishchenko 先生によるチュートリアル。ZDDに関する基礎的な事項を理解できる。
http://www.eecs.berkeley.edu/~alanmi/publications/2001/tech01_zdd.pdf - ZDDs – My notes
B. Lynn 氏による解説。ZDDを用いたパズル（数独やフィルオミノ等）の求解についても解説されている。
http://crypto.stanford.edu/pbc/notes/zdd/
その他、本誌 2012年5月号 pp. 232–237 「BDD/ZDDの技法と離散構造処理系」にBDD研究の歴史が解説されている。
ソフトウェアライブラリ
主要な処理系を紹介する。
- CUDD: CU Decision Diagram Package http://vlsi.colorado.edu/~fabio/CUDD/
Colorado大学のF. Somenzi先生による、最も使用されているBDD/ZDDライブラリの1つ。C,C++言語で記述されている。- Windows 環境にインストールする方法
http://www.technical-recipes.com/category/binary-decision-diagrams/ - CUDD Tutorial
http://www.cs.ucla.edu/~ethan/documents/schreiber_cudd_tutorial.pdf
- Windows 環境にインストールする方法
- BuDDy: http://sourceforge.net/projects/buddy/ (C,C++)
- CMU BDD: http://www.cs.cmu.edu/~modelcheck/bdd.html (C)
- JavaBDD: http://javabdd.sourceforge.net/ (Java)
- JDD: http://javaddlib.sourceforge.net/jdd/ (Java)
- BDD14/BDD15: http://www-cs-faculty.stanford.edu/~uno/programs.html
D. Knuth先生による、BDD/ZDD 処理系。CWEB (文芸的プログラミング) で書かれたソースコードを
C 言語に変換して用いる。 - SAPPORO BDD (非公開)
湊 真一先生による、C,C++言語用 BDD/ZDD/SeqBDD/πDD ライブラリ。公開を予定している。
http://eprints.lib.hokudai.ac.jp/dspace/bitstream/2115/48483/1/02_all.pdf (参考資料) - seqbdd: https://github.com/shu-den/seqbdd
伝住 周平氏による SeqBDD 処理系。Erlang で実装されている。筆者が確認した限り、公開されている唯一の SeqBDD 処理系である。 - bddbddb: http://bddbddb.sourceforge.net/
BDDを用いた演繹型関係データベースの実装。 - Java ソフトウェア解析のための bddbddb の使い方
http://sel.ist.osaka-u.ac.jp/~ishio/bddbddb/
に使用法が少し書かれている。 - miniBDD: http://www.cprover.org/miniBDD/
教育目的で書かれたC++ BDDライブラリ。
その他、様々な言語で実装された処理系が存在する。
- Ruby-BDD: http://people.cs.aau.dk/~adavid/BDD/
- Ocaml Implementation of binary decision diagrams: https://github.com/jdolecki/CS51-Final-Project
- lua-bdd: https://github.com/silentbicycle/lua-bdd
- MuDDy: ML interface to BuDDy https://github.com/kfl/muddy
- A shared, ordered binary decision diagram library written in Haskell: https://github.com/hguenther/bdd
- Haskell implementation of Reduced Ordered Binary Decision Diagrams: https://github.com/johnpmayer/robdd
研究の動向
決定グラフの最近の研究動向について、分野別に紹介する。以下の文献紹介は網羅的ではなく、
他にも様々な論文が存在する。
確率推論・ベイジアンネットワーク
BDD/ZDDをベイジアンネットワーク等の確率計算に用いる技法について、いくつか研究されている。
- M. Ishihata, Y. Kameya, T. Sato:
Variational Bayes inference for logic-based probabilistic models on BDDs.
Proc. of ILP, 2011.
http://ilp11.doc.ic.ac.uk/short_papers/ilp2011_submission_2.pdf - S. Minato, K. Satoh, T. Sato:
Compiling Bayesian networks by symbolic probability calculation based on zero-suppressed BDDs.
Proc. of IJCAI, pp. 2550–2555, 2007.
http://www.ijcai.org/papers07/Papers/IJCAI07-410.pdf - P. Prasad, A. Assi, A. Beg:
Binary Decision Diagrams and Neural Networks.
J. of Supercomputing, Vol. 39, No. 3, pp. 301–320, 2007.
http://www.azambeg.com/papers/docs/2007-03-01_JRN_binary-decision-diagrams-and-neural-networks.pdf
データマイニング
ZDDを用いてデータマイニングを行う研究がなされている。
- S. Minato, H. Arimura:
Efficient method of combinatorial item set analysis based on zero-suppressed BDDs.
Proc. of WIRI, pp. 4–11, 2005.
http://www-alg.ist.hokudai.ac.jp/~thomas/TCSTR/tcstr_04_1/tcstr_04_1.pdf - E. Loekito, J. Bailey:
Fast mining of high dimensional expressive contrast patterns using zero-suppressed binary decision diagrams.
Proc. of KDD, pp. 307–316, 2006.
http://ww2.cs.mu.oz.au/~jbailey/papers/rtfp343-loekito.pdf - S. Minato, T. Uno, H. Arimura:
LCM over ZBDDS: fast generation of very large-scale frequent itemsets using a compact graph-based representation.
Proc. of PAKDD, pp. 234–246, 2008.
LCM over ZDD は、頻出パターン列挙アルゴリズムLCMの解をZDDで圧縮して出力する技法である。
LCM単体より100倍以上の高速化を達成している。
http://www-alg.ist.hokudai.ac.jp/~thomas/TCSTR/tcstr_07_30/tcstr_07_30.pdf
ネットワーク信頼性評価
BDDを用いてネットワークの信頼性評価を行える。
各リンクの故障確率を仮定したときに、ネットワーク全体の故障確率の厳密な計算が可能となる。
- 今井 浩, 関根 京子:
グラフの Tutte 多項式計算システム.
数理解析研究所講究録, Vol. 1120, pp. 120–129, 1999.
http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1120-14.pdf - G. Hardy, C. Lucet, N. Limnios:
Computing all-terminal reliability of stochastic networks with binary decision diagrams.
Proc. of ASMDA, 2005.
http://conferences.telecom-bretagne.eu/asmda2005/IMG/pdf/proceedings/1468.pdf - 斎藤 寿樹, 川原 純, 吉仲 亮, 井上 武, 湊 真一:
高速なパスの列挙アルゴリズムを用いたネットワークの信頼性評価.
IN2011-55, pp. 57–62, 2011.
http://www-erato.ist.hokudai.ac.jp/~jkawahara/paper/IN2011.pdf
バイオインフォマティックス
- S. Yoon, C. Nardini, L. Benini, G. Micheli:
Discovering coherent biclusters from gene expression data using zero-suppressed binary decision diagrams.
IEEE/ACM Trans. Comput. Biol. Bioinformatics, Vol. 2, No. 4, pp. 339–354, 2005.
遺伝子発現の二重クラスタリングをZDDによって行う。
http://infoscience.epfl.ch/record/53546/files/Yoon_Discovering_2005.pdf - M. Kiyomi, Y. Okamoto, T. Saitoh:
Efficient Enumeration of the Directed Binary Perfect Phylogenies from Incomplete Data.
Proc. of SEA, pp. 248-259, 2012.
系統樹の列挙をZDDを用いて行う。分枝限定法では困難な規模のデータを扱うことができる。
http://arxiv.org/pdf/1203.3284.pdf
最適化問題・パズルへの応用
最適化問題において、与えられた制約を満たす解の列挙にZDDを用いることができる。
パズルの求解や問題生成（問題列挙）にも用いられる。
- 井上 武, 高野 圭司, 川原 純, 吉仲 亮, 岸本 章宏, 津田 宏治, 湊 真一:
ZDD とフロンティア法を用いた電力配電網の制約充足解列挙.
ERATO 湊離散構造処理プロジェクト 秋のワークショップ, 2011.
http://www-erato.ist.hokudai.ac.jp/html/php/workshop_2011_autumn/inoue.pdf (Slide) - 鈴木 拡, 湊 真一:
ZDD を用いた立体ペントミノパズルの解の列挙.
情報処理学会創立50周年記念（第72回）全国大会, 3ZP-5, pp. 245–246, 2010.
http://www.cyber.sist.chukyo-u.ac.jp/sirai/classes/seminar/IPSJ2010/pdf/ie/3ZP_5.pdf - R. Yoshinaka, T. Saitoh, J. Kawahara, K. Tsuruma, H. Iwashita, S. Minato:
Finding All Solutions and Instances of Numberlink and Slitherlink by ZDDs.
Algorithms, Vol. 5, No. 2, pp. 176–213, 2012.
http://www.mdpi.com/1999-4893/5/2/176/pdf
SeqBDD（文字列処理）
- E. Loekito, J. Bailey, J. Pei:
A binary decision diagram based approach for mining frequent subsequences.
Knowl. Inf. Syst. Vol. 24, No. 2, pp. 235–268, 2010
SeqBDDが提案された論文。SeqBDDを、系列マイニング（順序付きのアイテム集合のマイニング）に応用している。
http://ww2.cs.mu.oz.au/~jbailey/papers/seqMiner.pdf - S. Denzumi, H. Arimura, S. Minato:
Suffix-DDs: Substring Indices Based on Sequence BDDs for Constrained Sequence Mining.
TCS Technical Reports, TCS-TR-A-10-42, 2010.
SeqBDD による部分文字列の索引構築。
http://www-ikn.ist.hokudai.ac.jp/~arim/papers/denzumi_sufdd100524sub.pdf
http://www-erato.ist.hokudai.ac.jp/html/php/symposium2_docs/denzumi.pdf (Slide) - S. Denzumi, R. Yoshinaka, S. Minato, H. Arimura:
Efficient Algorithms on Sequence Binary Decision Diagrams for Manipulating Sets of Strings.
TCS Technical Reports, TCS-TR-A-11-53, 2011.
SeqBDD の効率の良い各種演算の提案。
http://www-alg.ist.hokudai.ac.jp/~thomas/TCSTR/tcstr_11_53/tcstr_11_53.pdf
πDD（置換・順列の処理）
- S. Minato:
PiDD: A New Decision Diagram for Efficient Problem Solving in Permutation Space.
Proc. of SAT, pp. 90–104, 2011.
πDD が提案された論文。πDDの代数演算を定義し、
置換ネットワークの最適解の求解や、ルービックキューブの最短手順の導出に応用している。
http://www-alg.ist.hokudai.ac.jp/~thomas/TCSTR/tcstr_11_50/tcstr_11_50.pdf - J. Kawahara, T. Saitoh, R. Yoshinaka, S. Minato:
Counting Primitive Sorting Networks by πDDs.
TCS Technical Reports, TCS-TR-A-11-54, 2011.
プリミティブソーティングネットワーク（あみだくじ）の総数をπDDを用いて数え上げている。
http://www-alg.ist.hokudai.ac.jp/~thomas/TCSTR/tcstr_11_54/tcstr_11_54.pdf
国際会議
決定グラフ専門の国際会議は存在しない。
決定グラフを扱う論文が複数投稿された実績のある国際会議を分野ごとに紹介する。
VLSI回路設計・CAD
- Design Automation Conference (DAC): http://www.dac.com/
- International Conference on Computer-Aided Design (ICCAD): http://iccad.com/
人工知能・知識発見
- Association for the Advancement of Artificial Intelligence (AAAI): http://www.aaai.org/home.html
- International Joint Conference on Artificial Intelligence (IJCAI): http://ijcai.org/
- ACM Special Interest Group on Knowledge Discovery and Data Mining (SIGKDD): http://www.sigkdd.org/
- Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD): http://pakdd.org/
アルゴリズム
- International Symposium on Algorithms and Computation (ISAAC): http://www.dais.is.tohoku.ac.jp/~tokuyama/ISAAC/isaacweb.html
- International Computing and Combinatorics Conference (COCOON): http://cocoon.it.usyd.edu.au/
- European Symposia on Algorithms (ESA): http://esa-symposium.org/
その他
- Computer Musings by Professor Donald E. Knuth: http://scpd.stanford.edu/knuth/index.jsp
D. Knuth 先生による講演動画。決定グラフ関連の講演は Fun With Binary Decision Diagrams (BDDs), Fun With Zero-Suppressed Binary Decision Diagrams (ZDDs), Bayesian Trees and BDDs の3本である。 - Ruby で楽しむBDD,ZDD: http://rubykaigi.org/2009/ja/talks/17S03
RubyKaigi 2009 でのBDD/ZDDに関する講演の動画が掲載されている。 - Javascript – Binary Decision Diagram: http://blog.vjeux.com/2011/project/javascript-binary-decision-diagram.html
Javascript によるBDDデモ。論理式を入力すると、BDDがインタラクティブに画像で表示される。 - ERATO湊離散構造処理系プロジェクト: http://www-erato.ist.hokudai.ac.jp/
決定グラフを中心とした離散構造処理系の研究を行っている。シンポジウムのページに決定グラフ関連の講演資料が多数掲載されている。筆者が所属するプロジェクト。 - オンライン整数列大辞典 (The On-Line Encyclopedia of Integer Sequences):
http://oeis.org/
「数の列」が多数収められているデータベース。
数列を検索ボックスに打ち込むと、その数列についての詳しい情報を調べることができる。
ZDDによる列挙アルゴリズム等の実装時、プログラムの出力結果を打ち込むと、登録されている数列が表示されることがあり、
出力結果の正しさの確認に使えることがある。
おわりに
BDDやZDD等の決定グラフを用いたデータ構造は、情報科学の多くの分野の基礎となる技術であり、
様々な応用に用いることができる。
計算機の発達、特にメインメモリの大容量化によって、BDD/ZDDの応用可能性が広がったと言え、
今後もますます技術の重要性は高まるであろう。
本稿の執筆に当たり、有益なアドバイスをいただきました湊 真一先生（北海道大学、JST）及び、
伝住 周平氏（北大）に感謝致します。