(57)【要約】      （修正有）【課題】集合族間の各種演算を高速に行うためのＺＳＤＤ（Zero-suppressed Sentential Decision Diagram）を効率的に構築する。【解決手段】ＺＳＤＤ構築装置１００の演算部２０において、ＺＳＤＤ構築部３２が、グラフのエッジ集合に含まれる各要素に対応するノードを葉ノードとして表現したｖｔｒｅｅのノードに対応する決定ノードと、集合を部分集合Ｘ、Ｙへ分割したときの、集合に含まれる要素又は定数である記号を表す終端ＺＳＤＤ又は決定ノードへの矢印を表す決定ＺＳＤＤであるプライムとサブとのペアを表す要素ノードとを含むＺＳＤＤを構築し、ｖｔｒｅｅの各ノードを、根ノードから順番に対象ノードとし、ｖｔｒｅｅの対象ノードを参照して、再帰的にＺＳＤＤを構築する。【選択図】図４
2018041161.tif 000002
【特許請求の範囲】
【請求項１】
入力されたグラフに基づいて、ノードとエッジとからなる完全二分木であって、前記グラフのエッジ集合Ｅに含まれる各要素に対応するノードを葉ノードとして表現したｖｔｒｅｅを構築するｖｔｒｅｅ構築部と、
前記グラフと、前記構築されたｖｔｒｅｅと、に基づいて、前記グラフのマッチングを表す前記エッジ集合Ｅの部分集合の各々からなる集合である集合族を表す有向非巡回グラフであって、前記ｖｔｒｅｅのノードに対応する決定ノードと、前記エッジ集合Ｅを部分集合Ｘ、Ｙへ分割したときの、前記エッジ集合Ｅに含まれる要素又は定数である記号を表す終端ＺＳＤＤ又は前記決定ノードへの矢印を表す決定ＺＳＤＤであるプライムとサブとのペアを表す要素ノードとを含むＺＳＤＤ（Zero-suppressed Sentential Decision Diagram）を構築するＺＳＤＤ構築部と、
を含み、
前記ＺＳＤＤ構築部は、前記構築されたｖｔｒｅｅの各ノードを、根ノードから順番に対象ノードとし、前記ｖｔｒｅｅの対象ノードを参照して、再帰的にＺＳＤＤを構築するＺＳＤＤ構築装置。
【請求項２】
入力された、台集合Ｓと、ノードとエッジとからなる完全二分木であって、前記台集合Ｓに含まれる各要素に対応するノードを葉ノードとして表現したｖｔｒｅｅと、に基づいて、予め定められた要素数Ｋとなる、前記台集合Ｓの部分集合の各々からなる集合である集合族を表す有向非巡回グラフであって、前記ｖｔｒｅｅのノードに対応する決定ノードと、前記台集合Ｓを部分集合Ｘ、Ｙへ分割したときの、前記台集合Ｓに含まれる要素又は定数である記号を表す終端ＺＳＤＤ又は前記決定ノードへの矢印を表す決定ＺＳＤＤであるプライムとサブとのペアを表す要素ノードとを含むＺＳＤＤ（Zero-suppressed Sentential Decision Diagram）を構築するＺＳＤＤ構築部と、
を含み、
前記ＺＳＤＤ構築部は、前記入力されたｖｔｒｅｅの各ノードを、根ノードから順番に対象ノードとし、前記ｖｔｒｅｅの対象ノードを参照して、再帰的にＺＳＤＤを構築するＺＳＤＤ構築装置。
【請求項３】
ｖｔｒｅｅ構築部が、入力されたグラフに基づいて、ノードとエッジとからなる完全二分木であって、前記グラフのエッジ集合Ｅに含まれる各要素に対応するノードを葉ノードとして表現したｖｔｒｅｅを構築するステップと、
ＺＳＤＤ構築部が、前記グラフと、前記構築されたｖｔｒｅｅと、に基づいて、前記グラフのマッチングを表す前記エッジ集合Ｅの部分集合の各々からなる集合である集合族を表す有向非巡回グラフであって、前記ｖｔｒｅｅのノードに対応する決定ノードと、前記エッジ集合Ｅを部分集合Ｘ、Ｙへ分割したときの、前記エッジ集合Ｅに含まれる要素又は定数である記号を表す終端ＺＳＤＤ又は前記決定ノードへの矢印を表す決定ＺＳＤＤであるプライムとサブとのペアを表す要素ノードとを含むＺＳＤＤ（Zero-suppressed Sentential Decision Diagram）を構築するステップと、
を含み、
前記ＺＳＤＤ構築部が構築するステップは、前記構築されたｖｔｒｅｅの各ノードを、根ノードから順番に対象ノードとし、前記ｖｔｒｅｅの対象ノードを参照して、再帰的にＺＳＤＤを構築するＺＳＤＤ構築方法。
【請求項４】
ＺＳＤＤ構築部が、入力された、台集合Ｓと、ノードとエッジとからなる完全二分木であって、前記台集合Ｓに含まれる各要素に対応するノードを葉ノードとして表現したｖｔｒｅｅと、に基づいて、予め定められた要素数Ｋとなる、前記台集合Ｓの部分集合の各々からなる集合である集合族を表す有向非巡回グラフであって、前記ｖｔｒｅｅのノードに対応する決定ノードと、前記台集合Ｓを部分集合Ｘ、Ｙへ分割したときの、前記台集合Ｓに含まれる要素又は定数である記号を表す終端ＺＳＤＤ又は前記決定ノードへの矢印を表す決定ＺＳＤＤであるプライムとサブとのペアを表す要素ノードとを含むＺＳＤＤ（Zero-suppressed Sentential Decision Diagram）を構築するステップ、
を含み、
前記ＺＳＤＤ構築部が構築するステップは、前記入力されたｖｔｒｅｅの各ノードを、根ノードから順番に対象ノードとし、前記ｖｔｒｅｅの対象ノードを参照して、再帰的にＺＳＤＤを構築するＺＳＤＤ構築方法。
【請求項５】
コンピュータを、請求項１又は２記載のＺＳＤＤ構築装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＺＳＤＤ構築装置、方法、及びプログラムに係り、特に、集合族をグラフとして計算機上に表現し、さらに表現した集合族間の演算を計算機上で実行するためのＺＳＤＤ構築装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
集合Ｓが与えられたとき、Ｓの部分集合を要素とするような集合は集合族とよばれる。様々な問題は、集合族を対象とした計算問題に帰着して解くことができる。たとえば、グラフＧ＝（Ｖ，Ｅ）が与えられたとき、グラフのマッチングとはＥの部分集合のうち、端点を共有するものが存在しないもののことをいう。そのため、マッチングの集合はＥを台集合とした集合族として表現することが可能である。マッチングのうち最大のものを選択する問題は最大マッチング問題とよばれ、多くの応用問題が最大マッチング問題に帰着して解かれている。最大マッチング問題は、可能なマッチングの集合が集合族として表現されているのであれば、集合族の中から最大のものを選択する問題として解くことができる。グラフを対象とした問題のほかにも、処理の対象が集合族として表現されるケースは多数存在する。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Shin-ichi Minato, "Zero-suppressed BDDs for set manipulation in combinatorial problems", In Proceedings of the 30th Design Automation Conference, pp 272-277, 1993.
【非特許文献２】Masaaki Nishino, Norihito Yasuda, Shin-ichi Minato and Masaaki Nagata, "Zero-suppressed Sentential Decision Diagrams", In Proceedings of the 30th AAAI Conference on Articial Intelligence, pp 1058-1066, 2016.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
集合族を対象とした計算は、集合族の大きさが膨大になると効率的に行うことが困難となる。前述のマッチングの個数は、グラフのエッジの総数｜Ｅ｜に対して最悪で指数倍となる可能性があるため、マッチングの集合を明示的に求めてそれに対して処理を行うことは非効率的である。
【０００５】
このような点を鑑みて、集合族を計算に適したデータ構造に変換して保持することによって、集合族を対象とした各種演算を高速に実行するアプローチが存在する。そのようなデータ構造の代表的なものとして、ゼロサプレス型二分決定グラフ（ＺＤＤ）（非特許文献１）がある。ＺＤＤは集合族を有向非巡回グラフ(ＤＡＧ)として表現することによって、集合族の要素数と比べてノード数が少ないグラフとして圧縮して表現し、処理することができるデータ構造である。対象によっては、指数個の部分集合からなるような集合族を、台集合のノードに対して多項式オーダーのノード数からなるＺＤＤとして表現することも可能である。ＺＤＤは集合族を圧縮して表現したうえで、様々な演算を実行可能であることを特徴とする。たとえば、集合族から要素数最大の部分集合を発見したり、集合族に含まれる部分集合の数を数え上げたりするような処理を、ＺＤＤのサイズに比例する計算時間で実行することが可能である。
【０００６】
ＺＤＤを用いた集合族の処理においてボトルネックとなるのが、集合族を表現するＺＤＤを構築する手続きである。ＺＤＤは集合族に対する演算を効率的に実行できるという特徴があるため、演算を繰り返すことで所望の集合族を段階的に構築するアプローチが一般的にはとられる。しかし、その場合には表現したい対象によっては演算の回数が指数的に増加したり、あるいは所望のＺＤＤを構築する課程で生成される中間生成物であるＺＤＤのサイズが非常に大きくなり、演算が効率的に行えなくなるなどの課題がある。
【０００７】
ＺＤＤの構築が非効率的になる課題に対処するため、演算を複数回繰り返すことなくＺＤＤを構築する、トップダウン構築とよばれるＺＤＤ構築法が考案された（非特許文献３参照）。
【０００８】
［非特許文献３］湊：「BDD/ZDD を用いたグラフ列挙索引化技法」オペレーションズ・リサーチ : 経営の科学 57(11), 597-603, 2012-11-01.
【０００９】
トップダウン構築法は、入力として与えられたグラフに対するマッチングの集合や、要素数Ｋの部分集合からなる集合族を表現するＺＤＤを構築するために用いることができる。トップダウン構築を用いると、一度の演算で所望の集合族を表現するＺＤＤを構築することができ、かつその計算時間は構築されたＺＤＤのノード数に対して多項式時間となるため、従来の集合族間の演算を繰り返してＺＤＤを構築する手法と比較して、効率的なＺＤＤの構築を実現できる。
【００１０】
一方、ＺＤＤを集合族を表現するための索引として用いる際の課題として、表現する対象によってはＺＤＤのノード数が増大するという点が挙げられる。ＺＤＤを用いた処理はＺＤＤのノード数に比例する計算時間がかかるため、ＺＤＤのサイズが増大すると処理が非効率的であるという課題があった。
【００１１】
集合族を索引化するための第二のアプローチとして、Zero-suppressed Sentential Decision Diagram (ＺＳＤＤ)（非特許文献２）を用いて集合族を表現する方法が挙げられる。ＺＳＤＤはＺＤＤと同様に集合族をＤＡＧとして表現するが、ＺＤＤと比較してノード数が少ないＤＡＧとして集合族を表現できることが可能である。さらに、ＺＤＤと同様に、ＺＳＤＤは集合族を対象とした様々な演算をＺＳＤＤのノード数に比例する時間で実行可能である。すなわち、ＺＳＤＤをＺＤＤの代替として用いることによって、ＺＤＤを用いたときと比較して高速に集合族を対象とした処理を実行することが可能である。
【００１２】
一方で、ＺＳＤＤを用いたときの課題として、ＺＳＤＤを用いて集合族を対象とした演算を実行しようとした場合、ＺＤＤを用いたときと同様にＺＳＤＤの構築が大きな問題となる。ＺＳＤＤもＺＤＤと同様に集合族間の演算を効率的に実行可能であるため、演算を繰り返し適用することによって、任意の集合族を表現するＺＳＤＤを構築することができる。しかし、ＺＤＤの場合と同様に演算の実行回数が指数的に増加したり、また中間生成物として得られるＺＳＤＤが非常に巨大になり、処理が非効率的になるといった課題がある。さらに、ＺＤＤの場合と異なり、ＺＳＤＤには効率的なトップダウン構築法が存在しないという課題がある。
【００１３】
本発明は、上記問題点を解決するために成されたものであり、集合族間の各種演算を高速に行うためのＺＳＤＤを効率的に構築することができるＺＳＤＤ構築装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記目的を達成するために、第１の発明に係るＺＳＤＤ構築装置は、入力されたグラフに基づいて、ノードとエッジとからなる完全二分木であって、前記グラフのエッジ集合Ｅに含まれる各要素に対応するノードを葉ノードとして表現したｖｔｒｅｅを構築するｖｔｒｅｅ構築部と、前記グラフと、前記構築されたｖｔｒｅｅと、に基づいて、前記グラフのマッチングを表す前記エッジ集合Ｅの部分集合の各々からなる集合である集合族を表す有向非巡回グラフであって、前記ｖｔｒｅｅのノードに対応する決定ノードと、前記エッジ集合Ｅを部分集合Ｘ、Ｙへ分割したときの、前記エッジ集合Ｅに含まれる要素又は定数である記号を表す終端ＺＳＤＤ又は前記決定ノードへの矢印を表す決定ＺＳＤＤであるプライムとサブとのペアを表す要素ノードとを含むＺＳＤＤ（Zero-suppressed Sentential Decision Diagram）を構築するＺＳＤＤ構築部と、を含み、前記ＺＳＤＤ構築部は、前記構築されたｖｔｒｅｅの各ノードを、根ノードから順番に対象ノードとし、前記ｖｔｒｅｅの対象ノードを参照して、再帰的にＺＳＤＤを構築する。
【００１５】
また、第２の発明に係るＺＳＤＤ構築装置は、入力された、台集合Ｓと、ノードとエッジとからなる完全二分木であって、前記台集合Ｓに含まれる各要素に対応するノードを葉ノードとして表現したｖｔｒｅｅと、に基づいて、予め定められた要素数Ｋとなる、前記台集合Ｓの部分集合の各々からなる集合である集合族を表す有向非巡回グラフであって、前記ｖｔｒｅｅのノードに対応する決定ノードと、前記台集合Ｓを部分集合Ｘ、Ｙへ分割したときの、前記台集合Ｓに含まれる要素又は定数である記号を表す終端ＺＳＤＤ又は前記決定ノードへの矢印を表す決定ＺＳＤＤであるプライムとサブとのペアを表す要素ノードとを含むＺＳＤＤ（Zero-suppressed Sentential Decision Diagram）を構築するＺＳＤＤ構築部と、を含み、前記ＺＳＤＤ構築部は、前記入力されたｖｔｒｅｅの各ノードを、根ノードから順番に対象ノードとし、前記ｖｔｒｅｅの対象ノードを参照して、再帰的にＺＳＤＤを構築する。
【００１６】
第３の発明に係るＺＳＤＤ構築方法は、ｖｔｒｅｅ構築部が、入力されたグラフに基づいて、ノードとエッジとからなる完全二分木であって、前記グラフのエッジ集合Ｅに含まれる各要素に対応するノードを葉ノードとして表現したｖｔｒｅｅを構築するステップと、ＺＳＤＤ構築部が、前記グラフと、前記構築されたｖｔｒｅｅと、に基づいて、前記グラフのマッチングを表す前記エッジ集合Ｅの部分集合の各々からなる集合である集合族を表す有向非巡回グラフであって、前記ｖｔｒｅｅのノードに対応する決定ノードと、前記エッジ集合Ｅを部分集合Ｘ、Ｙへ分割したときの、前記エッジ集合Ｅに含まれる要素又は定数である記号を表す終端ＺＳＤＤ又は前記決定ノードへの矢印を表す決定ＺＳＤＤであるプライムとサブとのペアを表す要素ノードとを含むＺＳＤＤ（Zero-suppressed Sentential Decision Diagram）を構築するステップと、を含んで実行することを特徴とし、前記ＺＳＤＤ構築部が構築するステップは、前記構築されたｖｔｒｅｅの各ノードを、根ノードから順番に対象ノードとし、前記ｖｔｒｅｅの対象ノードを参照して、再帰的にＺＳＤＤを構築する。
【００１７】
第４の発明に係るＺＳＤＤ構築方法は、ＺＳＤＤ構築部が、入力された、台集合Ｓと、ノードとエッジとからなる完全二分木であって、前記台集合Ｓに含まれる各要素に対応するノードを葉ノードとして表現したｖｔｒｅｅと、に基づいて、予め定められた要素数Ｋとなる、前記台集合Ｓの部分集合の各々からなる集合である集合族を表す有向非巡回グラフであって、前記ｖｔｒｅｅのノードに対応する決定ノードと、前記台集合Ｓを部分集合Ｘ、Ｙへ分割したときの、前記台集合Ｓに含まれる要素又は定数である記号を表す終端ＺＳＤＤ又は前記決定ノードへの矢印を表す決定ＺＳＤＤであるプライムとサブとのペアを表す要素ノードとを含むＺＳＤＤ（Zero-suppressed Sentential Decision Diagram）を構築するステップ、を含んで実行することを特徴とし、前記ＺＳＤＤ構築部が構築するステップは、前記入力されたｖｔｒｅｅの各ノードを、根ノードから順番に対象ノードとし、前記ｖｔｒｅｅの対象ノードを参照して、再帰的にＺＳＤＤを構築する。
【００１８】
第５の発明に係るプログラムは、コンピュータを、第１又は第２の発明に係るＺＳＤＤ構築装置の各部として機能させるためのプログラムである。
【発明の効果】
【００１９】
本発明のＺＳＤＤ構築装置、方法、及びプログラムによれば、ｖｔｒｅｅのノードに対応する決定ノードと、集合を部分集合Ｘ、Ｙへ分割したときの、集合に含まれる要素又は定数である記号を表す終端ＺＳＤＤ又は決定ノードへの矢印を表す決定ＺＳＤＤであるプライムとサブとのペアを表す要素ノードとを含む、前記グラフのマッチングを表す前記エッジ集合Ｅの部分集合の各々からなる集合である集合族、又は予め定められた要素数Ｋとなる、前記台集合Ｓの部分集合の各々からなる集合である集合族を表すＺＳＤＤを構築する際に、ｖｔｒｅｅの各ノードを、根ノードから順番に対象ノードとし、ｖｔｒｅｅの対象ノードを参照して、再帰的にＺＳＤＤを構築することにより、集合族間の各種演算を高速に行うためのＺＳＤＤを効率的に構築することができる、という効果が得られる。
【図面の簡単な説明】
【００２０】
【図１】ｖｔｒｅｅの一例を示す図である。
【図２】ＺＳＤＤの一例を示す図である。
【図３】ＺＳＤＤの計算機上での表現の一例を示す図である。
【図４】本発明の第１の実施の形態に係るＺＳＤＤ構築装置の構成を示すブロック図である。
【図５】ｖｔｒｅｅを構築する手続きを説明したAlgorithmの一例を示す図である。
【図６】第１の実施の形態のＺＳＤＤを構築する手続きを説明したAlgorithmの一例を示す図である。
【図７】recursiveBuildの処理を説明したAlgorithmの一例を示す図である。
【図８】第１の実施の形態のgetRootの処理を説明したAlgorithmの一例を示す図である。
【図９】第１の実施の形態のbuildDecisionLevelの処理を説明したAlgorithmの一例を示す図である。
【図１０】第１の実施の形態のbuildDecompositionLevel(ｖ,ｚ)の処理を説明したAlgorithmの一例を示す図である。
【図１１】insert(Z,u,z) の処理を説明したAlgorithmの一例を示す図である。
【図１２】本発明の第１の実施の形態に係るＺＳＤＤ構築装置におけるＺＳＤＤ構築処理ルーチンを示すフローチャートである。
【図１３】本発明の第２の実施の形態に係るＺＳＤＤ構築装置の構成を示すブロック図である。
【図１４】第２の実施の形態のＺＳＤＤを構築する手続きを説明したAlgorithmの一例を示す図である。
【図１５】第２の実施の形態のgetRootの処理を説明したAlgorithmの一例を示す図である。
【図１６】第２の実施の形態のbuildDecisionLevelの処理を説明したAlgorithmの一例を示す図である。
【図１７】第２の実施の形態のbuildDecompositionLevelの処理を説明したAlgorithmの一例を示す図である。
【図１８】本発明の第２の実施の形態に係るＺＳＤＤ構築装置におけるＺＳＤＤ構築処理ルーチンを示すフローチャートである。
【発明を実施するための形態】
【００２１】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００２２】
＜本発明の実施の形態に係る概要＞
【００２３】
まず、本発明の実施の形態における概要を説明する。
【００２４】
本発明の実施の形態では、ＺＳＤＤのためのトップダウン構築法を新たに考案する。提案する構築法はＺＤＤのためのトップダウン構築法を、ＺＳＤＤの事情にあわせて拡張したものである。本手法を用いることによって、ＺＤＤのトップダウン構築と同様に単一の手続きで、かつ構築されるＺＳＤＤのサイズに対して線形の時間・空間計算量でＺＳＤＤを構築することが可能である。本発明の実施の形態では、グラフのマッチングの集合を表すＺＳＤＤを構築するためのトップダウン構築法と、Ｋ要素からなる部分集合全てからなるＺＳＤＤを構築するためのトップダウン構築法を示す。
【００２５】
＜本発明の実施の形態に係る原理＞
【００２６】
次に、本発明の実施の形態における原理を説明する。
【００２７】
はじめに以下で利用する記号および概念を導入する。Ｇ＝（Ｖ，Ｅ）をグラフとする。Ｖはノードの集合、Ｅはエッジの集合とする。グラフのマッチングとは、Ｅの部分集合であり、端点を共有しないようなエッジの集合である。
【００２８】
集合族とは、ある台集合Ｚ＝｛Ａ，Ｂ，Ｃ，．．．，｝について、その部分集合Ｓ⊆Ｚを要素とするような集合のことである。例えばＺ＝｛Ａ，Ｂ，Ｃ，Ｄ｝とすると、｛｛Ａ，Ｂ｝，｛Ｂ｝，｛Ｂ，Ｃ｝，｛Ｃ，Ｄ｝｝はＺを台集合とする集合族である。記号
【００２９】
【数１】
2018041161.tif 000003
【００３０】
は空集合を表すとし、記号２ＺはＺのべき集合、すなわちＺの可能な全ての部分集合から構成される集合族を表すとする。また、｜Ｚ｜で集合の要素数を表す。
【００３１】
集合族に対する演算をいくつか定義する。ｆ，ｇを集合族とすると、ｆ∩ｇ＝｛Ｃ｜Ｃ∈ｆかつＣ∈ｇ｝，f∪ｇ＝｛Ｃ｜Ｃ∈ｆまたはＣ∈ｇ｝，
【００３２】
【数２】
2018041161.tif 000004
【００３３】
，
【００３４】
【数３】
2018041161.tif 000005
【００３５】
として、二項演算
【００３６】
【数４】
2018041161.tif 000006
【００３７】
を定義する。
【００３８】
次にＺＳＤＤについて説明する。ＺＳＤＤは集合族を再帰的な（Ｘ，Ｙ）-分割によって分割し、その分割の様子をＤＡＧとして表現したものになる。集合Ｘ，Ｙが台集合Ｚの分割、すなわち
【００３９】
【数５】
2018041161.tif 000007
【００４０】
を満たすとすると、Ｚを台集合とする集合族ｆ（Ｚ）の（Ｘ，Ｙ）分割は、
【００４１】
【数６】
2018041161.tif 000008
・・・（１）
【００４２】
と表される。ここでｐｉ（Ｘ）はＸを台集合とする集合族、ｓｉ（Ｙ）はＹを台集合とする集合族とする。（Ｘ，Ｙ）-分割においては、全てのｉ，ｊ：１＜ｉ＜ｊ≦ｎに対して
【００４３】
【数７】
2018041161.tif 000009
【００４４】
であり、かつ
【００４５】
【数８】
2018041161.tif 000010
【００４６】
を満たすとする。台集合をＺ＝｛Ａ，Ｂ，Ｃ，Ｄ｝，Ｘ＝｛Ａ，Ｂ｝，Ｙ＝｛Ｃ，Ｄ｝としたときの、集合族｛｛Ａ，Ｂ｝，｛Ｂ｝，｛Ｂ，Ｃ｝，｛Ｃ，Ｄ｝｝の（Ｘ，Ｙ）-分割は
【００４７】
【数９】
2018041161.tif 000011
・・・（２）
【００４８】
となる。なお、以下では（Ｘ，Ｙ）-分割を｛（ｐ１，Ｓ１），．．．，（ｐｎ，ｓｎ）｝とも表す。またｐｉをプライム、ｓｉをサブとよぶ。（Ｘ，Ｙ）-分割は集合族に対して再帰的に行うことができる。すなわち、例えば、上述の（Ｘ，Ｙ）-分割におけるｐ１＝｛｛Ａ，Ｂ｝｝は、さらに（Ｂ，Ａ）-分割によって
【００４９】
【数１０】
2018041161.tif 000012
【００５０】
と分割することができる。
【００５１】
続いてｖｔｒｅｅを導入する。ｖｔｒｅｅは台集合に含まれる各アイテムに対応するノードを葉とするような完全二分木のことである。図１は４つのアイテムＡ，Ｂ，Ｃ，Ｄに対するｖｔｒｅｅの例である。ｖｔｒｅｅの中間ノード（葉でないノード）ｖは、その部分木の葉ノードからなる変数の集合の分割を表現している。すなわち、ｖを根とする部分木の葉ノードに対応するアイテムの集合を、ｖの左側の子ノードを根とする部分木（ｖｌとする）の葉ノードに対応するアイテム集合と、ｖの右側の子ノードを根とする部分木（ｖｒとする）の葉ノードに対応するアイテム集合とに分割する。図１のｖｔｒｅｅの根ノードｖ３は、Ａ，ＢとＣ，Ｄへの分割に対応し、根の左側の子ノードｖ１はＢとＡへの分割に対応する。ｖｔｒｅｅのノードのうち、左側の子ノードが葉ノードであるようなノードを決定ｖｔｒｅｅノードとよぶ。決定ｖｔｒｅｅノードではないノードを分割ｖｔｒｅｅノードとよぶ。
【００５２】
ＺＳＤＤはあるｖｔｒｅｅが与えられたときに、そのｖｔｒｅｅにもとづいて集合族を再帰的に分割することによって、ＤＡＧとして表現したものである。αをＺＳＤＤ、αが表す集合族を<α>とすると、以下のようにＺＳＤＤは再帰的に定義される。
【００５３】
【数１１】
2018041161.tif 000013
2018041161.tif 000014
【００５４】
ここで
【００５５】
【数１２】
2018041161.tif 000015
【００５６】
を定数ＺＳＤＤとよび、Ｘ、±ＸをリテラルＺＳＤＤとよぶ。定数ＺＳＤＤとリテラルＺＳＤＤとをあわせて終端ＺＳＤＤとよぶ。一方、ある（Ｘ，Ｙ）-分割に対応するＺＳＤＤは分解ＺＳＤＤとよぶ。図２に集合族｛｛Ａ，Ｂ｝，｛Ｂ｝，｛Ｂ，Ｃ｝，｛Ｃ，Ｄ｝｝を表すＺＳＤＤを示す。図２中の丸ノードは、そのノードを根とするＤＡＧが表現する分解ＺＳＤＤを表しており、丸ノードを決定ノードとよぶ。決定ノード中の数字は対応するｖｔｒｅｅのノードを表している。決定ノードを親ノードとする四角いノードの対は要素ノードとよばれ、（Ｘ，Ｙ）分割｛（ｐ１，ｓ１），．．．，（ｐｎ，ｓｎ）｝における、あるプライムとサブのペア（ｐｉ，ｓｉ）を表している。
【００５７】
対のうち左側の四角がプライムを、右側の四角がサブを表している。プライム、サブはそれぞれ別の終端ＺＳＤＤもしくは決定ＺＳＤＤであり、終端ＺＳＤＤの場合は四角中に対応する終端ＺＳＤＤの記号を表記して表し、決定ＺＳＤＤの場合は別の決定ノードへの矢印として表現している。ある決定ノードと、その子ノードである要素ノード群とである（Ｘ，Ｙ）分割を表現している。すなわち、各要素ノードがあるプライムとサブのペア（ｐ，ｓ）に対応している。なお、ＺＳＤＤではサブが
【００５８】
【数１３】
2018041161.tif 000016
【００５９】
となるようなペアは省略する。ＺＳＤＤ中に
【００６０】
【数１４】
2018041161.tif 000017
【００６１】
に対応するような決定ノードが存在したならば、前者はαに、後者は
【００６２】
【数１５】
2018041161.tif 000018
【００６３】
にそれぞれ置き換える。
【００６４】
図２のＺＳＤＤの計算機上での表現方法を図３に示す。ＺＳＤＤは計算機上では、各中間ｖｔｒｅｅノードに対応する決定ＺＳＤＤノードの配列の集合として表現される。図３では中間ｖｔｒｅｅノード１、３、５のそれぞれについて、要素数１の配列が格納されている様子が表されている。配列の各要素は１つの決定ＺＳＤＤノードを、[（ｐ１，ｓ１），．．．，（ｐｎ，ｓｎ）］としてその子ノードである要素の集まりによって表している。ｐｉ，ｓｉは終端ＺＳＤＤを表す場合はその終端ＺＳＤＤに対応する記号
【００６５】
【数１６】
2018041161.tif 000019
【００６６】
として、そうでない場合にはｐｉ，ｓｉが対応する決定ＺＳＤＤノードの計算機中でのアドレスを保持する。図３中ではアドレスはｖｔｒｅｅノードＩＤと、そのｖｔｒｅｅノードＩＤに対応する配列中での対象の決定ＺＳＤＤのインデックスのペアとして表現される。
【００６７】
＜本発明の第１の実施の形態に係るＺＳＤＤ構築装置の構成＞
【００６８】
次に、本発明の第１の実施の形態に係るＺＳＤＤ構築装置の構成について説明する。図４に示すように、本発明の第１の実施の形態に係るＺＳＤＤ構築装置１００は、ＣＰＵと、ＲＡＭと、後述するＺＳＤＤ構築処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。このＺＳＤＤ構築装置１００は、機能的には図４に示すように入力部１０と、演算部２０と、出力部５０とを備えている。
【００６９】
入力部１０は、マッチングの集合を、計算する対象となるグラフＧ＝（Ｖ，Ｅ）として受け付ける。
【００７０】
演算部２０は、ｖｔｒｅｅ構築部３０と、ＺＳＤＤ構築部３２とを含んで構成されている。
【００７１】
ｖｔｒｅｅ構築部３０は、以下に説明するように、入力されたグラフＧに基づいて、ノードとエッジとからなる完全二分木であって、グラフのエッジ集合Ｅに含まれる各要素に対応するノードを葉ノードとして表現したｖｔｒｅｅを構築する。
【００７２】
ｖｔｒｅｅを構築する手続きについて図５のAlgorithm1に示す。まずステップ１として、グラフのbranch decompositionを計算する。グラフＧ＝（Ｖ，Ｅ）のbranch decompositionとは、木の葉ノードがＥの各辺に対応するような、２｜Ｅ｜−１ノードからなる完全二分木である（非特許文献４参照）。
【００７３】
［非特許文献４］Neil Robertson and P. D. Seymour, "Graph Minors. X. Obstructionsto Tree Decomposition", Journal of Combonatorial Theory B (52), pp 153-190,1991.
【００７４】
グラフが与えられたときに、そのbranch decompositionを求める方法として、例えば非特許文献５にある方法などが利用できる。
【００７５】
［非特許文献５］William Cook and Paul Seymour, "Tour Merging via Branchdecomposition", INFORMS Journal on Computing 15 (3), pp 233-248,2003.
【００７６】
次にステップ２として、あるエッジｅ∈Ｅを任意に定める。次にステップ３として、完全二分木であるbranch decompositionに、ｅが相当する葉ノードと、その隣接するノードとの間に新たにノードを追加し、かつ追加したノードを根とする根付き二分木を構築する。そのような根付き木は容易に求めることができる。得られた根付き二分木の葉ノードを除く各ノードは必ず２つの子ノードをもつことになる。次にステップ４で得られた根付き部分木の各中間ノードに対して、二つの子ノードを根とする部分木の大きさを調べ、小さな子ノードを左側部分木、大きな子ノードを右側部分木として設定する。こうして構築された根付き木はｖｔｒｅｅとなるため、ステップ５で得られたｖｔｒｅｅを出力する。また、各ｖｔｒｅｅノードｖについてfrontier(ｖ)を定義する。frontier(ｖ)はグラフのエッジの集合Ｅの分割であるエッジの集合Ｅ１とＥ２のそれぞれの誘導グラフに共通して含まれるノードの集合とする。ここでＥ１とＥ２は、ｖｔｒｅｅからノードｖを除いて得られる２つの木に含まれる葉ノードに対応するグラフのエッジの集合である。
【００７７】
ＺＳＤＤ構築部３２は、以下に説明するように、入力されたグラフＧと、構築されたｖｔｒｅｅと、に基づいて、グラフのマッチングを表すエッジ集合Ｅの部分集合の各々からなる集合である集合族を表す有向非巡回グラフであって、ｖｔｒｅｅのノードに対応する決定ノードと、エッジ集合Ｅを部分集合Ｘ、Ｙへ分割したときの、エッジ集合Ｅに含まれる要素又は定数である記号を表す終端ＺＳＤＤ又は決定ノードへの矢印を表す決定ＺＳＤＤであるプライムとサブとのペアを表す要素ノードとを含むＺＳＤＤを構築する。ここで、構築されたｖｔｒｅｅの各ノードを、根ノードから順番に対象ノードとし、ｖｔｒｅｅの対象ノードを参照して、再帰的にＺＳＤＤを構築し、構築したＺＳＤＤを出力部５０に出力する。
【００７８】
ＺＳＤＤを構築する手続きについて図６のAlgorithm2を用いて説明する。まず入力としてグラフＧ＝（Ｖ，Ｅ）と、構築されたｖｔｒｅｅとを受け取ったあとに、ステップ１、２で配列Ｚの各要素を初期化する。配列Ｚは上記図３に示す、ＺＳＤＤの計算機内での表現に用いられる配列である。なお、図３ではＺ［ｖ］に対応する配列の要素は決定ＺＳＤＤノードを表すとし、かつ決定ＺＳＤＤノードはその子ノードである要素ＺＳＤＤノードのリストによって表現されるとしたが、以下では各決定ＺＳＤＤノードはmate配列とよばれる配列を追加で保持するものとする。mate配列は｜Ｖ｜次元の整数値を保持する配列であり、ＺＳＤＤ構築の途中段階における、決定ＺＳＤＤノードの状態を表現するために用いられる。配列Ｚを初期化したのち、ステップ４でサブルーチンgetRootを呼び出す。getRootはＺＳＤＤの根に相当する決定ＺＳＤＤノードを生成する手続きである。処理の詳細は後述する。getRootで生成される決定ＺＳＤＤノードはmate配列を要素として持つが、子ノードは保持しない。子ノードは以降のトップダウン構築手続きで逐次構築される。ステップ５で再帰的なＺＳＤＤ構築手続きであるrecursiveBuildに、vrootとＺを引数として与えることで、冗長なノードを含むＺＳＤＤを構築する。recursiveBuildについては後述する。ステップ６で構築したＺＳＤＤを簡約化する。簡約化の手続きとしては非特許文献２に記載のtrimmingのための手続きを用いることができる。ステップ７でＺＳＤＤを出力し、処理を終了する。
【００７９】
次に、上記Algorithm2におけるrecursiveBuildについて図７に示すAlgorithm3をもとに説明する。recursiveBuildの挙動は、引数として与えられた対象ノードとしてのｖｔｒｅｅノードが決定ｖｔｒｅｅノードであるかどうかによって異なる。ステップ１で与えられたｖｔｒｅｅノードｖが決定ｖｔｒｅｅノードであるかを判定し、決定ｖｔｒｅｅノードであったならステップ２〜ステップ２５を実行し、そうでなければステップ２７〜ステップ３１を実行する。ｖが決定ｖｔｒｅｅノードであったならば、Ｚ［ｖ］に格納されている各決定ノードｚについて、まず空の配列elemsを準備する（ステップ３）。その後、ｂ∈｛ftrue,false｝について、buildDecisionLevel(v,z,b)を実行する（ステップ５）。buildDecisionLevelは決定ＺＳＤＤノードｚの子ノードである要素ノードのsubに相当するノードｓを生成するための手続きである。処理については後述する。ステップ６でｓが終端ノード
【００８０】
【数１７】
2018041161.tif 000020
【００８１】
であるかを判定し、もし
【００８２】
【数１８】
2018041161.tif 000021
【００８３】
であるならばステップ４に遷移する（ステップ７）。次にステップ８でｓが終端ＺＳＤＤノードかどうかを確認し、もしｓが終端ＺＳＤＤノードでないならばステップ９の処理を実行する。ここで処理insert(Z,u,z)は図１１に示すAlgorithm7に記載の処理を行い、Ｚ［ｕ］に既にzが含まれているならそのアドレスを、そうでないならＺ［ｕ］にｚを追加したうえでそのアドレスを返す処理である。ステップ１１でｂがtrueかどうかを確認し、trueであるならばステップ１２でｐにεを設定し、そうでないならばステップ１４でｐに
【００８４】
【数１９】
2018041161.tif 000022
【００８５】
を設定する。ステップ１６でelemsに(p,s)の対からなる要素ノードを追加する。ステップ１８で、elemsが要素ノード
【００８６】
【数２０】
2018041161.tif 000023
【００８７】
のみを要素として含むのならば、それらを削除して代わりに
【００８８】
【数２１】
2018041161.tif 000024
【００８９】
をelemsに加える。ステップ２１でelemsに含まれる要素ノード群をzの子ノードとして設定する。全てのｚ∈Ｚ［ｖ］について処理が終了したならば、ステップ２３でｖｒが葉ノードであるかどうかを確認し、葉ノードでない場合にはステップ２４でrecursiveBuild(ｖｒ,Ｚ)を呼び出す。ｖｔｒｅｅノードｖが決定ｖｔｒｅｅノードでない場合は、ステップ２７〜ステップ３０で全てのｚ∈Ｚ［ｖ］について、buildDecompositionLevel(ｖ,ｚ)を呼び出してｚの子ノード群elemsを計算し、ｚの子ノードとして設定する。buildDecompositionLevel(ｖ,ｚ)の具体的な処理内容については後述する。その後、ステップ３０、３１でｖｌ,ｖｒをそれぞれ引数としてrecursiveBuildを呼び出す。全ての計算が終わるとＺに計算済みのＺＳＤＤが格納されているため、これを出力として取り出して処理を終了する。
【００９０】
次にgetRootの処理について図８に示すAlgorithm4をもとに説明する。Algorithm4では、ステップ１、２でmate配列ｍの全ての要素にシンボルUntouchを格納し、ステップ４でｍのみを要素として含むリストを出力する。
【００９１】
次にbuildDecisionLevelの処理について図９に示すAlgorithm5をもとに説明する。まずステップ１でｚのmate配列をｍにコピーする。ステップ２でｂがtrueかどうかを確認して、trueであった場合にはステップ３〜ステップ８を実行する。ステップ３ではｖｌがｖｔｒｅｅの葉ノードであることを利用して、ｖｌに相当するグラフのエッジの両端点ｕ１，ｕ２を取り出す。ステップ４でｍ［ｕ１］＝Touchまたはｍ［ｕ２］＝Touchを満たすかを調べ、もし満たす場合には終端ＺＳＤＤ
【００９２】
【数２２】
2018041161.tif 000025
【００９３】
を出力して処理を終了する。ステップ７、８でｍ［ｕ１］、ｍ［ｕ２］のそれぞれに記号Touchを設定する。ステップ１０で、frontier(ｖ)に含まれていて、かつfrontier(ｖｒ)に含まれないmate配列の要素の各インデックスｕについて、ｍ［ｕ］＝Reserveであるかを調べ（ステップ１１）、もし条件を満たすならば
【００９４】
【数２３】
2018041161.tif 000026
【００９５】
を出力し処理を終了する。そうでないならばｍ［ｕ］にFinishを設定する（ステップ１４）。ステップ１７でｖｒが終端ｖｔｒｅｅノードであるかを調べる。もし終端ｖｔｒｅｅノードでないのであれば、ｍをmate配列に設定した、新しいＺＳＤＤノードを出力する（ステップ２９）。もしｖｒが終端ｖｔｒｅｅノードであるのならばステップ１８に進み、（ｕ１，ｕ２）をｖｒに相当するエッジの端点に設定する。ステップ１９〜ステップ２７で、ｍ［ｕ１］とｍ［ｕ２］の値の組合せに応じた終端ＺＳＤＤを出力して処理を終了する。
【００９６】
次にbuildDecompositionLevel(ｖ,ｚ)で行う処理について図１０に示すAlgorithm6を用いて説明する。ステップ１で空の配列elemsを用意する。次にステップ２、３でｚのmate配列をコピーした配列mpとmsを作成する。次にステップ４〜ステップ６でfrontier(ｖｌ)−frontier(ｖｒ)の各要素についてmp[u]をFinishedに設定する。ステップ７〜ステップ９でfrontier(ｖｒ)−frontier(ｖｌ)の各要素についてms[ｕ]をFinishedに設定する。ステップ１０でfrontier(ｖｌ)とfrontier(ｖｒ)に共通なノードの集合commonを計算する。ステップ１１−１８で、mate配列mpとmsの、commonに含まれるノードに対応する要素への可能な割り当てパターンを全て列挙し、その割り当てパターンに応じてm'p、m'sの値を設定し、elemsの要素を設定する。commonへ含まれる要素への可能な割り当てパターンは各u∈commonに対応する要素への割り当て方の組合せによって以下のように設定する。ｚのmate配列のｕに対応する値がReservedの場合、可能な割り当てパターンはm'p[ｕ]＝Reservedかつm's[ｕ]＝Touchまたはm'p[ｕ]＝Touchかつm's[ｕ]＝Reservedとなる。ｚのmate配列のｕに対応する値がTouchの場合、可能な割り当てパターンはm'p[ｕ]＝Touchかつm's[ｕ]＝Touchとなる。ｚのmate配列のｕに対応する値がUntouchの場合、可能な割り当てパターンはm'p[ｕ]＝Reservedかつm's[ｕ]＝Touchまたはm'p[ｕ]＝Touchかつm's[ｕ]＝Untouchとなる。各パターンは(u,a,b)の３つ組の集合として表される。ここでuはノードの値、ａはm'p[ｕ]の値、ｂはm's[ｕ]の値である。これらの各パターンについて、ステップ１２、１３でmp,msをコピーしたm'p,m'sを作成し、ステップ１４−１６でm'p,m'sの各要素をパターンに応じて更新する。ステップ１８、１９でmp,msを最終的に更新する。
【００９７】
＜本発明の第１の実施の形態に係るＺＳＤＤ構築装置の作用＞
【００９８】
次に、本発明の第１の実施の形態に係るＺＳＤＤ構築装置１００の作用について説明する。入力部１０においてマッチングの集合を計算する対象となるグラフＧ＝（Ｖ，Ｅ）を受け付けると、ＺＳＤＤ構築装置１００は、図１２に示すＺＳＤＤ構築処理ルーチンを実行する。
【００９９】
まず、ステップＳ１００では、入力部１０で受け付けたグラフＧに基づいて、ノードとエッジとからなる完全二分木であって、グラフのエッジ集合Ｅに含まれる各要素に対応するノードを葉ノードとして表現したｖｔｒｅｅを構築する。
【０１００】
次に、ステップＳ１０２では、入力部１０で受け付けたグラフＧと、ステップＳ１００で構築されたｖｔｒｅｅと、に基づいて、グラフのマッチングを表すエッジ集合Ｅの部分集合の各々からなる集合である集合族を表す有向非巡回グラフであって、ｖｔｒｅｅのノードに対応する決定ノードと、エッジ集合Ｅを部分集合Ｘ、Ｙへ分割したときの、エッジ集合Ｅに含まれる要素又は定数である記号を表す終端ＺＳＤＤ又は決定ノードへの矢印を表す決定ＺＳＤＤであるプライムとサブとのペアを表す要素ノードとを含むＺＳＤＤを構築する。ここで、構築されたｖｔｒｅｅの各ノードを、根ノードから順番に対象ノードとし、ｖｔｒｅｅの対象ノードを参照して、再帰的にＺＳＤＤを構築し（Algrithm2,Algrithm3参照）、構築したＺＳＤＤを出力部５０に出力する。
【０１０１】
以上説明したように、本発明の第１の実施の形態に係るＺＳＤＤ構築装置によれば、構築されたｖｔｒｅｅのノードに対応する決定ノードと、エッジ集合を部分集合Ｘ、Ｙへ分割したときの、エッジ集合に含まれる要素又は定数である記号を表す終端ＺＳＤＤ又は決定ノードへの矢印を表す決定ＺＳＤＤであるプライムとサブとのペアを表す要素ノードとを含むＺＳＤＤを構築する際に、ｖｔｒｅｅの各ノードを、根ノードから順番に対象ノードとし、ｖｔｒｅｅの対象ノードを参照して、再帰的にＺＳＤＤを構築することにより、集合族間の各種演算を高速に行うための、グラフのマッチングを表すエッジ集合Ｅの部分集合の各々からなる集合である集合族を表すＺＳＤＤを効率的に構築することができる。
【０１０２】
＜本発明の第２の実施の形態に係るＺＳＤＤ構築装置の構成＞
【０１０３】
次に、本発明の第２の実施の形態に係るＺＳＤＤ構築装置の構成について説明する。なお、第１の実施の形態と同様となる箇所については同一符号を付して説明を省略する。
【０１０４】
第２の実施の形態では、台集合Ｓの要素数Ｋからなる部分集合からなる集合族を表すＺＳＤＤを構築する手続きを行う。第１の実施の形態におけるマッチングの場合と類似であるが、グラフを入力として受け取らない点が異なる。また、第２の実施の形態では、ｖｔｒｅｅは任意のｖｔｒｅｅを外部から与えられるとする。ただし、与えられたｖｔｒｅｅでは、ｖｒが葉ノードであるような分岐ｖｔｒｅｅノードは含まれないとする。
【０１０５】
図１３に示すように、本発明の第２の実施の形態に係るＺＳＤＤ構築装置２００は、ＣＰＵと、ＲＡＭと、後述するＺＳＤＤ構築処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。このＺＳＤＤ構築装置２００は、機能的には図１３に示すように入力部２１０と、演算部２２０と、出力部２５０とを備えている。
【０１０６】
入力部２１０は、台集合Ｓ、及びｖｔｒｅｅの入力を受け付ける。ｖｔｒｅｅは、ノードとエッジとからなる完全二分木であって、台集合Ｓに含まれる各要素に対応するノードを葉ノードとして表現したものである。
【０１０７】
演算部２２０は、ＺＳＤＤ構築部２３２を含んで構成されている。
【０１０８】
ＺＳＤＤ構築部２３２は、以下に説明するように入力された、台集合Ｓと、ｖｔｒｅｅと、に基づいて、予め定められた要素数Ｋとなる、台集合Ｓの部分集合の各々からなる集合である集合族を表す有向非巡回グラフであって、ｖｔｒｅｅのノードに対応する決定ノードと、台集合Ｓを部分集合Ｘ、Ｙへ分割したときの、台集合Ｓに含まれる要素又は定数である記号を表す終端ＺＳＤＤ又は決定ノードへの矢印を表す決定ＺＳＤＤであるプライムとサブとのペアを表す要素ノードとを含むＺＳＤＤを構築する。ここで、入力されたｖｔｒｅｅの各ノードを、根ノードから順番に対象ノードとし、ｖｔｒｅｅの対象ノードを参照して、再帰的にＺＳＤＤを構築し、構築したＺＳＤＤを出力部２５０に出力する。
【０１０９】
第２の実施の形態のＺＳＤＤ構築処理について、図１４に示すAlgorithm8を用いて説明する。まずステップ１〜ステップ３で全てのｖｔｒｅｅノードｖに対してＺ［ｖ］を初期化する。ステップ４でＺ［ｖｒｏｏｔ］をgetRootの実行結果で初期化する。getRootの処理については後述する。次にステップ４でrecursive-Build(Algorithm3、マッチングの場合と同様)を実行し、ステップ５でReduce処理（マッチングの場合と同様）を実行する。getRoot、buildDecisionLevel、buildDecompo-sitionLevelはマッチングの場合と異なる手続きを実行する。それぞれの処理について以下に説明する。なお、以下の手続きでは、ＺＳＤＤの状態は自然数ｃで表現する。
【０１１０】
getRoot手続きについて図１５に示すAlgorithm9に示す。ステップ１でｃにＫを代入して、ステップ２でｃを状態とする１つのＺＳＤＤノードからなる集合を出力する。
【０１１１】
buildDecisionLevelの手続きについて図１６に示すAlgorithm10で説明する。まずステップ１でｃにＺＳＤＤノードｚの状態をコピーする。もしb=trueの場合（ステップ２）、c=0であれば
【０１１２】
【数２４】
2018041161.tif 000027
【０１１３】
を出力し、（ステップ３、４）そうでないならばｃをｃ−１に更新する。ステップ９でｃ＝０であったならば、εを出力する。もしｖｒが葉ノードであったならば、ｃ＝１のときに
【０１１４】
【数２５】
2018041161.tif 000028
【０１１５】
を出力し、そうでない場合に
【０１１６】
【数２６】
2018041161.tif 000029
【０１１７】
を出力する（ステップ１２−１７）。もしｖｒが葉ノードでなければ、ｃを状態とするＺＳＤＤノードを出力して処理を終了する（ステップ１９）。
【０１１８】
buildDecompositionLevel手続きについて図１７に示すAlgorithm11を用いて説明する。まずステップ１でｃにｚの状態をコピーする。次にelemsを初期化する（ステップ２）。ステップ３〜ステップ１７でｉを０からｃまでの各値に設定して処理を行う。ステップ４、５でｃｐ,ｃｓの値をｉの値に応じて設定する。ステップ６〜ステップ１６では、ｃｐ,ｃｓの値に応じて処理を分岐する。ｃｐ＝０の場合、ｃｓ＝０の場合、それ以外の場合について、それぞれelemsに(ε,ｚｓ),(ｚｐ,ε)、(ｚｐ,ｚｓ)を追加する。ここでｚｐ,ｚｓはそれぞれｃｐ,ｃｓを状態としてもつユニークなＺＳＤＤノードのアドレスである。最後にステップ１８でelemsを出力して処理を終了する。
＜本発明の第２の実施の形態に係るＺＳＤＤ構築装置の作用＞
【０１１９】
次に、本発明の第２の実施の形態に係るＺＳＤＤ構築装置２００の作用について説明する。入力部２１０において台集合Ｓ、及びｖｔｒｅｅを受け付けると、ＺＳＤＤ構築装置２００は、図１８に示すＺＳＤＤ構築処理ルーチンを実行する。
【０１２０】
ステップＳ２００では、入力部２１０で受け付けた台集合Ｓと、ｖｔｒｅｅと、に基づいて、予め定められた要素数Ｋとなる、台集合Ｓの部分集合の各々からなる集合である集合族を表す有向非巡回グラフであって、ｖｔｒｅｅのノードに対応する決定ノードと、台集合Ｓを部分集合Ｘ、Ｙへ分割したときの、台集合Ｓに含まれる要素又は定数である記号を表す終端ＺＳＤＤ又は決定ノードへの矢印を表す決定ＺＳＤＤであるプライムとサブとのペアを表す要素ノードとを含むＺＳＤＤを構築する。ここで、入力されたｖｔｒｅｅの各ノードを、根ノードから順番に対象ノードとし、ｖｔｒｅｅの対象ノードを参照して、再帰的にＺＳＤＤを構築し（Algorithm8参照）、構築したＺＳＤＤを出力部２５０に出力する。
【０１２１】
以上説明したように、本発明の第２の実施の形態に係るＺＳＤＤ構築装置によれば、入力されたｖｔｒｅｅのノードに対応する決定ノードと、台集合Ｓを部分集合Ｘ、Ｙへ分割したときの、台集合Ｓに含まれる要素又は定数である記号を表す終端ＺＳＤＤ又は決定ノードへの矢印を表す決定ＺＳＤＤであるプライムとサブとのペアを表す要素ノードとを含むＺＳＤＤを構築する際に、ｖｔｒｅｅの各ノードを、根ノードから順番に対象ノードとし、ｖｔｒｅｅの対象ノードを参照して、再帰的にＺＳＤＤを構築することにより、集合族間の各種演算を高速に行うための、予め定められた要素数Ｋとなる、台集合Ｓの部分集合の各々からなる集合である集合族を表すＺＳＤＤを効率的に構築することができる。
【０１２２】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【符号の説明】
【０１２３】
１０、２１０  入力部
２０、２２０  演算部
３０   ｖｔｒｅｅ構築部
３２、２３２  ＺＳＤＤ構築部
５０、２５０  出力部
１００、２００       ＺＳＤＤ構築装置
【図１】
2018041161.tif 000030
【図２】
2018041161.tif 000031
【図３】
2018041161.tif 000032
【図４】
2018041161.tif 000033
【図５】
2018041161.tif 000034
【図６】
2018041161.tif 000035
【図７】
2018041161.tif 000036
【図８】
2018041161.tif 000037
【図９】
2018041161.tif 000038
【図１０】
2018041161.tif 000039
【図１１】
2018041161.tif 000040
【図１２】
2018041161.tif 000041
【図１３】
2018041161.tif 000042
【図１４】
2018041161.tif 000043
【図１５】
2018041161.tif 000044
【図１６】
2018041161.tif 000045
【図１７】
2018041161.tif 000046
【図１８】
2018041161.tif 000047