第 4 章 空間解析器の高速化
4.12 高速化のまとめ
行うことで、弱い制約条件を極力利用しないグラフの訪問を実現できることを示した。ま た、属性値テーブルを利用することで、訪問先の対応するトークンを即座に決定すること ができるようになることを示した。これにより、計算の木などの例ではO(1)の解析を実 現できた。つまり、インタラクティブなシステムにおけるインクリメンタルな解析が図形 数によらず一定時間で行える。また、全体の解析に関しても線形の処理時間で解析が終了 する。
これらの制約条件グラフを利用した提案手法では、解析を高速化できないようなルール も存在する。これは、あるノードに到達するためのすべてのエッジが弱い制約条件であっ た場合や、ある記号がどのような制約条件にも含まれていない場合である。具体的には、
次のような例が考えられる。
q:Quadruplet ::= a:Node, b:Node, c:Node, d:Node where(
a.val <= b.val b.val <= c.val c.val <= d.val ) {}
このように、すべてが弱い制約条件の場合は、最悪の計算量が必要となる。この場合、
1つのトークンの追加にO(n3)の処理が必要になる。
ただし、このような定義がなされることは一般に考えられない。なぜなら、記号Node が5つ以上あった場合に、どの4つ組を選ぶか何も条件を指定していない。つまり解釈が 曖昧な定義である。そのような定義をあえてする必要があるか疑問である。また、4.1.1節 で述べたように、このような定義はChokらの手法をベースにしたインクリメンタルな解 析では正しく扱うことができない。したがって、何らかの条件、たとえば、隣接する記号 間の4つ組であるといった制約条件が加えられることになる。こうすることにより、強い 制約条件が与えられ、高速に解析が行えるようになる。
弱い制約条件による曖昧性をnot-existの記号を利用して取り除いているようなケースに おいては、実用的で曖昧性のない定義であっても高速化が実現できない場合がある。たと えば、次のような例である。
m:PairNode ::= f:Node, s:Node where ( f.mid_y == s.mid_y
f.mid_x < s.mid_x
not exist n:Node where ( f.mid_y == n.mid_y f.mid_x < n.mid_x n.mid_x < s.mid_x )
) {}
この定義は、水平方向に隣り合う記号Nodeを1つの非終端記号としている。このとき、
横にある記号Nodeがどれくらい離れているのか分からない場合は、単に左右に並んでい
4.12 高速化のまとめ 63
るとしか記述できない。この場合では、“f.mid x < s.mid x”という条件で指定されて いる。しかしこれだけでは間に他の記号Nodeが存在しても認識してしまうため、これを 避ける必要がある。このためにnot-existの記号を利用して、間に入る記号Nodeが存在し ないという条件を記述している。これにより、曖昧な解釈が発生しない。しかし、先の弱 い制約条件“f.mid x < s.mid x”があるため、このルールに関する解析では、制約条件 グラフを利用することによる高速化が実現できない。
ChokらのアルゴリズムやBaltの手法では、RHSの記号数に依存した計算量が必要で あった。一方、提案手法の制約条件グラフを利用した解析手法では、RHSの記号数には直 接依存しない。これまで述べたように、エッジで利用されている制約条件に依存し、それ らがどのように記号と結びついているかによって計算量が変化する。訪問に利用するエッ ジが、座標の一致のような制約条件の場合は、ハッシュ表を用いてO(1)で対応するトー クンが発見できた。また、それ以外の場合でも多くの場合O(logn)で対応するトークンを 見つけることができる。これにより、すべてが強い制約条件のエッジを利用して訪問した 場合、1トークンに対する解析は、最速でO(1)の計算量で、遅くともO(logn)の計算量 で解析が可能である。つまり、図式全体の解析には、O(n)からO(nlogn)の計算量で解 析できるということである。3.3節で調査した図形言語は、すべてこの条件に当てはまる。
提案したアルゴリズムの正当性、つまり、このアルゴリズムが図形言語を正しく識別し、
解析が終了するための条件は、4.1.1節で示したChokらのアルゴリズムにおける条件と同 じである。つまり、扱える図形言語の範囲は変わっていない。なぜなら、提案手法では、
Chokらのアルゴリズムのインクリメンタルな解析部分に関する高速化を行っただけだか らである。
提案手法は、このような条件を満たす図形言語に対して適用できる高速化手法である。
特定の図形言語に関する解析器を高速化したのではない。もちろん、図形言語が特定され れば、それに特化した解析アルゴリズムを構築することで高速化が実現できるが、本研究 では、より一般的な解析アルゴリズムを提案した。これにより、図形文法を与えるだけで、
高速な解析器を利用することが可能となる。
本研究では、図形文法としてCMGを対象に解析アルゴリズムの高速化を行った。も ちろん、他の図形文法に基づく解析も知られている。たとえば、WittenburgはRelational Grammarsに対してEarley-style[Ear70]の解析を用いることで高速化を行っている[Wit92]。 しかし、これは、Relational GrammarsがCMGに比べて記述力の弱い文法であるため高速 な解析が実現できている。本研究で提案した手法は、より広い範囲の図形言語を扱える CMGにおいて、高速な解析を実現する。