1.1 概要

本パッケージは、ZDD(Zero-suppressed Binary Decision Diagrams: ゼロサプレス型二分決定グラフ)を利用し、 重み付きのアイテムの組み合わせ集合をコンパクトに格納することを可能とするVSOP (Valued-Sum-Of-Products calculator)[をruby拡張ライブラリとして実装したものである。 ZDDの生みの親である湊真一教授が開発/コーディングされたパッケージをruby言語において利用できるように拡張したもので、 ERATO湊離散構造処理系プロジェクト において開発されたものである。

ZDDを使えば、膨大な組み合せ集合を非常にコンパクトに表現することが可能となる。 例えば、スーパーマーケットにおける購入履歴から、ある一定の頻度以上購入された商品の組み合せ(頻出アイテム集合)を列挙すると、 その数は膨大になることが多いが、ZDDを使えば、それら全ての組み合せを非常にコンパクトに格納することが可能となる。 しかも、コンパクトに格納されたZDDオブジェクトに対して、各種演算を直接適用することが可能で、 大規模なアイテム集合を非常に効率よく処理することが可能となる。 例えば、列挙された数億件の頻出アイテム集合から「納豆」を含むパターンのみを選択したり、 男性の頻出アイテム集合と女性の頻出アイテム集合との差異を計算したりすることが、それらのZDDのサイズにほぼ比例して行うことが可能なのである。 理論的な詳細は、巻末の参考文献を参照されたい。

本パッケージにおいて、ZDDはrubyオブジェクト(「ZDDオブジェクト」と呼ぶ)として扱われる。 そしてZDDオブジェクトに対して定義された各種関数はクラスメソッドとして利用でき、 また、ZDDオブジェクトに対する各種演算子(+,-,==など)も、ZDDに対する演算子としてオーバーロードされており、 ZDDとrubyの機能をシームレスに組み合わせて利用することを可能としている。 さらに、自動的な型変換もサポートしており、よりストレスなくプログラミングができるように工夫している。