Vol.27 No.5 (2012/09) 決定グラフを用いたデータ構造

私のブックマーク

決定グラフを用いたデータ構造

科学技術振興機構　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上のリソースを紹介する。

解説記事・書籍

その他、本誌 2012年5月号 pp. 232–237 「BDD/ZDDの技法と離散構造処理系」にBDD研究の歴史が解説されている。

ソフトウェアライブラリ

主要な処理系を紹介する。

その他、様々な言語で実装された処理系が存在する。

研究の動向

決定グラフの最近の研究動向について、分野別に紹介する。以下の文献紹介は網羅的ではなく、
他にも様々な論文が存在する。

確率推論・ベイジアンネットワーク

BDD/ZDDをベイジアンネットワーク等の確率計算に用いる技法について、いくつか研究されている。

データマイニング

ZDDを用いてデータマイニングを行う研究がなされている。

ネットワーク信頼性評価

BDDを用いてネットワークの信頼性評価を行える。
各リンクの故障確率を仮定したときに、ネットワーク全体の故障確率の厳密な計算が可能となる。

バイオインフォマティックス

  • 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を用いることができる。
パズルの求解や問題生成（問題列挙）にも用いられる。

SeqBDD（文字列処理）

πDD（置換・順列の処理）

国際会議

決定グラフ専門の国際会議は存在しない。
決定グラフを扱う論文が複数投稿された実績のある国際会議を分野ごとに紹介する。

VLSI回路設計・CAD

人工知能・知識発見

アルゴリズム

その他

  • 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）及び、
伝住 周平氏（北大）に感謝致します。