グラフ構造スタック

コンピュータサイエンスにおいて、グラフ構造スタック(GSS) は、各有向パスがスタックを表す有向非巡回グラフです。グラフ構造スタックは、プッシュダウンオートマトンにおける通常のスタックを置き換える、富田アルゴリズムの重要な部分です。これにより、アルゴリズムは、あいまいな文法を解析する際に非決定的な選択をエンコードすることができ、効率が向上する場合があります。

次の図には、{7,3,1,0}、{7,4,1,0}、{7,5,2,0}、{8,6,2,0} の 4 つのスタックがあります。

非決定性をシミュレートする別の方法は、必要に応じてスタックを複製することです。頂点が共有されないため、複製の効率は低くなります。この例では、9 個ではなく 16 個の頂点が必要になります。

オペレーション

GSSnode * GSS::add ( GSSnode * prev , int elem ) { int prevlevel = prev -> level ; assert ( levels . size () >= prevlevel + 1 ); int level = prevlevel + 1 ; if ( levels . size () == level ) { levels . resize ( level + 1 ); } GSSnode * node = findElemAtLevel ( level , elem ); if ( node == nullptr ) { node = new GSSnode (); node -> elem = elem ; node -> level = level ; levels [ level ]. push_back ( node ); } node -> add ( prev ); return node ; }

void GSS::remove ( GSSnode * node ) { if ( levels . size () > node -> level + 1 ) if ( findPrevAtLevel ( node -> level + 1 , node )) throw Exception ( "上からのみ削除できます。" ); for ( int i = 0 ; i < levels [ node -> level ]. size (); i ++ ) if ( levels [ node -> level ][ i ] == node ) { levels [ node -> level ]. erasing ( levels [ node -> level ]. begin () + i ); break ; } delete node ; }

参考文献

富田勝.グラフ構造スタックと自然言語解析. 計算言語学会年次大会, 1988. [1]
エリザベススコット、エイドリアンジョンストンGLL 解析gll.pdf