(57)【要約】【課題】偽陽性のエラーのみを許容し、かつ、その発生数の少ない近似ＺＤＤを構築すること。【解決手段】近似ＺＤＤ構築方法は、ゼロサプレス型二分決定グラフを入力として、前記ゼロサプレス型二分決定グラフにおける同一ラベルのノードが表す組合せ集合間の包含関係に基づいて、マージ可能なノードのペアを探索する探索手順と、マージ可能なノードのペアのマージ操作によって発生する偽陽性のエラー数と前記マージ操作によって削減されるノード数とを組み合わせた所定の指標値を用いて、前記探索手順で探索されたペアの中からマージ対象のペアを選択する選択手順と、前記選択手順で選択されたペアにマージ操作を行って、前記ペアに含まれる第１のノードを第２のノードにマージする操作手順と、をコンピュータが実行することを特徴とする。【選択図】図４
2020201556.tif 000002
【特許請求の範囲】
【請求項１】
ゼロサプレス型二分決定グラフを入力として、前記ゼロサプレス型二分決定グラフにおける同一ラベルのノードが表す組合せ集合間の包含関係に基づいて、マージ可能なノードのペアを探索する探索手順と、
マージ可能なノードのペアのマージ操作によって発生する偽陽性のエラー数と前記マージ操作によって削減されるノード数とを組み合わせた所定の指標値を用いて、前記探索手順で探索されたペアの中からマージ対象のペアを選択する選択手順と、
前記選択手順で選択されたペアにマージ操作を行って、前記ペアに含まれる第１のノードを第２のノードにマージする操作手順と、
をコンピュータが実行することを特徴とする近似ＺＤＤ構築方法。
【請求項２】
前記探索手順は、
前記ラベル毎に、該ラベルのノードｕと同一ラベルのノードｖであって、かつ、前記ノードｕが表す組合せ集合を含む組合せ集合を表すノードｖを探索することで、前記ノードｕと前記ノードｖとのペア（ｕ，ｖ）を前記マージ可能なノードのペアとして探索する、ことを特徴とする請求項１に記載の近似ＺＤＤ構築方法。
【請求項３】
前記探索手順は、
前記ノードｕの０−枝が指すノードｕ０が、該ノードｕ０と同一ラベルのノードｚｐ（ｕ０，ｌ（ｕ０））であって、かつ、前記ノードｖから０−枝のみを辿るパスが指すノードｚｐ（ｕ０，ｌ（ｕ０））にマージ可能であると共に、前記ノードｕの１−枝が指すノードｕ１が、該ノードｕ１と同一ラベルのノードｚｐ（ｕ１，ｌ（ｕ１））であって、かつ、前記ノードｖから０−枝のみを辿るパスが指すノードｚｐ（ｕ１，ｌ（ｕ１））にマージ可能である場合に、前記ノードｕと前記ノードｖとのペア（ｕ，ｖ）を前記マージ可能なノードのペアとする、ことを特徴とする請求項２に記載の近似ＺＤＤ構築方法。
【請求項４】
前記探索手順は、
前記ゼロサプレス型二分決定グラフが表現する組合せ集合が単調性を有する場合、ラベル毎に、該ラベルのノードｕであって、かつ、前記ゼロサプレス型二分決定グラフの先頭ノードから０−枝のみを辿るパスが指すノード以外のノードｕと、前記ノードｕが表す組合せ集合を含む組合せ集合を表すノードｓｕｐ（ｕ）であって、かつ、所定の条件を満たすノードの集合Ｃの中でノードが表す組合せ集合の個数が最も少ないノードｓｕｐ（ｕ）とのペア（ｕ，ｓｕｐ（ｕ））を前記マージ可能なノードのペアとして探索する、ことを特徴とする請求項１に記載の近似ＺＤＤ構築方法。
【請求項５】
ゼロサプレス型二分決定グラフを入力として、前記ゼロサプレス型二分決定グラフにおける同一ラベルのノードが表す組合せ集合間の包含関係に基づいて、マージ可能なノードのペアを探索する探索手段と、
マージ可能なノードのペアのマージ操作によって発生する偽陽性のエラー数と前記マージ操作によって削減されるノード数とを組み合わせた所定の指標値を用いて、前記探索手段により探索されたペアの中からマージ対象のペアを選択する選択手段と、
前記選択手段により選択されたペアにマージ操作を行って、前記ペアに含まれる第１のノードを第２のノードにマージする操作手段と、
を有することを特徴とする近似ＺＤＤ構築装置。
【請求項６】
コンピュータに、請求項１乃至４の何れか一項に記載の近似ＺＤＤ構築方法における各手順を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、近似ＺＤＤ構築方法、近似ＺＤＤ構築装置及びプログラムに関する。
【背景技術】
【０００２】
組合せ集合とは、或るアイテムの集合に対して、そのアイテムの組合せからなる集合のことである。この組合せ集合の中身の組合せ数（つまり、組合せ集合の各要素が表す組合せの種類数）は、一般に、もとのアイテム数と比べて多くなってしまう場合が多く、組合せ集合の中身の全てを明示的に持つことが難しくなることが多い。そこで、組合せ集合をコンパクトに表現して、なおかつその組合せ集合に対する問い合わせ（この問い合わせは「クエリ」とも称される。）や、他の組合せ集合との合併等の演算を効率的に行うことができるような表現形が提案されている。このような表現形は、例えば、購買データの頻出パターンマイニングや文書要約、通信ネットワークに関する解析、数理最適化等の分野で広く用いられる。
【０００３】
上記の表現形は決定グラフとも呼ばれ、その１つとして、二分決定グラフ（ＢＤＤ：Binary Decision Diagram）が知られている（例えば、非特許文献１参照）。ＢＤＤは組合せ集合を圧縮して表現し、様々なクエリに答えられるため、多く用いられている。また、ＢＤＤの１種として、ゼロサプレス型二分決定グラフ（ＺＤＤ：Zero-suppressed Binary Decision Diagram）が知られている（例えば、非特許文献２参照）。ＺＤＤは、特に、現実によく現れる疎な組合せ集合をよく圧縮して表現できるため、実際に多く用いられている。なお、疎な組合せ集合とは、組合せ集合の中身（各要素）が表す組合せを構成するアイテムの個数が少ないものが多い組合せ集合や、組合せ集合の中身の個数が全組合せ数に対して大幅に少ないが、もとのアイテム数と比べると大幅に多いような組合せ集合等のことである。
【０００４】
ここで、ＢＤＤやＺＤＤ等の決定グラフを用いて問題を解くアプローチの効率性は、組合せ集合を表現する決定グラフのサイズ（つまり、決定グラフのノード数）に依存することが知られている。しかしながら、決定グラフは組合せ集合をコンパクトに表現することができるものの、一般に決定グラフのサイズがどの程度になるかは分からず、大きな問題に対しては決定グラフのサイズが大きくなり過ぎることがしばしば起こる。そこで、決定グラフが表現する組合せ集合とよく似た組合せ集合を表現する、より小さな決定グラフを構築する技術（つまり、もとの決定グラフをより小さな決定グラフで近似する技術）が従来から提案されている。例えば、非特許文献３や非特許文献４では、ＢＤＤに対してノードの併合や消去等の操作を行って、もとの組み合わせ集合と似た組合せ集合を表現する、より小さなＢＤＤを構築する技術が提案されている、また、例えば、非特許文献５や非特許文献６では、表現したい組合せ集合に関する情報から直接、その組合せ集合に似た組合せ集合を表現する小さなＢＤＤを構築する技術が提案されている。
【０００５】
上記の近似を行った結果、元々の組合せ集合には入っていなかった組合せが、近似後の組合せ集合に入ってしまう場合は偽陽性のエラーと呼ばれる。一方で、元々の組合せ集合には入っていた組合せが、近似後の組合せ集合に入っていない場合は偽陰性のエラーと呼ばれる。偽陽性のエラーと偽陰性のエラーとの両方が近似後の組合せ集合で発生すると応用範囲が大幅に制限されてしまうため、実用上は偽陽性か偽陰性のどちらかのエラーのみを許容するように近似することが重要である。非特許文献３〜６で提案されている技術はいずれも偽陽性か偽陰性のどちらかのエラーのみを許容している。なお、偽陰性のエラーのみを許容する近似手法の逆の手順を行うことで偽陽性のエラーのみを許容する近似手法を実現することが可能であるため、非特許文献３〜６で提案されている技術はいずれも偽陽性のエラーのみを許容する技術と見做すことができる。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Randal E. Bryant. Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers, Vol. C-35, pp. 677-691, 1986.
【非特許文献２】Shin-ichi Minato. Zero-suppressed BDDs for set manipulation in combinatorial problems. In Proceedings of the 30th ACM/IEEE Design Automation Conference (DAC 1993), pp. 272-277, 1993.
【非特許文献３】Kavita Ravi and Fabio Somenzi. High-density reachability analysis. In Proceedings of the 1995 IEEE/ACM International Conference on Computer-Aided Design (ICCAD 1995), pp. 154-158, 1995.
【非特許文献４】Kavita Ravi, Kenneth L. McMillan, Thomas R. Shiple, and Fabio Somenzi. Approximation and decomposition of binary decision diagrams. In Proceedings of the 35th ACM/IEEE Design Automation Conference (DAC 1998), pp. 445-450, 1998.
【非特許文献５】Tarik Hadzic, John N. Hooker, Barry O'Sullivan, and Peter Tiedemann. Approximate compilation of constraints into multivalued decision diagrams. In Proceedings of the 14th International Conference on Principles and Practice of Constraint Programming (CP 2008), pp. 448-462, 2008.
【非特許文献６】David Bergman, Willem-Jan van Hoeve, and John N. Hooker. Manipulating MDD relaxations for combinatorial optimization. In Proceedings of the 8th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2011), pp. 20-35, 2011.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上記の非特許文献３や非特許文献４で提案されている技術をＺＤＤに適用しようとした場合、次のような問題があった。すなわち、非特許文献３や非特許文献４では、ＢＤＤのノードを消して、代わりに全ての組合せを含む集合（べき集合）を表すノードに付け替える、という操作が行われるが、現実に現れる疎な組合せ集合の中身は全ての組合せよりも大幅に少ない数である場合が多い。このため、非特許文献３や非特許文献４で提案されている技術をＺＤＤに適用しようとした場合、偽陽性のエラーが多く発生し過ぎてしまうことが多い。
【０００８】
また、非特許文献４ではＲｅｍａｐと呼ばれる操作が行われているが、この操作はノードが表す組合せ集合間の包含関係に基づいたものであり、ＢＤＤのノード数は減らすことができるものの、この操作をＺＤＤに適用しても、ＺＤＤのノード数は減らすことができない。
【０００９】
なお、非特許文献５や非特許文献６で提案されている技術は、基本的に最適化問題を解くための近似決定グラフを作成することに特化している。このため、最適化問題以外に適用する場合には対象とする組合せ集合に応じて注意深く手法を設計し直す必要がある。
【００１０】
本発明は、上記の点に鑑みてなされたもので、偽陽性のエラーのみを許容し、かつ、その発生数の少ない近似ＺＤＤを構築することを目的とする。
【課題を解決するための手段】
【００１１】
上記目的を達成するため、本発明の実施の形態における近似ＺＤＤ構築方法は、ゼロサプレス型二分決定グラフを入力として、前記ゼロサプレス型二分決定グラフにおける同一ラベルのノードが表す組合せ集合間の包含関係に基づいて、マージ可能なノードのペアを探索する探索手順と、マージ可能なノードのペアのマージ操作によって発生する偽陽性のエラー数と前記マージ操作によって削減されるノード数とを組み合わせた所定の指標値を用いて、前記探索手順で探索されたペアの中からマージ対象のペアを選択する選択手順と、前記選択手順で選択されたペアにマージ操作を行って、前記ペアに含まれる第１のノードを第２のノードにマージする操作手順と、をコンピュータが実行することを特徴とする。
【発明の効果】
【００１２】
偽陽性のエラーのみを許容し、かつ、その発生数の少ない近似ＺＤＤを構築することができる。
【図面の簡単な説明】
【００１３】
【図１】ＺＤＤの一例を説明するための図である。
【図２】包含関係及びマージ可能なノードのペアの一例を説明するための図である。
【図３】本発明の実施の形態における近似ＺＤＤ構築装置の機能構成の一例を示す図である。
【図４】近似ＺＤＤ構築処理の一例を示すフローチャートである。
【図５】マージ可能なノードの全てのペアのリストを算出する処理の一例を示すフローチャートである。
【図６】ノードのペアがマージ可能か否かを判定する場合の一例を説明するための図である。
【図７】ＺＤＤの各ノードのモデルカウントを算出する処理の一例を示すフローチャートである。
【図８】ＺＤＤの各ノードにおける先頭ノードからのパスの個数を算出する処理の一例を示すフローチャートである。
【図９】Ｄｏｍｉｎａｔｏｒ  Ｔｒｅｅの一例を説明するための図である。
【図１０】マージ可能な条件の一例を説明するための図である。
【図１１】ＺＤＤが単調減少な組み合わせ集合を表現する場合に、マージ可能なノードの一部のペアのリストを算出する処理の一例を示すフローチャートである。
【図１２】ケース１又はケース２に該当するｓｕｐ（ｕ）の候補を探索する処理の一例を示すフローチャートである。
【図１３】ケース３に該当とするｓｕｐ（ｕ）の候補を探索する処理の一例を示すフローチャートである。
【図１４】本発明の実施の形態における近似ＺＤＤ構築装置のハードウェア構成の一例を示す図である。
【発明を実施するための形態】
【００１４】
以下、本発明の実施の形態（以降、「本実施形態」とも表す。）について説明する。本実施形態では、偽陽性のエラーのみを許容し、かつ、その発生数の少ない近似ＺＤＤを構築する場合について説明する。近似ＺＤＤとは、与えられたＺＤＤが表現する組合せ集合に近似する組合せ集合（つまり、与えられたＺＤＤが表現する組合せ集合と似た組合せ集合）を表現し、かつ、与えられたＺＤＤよりもサイズの小さいＺＤＤのことである。なお、ＺＤＤのサイズとは、後述するように、ＺＤＤのノードの個数のことである。
【００１５】
＜ＺＤＤの説明＞
まず、ＺＤＤについて説明する。本実施形態では、便宜のため、ＺＤＤで表現したい組合せ集合のもととなるアイテムの集合中の各アイテムに、１からｃまでの番号を付与するものとする。例えば、アイテムの集合Ａとすれば、Ａ＝｛ａ１，ａ２，・・・，ａｃ｝と表されるものとする。組合せ集合の中身（つまり、組合せ集合の各要素）は、アイテムの集合中の各アイテムの組合せで表される。具体的には、組合せ集合の或る１つの要素は、｛ａ１，ａ２｝や｛ａ１，ａ２，ａ３｝、｛ａ１，ａ３｝等とアイテムの集合中の各アイテムの組合せで表される。なお、組合せには、「アイテム無し」を意味する組合せとして、φも含まれる。
【００１６】
ＺＤＤは、組合せ集合を、ノードと向きのあるエッジとの集まりでできたループのないグラフ（有向非巡回グラフ（ＤＡＧ：Directed Acyclic Graph））で表現するデータ構造である。ＺＤＤは、
【００１７】
【数１】
2020201556.tif 000003
（以降、「第１終端ノード」とも表す。）及び終端ノード⊥（以降、「第２終端ノード」とも表す。）と、分岐ノードとの２種類のノードを持ち、各終端ノードから出るエッジは無く、各分岐ノードからは「０−枝」と「１−枝」と呼ばれる２つのエッジが出る。本実施形態では、分岐ノードｖに対して、このノードから出る０−枝が指す先のノードを「０−子ノード」と呼び、ｖ０で表す。また、同様に、分岐ノードｖに対して、このノードから出る１−枝が指す先のノードを「１−子ノード」と呼び、ｖ１で表す。
【００１８】
また、各分岐ノードｖには、ラベルと呼ばれる整数値ｌ（ｖ）∈｛１，・・・，ｃ｝が付与されており、このラベルによってアイテムの番号と対応付けられている。なお、終端ノードについては、例えば、ラベルの値をｃ＋１等としておく。
【００１９】
このとき、ＺＤＤは、各分岐ノードの０−枝と１−枝が、必ずラベルが小さい方のノードから大きい方のノードに向かうようにする。すなわち、任意の分岐ノードｖに対して、ｌ（ｖ）＜ｌ（ｖ０）かつｌ（ｖ）＜ｌ（ｖ１）が成立するようにする。また、ＺＤＤのサイズはノードの個数として定義する。
【００２０】
以上の準備により、ＺＤＤの各ノードが表す組合せ集合は、次のように再帰的に定義することができる。なお、ＺＤＤのノードｖに対して、ｖが表す組合せ集合を
【００２１】
【数２】
2020201556.tif 000004
と表す。
【００２２】
・終端ノードについては、
【００２３】
【数３】
2020201556.tif 000005
とする。すなわち、第１終端ノードが表す組合せ集合を「「アイテム無し」を意味する組合せφのみを含む集合」、第２終端ノードが表す組合せ集合を「組み合わせを１つも含まない集合」とする。
【００２４】
・分岐ノードｖについては、
【００２５】
【数４】
2020201556.tif 000006
とする。
【００２６】
ここで、ｉ＝１，・・・，ｃに対して、第ｉ層Ｌｉを、ラベルｉを持つノードの集合として定義する。すると、ＺＤＤは、例えば、図１に示すように、ノードが上から層の順番Ｌ１，・・・，Ｌｃで出現するようなグラフとして描ける。図１に示すＺＤＤでは、各終端ノードが四角形、各分岐ノードとそのラベルが円、各０−枝が破線矢印、各１−枝が実線矢印で描かれている。図１に示すＺＤＤは、組合せ集合｛φ，｛２｝，｛３｝，｛４｝，｛１，３｝，｛１，４｝，｛２，３｝，｛２，４｝，｛３，４｝，｛１，２，３｝｝を表現している。これは、ラベル１の分岐ノードが表す組合せ集合と同じである。なお、層は「階層」等と称されてもよい。
【００２７】
図１に示すＺＤＤにおいて、ラベル２の左側の分岐ノードは組合せ集合｛｛３｝，｛４｝，｛２，３｝｝を表しており、ラベル２の右側の分岐ノードは組合せ集合｛φ，｛２｝，｛３｝，｛４｝，｛２，３｝，｛２，４｝，｛３，４｝｝を表している。他の分岐ノードが表す組合せ集合についても、図１に示す通りである。
【００２８】
なお、コンピュータ等の計算機上では、終端ノードは定数長のデータとしてそのまま表現され、各分岐ノードｖは、ラベルｌ（ｖ）、０−子ノードｖ０へのポインタ及び１−子ノードｖ１へのポインタの３つの組で表現される。
【００２９】
＜本実施形態で説明する手法の概略＞
本実施形態では、同じ層内の各ノードが表す組合せ集合間の包含関係に着目し、マージ可能なノードのペアを見つけてマージすることでノードの数を減らす手法について説明する。この手法を用いることにより、例えば、組合せ集合をべき集合に置き換えるような操作（例えば非特許文献３に記載されている操作）が発生しないため偽陽性のエラーの発生を少なくすることができる。このため、本実施形態では、偽陽性のエラーのみを許容し、かつ、その発生数が少ない近似ＺＤＤを構築することが可能となる。本実施形態では、与えられたＺＤＤに対して、この手法を実現する処理を実行して近似ＺＤＤを構築するコンピュータを「近似ＺＤＤ構築装置１０」として、この近似ＺＤＤ構築装置１０について説明する。以降では、近似ＺＤＤ構築装置１０に与えられるＺＤＤをＧ、このＧの近似ＺＤＤをＧ´とも表す。
【００３０】
なお、上記の非特許文献４に記載のＲｅｍａｐと呼ばれる操作もノードが表す組合せ集合間の包含関係に注目しているが、Ｒｅｍａｐでは、或るノードに対してその０−子ノードと１−子ノードとの間の包含関係にしか着目しておらず、同じ層内の任意のノードのペアに対する包含関係はみていない。
【００３１】
また、本実施形態で説明する手法は、対象とする組合せ集合に囚われないため、汎用的に用いることができる。
【００３２】
＜包含関係及びマージ可能なノードのペアの説明＞
ここで、上記の「包含関係」や「マージ可能なノードのペア」について説明する。例えば、図２（ａ）に示すＺＤＤでは、ラベル３を持つ２つのノードのうち、左側のノードは組合せ集合｛φ，｛３｝｝を表しており、右側のノードは組合せ集合｛｛３｝｝を表している。したがって、これらの組合せ集合の間には、｛｛３｝｝⊆｛φ，｛３｝｝という包含関係がある。
【００３３】
このとき、右側のノードに入るエッジを、左側のノードに入るように付け替えて、右側のノードを消去すると、図２（ｂ）に示すＺＤＤ（近似ＺＤＤ）が得られる。これにより、偽陽性のエラーは発生し得るが、偽陰性のエラーは発生しない。
【００３４】
このように、同じラベルが付与されている２つのノードｕ，ｖに対して、ノードｕに入るエッジをノードｖに入るように付け替えて、ノードｕを消去する操作のことを「マージ」又は「マージ操作」という。そして、ノードｕをノードｖにマージする場合、ノードｕが表す組合せ集合が、ノードｖが表す組合せ集合に包含されているとき、偽陽性のエラーは発生し得るものの、マージを行っても偽陰性のエラーは発生しない。
【００３５】
例えば、図２（ｂ）に示すＺＤＤでは、図２（ａ）に示すＺＤＤに対して、ラベル１のノードと、ラベル２のノードとで偽陽性のエラーが発生しているものの、偽陰性のエラーは発生していない。具体的には、図２（ｂ）に示すＺＤＤでは、図２（ａ）に示すＺＤＤに対して、ラベル１のノードが表す組合せ集合に組合せφ及び｛１｝が、ラベル２のノードが表す組合せ集合に組合せφが追加されており、偽陽性のエラーが発生している。
【００３６】
そこで、本実施形態では、同じラベルが付与されている２つのノードｕ，ｖ（つまり、同じ層の２つのノードｕ，ｖ）について、ノードｕが表す組合せ集合が、ノードｖが表す組合せ集合に包含されている場合に、これら２つノードｕ，ｖを「マージ可能なノードのペア」と表す。
【００３７】
＜近似ＺＤＤ構築装置１０の機能構成＞
次に、本実施形態に係る近似ＺＤＤ構築装置１０の機能構成について、図３を参照しながら説明する。図３は、本発明の実施の形態における近似ＺＤＤ構築装置１０の機能構成の一例を示す図である。
【００３８】
図３に示すように、本実施形態に係る近似ＺＤＤ構築装置１０は、機能部として、入力部１０１と、前処理部１０２と、操作部１０３と、出力部１０４とを有する。これら各機能部は、例えば、近似ＺＤＤ構築装置１０にインストールされた１以上のプログラムが、ＣＰＵ（Central Processing Unit）等に実行させる処理により実現される。
【００３９】
入力部１０１は、ＺＤＤ  Ｇと所定の閾値θとを入力する。閾値θとは、ＺＤＤ  Ｇ´のサイズを表す閾値である。なお、入力部１０１の入力元は、任意の入力元としてよい。このような入力元としては、ＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）等の補助記憶装置、キーボードやマウス等の入力装置、通信ネットワークを介して接続される他の装置等が挙げられる。
【００４０】
前処理部１０２は、入力部１０１により入力されたＺＤＤ  Ｇの中から、ノード間の包含関係に基づいてマージ可能なノードのペアを複数探索し、これらのペアをリスト化したリストＲを算出する。
【００４１】
操作部１０３は、前処理部１０２により算出されたリストＲを用いてＺＤＤ  Ｇのノードをマージする操作を行って、閾値θ未満のサイズのＺＤＤ  Ｇ´（つまり、近似ＺＤＤ）を構築する。なお、例えば、閾値θ未満のサイズのＺＤＤ  Ｇ´を構築することができない場合、操作部１０３は、可能な限り小さいサイズのＺＤＤを構築してＧ´とすればよい。
【００４２】
出力部１０４は、操作部１０３により構築されたＺＤＤ  Ｇ´を出力する。なお、出力部１０４の出力先は任意の出力先としてよい。このような出力先としては、例えば、補助記憶装置、ディスプレイ等の表示装置、通信ネットワークを介して接続される他の装置等が挙げられる。
【００４３】
［実施例１］
以降では、実施例１として、前処理部１０２が、与えられたＺＤＤ  Ｇの中から、マージ可能なノードの全てのペアを探索する場合について説明する。
【００４４】
＜近似ＺＤＤ構築処理＞
本実施形態に係る近似ＺＤＤ構築装置１０が実行する近似ＺＤＤ構築処理について、図４を参照しながら説明する。図４は、近似ＺＤＤ構築処理の一例を示すフローチャートである。
【００４５】
入力部１０１は、ＺＤＤ  Ｇと所定の閾値θとを入力する（ステップＳ１０１）。
【００４６】
次に、前処理部１０２は、上記のステップＳ１０１で入力されたＺＤＤ  Ｇの中から、ノード間の包含関係に基づいてマージ可能なノードのペアを全て探索し、探索されたペアをリスト化したリストＲを算出する（ステップＳ１０２）。なお、リストＲは、補助記憶装置やＲＡＭ（Random Access Memory）等のメモリに格納される。
【００４７】
ここで、ノードｕをノードｖにマージ可能であるということを（ｕ，ｖ）∈Ｒと表すことにすると、その必要十分条件は、
【００４８】
【数５】
2020201556.tif 000007
となる。また、ｌ（ｕ）＝ｌ（ｖ）のとき、
【００４９】
【数６】
2020201556.tif 000008
は、
【００５０】
【数７】
2020201556.tif 000009
と同値である。すなわち、１つ下の層での包含関係が分かっていれば、それをもとに１つ上の層での包含関係を計算することができる。そこで、いま、ノードｕとｋ∈｛１，・・・，ｃ｝に対して、ｚｐ（ｕ，ｋ）を、ノードｕから０−枝のみを辿って行ける、ラベルｋのノードとする。もしそのようなノードがなければ、ｚｐ（ｕ，ｋ）＝ｎｕｌｌとする。なお、ｚｐ（ｕ，ｋ）はもし存在すれば一意に定まる。
【００５１】
このｚｐ（ｕ，ｋ）を用いると、ＺＤＤ  Ｇの中からマージ可能なノードペアを全て探索してリストＲを算出する処理（図４のステップＳ１０２）の詳細は、図５に示すフローチャートのようになる。図５は、マージ可能なノードの全てのペアのリストを算出する処理の一例を示すフローチャートである。
【００５２】
まず、前処理部１０２は、第１終端ノードが表す組合せ集合｛φ｝と第２終端ノードが表す組合せ集合｛｝との間の包含関係から、
【００５３】
【数８】
2020201556.tif 000010
とする（ステップＳ２０１）。
【００５４】
次に、前処理部１０２は、ｉを１ずつ減じながらｉ＝ｃからｉ＝１まで、ステップＳ２０３の処理を繰り返し実行する（ステップＳ２０２）。また、ステップＳ２０３では、前処理部１０２は、ＺＤＤ  Ｇの第ｉ層Ｌｉ中の全てのノードのペア（ｕ，ｖ）に対して、ステップＳ２０４〜ステップＳ２０５の処理を繰り返し実行する。すなわち、前処理部１０２は、第ｃ層から第１層まで、下から上の順に各層の全てのノードのペア（ｕ，ｖ）に対して包含関係を探索する。
【００５５】
ステップＳ２０４では、前処理部１０２は、ＺＤＤ  Ｇの第ｉ層Ｌｉ中のノードのペア（ｕ，ｖ）に対して、（ｕ０，ｚｐ（ｖ０，ｌ（ｕ０）））∈Ｒかつ（ｕ１，ｚｐ（ｖ１，ｌ（ｕ１）））∈Ｒを満たすか否かを判定する。
【００５６】
ここで、（ｕ０，ｚｐ（ｖ０，ｌ（ｕ０）））∈Ｒとは、例えば、図６に示すように、ノードｕ０が、ノードｖ０から０−枝のみを辿って行ける、ラベルｌ（ｕ０）のノードｚｐ（ｖ０，ｌ（ｕ０））にマージ可能であることを意味する。同様に、（ｕ１，ｚｐ（ｖ１，ｌ（ｕ１）））∈Ｒとは、例えば、図６に示すように、ノードｕ１が、ノードｖ１から０−枝のみを辿って行ける、ラベルｌ（ｕ１）のノードｚｐ（ｖ１，ｌ（ｕ１））にマージ可能であることを意味する。なお、図６では、０−枝のみからなるパスを破線の曲線で表している。
【００５７】
他方で、（ｕ０，ｚｐ（ｖ０，ｌ（ｕ０）））∈Ｒという条件は
【００５８】
【数９】
2020201556.tif 000011
と同値であり、（ｕ１，ｚｐ（ｖ１，ｌ（ｕ１）））∈Ｒという条件は
【００５９】
【数１０】
2020201556.tif 000012
と同値である。
【００６０】
したがって、（ｕ０，ｚｐ（ｖ０，ｌ（ｕ０）））∈Ｒかつ（ｕ１，ｚｐ（ｖ１，ｌ（ｕ１）））∈Ｒという条件を満たす場合、ノードｕをノードｖにマージ可能であり、（ｕ，ｖ）∈Ｒとなる。
【００６１】
そこで、上記のステップＳ２０４の条件を満たす場合、前処理部１０２は、Ｒ←Ｒ∪｛（ｕ，ｖ）｝とする（ステップＳ２０５）。すなわち、この場合、リストＲに対して、ノードのペア（ｕ，ｖ）を追加する。一方で、前処理部１０２は、上記のステップＳ２０４の条件を満たさない場合、ステップＳ２０５の処理は行わない（つまり、ノードのペア（ｕ，ｖ）をリストＲに追加しない。）。なお、リストＲはマージ可能なノードのペア（ｕ，ｖ）を要素とする集合であるため、集合Ｒと称されてもよい。
【００６２】
以上により、ＺＤＤ  Ｇの各層のマージ可能な全てのノードのペア（ｕ，ｖ）のリストＲが算出される。
【００６３】
図４に戻る。ステップＳ１０２に続いて、操作部１０３は、上記のステップＳ１０２で算出されたリストＲを用いてＺＤＤ  Ｇのノードのマージ操作を行って、閾値θ未満のサイズのＺＤＤ  Ｇ´を構築する（ステップＳ１０３）。すなわち、操作部１０３は、例えば、リストＲから１つのペア（ｕ，ｖ）を選択して、このペアのノードｕをノードｖにマージする、という操作をＺＤＤ  Ｇのサイズがθ未満になるまで繰り返すことで、ＺＤＤ  Ｇ´を構築する。なお、リストＲの全てのペア（ｕ，ｖ）でノードｕをノードｖにマージしてもＺＤＤ  Ｇのサイズがθ未満にならない場合、操作部１０３は、可能な限り小さいサイズのＺＤＤ（つまり、リストＲの全ての（ｕ，ｖ）でノードｕをノードｖにマージしたＺＤＤ）をＧ´とすればよい。
【００６４】
ここで、上記のステップＳ１０３において、リストＲからどのペア（ｕ，ｖ）を選択するかは、例えば、そのペアのノードｕをノードｖにマージすることで発生する偽陽性のエラーの個数ＥＧ（ｕ，ｖ）と、ノードｕを消すことにより減るノードの個数Ｎ（ｕ）とを組み合わせた所定の指標値を用いて、その指標値が最も良いペアを選択すればよい。
【００６５】
例えば、ノードのペアの選択及びマージ操作の各繰り返しを表すインデックスをｊ（ｊ＝１，２，・・・）、繰り返しｊの開始時点のＺＤＤをＧｊとして、ＺＤＤ  Ｇｊが表現する組合せ集合
【００６６】
【数１１】
2020201556.tif 000013
の中身の組合せの個数を
【００６７】
【数１２】
2020201556.tif 000014
とする。なお、Ｇ＝Ｇ１である。
【００６８】
このとき、各繰り返しｊにおいて、指標値
【００６９】
【数１３】
2020201556.tif 000015
を最小にするようなノードのペア（ｕ，ｖ）を選択する、という方法が挙げられる。この指標値Ｈ（ｕ，ｖ）を用いることで、偽陽性のエラーの発生数
【００７０】
【数１４】
2020201556.tif 000016
が抑えられ、かつ、マージ操作によって減るノードの個数Ｎ（ｕ）が多いようなノードのペア（ｕ，ｖ）を選択することが可能となる。
【００７１】
ここで、上記の指標値Ｈ（ｕ，ｖ）に含まれるＥＧｊ（ｕ，ｖ）やＮ（ｕ）等はマージ操作が行われる毎に計算し直す必要があるため、各ペアに対して効率的に計算できることが求められる。
【００７２】
まず、ＥＧｊ（ｕ，ｖ）については、ＺＤＤ  Ｇｊの一番上のノードｒ（つまり、Ｇｊの先頭ノード）からノードｕまでのパスの個数をＴ（ｕ）として、
【００７３】
【数１５】
2020201556.tif 000017
により求めることができる。ここで、簡単のため、
【００７４】
【数１６】
2020201556.tif 000018
として、Ｂをモデルカウントとも表す。
【００７５】
各Ｔ（ｕ）やＢ（ｕ）は、動的計画法を用いて、全てのノードｕに対して効率的に求めることが可能である。なお、
【００７６】
【数１７】
2020201556.tif 000019
である。
【００７７】
ＺＤＤ  Ｇｊの各ノードｕのモデルカウントＢ（ｕ）を算出する処理は、図７に示すフローチャートのようになる。図７は、ＺＤＤの各ノードのモデルカウントを算出する処理の一例を示すフローチャートである。
【００７８】
まず、操作部１０３は、第１終端ノードが表す組合せ集合｛φ｝と第２終端ノードが表す組合せ集合｛｝から、
【００７９】
【数１８】
2020201556.tif 000020
とする（ステップＳ３０１）。
【００８０】
次に、操作部１０３は、ｉを１ずつ減じながらｉ＝ｃからｉ＝１まで、ステップＳ３０３の処理を繰り返し実行する（ステップＳ３０２）。また、ステップＳ３０３では、操作部１０３は、ＺＤＤ  Ｇｊの第ｉ層Ｌｉ中の全てのノードｕに対して、ステップＳ３０４の処理を繰り返し実行する。
【００８１】
ステップＳ３０４では、操作部１０３は、ＺＤＤ  Ｇｊの第ｉ層Ｌｉ中のノードｕに対して、Ｂ（ｕ）←Ｂ（ｕ０）＋Ｂ（ｕ１）とする。
【００８２】
以上により、ＺＤＤ  Ｇｊの全てのノードｕに対して、モデルカウントＢ（ｕ）を算出することができる。
【００８３】
また、ＺＤＤ  Ｇｊの各ノードｕのＴ（ｕ）を算出する処理は、図８に示すフローチャートのようになる。図８は、ＺＤＤの各ノードにおける先頭ノードからのパスの個数を算出する処理の一例を示すフローチャートである。
【００８４】
まず、操作部１０３は、ＺＤＤ  Ｇｊの全てのノードｕに対して、Ｔ（ｕ）←０とする（ステップＳ４０１）。
【００８５】
次に、操作部１０３は、ＺＤＤ  Ｇｊの先頭ノードをｒとして、Ｔ（ｒ）←１とする（ステップＳ４０２）。
【００８６】
次に、操作部１０３は、ｉを１ずつ増加させながらｉ＝１からｉ＝ｃまで、ステップ４０４の処理を繰り返し実行する（ステップＳ４０３）。また、ステップＳ４０３では、操作部１０３は、ＺＤＤ  Ｇｊの第ｉ層Ｌｉ中の全てのノードｕに対して、ステップＳ４０５の処理を繰り返し実行する。
【００８７】
ステップＳ４０５では、操作部１０３は、Ｔ（ｕ０）←Ｔ（ｕ０）＋Ｔ（ｕ）及びＴ（ｕ１）←Ｔ（ｕ１）＋Ｔ（ｕ）とする。
【００８８】
以上により、ＺＤＤ  Ｇｊの全てのノードｕに対して、先頭ノードｒからノードｕまでのパスの個数Ｔ（ｕ）を算出することができる。
【００８９】
次に、Ｎ（ｕ）については、Ｄｏｍｉｎａｔｏｒ  Ｔｒｅｅと呼ばれるデータ構造を用いて効率的に計算することができる。ＺＤＤ  Ｇｊの先頭ノードをｒとした場合、ノードｕがノードｖのＤｏｍｉｎａｔｏｒであるとは、ノードｒからノードｖまでの任意のパスが必ずノードｕを通る、ということである。このとき、各ノード間のＤｏｍｉｎａｔｏｒの関係は、Ｄｏｍｉｎａｔｏｒ  Ｔｒｅｅという木構造で記述することができる。
【００９０】
Ｄｏｍｉｎａｔｏｒ  Ｔｒｅｅは、ノードｕがノードｖのＤｏｍｉｎａｔｏｒであるとき、かつそのときに限り、ノードｕがノードｖの祖先（つまり、木構造を上に辿って行くことで辿り着けるノード）である、という性質を持つ。Ｄｏｍｉｎａｔｏｒ  Ｔｒｅｅは、例えば、以下の参考文献等に記載されているアルゴリズムを用いることで、ＺＤＤ  Ｇｊに対して高速に計算することができる。
【００９１】
［参考文献］
Thomas Lengauer and Robert E. Tarjan. A fast algorithm for finding dominators in a flowgraph. ACM Transactions on Programming Languages and Systems (TOPLAS), Vol. 1, pp.121-141, 1979.
Ｄｏｍｉｎａｔｏｒ  Ｔｒｅｅが計算できれば、Ｎ（ｕ）は、Ｄｏｍｉｎａｔｏｒ  Ｔｒｅｅにおけるノードｕの子孫ノード（つまり、木構造中でノードｕよりも下にあるノード）の個数に対して、ノードｕ自身の個数１を加えた値として計算することができる。したがって、各Ｎ（ｕ）は、Ｄｏｍｉｎａｔｏｒ  Ｔｒｅｅ中のボトムアップな計算により、全てのノードｕに対して効率的に求めることができる。
【００９２】
例えば、或るＺＤＤと、このＺＤＤに対応するＤｏｍｉｎａｔｏｒ  Ｔｒｅｅとを図９に示す。図９中の数字は、ＺＤＤの各ノードのノード番号を表す。図９に示す例の場合、ノード番号２のノードは、ノード番号５、ノード番号６及びノード番号８の各ノードのＤｏｍｉｎａｔｏｒである。したがって、ノード番号２のノードをマージ操作によって消した場合、ノード番号５、ノード番号６及びノード番号８の３つのノードも同時に消えることになり、Ｎ（ノード番号２のノード）＝３＋１＝４と求めることができる。
【００９３】
図４に戻る。ステップＳ１０３に続いて、出力部１０４は、上記のステップＳ１０３で構築されたＺＤＤ  Ｇ´（つまり、ＺＤＤ  Ｇの近似ＺＤＤ）を出力する（ステップＳ１０４）。これにより、与えられたＺＤＤ  Ｇの近似ＺＤＤであるＧ´が得られる。
【００９４】
以上のように、実施例１の近似ＺＤＤ構築装置１０は、与えられたＺＤＤの同一層内の任意のノードペアに対する包含関係に基づいてマージ可能なノードのペアを探索することで、偽陽性のエラーのみを許容し、かつ、その発生数の少ない近似ＺＤＤを構築することができる。
【００９５】
［実施例２］
以降では、実施例２として、与えられたＺＤＤ  Ｇが表現する組合せ集合が単調性という性質を有する場合（つまり、組合せ集合が単調減少又は単調増加である場合）について説明する。この場合、前処理部１０２は、実施例１と異なり、マージ可能なノードの一部のペアを探索することにより、近似ＺＤＤ構築処理をより高速に実行することが可能となる。
【００９６】
組合せ集合が単調減少であるとは、組合せ集合中の任意の組合せから任意に１つのアイテムを取り除いても、その組合せが当該組合せ集合に含まれる場合をいう。同様に、組合せ集合が単調増加であるとは、組合せ集合中の任意の組合せに対して、当該組合せ集合のもととなるアイテムの集合から任意に１つのアイテムを加えても、その組合せが当該組合せ集合に含まれる場合をいう。なお、単調性を有する組合せ集合は、例えば、線形な組合せ不等式（具体的には、ｗ１Ｘ１＋・・・＋ｗＮＸＮ≦Ｔといった形式で表現できる不等式）を表現する場合等、応用上も様々な場面で現れる。
【００９７】
ここで、前処理部１０２で包含関係のあるノードのペアを全て探索すると、最悪の場合は与えられたＺＤＤのサイズの二乗の数のペアが探索されるため、これらのペアを全て保持するとメモリを圧迫するおそれがある。そこで、実施例２では、それらのペアのうち、マージしてもあまり偽陽性のエラーが発生しないと思われる一部のペアのみをリストＲに保持する。これにより、実施例１と比較して、近似ＺＤＤ構築処理をより高速に実行することができると共に、メモリの使用量を削減することが可能となる。
【００９８】
以降では、組合せ集合は単調減少であるものとして説明するが、組合せ集合が単調増加である場合についても同様に適用可能である。
【００９９】
なお、実施例２は、主に、実施例１との相違点について説明し、実施例１と同様の構成要素については、その説明を省略するものとする。
【０１００】
＜マージ可能な条件＞
まず、ＺＤＤの各層に対して、先頭ノードから０−枝のみを辿って到達できるノードを特殊なノードと呼ぶことにする。このとき、単調性により、特殊なノードが表す組合せ集合は、この特殊なノードが属する層の他のどのノードが表す組合せ集合をも含む。すなわち、特殊なノードにはマージ可能なノードが存在しない。
【０１０１】
逆に、どの層でも、特殊でないノードは、その層の特殊なノードにマージ可能である。すなわち、特殊でないノードｕに対しては、少なくとも１つはマージ可能なノードが存在することになる。
【０１０２】
そこで、本実施例では、上の層から順番に、各特殊でないノードｕに対して、偽陽性のエラーの発生数が少ないと思われるマージ可能なノードｓｕｐ（ｕ）とのペア（ｕ，ｓｕｐ（ｕ））を１つ計算していく。なお、偽陽性のエラーの発生数が少ないと思われるマージ可能なノードとは、マージ可能なノードのうち、当該ノードが表す組合せ集合中の組合せの個数が少ないと思われるノードのことである。
【０１０３】
ここで、本実施例では、ＺＤＤの各層の特殊でないノードｕに対して、図１０（ａ）〜図１０（ｃ）にそれぞれ示す以下のケース１〜ケース３のマージ可能なノードを考える。なお、図１０では、０−枝のみからなるパスを破線の曲線で表している。
【０１０４】
（ケース１）図１０（ａ）に示すように、ｕ＝ｐ０となるノードｐに対して、ノードｐが他のノードｑにマージ可能である場合（つまり、ｌ（ｐ）＝ｌ（ｑ）、かつ、ノードｐが表す組合せ集合が、ノードｑが表す組合せ集合に包含される場合）に、ｚｐ（ｑ，ｌ（ｕ））がｕと相異なるなら、ノードｕはノードｚｐ（ｑ，ｌ（ｕ））にマージ可能である。
【０１０５】
（ケース２）図１０（ｂ）に示すように、ｕ＝ｐ１となるノードｐに対して、ｚｐ（ｐ，ｌ（ｕ））がｕと相異なるなら、ノードｕはノードｚｐ（ｐ，ｌ（ｕ））にマージ可能である。
【０１０６】
（ケース３）図１０（ｃ）に示すように、ｕ＝ｐ１となるノードｐに対して、ノードｐが他のノードｑにマージ可能である場合に、ｚｐ（ｑ１，ｌ（ｕ））がｕと相異なるなら、ノードｕはノードｚｐ（ｑ１，ｌ（ｕ））にマージ可能である。
【０１０７】
＜近似ＺＤＤ構築処理＞
以降では、近似ＺＤＤ構築装置１０が実行する近似ＺＤＤ構築処理について説明する。実施例２では、図４のステップＳ１０２の処理の詳細のみが実施例１と異なる（つまり、図４のステップＳ１０１及びステップＳ１０３〜ステップＳ１０４は実施例２でも同様である。）。そこで、以降では、図４のステップＳ１０２の処理の詳細について、図１１を参照しながら説明する。図１１は、ＺＤＤが単調減少な組み合わせ集合を表現する場合に、マージ可能なノードの一部のペアのリストを算出する処理の一例を示すフローチャートである。なお、図１１では、特殊でないノードｕに対して、ｓｕｐ（ｕ）の候補となる集合をＣで表す。
【０１０８】
まず、前処理部１０２は、Ｒ←φとする（ステップＳ５０１）。
【０１０９】
次に、前処理部１０２は、ｉを１ずつ増加させながらｉ＝１からｉ＝ｃまで、ステップＳ５０３の処理を繰り返し実行する（ステップＳ５０２）。また、ステップＳ５０３では、前処理部１０２は、ＺＤＤ  Ｇの第ｉ層Ｌｉ中の特殊でない全てのノードｕに対して、ステップＳ５０４〜ステップＳ５０９の処理を繰り返し実行する。
【０１１０】
すなわち、特殊でないノードｕに対して、前処理部１０２は、まず、Ｃ←φとする（ステップＳ５０４）。次に、前処理部１０２は、Ｐ０及びＰ１を以下により定義する（ステップＳ５０５）。
【０１１１】
・Ｐ０←｛ｖ｜ｖはＧのノード，ｕ＝ｖ０｝
・Ｐ１←｛ｖ｜ｖはＧのノード，ｕ＝ｖ１｝
すなわち、０−枝がｕを指すノードの集合をＰ０、１−枝がｕを指すノードの集合をＰ１とする。
【０１１２】
次に、前処理部１０２は、ケース１又はケース２に該当するｓｕｐ（ｕ）の候補（つまり、ケース１又はケース２のいずれかに該当するマージ可能なノード）を探索する（ステップＳ５０６）。この探索処理の詳細は、図１２に示すフローチャートのようになる。図１２は、ケース１又はケース２に該当するｓｕｐ（ｕ）の候補を探索する処理の一例を示すフローチャートである。
【０１１３】
前処理部１０２は、全てのｐ∈Ｐ０∪Ｐ１に対して、ステップＳ６０２の処理と、ステップＳ６０３の処理と、ステップＳ６０５の処理とを繰り返し実行する（ステップＳ６０１）。
【０１１４】
ステップＳ６０２では、前処理部１０２は、ｑ←ｐとする。次に、ステップＳ６０３では、前処理部１０２は、ｕ＝ｚｐ（ｑ，ｌ（ｕ））である間（つまり、ノードｕとノードｚｐ（ｑ，ｌ（ｕ））とが一致している間）、ステップＳ６０４の処理を繰り返し実行する。ステップＳ６０４では、前処理部１０２は、ｑ←ｓｕｐ（ｐ）とする。
【０１１５】
すなわち、ｐ∈Ｐ０である場合は、上記のステップＳ６０３の繰り返しによってケース１に該当するノードｚｐ（ｑ，ｌ（ｕ））が探索される。同様に、ｐ∈Ｐ１である場合には、上記のステップＳ６０３の繰り返しによってケース２に該当するノードｚｐ（ｐ，ｌ（ｕ））が探索される。このとき、ｐはｓｕｐ（ｐ）だけでなくｓｕｐ（ｓｕｐ（ｐ））やｓｕｐ（ｓｕｐ（ｓｕｐ（ｐ）））等のｓｕｐを重ねたノードにもマージ可能であることを用いて、ケース１又はケース２に該当するｚｐ（ｑ，ｌ（ｕ））が探索される（言い換えれば、ｚｐ（ｑ，ｌ（ｕ））がｕと異なるようなｑが探索される。）。
【０１１６】
そして、ステップＳ６０５では、前処理部１０２は、上記のステップＳ６０３の繰り返しで探索されたｚｐ（ｑ，ｌ（ｕ））をＣに追加する。すなわち、前処理部１０２は、Ｃ←Ｃ∪｛ｚｐ（ｑ，ｌ（ｕ））｝とする。これにより、ケース１又はケース２に該当するマージ可能なノードが、ｓｕｐ（ｕ）の候補の集合Ｃに追加される。
【０１１７】
図１１に戻る。ステップＳ５０６に続いて、前処理部１０２は、ケース３に該当するｓｕｐ（ｕ）の候補（つまり、ケース３に該当するマージ可能なノード）を探索する（ステップＳ５０７）。この探索処理の詳細は、図１３に示すフローチャートのようになる。図１３は、ケース３に該当とするｓｕｐ（ｕ）の候補を探索する処理の一例を示すフローチャートである。
【０１１８】
前処理部１０２は、全てのｐ∈Ｐ１に対して、ステップＳ７０２の処理と、ステップＳ７０３の処理と、ステップＳ７０５〜ステップＳ７０６の処理とを繰り返し実行する（ステップＳ７０１）。
【０１１９】
ステップＳ７０２では、前処理部１０２は、ｑ←ｐとする。次に、ステップＳ７０３では、前処理部１０２は、ｕ＝ｚｐ（ｑ１，ｌ（ｕ））かつｑが特殊でないノードである間（つまり、ノードｕとｚｐ（ｑ１，ｌ（ｕ））とが一致しており、かつ、ｑが特殊でないノードである間）、ステップＳ７０４の処理を繰り返し実行する。ステップＳ７０４では、前処理部１０２は、ｑ←ｓｕｐ（ｐ）とする。なお、前処理部１０２は、ｕ≠ｚｐ（ｑ１，ｌ（ｕ））又はｑが特殊なノードとなった場合に繰り返しを終了する。
【０１２０】
次に、ステップＳ７０５では、前処理部１０２は、ｕ≠ｚｐ（ｑ１，ｌ（ｕ））であるか否かを判定する。そして、ｕ≠ｚｐ（ｑ１，ｌ（ｕ））であると判定した場合、前処理部１０２は、ｚｐ（ｑ１，ｌ（ｕ））をＣに追加する。すなわち、前処理部１０２は、Ｃ←Ｃ∪｛ｚｐ（ｑ１，ｌ（ｕ））｝とする。これにより、ケース３に該当するマージ可能なノードが探索され、ｓｕｐ（ｕ）の候補の集合Ｃに追加される。
【０１２１】
一方で、ｕ＝ｚｐ（ｑ１，ｌ（ｕ））であると判定した場合は、前処理部１０２は、ステップＳ７０６の処理は行わない。この場合は、ｚｐ（ｑ１，ｌ（ｕ））はケース３のマージ可能なノードに該当しないためである。
【０１２２】
図１１に戻る。ステップＳ５０７に続いて、前処理部１０２は、偽陽性のエラーの発生数が少ないと思われるマージ可能なノードをＣから選択し、それをｓｕｐ（ｕ）とする（ステップＳ５０８）。すなわち、前処理部１０２は、
【０１２３】
【数１９】
2020201556.tif 000021
とする。
【０１２４】
次に、前処理部１０２は、Ｒ←Ｒ∪｛（ｕ，ｓｕｐ（ｕ））｝とする（ステップＳ５０９）。すなわち、リストＲに対して、ノードのペア（ｕ，ｓｕｐ（ｕ））を追加する。
【０１２５】
以上のように、実施例２では、ＺＤＤ  Ｇが表現する組合せ集合が単調性を有する場合に、マージ可能なペアのリストＲとして保持するペアの数を削減することが可能となる。また、これにより、図４のステップＳ１０３でリストＲからペアを選択する際の計算量（つまり、例えば、各ノードのペアの指標値を計算する際の総計算量）を削減することが可能となり、近似ＺＤＤ構築処理をより高速に実行することが可能となる。
【０１２６】
＜効果及び応用例＞
以上のように、本実施形態に係る近似ＺＤＤ構築装置１０は、与えられたＺＤＤに対して、偽陽性のエラーのみを許容し、かつ、その発生数の少ない近似ＺＤＤを構築することができる。特に、本実施形態に係る近似ＺＤＤ構築装置１０と従来技術とで同程度のサイズの近似ＺＤＤを出力した場合、本実施形態に係る近似ＺＤＤ構築装置１０では、従来技術と比較して、近似ＺＤＤの偽陽性のエラーの発生数を数百倍少なくすることができた。
【０１２７】
なお、偽陽性のエラーのみを許容するＺＤＤは、一例として、以下のような応用が考えられる。
【０１２８】
まず、或る組合せが対象とする組合せ集合に入っているか否かを回答するメンバーシップ問い合わせについて応用可能である。偽陽性のエラーのみを許容するＺＤＤを用いることで、メンバーシップ問い合わせにおいて、本来は含んでいる組合せを含まないと回答してしまうような間違いの発生を防止することができる。偽陽性のエラーのみを許容するＺＤＤが表現する組合せ集合にはもとのＺＤＤが表現する組合せ集合中の全ての組合せが含まれているため、この性質を用いて或る条件を満たす組合せのフィルタリングも可能である。
【０１２９】
次に、組合せ最適化問題にも応用可能である。組合せ最適化問題では、その制約を偽陽性のエラーのみを許容するＺＤＤで表現することによって、その最適化問題の目的関数値の上限が得られる。組合せ最適化問題を解く際に、良い目的関数値の上限を効率的に得られることは、解を探索する上で重要である。
【０１３０】
最後に、仮にもとの組合せ集合に対するメンバーシップ問い合わせが簡単に正しくできる場合、偽陽性のエラーのみを許容するＺＤＤを用いて、もとの組合せ集合中の組合せのランダムサンプリングが可能である。例えば、もとの組合せ集合が線形組合せ不等式を表現していたり、グラフ中の特定の条件を満たす部分グラフを表現していたりする場合がこの状況に相当し、有効なランダムサンプリング可能となる。
【０１３１】
＜近似ＺＤＤ構築装置１０のハードウェア構成＞
最後に、本実施形態に係る近似ＺＤＤ構築装置１０のハードウェア構成について、図１４を参照しながら説明する。図１４は、本発明の実施の形態における近似ＺＤＤ構築装置１０のハードウェア構成の一例を示す図である。
【０１３２】
図１４に示すように、本実施形態に係る近似ＺＤＤ構築装置１０は、ハードウェアとして、入力装置２０１と、表示装置２０２と、外部Ｉ／Ｆ２０３と、ＲＡＭ２０４と、ＲＯＭ（Read Only Memory）２０５と、ＣＰＵ２０６と、通信Ｉ／Ｆ２０７と、補助記憶装置２０８とを有する。これら各ハードウェアは、それぞれがバスＢを介して通信可能に接続されている。
【０１３３】
入力装置２０１は、例えばキーボードやマウス、タッチパネル等であり、ユーザが各種操作を入力するのに用いられる。表示装置２０２は、例えばディスプレイ等であり、近似ＺＤＤ構築装置１０の処理結果を表示する。なお、近似ＺＤＤ構築装置１０は、入力装置２０１及び表示装置２０２の少なくとも一方を有していなくてもよい。
【０１３４】
外部Ｉ／Ｆ２０３は、外部装置とのインタフェースである。外部装置には、記録媒体２０３ａ等がある。近似ＺＤＤ構築装置１０は、外部Ｉ／Ｆ２０３を介して、記録媒体２０３ａ等の読み取りや書き込みを行うことができる。記録媒体２０３ａには、近似ＺＤＤ構築装置１０が有する各機能部（すなわち、入力部１０１、前処理部１０２、操作部１０３及び出力部１０４等）を実現する１以上のプログラム等が記録されていてもよい。
【０１３５】
記録媒体２０３ａには、例えば、フレキシブルディスク、ＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disk）、ＳＤメモリカード（Secure Digital memory card）、ＵＳＢ（Universal Serial Bus）メモリカード等がある。
【０１３６】
ＲＡＭ２０４は、プログラムやデータを一時保持する揮発性の半導体メモリである。ＲＯＭ２０５は、電源を切ってもプログラムやデータを保持することができる不揮発性の半導体メモリである。ＲＯＭ２０５には、例えば、ＯＳ（Operating System）に関する設定情報や通信ネットワークに関する設定情報等が格納されている。
【０１３７】
ＣＰＵ２０６は、ＲＯＭ２０５や補助記憶装置２０８等からプログラムやデータをＲＡＭ２０４上に読み出して処理を実行する演算装置である。
【０１３８】
通信Ｉ／Ｆ２０７は、近似ＺＤＤ構築装置１０を通信ネットワークに接続するためのインタフェースである。近似ＺＤＤ構築装置１０が有する各機能部を実現する１以上のプログラムは、通信Ｉ／Ｆ２０７を介して、所定のサーバ装置等から取得（ダウンロード）されてもよい。
【０１３９】
補助記憶装置２０８は、例えば、ＨＤＤやＳＳＤ等であり、プログラムやデータを格納している不揮発性の記憶装置である。補助記憶装置２０８に格納されているプログラムやデータには、例えば、ＯＳ、当該ＯＳ上で各種機能を実現するアプリケーションプログラム、近似ＺＤＤ構築装置１０が有する各機能部を実現する１以上のプログラム等がある。
【０１４０】
本実施形態に係る近似ＺＤＤ構築装置１０は、図１４に示すハードウェア構成を有することにより、上述した各種処理を実現することができる。なお、図１４では、本実施形態に係る近似ＺＤＤ構築装置１０が１台の装置（コンピュータ）で実現されている場合を示したが、これに限られない。本実施形態に係る近似ＺＤＤ構築装置１０は、複数台の装置（コンピュータ）で実現されていてもよい。また、１台の装置（コンピュータ）には、複数のＣＰＵ２０６や複数のメモリ（ＲＡＭ２０４やＲＯＭ２０５、補助記憶装置２０８等）が含まれていてもよい。
【０１４１】
本発明は、具体的に開示された上記の実施形態に限定されるものではなく、特許請求の範囲から逸脱することなく、種々の変形や変更が可能である。
【符号の説明】
【０１４２】
１０        近似ＺＤＤ構築装置
１０１      入力部
１０２      前処理部
１０３      操作部
１０４      出力部
【図１】
2020201556.tif 000022
【図２】
2020201556.tif 000023
【図３】
2020201556.tif 000024
【図４】
2020201556.tif 000025
【図５】
2020201556.tif 000026
【図６】
2020201556.tif 000027
【図７】
2020201556.tif 000028
【図８】
2020201556.tif 000029
【図９】
2020201556.tif 000030
【図１０】
2020201556.tif 000031
【図１１】
2020201556.tif 000032
【図１２】
2020201556.tif 000033
【図１３】
2020201556.tif 000034
【図１４】
2020201556.tif 000035