(57)【特許請求の範囲】
【請求項１】
入力された演算命令と、ノードとエッジとからなる完全二分木であって、集合Ｚに含まれる各要素に対応するノードを葉ノードとして表現したｖｔｒｅｅと、に基づいて、前記演算命令の結果である、前記ｖｔｒｅｅから求まる前記集合Ｚの部分集合の各々からなる集合である集合族ｆ（Ｚ）を表す有向非巡回グラフであって、前記ｖｔｒｅｅのノードに対応する決定ノードと、前記集合Ｚを分割した部分集合Ｘ、Ｙに分けて、前記部分集合Ｘの部分集合からなる集合族と部分集合Ｙの部分集合からなる集合族との結合演算を用いて、前記集合族ｆ（Ｚ）を表現したときの、前記結合演算を表す要素ノードとを含むＺＳＤＤ（Zero-suppressed Sentential Decision Diagram）を演算する演算処理部
を含み、
前記ＺＳＤＤは、空集合との結合演算で表わされる要素ノードが省略されて表される演算実行装置。
【請求項２】
前記演算処理部は、前記演算命令と、前記ｖｔｒｅｅと、前記演算命令の引数となる前記ＺＳＤＤ、及び変数の少なくとも一方とに基づいて、前記演算命令の結果であるＺＳＤＤを演算する請求項１記載の演算実行装置。
【請求項３】
前記演算処理部は、
前記入力された演算命令が、定数でない前記ＺＳＤＤが引数αとなり、前記ｖｔｒｅｅのノードを引数ｖとする演算命令Ｅｘｐａｎｄである場合に、前記引数αであるＺＳＤＤに対応する前記ｖｔｒｅｅのノードをノードｕとし、
前記ノードｕと、前記引数ｖであるノードとの関係に応じて、前記引数αである前記ＺＳＤＤ、
【数１】
0006451997.tif 000029
であるＺＳＤＤ、及び
【数２】
0006451997.tif 000030
であるＺＳＤＤの何れか一つを返す請求項１又は２記載の演算実行装置。
【請求項４】
前記演算処理部は、
前記入力された演算命令が、前記要素ノードの集合が引数γとなる演算命令ＵｎｉｑｕｅＤである場合に、前記引数γとなる前記要素ノードの集合に要素ノードが含まれなければ、定数ＺＳＤＤである⊥を返し、
前記引数γとなる前記要素ノードの集合が、
【数３】
0006451997.tif 000031
、又は
【数４】
0006451997.tif 000032
であれば、ＺＳＤＤであるαを返し、
前記引数γとなる前記要素ノードの集合が、
【数５】
0006451997.tif 000033
及び
【数６】
0006451997.tif 000034
の何れでもなければ、前記引数γとなる前記要素ノードの集合に対応する前記決定ノードを作成して、決定ノードテーブルに格納する請求項３記載の演算実行装置。
【請求項５】
前記演算処理部は、前記入力された演算命令が、ＺＳＤＤが引数αとなる演算命令Ｃｏｍｐｒｅｓｓである場合に、前記引数αとなるＺＳＤＤに含まれる要素のノードの集合｛（ｐ1，ｓ1），・・・，（ｐｎ，ｓｎ）｝のうち、ｓｉ＝ｓｊとなる要素ノードのペア（ｐi，ｓi），（ｐj，ｓj）を、ｐiが表す集合族とｐjが表す集合族との和であるＵｎｉｏｎ（ｐi，ｐj）を用いた（Ｕｎｉｏｎ（ｐi，ｐj），ｓｉ）に置き換えた、前記引数αとなるＺＳＤＤを返す請求項４記載の演算実行装置。
【請求項６】
演算処理部を含む、演算実行装置における演算実行方法であって、
前記演算処理部は、入力された演算命令と、ノードとエッジとからなる完全二分木であって、集合Ｚに含まれる各要素に対応するノードを葉ノードとして表現したｖｔｒｅｅと、に基づいて、前記演算命令の結果である、前記ｖｔｒｅｅから求まる前記集合Ｚの部分集合の各々からなる集合である集合族ｆ（Ｚ）を表す有向非巡回グラフであって、前記ｖｔｒｅｅのノードに対応する決定ノードと、前記集合Ｚを分割した部分集合Ｘ、Ｙに分けて、前記部分集合Ｘの部分集合からなる集合族と部分集合Ｙの部分集合からなる集合族との結合演算を用いて、前記集合族ｆ（Ｚ）を表現したときの、前記結合演算を表す要素ノードとを含むＺＳＤＤ（Zero-suppressed Sentential Decision Diagram）を演算し、
、
前記ＺＳＤＤは、空集合との結合演算で表わされる要素ノードが省略されて表される演算実行方法。
【請求項７】
コンピュータを、請求項１から請求項５の何れか１項記載の演算実行装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、集合族をグラフとして計算機上に表現し、さらに表現した集合族間の演算を計算機上で実行するための演算実行装置、方法、及びプログラムに関するものである。
【背景技術】
【０００２】
計算機上で集合族を表現するための従来技術として、Zero-suppressed Binary Decision Diagram（以後、ＺＤＤとする）がある（非特許文献１）。ＺＤＤは、集合族を有向非巡回グラフ（Directed Acyclic Graph:以後ＤＡＧとする）として表現し、グラフのノード数にほぼ比例する計算時間で、集合族間の演算処理を実行することが可能である。
【０００３】
また、ＺＤＤのほかにも、同様に集合族をＤＡＧとして表現できる技術として、Binary Decision Diagram（以後、ＢＤＤとする）、及びSentential Decision Diagram（以後、ＳＤＤとする）がある（非特許文献２、非特許文献３）。
【０００４】
ここで、ＺＤＤとＢＤＤとを比べると、ＺＤＤのほうが集合族をよりノード数の少ないグラフとして表現できる傾向がある。また、ＳＤＤとＢＤＤとを比べると、ＳＤＤはＢＤＤを一般化した技術であり、ＳＤＤの方がよりノード数の少ないグラフとして集合族を表現できる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Minato, S. 1993. Zero-suppressed BDDs fro set manipulation in combinatorial problems, In proceedings of the 30th ACM/IEEE Design Automation Conference,pp. 272-277.
【非特許文献２】Bryant, R. E. 1986. Graph-based algorithms for boolean function manipulation. IEEE trans. on computers, C-35 (8): pp 677-691.
【非特許文献３】Darwiche, A. 2011. SDD: A new canonical representation of propositional knowledge bases, In proceedings of the 22nd international joint conference on Artificial Intelligence.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、上述したＺＤＤは、グラフのノード数にほぼ比例する計算時間で、集合族間の演算処理を実行することから、ノード数が多い場合には、演算処理に時間がかかるという問題がある。
【０００７】
本発明では、上記問題点を解決するために成されたものであり、集合族間の各種演算を高速に行うことができる演算実行装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記目的を達成するために、第１の発明に係る演算実行装置は、入力された演算命令と、ノードとエッジとからなる完全二分木であって、集合Ｚに含まれる各要素に対応するノードを葉ノードとして表現したｖｔｒｅｅと、に基づいて、前記演算命令の結果である、前記ｖｔｒｅｅから求まる前記集合Ｚの部分集合の各々からなる集合である集合族ｆ（Ｚ）を表す有向非巡回グラフであって、前記ｖｔｒｅｅのノードに対応する決定ノードと、前記集合Ｚを分割した部分集合Ｘ、Ｙに分けて、前記部分集合Ｘの部分集合からなる集合族と部分集合Ｙの部分集合からなる集合族との結合演算を用いて、前記集合族ｆ（Ｚ）を表現したときの、前記結合演算を表す要素ノードとを含むＺＳＤＤ（Zero-suppressed Sentential Decision Diagram）を演算する演算処理部を含んで構成され、前記ＺＳＤＤは、空集合との結合演算で表わされる要素ノードが省略されて表される。
【０００９】
第２の発明に係る演算実行方法は、演算処理部を含む、演算実行装置における演算実行方法であって、前記演算処理部は、入力された演算命令と、ノードとエッジとからなる完全二分木であって、集合Ｚに含まれる各要素に対応するノードを葉ノードとして表現したｖｔｒｅｅと、に基づいて、前記演算命令の結果である、前記ｖｔｒｅｅから求まる前記集合Ｚの部分集合の各々からなる集合である集合族ｆ（Ｚ）を表す有向非巡回グラフであって、前記ｖｔｒｅｅのノードに対応する決定ノードと、前記集合Ｚを分割した部分集合Ｘ、Ｙに分けて、前記部分集合Ｘの部分集合からなる集合族と部分集合Ｙの部分集合からなる集合族との結合演算を用いて、前記集合族ｆ（Ｚ）を表現したときの、前記結合演算を表す要素ノードとを含むＺＳＤＤ（Zero-suppressed Sentential Decision Diagram）を演算し、前記ＺＳＤＤは、空集合との結合演算で表わされる要素ノードが省略されて表される。
【００１０】
第１及び第２の発明によれば、演算処理部により、入力された演算命令と、ノードとエッジとからなる完全二分木であって、集合Ｚに含まれる各要素に対応するノードを葉ノードとして表現したｖｔｒｅｅと、に基づいて、演算命令の結果である、ｖｔｒｅｅから求まる集合Ｚの部分集合の各々からなる集合である集合族ｆ（Ｚ）を表す有向非巡回グラフであって、ｖｔｒｅｅのノードに対応する決定ノードと、集合Ｚを分割した部分集合Ｘ、Ｙに分けて、部分集合Ｘの部分集合からなる集合族と部分集合Ｙの部分集合からなる集合族との結合演算を用いて、集合族ｆ（Ｚ）を表現したときの、結合演算を表す要素ノードとを含む、空集合との結合演算で表わされる要素ノードが省略されて表されるＺＳＤＤを演算する。
【００１１】
このように、入力された演算命令と、ｖｔｒｅｅとに基づいて、演算命令の結果である、集合族ｆ（Ｚ）を表す有向非巡回グラフであって、ｖｔｒｅｅのノードに対応する決定ノードと、集合Ｚを分割した部分集合Ｘ、Ｙに分けて、部分集合Ｘの部分集合からなる集合族と部分集合Ｙの部分集合からなる集合族との結合演算を用いて、集合族ｆ（Ｚ）を表現したときの、結合演算を表す要素ノードとを含む、空集合との結合演算で表わされる要素ノードが省略されて表されるＺＳＤＤを演算することにより、集合族間の各種演算を高速に行うことができる。
【００１２】
また、第１の発明において、前記演算処理部は、前記演算命令と、前記ｖｔｒｅｅと、前記演算命令の引数となる前記ＺＳＤＤ、及び変数の少なくとも一方とに基づいて、前記演算命令の結果であるＺＳＤＤを演算してもよい。
【００１３】
また、第１の発明において、前記演算処理部は、前記入力された演算命令が、定数でない前記ＺＳＤＤが引数αとなり、前記ｖｔｒｅｅのノードを引数ｖとする演算命令Ｅｘｐａｎｄある場合に、前記引数αであるＺＳＤＤに対応する前記ｖｔｒｅｅのノードをノードｕとし、前記ノードｕと、前記引数ｖであるノードとの関係に応じて、前記引数αである前記ＺＳＤＤ、
【００１４】
【数１】
0006451997.tif 000002
【００１５】
であるＺＳＤＤ、及び
【００１６】
【数２】
0006451997.tif 000003
【００１７】
であるＺＳＤＤの何れか一つを返してもよい。
【００１８】
また、第１の発明において、前記演算処理部は、前記入力された演算命令が、前記要素ノードの集合が引数γとなる演算命令ＵｎｉｑｕｅＤである場合に、前記引数γとなる前記要素ノードの集合に要素ノードが含まれなければ、定数ＺＳＤＤである⊥を返し、前記引数γとなる前記要素ノードの集合が、
【００１９】
【数３】
0006451997.tif 000004
【００２０】
、又は
【００２１】
【数４】
0006451997.tif 000005
【００２２】
であれば、ＺＳＤＤであるαを返し、前記引数γとなる前記要素ノードの集合が、
【００２３】
【数５】
0006451997.tif 000006
【００２４】
及び
【００２５】
【数６】
0006451997.tif 000007
【００２６】
の何れでもなければ、前記引数γとなる前記要素ノードの集合に対応する前記決定ノードを作成して、決定ノードテーブルに格納してもよい。
【００２７】
また、第１の発明において、前記演算処理部は、前記入力された演算命令が、ＺＳＤＤが引数αとなる演算命令Ｃｏｍｐｒｅｓｓである場合に、前記引数αとなるＺＳＤＤに含まれる要素のノードの集合｛（ｐ1，ｓ1），・・・，（ｐｎ，ｓｎ）｝のうち、ｓｉ＝ｓｊとなる要素ノードのペア（ｐi，ｓi），（ｐj，ｓj）を、ｐiが表す集合族とｐjが表す集合族との和であるＵｎｉｏｎ（ｐi，ｐj）を用いた（Ｕｎｉｏｎ（ｐi，ｐj），ｓｉ）に置き換えた、前記引数αとなるＺＳＤＤを返してもよい。
【００２８】
また、本発明のプログラムは、コンピュータを、上記の演算実行装置を構成する各部として機能させるためのプログラムである。
【発明の効果】
【００２９】
以上説明したように、本発明の演算実行装置、方法、及びプログラムによれば、入力された演算命令と、ｖｔｒｅｅとに基づいて、演算命令の結果である、集合族ｆ（Ｚ）を表す有向非巡回グラフであって、ｖｔｒｅｅのノードに対応する決定ノードと、集合Ｚを分割した部分集合Ｘ、Ｙに分けて、部分集合Ｘの部分集合からなる集合族と部分集合Ｙの部分集合からなる集合族との結合演算を用いて、集合族ｆ（Ｚ）を表現したときの、結合演算を表す要素ノードとを含む、空集合との結合演算で表わされる要素ノードが省略されて表されるＺＳＤＤを演算することにより、集合族間の各種演算を高速に行うことができる。
【図面の簡単な説明】
【００３０】
【図１】ｖｔｒｅｅの一例を示す図である。
【図２】ＺＳＤＤを再帰的に定義する例を示す図である。
【図３】ＺＳＤＤの一例を示す図である。
【図４】本実施形態に係る演算実行装置の機能的構成を示すブロック図である。
【図５】本実施形態に係る演算実行装置において用いる演算の例を示す図である。
【図６】決定ノードテーブルの一例を示す図である。
【図７】メモの一例を示す図である。
【図８】Intersection(α，β)のアルゴリズムの一例を示す図である。
【図９】Expand(α，ｖ)のアルゴリズムの一例を示す図である。
【図１０】Compress(α)のアルゴリズムの一例を示す図である。
【図１１】UniqueD（γ）のアルゴリズムの一例を示す図である。
【図１２】Union (α，β)のアルゴリズムの一例を示す図である。
【図１３】Difference (α，β)のアルゴリズムの一例を示す図である。
【図１４】Change(α，ｘ)のアルゴリズムの一例を示す図である。
【図１５】本実施形態に係る演算実行装置における演算実行処理ルーチンの一例を示すフローチャートである。
【発明を実施するための形態】
【００３１】
以下、図面を参照して本発明の実施形態を詳細に説明する。
【００３２】
＜本実施形態の概要＞
まず、本実施形態の概要について説明する。
【００３３】
上述のＺＤＤ、ＢＤＤ、及びＳＤＤは、ともに集合族をノード数の少ないＤＡＧとして表現するための技術であるが、ＺＤＤ、ＢＤＤ、及びＳＤＤの手法は、より少ないノード数からなるＤＡＧとして表現可能であるほど、ＺＤＤ、ＢＤＤ、及びＳＤＤを用いた各種問い合わせに対して高速な処理が可能であるという特徴がある。したがって、演算が実行であるという性質を満たしつつ、よりノード数が少ないグラフとして表現できる技術の価値が高いといえる。
【００３４】
本実施形態においては、新たなＤＡＧに基づく集合族の表現方法、Zero-suppressed Sentential Decision Diagram（以後、ＺＳＤＤとする）を用いる。ＺＳＤＤはＳＤＤの変種であり、ＳＤＤで用いられていた、ＢＤＤと類似のグラフの簡約化のための規則を、ＺＤＤと類似の簡約化規則で置き換えることで得られる。
【００３５】
ＺＳＤＤはＺＤＤと同様に集合族間の演算を実行可能である。また、ＺＳＤＤはＺＤＤの一般化であり、かつＺＤＤよりも少ない節点数で集合族を表現することが可能である。さらに、ＺＳＤＤはＳＤＤよりも少ないノード数で集合族を表現することが可能である。そのため、ＺＳＤＤのポイントは、従来技術の方法より少ないノードからなるＤＡＧを得るために利用する簡約化規則にある。
【００３６】
ここで、ＺＳＤＤは、ある部分ＺＳＤＤが空集合のみを要素として持つ組合せ集合
【００３７】
【数７】
0006451997.tif 000008
【００３８】
を表現しているときに、ノードを削除するような簡約化規則を用いることによって、ＺＳＤＤはＳＤＤよりも少ないノード数からなるＤＡＧとして集合族を表現することができる。
【００３９】
次に、後述する演算実行装置の説明において用いる文言の定義について説明する。
【００４０】
まず、本実施形態における集合族とは、ある集合Ｚ＝｛Ａ，Ｂ，Ｃ，．．．，｝について、その部分集合Ｓ⊆Ｚからなる集合のことである。例えば、Ｚ＝｛Ａ，Ｂ，Ｃ，Ｄ｝に対して、
【００４１】
【数８】
0006451997.tif 000009
【００４２】
は集合族である。ここで、記号
【００４３】
【数９】
0006451997.tif 000010
【００４４】
は空集合を表すとし、記号２ＺはＺの可能なすべての部分集合からなる集合族を表すとする。また、｜Ｚ｜は、集合の要素数を表す。
【００４５】
次に、集合族に対する演算を定義する。ここで、ｆ、及びｇを集合族とすると、ｆ∩ｇ＝｛Ｓ｜Ｓ∈ｆかつＳ∈ｇ｝、ｆ∪ｇ＝｛Ｓ｜Ｓ∈ｆまたはＳ∈ｇ｝、
【００４６】
【数１０】
0006451997.tif 000011
【００４７】
、
【００４８】
【数１１】
0006451997.tif 000012
【００４９】
として、演算
【００５０】
【数１２】
0006451997.tif 000013
【００５１】
を定義する。
【００５２】
更に、集合族は論理関数ｆ（ｘ１，ｘ２，．．．，ｘ｜Ｚ｜）により表現することができる。ｘ１，ｘ２，．．．，ｘ｜Ｚ｜は０もしくは１の値をとる二値変数であり、ｆは｜Ｚ｜個の二値変数を入力として受け取り、０若しくは１の値と出力する関数である。
【００５３】
ある集合族は、集合族に含まれる各部分集合に対応する入力が与えられたときにのみ１を返す論理関数として表現できる。例えば、上記の集合族であれば、４引数の関数ｆ（ｘＡ，ｘＢ，ｘＣ，ｘＤ）として表現でき、例えば、｛Ａ，Ｂ｝に対応する入力として（ｘＡ，ｘＢ，ｘＣ，ｘＤ）＝（１，１，０，０）が与えられときに１を返す。そのほかにも、｛Ｂ｝｛Ｂ，Ｃ｝，｛Ｃ，Ｄ｝，
【００５４】
【数１３】
0006451997.tif 000014
【００５５】
に対応する入力、すなわち、（０，１，０，０）、（０，１，１，０）、（０，０，１，１）、及び（０，０，０，０）が与えられたときにのみ１を返し、それ以外の入力に対しては０を返す関数である。
【００５６】
ここで、集合族ｆ（Ｚ）の（Ｘ，Ｙ）分割とは、集合Ｚを、別々の集合Ｘと集合Ｙとに分割したうえで、ｆ（Ｚ）を
【００５７】
【数１４】
0006451997.tif 000015
【００５８】
として表現する方法である。ここで、ｐｉ（Ｘ）は、集合Ｘの部分集合からなる集合族、ｓｉ（Ｙ）は、集合Ｙの部分集合からなる集合族とする。また、ｐｉは、すべての
【００５９】
【数１５】
0006451997.tif 000016
【００６０】
について、
【００６１】
【数１６】
0006451997.tif 000017
【００６２】
であり、かつ
【００６３】
【数１７】
0006451997.tif 000018
【００６４】
を満たすとする。さらに、
【００６５】
【数１８】
0006451997.tif 000019
【００６６】
であるとする。また、ｓｉ（Ｙ）は、
【００６７】
【数１９】
0006451997.tif 000020
【００６８】
について、ｓｉ≠ｓｊを満たすとする。そのため、上記のＡ、Ｂ，Ｃ、及びＤについて、（ＡＢ，ＣＤ）分割を行うと、
【００６９】
【数２０】
0006451997.tif 000021
【００７０】
となる。なお、以下、（Ｘ，Ｙ）分割を、｛（ｐ１，ｓ１），．．．，（ｐｎ，ｓｎ）｝とする。
【００７１】
次に、ｖｔｒｅｅを定義する。ｖｔｒｅｅとは、集合に含まれる各アイテムに対応するノードを葉ノードとし、各ノードをエッジで結んでいるような完全二分木のことである。図１に４つのアイテムＡ、Ｂ、Ｃ、及びＤに対するｖｔｒｅｅの例を示す。
【００７２】
ｖｔｒｅｅの葉でないノードである各中間ノードｖは、集合のある分割を表現している。すなわち、ノードｖを根とする木の葉ノードに対応するアイテムの集合を、ノードｖの左側の子ノードを根とする部分木（以後、ｖｌとする）の葉ノードに対応するアイテム集合と、ノードｖの右側の子ノードを根とする部分木（以後、ｖｒとする）の葉ノードに対応するアイテム集合とに分割する。図１の根ノードは、（ＡＢ，ＣＤ）分割に対応している。
【００７３】
次に、ＺＳＤＤを定義する。ＺＳＤＤは、あるｖｔｒｅｅが与えられたときに、当該ｖｔｒｅｅに基づいて再帰的に組合せ集合を（Ｘ，Ｙ）分割によって分割することにより、ＤＡＧとして組合せ集合を表現する。分割された組合せ集合と、ＺＳＤＤの構造との対応を図２に示す。ここで、図２のαをＺＳＤＤ、αが表現する集合族を＜α＞とすると、図２の様にＺＳＤＤは再帰的に定義される。
【００７４】
ここで、⊥、及びεを定数ＺＳＤＤとし、ｘ、及び±ｘをリテラルＺＳＤＤとする。なお、εは、
【００７５】
【数２１】
0006451997.tif 000022
【００７６】
であり、⊥は、
【００７７】
【数２２】
0006451997.tif 000023
【００７８】
である。また、±ｘは、
【００７９】
【数２３】
0006451997.tif 000024
【００８０】
のように、｛ｘ｝と空集合とを要素とする集合族である。
【００８１】
また、定数ＺＳＤＤ、及びリテラルＺＳＤＤをあわせて終端ＺＳＤＤとする。一方、ある（Ｘ，Ｙ）分割を表現するＺＳＤＤを分割ＺＳＤＤとする。
【００８２】
図３に集合族
【００８３】
【数２４】
0006451997.tif 000025
【００８４】
を表現するＺＳＤＤを表す。図３の丸ノードは、当該ノードを根とするＤＡＧが表現する分割ＺＳＤＤを表現しており、丸ノードを決定ノードとする。決定ノード中の数字は、対応するｖｔｒｅｅノードを表している。
【００８５】
また、決定ノードを親に持つ四角ノードは、あるペア（ｐｉ，ｓｉ）を表現しており、これを要素ノードとする。要素ノードの左側がｐｉであり、右側がｓｉに対応しており、それぞれの終端ＺＳＤＤか、分割ＺＳＤＤに対応している。
【００８６】
また、決定ノードとその子ノードである要素ノード群とで、ある（Ｘ，Ｙ）分割を表している。なお、（Ｘ，Ｙ）分割
【００８７】
【数２５】
0006451997.tif 000026
【００８８】
を表わす分割ＺＳＤＤでは、（ｐｎ，⊥）に対応する要素ノードはＺＳＤＤ中では明示的に持たないものとする。また、ＺＳＤＤは、｛（ε，α）｝、｛（α，ε）｝、及び｛｝の形の分割ＺＳＤＤをもたない。ＺＳＤＤ中にこれらの形の分割ＺＳＤＤが存在していた場合、前者はαに、後者は⊥にそれぞれ置き換えるものとする。当該、決定ノードを削除する規則により、ＺＳＤＤは集合族をコンパクトに表現することができる。
【００８９】
＜本発明の実施形態に係る演算実行装置の構成＞
次に、本発明の実施形態に係る演算実行装置の構成について説明する。図４に示すように、本実施形態に係る演算実行装置１００は、ＣＰＵと、ＲＡＭと、後述する演算実行処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この演算実行装置１００は、機能的には図４に示すように入力部１０と、演算部２０と、出力部９０とを含んで構成されている。
【００９０】
入力部１０は、対象となるｖｔｒｅｅを受け付ける。なお、入力部１０はｖｔｒｅｅを他の入力よりも先に受け付けるものとする。
【００９１】
また、入力部１０は、ＺＳＤＤ間の演算命令を受け付け、更に、当該演算命令において引数が必要な場合には当該引数を受け付ける。なお、本実施形態において対象となる演算を図５に示す。
【００９２】
演算部２０は、ＺＳＤＤ記憶部２２と、演算処理部２４とを含んで構成されている。
【００９３】
ＺＳＤＤ記憶部２２には、入力部１０において受け付けたｖｔｒｅｅと、例えば、図６に示すＺＳＤＤの決定ノードを記憶する決定ノードテーブルと、例えば、図７に示す演算効率化のためのメモとが記憶されている。
【００９４】
ここで、図６に示すＺＳＤＤの決定ノードを記憶する決定ノードテーブルは、各決定ノードについて、当該決定ノードのノードＩＤ、当該決定ノードＩＤに対応するｖｔｒｅｅのノードのノードＩＤ、及び当該決定ノードの子要素ノードの集合が記憶されている。なお、決定ノードテーブル内で、ｖｔｒｅｅノードＩＤ、及び子要素ノードの集合が一致する決定ノードは一意であるものとする。
【００９５】
また、図７に示す演算効率化のためのメモは、演算命令及び当該演算命令の引数からなるタプルをキーとし、当該演算命令の結果のＺＳＤＤのノードＩＤ（図７のメモ内においては「値」の欄において示す）を保持する。
【００９６】
なお、分割ＺＳＤＤは、当該分割ＺＳＤＤの根ノードに対応する決定ノードのアドレスによって表現される。また、終端ＺＳＤＤは、計算機中ではε、⊥、ｘ、±ｘに対応する定数として表現される。
【００９７】
演算処理部２４は、ＺＳＤＤに記憶部２２に記憶されているｖｔｒｅｅ、決定ノードテーブル、及びメモと、入力部１０において受け付けた演算命令、及び引数とに基づいて、演算を行い、演算結果をＺＳＤＤ記憶部２２に記憶すると共に、出力部９０から出力する。
【００９８】
以下、具体的に演算毎の処理の説明をする。
【００９９】
まず、演算命令がEmptyFamily()である場合には、対象となる終端ＺＳＤＤεを作成する。
【０１００】
また、演算命令がEmpty()である場合には、対象となる終端ＺＳＤＤ⊥を作成する。
【０１０１】
また、演算命令がLiteral(x)である場合には、入力部１０において受け付けた引数ｘであるＺＳＤＤに基づいて、終端ＺＳＤＤｘを作成する。
【０１０２】
また、演算命令がLiteralEmpty(x)である場合には、入力部１０において受け付けた引数ｘであるＺＳＤＤに基づいて、終端ＺＳＤＤ±ｘを作成する。
【０１０３】
また、演算命令がIntersection(α，β)である場合には、ＺＳＤＤ記憶部２２に記憶されているｖｔｒｅｅ、決定ノードテーブル、及びメモと、入力部１０において受け付けた引数であるＺＳＤＤα、及びＺＳＤＤβとに基づいて、図８に示すアルゴリズムを実行し、＜α＞∩＜β＞を表すＺＳＤＤを作成する。
【０１０４】
ここで、図８に示すアルゴリズムについて詳述する。
【０１０５】
図８に示すアルゴリズムにおいて、まず、１行目で、入力部１０において受け付けたＺＳＤＤα、及びＺＳＤＤβ共に定数又はリテラルであるか否かを判定し、両ＺＳＤＤが共に定数又はリテラルである場合には、当該Intersection(α，β)は、定数又はリテラルとなることから容易に計算することができ、アルゴリズムの２行目に示すように当該計算を行い、結果を出力する。
【０１０６】
一方、両ＺＳＤＤの何れか一方が定数又はリテラルでない場合には、ＺＳＤＤ記憶部２２に記憶されている決定ノードテーブルに当該Intersection(α，β)に対応する演算結果が格納されているか否かを判定し、格納されている場合には、当該アルゴリズムの３行目、及び４行目に示すように当該演算結果を出力する。また、格納されていない場合には、実際に演算を行う。
【０１０７】
実際の演算処理を図８のアルゴリズムの６行目から２１行目までに示す。まず、６行目において、新しい分割γを｛｝として初期化する。次に、７行目において、入力部１０において受け付けたＺＳＤＤαとＺＳＤＤβとの各々において、当該ＺＳＤＤに対応するｖｔｒｅｅのノードの共通の祖先のうち、最も深いノードｖを取得する。ここで、ＺＳＤＤα、及びＺＳＤＤβのどちらかがεもしくは⊥である場合には、εもしくは⊥が示す定数でないＺＳＤＤが対応するｖｔｒｅｅのノードをノードｖとする。
【０１０８】
次に、８行目及び９行目に示すように、Expand(α，ｖ)、及びExpand(β，ｖ)を各々計算する。このExpandは入力されたＺＳＤＤを、ノードｖに対応する（Ｘ，Ｙ）分割によって分割した分割ＺＳＤＤに変換したものを出力するものである。なお、Expandの処理の詳細については、後述する。
【０１０９】
次に、１０行目から１８行目に示すように、Expandによりよって得られた分割ＺＳＤＤに含まれる要素ノード（ｐｉ，ｓｉ），（ｑｊ，ｒｊ）の各ペアについて、再帰的にIntersectionを計算し、計算結果をγに追加する。
【０１１０】
次に、２０行目に示すように、γをCompress(γ)で置き換える。次に、２１行目に示すように、UniqueD(γ)を計算し、当該計算結果を、ＺＳＤＤ記憶部２２に記憶されているメモに登録し、計算結果を出力して処理を終了する。なお、Compress(γ)及びUniqueD(γ)の処理の詳細については、後述する。
【０１１１】
次に、Expandについて説明する。ここでは、Expand(α，ｖ)について説明するが、Expand(β，ｖ)についても同様の処理を行う。図９に示すように、Expand(α，ｖ)は、ノードｖとＺＳＤＤαとの関係から、演算のための一時的な分割ＺＳＤＤを生成する処理である。
【０１１２】
Expand(α，ｖ)は、図９の１行目に示すように、ＺＳＤＤαが⊥である場合には｛｝を返す。一方、４行目に示すように、ＺＳＤＤαがεである場合には、｛（ε，ε）｝を返す。また、７行目から１４行目に示すように、ＺＳＤＤαが⊥及びεのどちらでもない場合には、ＺＳＤＤαに対応するｖｔｒｅｅノードｕと、ノードｖとの関係に応じて、
【０１１３】
【数２６】
0006451997.tif 000027
【０１１４】
の何れかを出力する。
【０１１５】
次に、Compress(α)について説明する。ここでは、Compress(α)として説明するが、Compress(γ)も同様の処理となる。図１０に示すように、Compress(α)は、ＺＳＤＤαの要素ノードの集合｛（ｐ１，ｓ１），．．．，（ｐｎ，ｓｎ）｝を、全てのｉ≠ｊについてｓｉ≠ｓｊとなるように変換する処理である。Compress(α)の処理は、図１０に示すように、ｓｉ＝ｓｊとなるような要素ノードのペア（ｐｉ，ｓｉ），（ｐｊ，ｓｊ）を、（Union（ｐｉ，ｐｊ），ｓｉ）で置き換えることを繰り返すことで、ｓｉ＝ｓｊとなるような要素ノードのペアを全て消去し、出力する。
【０１１６】
次に、UniqueD(γ)について説明する。UniqueD(γ)は、図１１に示すように、要素ノードの集合γから、対応するＺＳＤＤを作成し、出力する処理である。図１１の２行目に示すように、要素ノードの集合γ中に要素ノードが含まれない場合、終端ＺＳＤＤ⊥を出力する。一方、４行目に示すように、要素ノードの集合γが｛（ε，α）｝または｛（α，ε）｝である場合には、ＺＳＤＤαを出力して処理を終了する。また、要素ノードの集合γ中に要素ノードが含まれ、かつ要素ノードの集合γが｛（ε，α）｝及び｛（α，ε）｝の何れでもない場合には、要素ノードの集合γと同等の決定ノードが、決定ノードテーブルに含まれていないかを判定し、含まれていないと判定された場合には、要素ノードの集合γに対応する決定ノードを作成してＺＳＤＤ記憶部２２に記憶されている決定ノードテーブルに格納する。そして、決定ノードテーブルに格納した要素ノードの集合γに対応するＺＳＤＤを出力して処理を終了する。
【０１１７】
また、演算命令がUnion(α，β)である場合には、ＺＳＤＤ記憶部２２に記憶されているｖｔｒｅｅ、決定ノードテーブル、及びメモと、入力部１０において受け付けた引数であるＺＳＤＤα、及びＺＳＤＤβとに基づいて、図１２に示すアルゴリズムを実行し、＜α＞∪＜β＞を表すＺＳＤＤを作成する。なお、Union(α，β)は、上述したIntersection(α，β)と処理はほぼ同等となり、γの候補を作成するときの再帰的な処理の部分の処理が異なる。具体的には、図１２のアルゴリズムの１９行目から３９行目である。
【０１１８】
また、演算命令がDifference(α，β)である場合には、ＺＳＤＤ記憶部２２に記憶されているｖｔｒｅｅ、決定ノードテーブル、及びメモと、入力部１０において受け付けた引数であるＺＳＤＤα、及びＺＳＤＤβとに基づいて、図１３に示すアルゴリズムを実行し、＜α＞−＜β＞を表すＺＳＤＤを作成する。なお、Difference (α，β)は、上述したIntersection(α，β)と処理はほぼ同等となり、γの候補を作成するときの再帰的な処理の部分の処理が異なる。具体的には、図１３のアルゴリズムの１９行目から３０行目である。
【０１１９】
また、演算命令がChange(α，ｘ)である場合には、ＺＳＤＤ記憶部２２に記憶されているｖｔｒｅｅ、決定ノードテーブル、及びメモと、入力部１０において受け付けた引数であるＺＳＤＤα、及びアイテムｘとに基づいて、図１４に示すアルゴリズムを実行し、集合族＜α＞に出現するアイテムｘを反転させたＺＳＤＤを出力する。具体的には、Change(α，ｘ)は、ＺＳＤＤαが表す集合族に含まれる各集合Ｓ∈＜α＞について、ｘ∈ＳならばＳをｓ−｛ｘ｝で置き換え、ｘがＳに含まれないならば、ＳをＳ∪｛ｘ｝で置き換えて得られる集合族を表現するＺＳＤＤを返す処理である。
【０１２０】
例えば、
【０１２１】
【数２７】
0006451997.tif 000028
【０１２２】
に対して、Change(α，Ｃ)を適用すると、｛｛Ａ，Ｂ｝，｛Ａ，Ｃ｝，｛Ｃ｝｝を表すＺＳＤＤが出力される。
【０１２３】
図１４にChange(α，ｘ)の処理のアルゴリズムを示す。
【０１２４】
まず、図１４の２行目に示すように、ＺＳＤＤαが定数またはリテラルであるか判定し、ＺＳＤＤαが定数またはリテラルである場合には、Changeを適用した結果も定数またはリテラルになるため、計算して出力する。一方、４行目に示すように、Changeの計算結果がＺＳＤＤ記憶部２２に記憶されているメモに格納されている場合には、当該計算結果を出力して処理を終了する。また、６行目に示すように、Changeの計算結果がＺＳＤＤ記憶部２２に記憶されているメモに格納されていない場合には、要素ノードの集合γを初期化し、７行目に示すように、ノードｖを決定する。
【０１２５】
そして、８行目から１６行目に示すように、Expand(α，ｖ)の各要素について、再帰的にChangeを適用し、適用した結果をγに格納する。最後に、１７行目に示すように、UniqueD(γ)によって対応するＺＳＤＤを計算し、結果をメモに格納して、結果を出力する。
【０１２６】
＜本発明の実施形態に係る演算実行装置の作用＞
次に、本発明の実施形態に係る演算実行装置１００の作用について説明する。演算実行装置１００は、まず、入力部１０において受け付けた、対象となるｖｔｒｅｅを受け付けると当該ｖｔｒｅｅをＺＳＤＤ記憶部２２に記憶する。また、演算実行装置１００は、入力部１０において、EmptyFamily()、又はEmpty()の演算命令を受け付けると、対象となる終端ＺＳＤＤε又は終端ＺＳＤＤ⊥を作成し、出力部９０から出力する。
【０１２７】
また、演算実行装置１００は、入力部１０において、Literal(x)、又はLiteralEmpty(x)の演算命令と引数ｘとを受け付けると、対象となる終端ＺＳＤＤｘ又は終端ＺＳＤＤ±ｘを作成し、出力部９０から出力する。
【０１２８】
また、演算実行装置１００は、入力部１０において、Intersection(α，β)、Union(α，β)、Difference(α，β)、又はChange(α，ｘ)の演算命令と、当該演算命令における引数とを受け付けると、演算実行装置１００によって、図１５に示す演算実行処理ルーチンが実行される。
【０１２９】
まず、図１５に示す演算実行処理ルーチンのステップＳ１００では、ＺＳＤＤ記憶部２２に記憶されているｖｔｒｅｅ、決定ノードテーブル、及びメモを読み込む。
【０１３０】
次に、ステップＳ１０２では、入力部１０において受け付けた演算命令に応じて、ステップＳ１００において取得したｖｔｒｅｅ、決定ノードテーブル、及びメモと、入力部１０において受け付けた演算命令及び引数とに基づいて、上述に詳細を示した当該演算命令を実行し、演算結果であるＺＳＤＤを取得する。
【０１３１】
次に、ステップＳ１０４では、ステップＳ１０２において取得したＺＳＤＤをＺＳＤＤ記憶部２２に記憶すると共に、出力部９０から出力し、演算実行処理ルーチンを終了する。
【０１３２】
以上説明したように、本発明の実施形態に係る演算実行装置によれば、入力された演算命令と、ｖｔｒｅｅとに基づいて、演算命令の結果である、集合族ｆ（Ｚ）を表す有向非巡回グラフであって、ｖｔｒｅｅのノードに対応する決定ノードと、集合Ｚを分割した部分集合Ｘ、Ｙに分けて、部分集合Ｘの部分集合からなる集合族と部分集合Ｙの部分集合からなる集合族との結合演算を用いて、集合族ｆ（Ｚ）を表現したときの、結合演算を表す要素ノードとを含む、空集合との結合演算で表わされる要素ノードが省略されて表されるＺＳＤＤを演算することにより、集合族間の各種演算を高速に行うことができる。
【０１３３】
また、集合族をノード数が少ないＤＡＧとして表現し、また、集合族間の各種演算を実行することができる。
【０１３４】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０１３５】
例えば、本実施形態においては、入力した演算命令に必要な引数を入力する場合について説明したが、これに限定されるものではなく、入力されたｖｔｒｅｅに基づいて、図５に示す演算命令（EmptyFamily()、Empty()、Literal(x)、及びLiteralEmpty(x)）を演算することにより、対象となる演算命令に必要となるＺＳＤＤの引数を作成し、ＺＳＤＤ記憶部に記憶しておいてもよい。その場合、対象となる演算命令に基づいて、ＺＳＤＤ記憶部に記憶されている対象となるＺＳＤＤを読み込む。なお、Literal(x)、及びLiteralEmpty(x)の演算命令を実行する場合には、必要な引数ｘは入力する。
【０１３６】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能であるし、ネットワークを介して提供することも可能である。
【符号の説明】
【０１３７】
１０   入力部
２０   演算部
２２   ＺＳＤＤ記憶部
２４   演算処理部
９０   出力部
１００ 演算実行装置
【図１】
0006451997.tif 000035
【図２】
0006451997.tif 000036
【図３】
0006451997.tif 000037
【図４】
0006451997.tif 000038
【図５】
0006451997.tif 000039
【図６】
0006451997.tif 000040
【図７】
0006451997.tif 000041
【図８】
0006451997.tif 000042
【図９】
0006451997.tif 000043
【図１０】
0006451997.tif 000044
【図１１】
0006451997.tif 000045
【図１２】
0006451997.tif 000046
【図１３】
0006451997.tif 000047
【図１４】
0006451997.tif 000048
【図１５】
0006451997.tif 000049