V´ azquez らのアルゴリズムの出力の平均状態数の 削減
4.6 より有効な選択順の検討
4.6.1 状態の選択順
V´azquezらのアルゴリズムで任意性のある状態の選択順について，サイズの小さい状
態P を優先する戦略を考案して実験を行い，戦略の有効性を確認したが，サイズの小さ い状態を優先する戦略より，サイズの大きい状態を優先する戦略のほうが，出力の状態 数が小さくなる例も見つかった．その例を，図4.11に示す．
図4.11では，NFA Mを共通の入力とするV´azquezらのアルゴリズムの，サイズの小 さい（遷移元）状態を優先する場合と，サイズの大きい（遷移元）状態を優先する場合 のそれぞれの処理過程を示しているが，文字はb, aの選択順とした．図中の分岐部分に 着目すると，サイズの大きい遷移元状態{1,2}を優先した方が，サイズの小さい状態{0} を優先した方より，分割に関与しない空集合∅を除けば，遷移先状態が小さくなってい る．そして，大きい状態を優先する方は，状態{4} ⊂ {3,4}が先に出現することで，状 態{3,4}の出現を防げているといえる．
前述の状態の選択戦略は，遷移先の状態δ(P, a)を小さくするために，遷移先が小さく なる可能性が高い，小さい遷移元の状態P を選ぶとしたため，図4.11のような例は防ぐ ことができない．こうした問題を解決する選択順としては，V´azquezらのアルゴリズム を逸脱する部分はあるが，例えば，選択待ちの全ての状態P について，その全ての遷移 先をあらかじめ列挙しておいて，その遷移先が小さいものから処理を進めるといったも のが考えられる．
0 10 20 30 40 50 60 70 80
|Q|
0 20 40 60 80 100 120
|Q'|
Minimum-delta()-first Minimum-state-first Minimum-state-delta()-first
図 4.8: 状態と文字の選択順による，V´azquezらのアルゴリズムの出力の状態数の違い
（|Σ|= 4）．
0 10 20 30 40 50 60 70 80
|Q|
0 20 40 60 80 100 120
|Q'|
Minimum-delta()-first Minimum-state-first Minimum-state-delta()-first
図 4.9: 状態と文字の選択順による，V´azquezらのアルゴリズムの出力の状態数の違い
（|Σ|= 16）．
0 5 10 15 20 25 30
alphabet size 0
5 10 15 20 25 30 35
|Q'|
Minimum-delta()-first Minimum-state-first Minimum-state-delta()-first
図 4.10: 状態と文字の選択順による，V´azquezらのアルゴリズムの出力の状態数の違い
（|Q|= 20）．
4 ⊂ {3,4}
𝛿 1,2,3,4 , 𝑏 = 0,1,2,3,4 , 𝛿 1,2,3,4 , 𝑎 = 1,2
：選択済みの状態
：選択待ちの状態
入力
𝑏 𝑏
0 1 2 𝑎 3
𝑎
𝑎 𝑎 𝑏
4 𝑎
𝑏 𝑏
{1,2,3,4}
{1,2, 3,4}
{1,2}
𝑏
{4}
{0}
𝑎 𝑏
{1}
𝑏 𝑎, 𝑏
𝑏 {1,2,3,4}
{1,2}
𝑏 {0}
𝑎 𝑏
{1,2,3,4}
{1,2}
𝑏
{3,4}
{0}
𝑎 𝑎
𝑏 𝑎
𝛿 0 , 𝑏 = ∅, 𝛿 0 , 𝑎 = 0,3,4
𝛿 1,2 , 𝑏 = 0,4 , 𝛿 1,2 , 𝑎 = 1
サイズの大きい 状態{1,2}を優先 サイズの小さい 状態{0}を優先
図 4.11: サイズが大きい状態を優先した方が，V´azquezらのアルゴリズムの出力の状態 数が小さくなる例．
4.6.2 文字の選択順
V´azquezらのアルゴリズムで任意性のある文字の選択順について，遷移先状態δ(P, a) のサイズが小さくなる文字aを優先する戦略を考案して実験を行い，戦略の有効性を確 認したが，遷移先の小さい文字を優先する戦略より，大きい文字を優先する戦略のほう が，出力の状態数が小さくなる例も見つかった．その例を，図4.12に示す．
図4.12では，図4.11と同じNFAMを共通の入力とするV´azquezらのアルゴリズムの，
遷移先の小さい文字を優先する場合と，大きい文字を優先する場合のそれぞれの処理過程 を示しているが，状態は{1,2,3,4},{1,2}の選択順とした．遷移先の小さい文字を優先す る場合は，先に既出の状態{1,2,3,4}の真部分集合である{1,2}の方を選択し出現させ，
後で既出の状態{1,2,3,4}を部分集合にもつ{0,1,2,3,4}の方を選択し，状態{3,4},{0} を出現させている．対して，遷移先の大きい文字を優先する場合は，先に{0,1,2,3,4}の 方を選択することで，状態{3,4}は出現していない．そして，状態{4} ⊂ {3,4}が先に 出現することで，状態{3,4}の出現を防げているといえる．
図4.12のような例は，遷移先状態δ(P, a)が小さいものを優先すればよいとは限らない ことを示すものであり，前項の最後に述べた，遷移先状態を列挙する戦略でも防ぐことが
4 ⊂ {3,4}
𝛿 1,2,3,4 , 𝑎
= 1,2
{1,2,3,4}
遷移先の大きい 文字𝑏を優先 遷移先の小さい
文字𝑎を優先
{1,2,3,4}
{1,2}
𝑎
{1,2,3,4}
{1,2}
𝑏
{3,4}
{0}
𝑎, 𝑏 𝑎, 𝑏
{1,2,3,4} 𝑏 {0}
𝑏
{1,2,3,4}
{1,2}
𝑏 {0}
𝑎 𝑏
{1,2, 3,4}
{1,2}
𝑏
{4}
{0}
𝑎 𝑏
{1}
𝑏 𝑏
𝑏 𝛿 1,2,3,4 , 𝑏
= 0,1,2,3,4 𝛿 1,2,3,4 , 𝑎
= 1,2 𝛿 1,2,3,4 , 𝑏
= 0,1,2,3,4
𝛿 1,2 , 𝑏
= 0,1,4
：選択済みの状態
：選択待ちの状態
入力
𝑏 𝑏
0 1 2 𝑎 3
𝑎
𝑎 𝑎 𝑏
4
𝑏 𝑏
図 4.12: 遷移先が大きくなる文字を優先した方が，V´azquezらのアルゴリズムの出力の 状態数が小さくなる例．
できない．こうした問題を解決する可能性のある選択順としては，既出の状態同士でその 包含関係を調べて，他のどの状態も部分集合として持たない状態P1（∀P0 ∈Q\{P1}, P0 ⊈ P1 ∈Q）を把握しておき，P1を部分集合にもつ遷移先状態δ(P, a)がある場合には，その 遷移先をもつ遷移元状態P や文字aを優先するといったものが考えられる．さらに，P1 を部分集合にもつ遷移先δ(P, a)が複数ある場合には，P1とサイズの近い，小さい状態か ら選択するのがよいと考えられる．これは，図4.13に示した例から予想できる．
図4.13は，上記のP1 ={0}の例であり，{0}を部分集合にもつ遷移先状態の選択順に よる，V´azquezらのアルゴリズの処理過程の違いを表すが，{0}とサイズの近い，小さい 遷移先状態を優先する場合の方が，より小さい状態{2},{3}を出現させている．
{0}
{0}
{1}
𝑎 𝑎
{0}
{1} {2}
𝑏 𝑎, 𝑏
𝑎, 𝑏
{0}
{1}
𝑐
{2}
{3}
𝑏, 𝑐 𝑎, 𝑏, 𝑐
𝑎, 𝑏, 𝑐
{0} 𝑐 {1,2,3}
𝑐
{0} 𝑐
{1,2}
{1,2,3}
𝑏 𝑏, 𝑐
{0}
{1}
𝑐
{1,2}
{1,2,3}
𝑏 𝑎
𝑎, 𝑏, 𝑐
𝛿 0 , 𝑐
= 0,1,2,3
𝛿 0 , 𝑎
= 0,1 𝛿 0 , 𝑏
= 0,1,2 𝛿 0 , 𝑏
= 0,1,2
𝛿 0 , 𝑐
= 0,1,2,3 𝛿 0 , 𝑎
= 0,1 0を部分集合にもつ遷移先の
大きいものを優先
入力𝑀 = 𝑄, Σ, 𝛿, 𝐼, 𝐹 ：
：選択済みの状態
：選択待ちの状態 𝐼 = 0 ,
𝛿 0 , 𝑎 = 0,1 , 𝛿 0 , 𝑏 = 0,1,2 , 𝛿 0 , 𝑐 = 0,1,2,3 .
0を部分集合にもつ遷移先の 小さいものを優先
2 ⊂ {1,2}
3 ⊂ {1,2,3}
図 4.13: V´azquezらのアルゴリズムの文字の選択順の改良案の例．