制約条件を利用した組合せの削減

BaltはC₁の制約条件を利用して探索範囲を限定させ、解析を高速化させた。これを拡 張し、C2の制約条件も利用した解析手法を提案する[Iiz03a]。3.3節に示したように、図 形言語の定義では、C2の制約条件を多く利用している。よって、この制約条件を利用す ることで効率的に計算量を削減することができる。

ルール適用において、まず、各RHSの記号に該当するトークン列がトークンデータベー スから選ばれる。Baltの手法では、この時点でそれぞれの記号に対応するトークンをC1の 制約条件を利用し、制約条件を満たさないトークンを除外する。この前処理により、トー クンが減少するため、探索する組合せも減少することになる。これによって求められた トークンはMという変数に入れられるとする。Mは配列になっており、M[k]はk番目の RHSの記号に対応するトークンの集合が設定されているものとする。

提案する手法では、ここでさらにC2の制約条件を利用する。このアルゴリズムは以下 のようになる。

routine CheckConstraintDouble(C, M) [X,Y] := ArgumentPosition(C) Xold := M[X]

Yold := M[Y]

M[X] := {}

M[Y] := {}

for each I in Xold do for each J in Yold do

if StatisfiesConstraint([I,J], C) then AddToSet(M[X], I)

AddToSet(M[Y], J) RemoveFromSet(Yold, J) endif

end end return M end

CheckConstraintDouble()は、第2引数で与えられたトークン集合の配列から、第1引数

4.3 制約条件を利用した組合せの削減 31

に与えられた制約条件を満たすトークンを選択し、新たなトークン集合の配列を返す関数 である。まず、ArgumentPosition()を利用して制約条件で利用している記号の位置を取得 し、XとYに設定する。この後、M[X]とM[Y]で構成される組合せに対して制約条件の チェックを行う。XoldとYoldに元となるトークン集合として、現在のM[X]とM[Y]が設 定される。そして、M[X]とM[Y]は空集合に初期化される。この後、Xoldに関するルー プがあり、トークンが変数Iに設定される。さらにその内部で、Yoldに関するループがあ り、トークンが変数Jに設定される。そこで制約条件がチェックされる。制約条件が成立 した場合は、このトークンは利用可能であるので、AddToSet()を用いてトークンIとJが、

M[X]とM[Y]に追加される。このとき、次のYoldに関するループでは、トークンJを再 度チェックする必要がないので、RemoveFromSet()を用いてYoldからトークンJを取り除 いている。以上のループを繰り返すことで、制約条件を満たす可能性のあるトークンの集 合を求めることができる。

上記関数を利用したルール適用は、次のようになる。

routine EvaluateRule(P) T := Variables(P) C := Constraints(P) M := GetTokenList(T, D)

for each L in SinglesOf(C) do M := CheckConstraintSingle(L, M) end

for each L in DoublesOf(C) do M := CheckConstraintDouble(L, M) end

changed := false

for each A in Combination(M) do if SatisfiesConstraints(A, C) then

N := NewNonTerminal(A, P) D := (D\A)∪{N}

changed := true endif

end

return changed end

まず、GetTokenList()を用いて、各記号に当てはまるトークン集合の配列を求めMに設

定する。この後、SinglesOf()を用いてC₁の制約条件を取り出し、これに関して

Check-ConstraintSingle()を用いてC1の制約条件を満たすトークンにMを限定させる。さらに、

DoublesOf()を用いてC2の制約条件を取り出し、これに関してCheckConstraintDouble()を 用いてC₂の制約条件を満たすトークンにMを限定させる。この2段階の制約条件の利用 により削減されたトークン集合を利用し、Combination()で組合せを求め、最終的な制約 条件のチェックを行っている。

このアルゴリズムでは、C₂の制約条件を利用したトークンの限定の前処理にO(n²)の 計算量が必要となる。また、トークンの組合せは減少してはいるものの、組合せ数のオー ダに変化はないため、全体としてO(n^k)の計算量が必要である。前処理の部分があるた め、その計算量は増えるが、これによる探索範囲の削減効果によって、全体の計算量は減 少するものと期待される。なお、ルールがR₁のルールの場合には、C₂の制約条件は存在 しないため前処理はO(n)であり、全体としての計算量もO(n)である。

このアルゴリズムは、簡単に3つ以上の記号に関する制約条件を利用する場合に拡張で きる。しかし、今回の3.3節の調査により、このような制約条件は利用されていなかった ため、C2の制約条件までを利用したアルゴリズムのみを提示した。

ここで具体的な例を用いて、組合せの削減を示す。例として、4.1.2節の例における初期 状態のトークンのうち、以下の5つのトークンまでが入力された状態を考える。

D ={1, 2, 3, 4, 5}

このとき、ルール1における各記号に対応するトークン集合の配列は次のようになる M[1]={1, 2, 3}

M[2]={4, 5}

このとき、組合せを求めると次の6個となる。

[1,4], [1,5], [2,4], [2,5], [3,4], [3,5] (4.4) ここで、C1の制約条件“isValue(t.text)”を利用することで、トークン4は制約条件を 満たさないことが分かるので次のようになる。

M[1]={1, 2, 3}

M[2]={5}

よって、組合せは以下の3個に減少される。

[1,5], [2,5], [3,5] (4.5)

提案手法では、ここでさらにC₂の制約条件“c.mid == t.mid”を利用する。M[1]と M[2]で構成されるトークンの組合せのうち、この制約条件を満たすのは、[2,5]の組合せ のみである。よって、トークン1とトークン3に接続できる記号Textに対応したトークン が存在しないことが分かるため、これらがM[1]から除外される。これによりトークン集 合の配列は次のようになる。

M[1]={2}

M[2]={5}

よって、組合せは以下の1個に減少させることができる。

[2,5] (4.6)