dfa-0.02 DFA 状態数の最小化対応版(まだ NFA 経由)

昨日の「dfa-0.01 正規表現から DFA へ(NFA 経由版)」は、動くのですが、問題がありました。正規表現によっては、DFA の状態数が膨らんでしまうのです。
例えば、xy で終わるけど、途中には xy が現れない文字列にマッチする正規表現 /(?:(?!xy).)*xy/ を開包の展開した /(y|z)*xx*(z(y|z)*xx*)*y/ に対しては、状態数が 11 個に膨れ上がってしまいます。この正規表現に対応する DFA の状態数はたった 3 個で済むのに !

$ perl -MDFA -e 'print DFA->compose("(y|z)*xx*(z(y|z)*xx*)*y")->inspect'
   0: {"y" => 2,"x" => 1,"z" => 3}
   1: {"y" => 5,"x" => 4,"z" => 6}
   2: {"y" => 2,"x" => 1,"z" => 3}
   3: {"y" => 2,"x" => 1,"z" => 3}
   4: {"y" => 5,"x" => 4,"z" => 6}
   5: {"\0final" => 0}
   6: {"y" => 8,"x" => 7,"z" => 9}
   7: {"y" => 5,"x" => 10,"z" => 6}
   8: {"y" => 8,"x" => 7,"z" => 9}
   9: {"y" => 8,"x" => 7,"z" => 9}
  10: {"y" => 5,"x" => 10,"z" => 6}

ということで、昨日に続いて、ドラゴンブックをネタ本にして、「3.9 DFA によるパターン照合の最適化」の「DFAの状態数の最小化」を実装しました。といっても、これのアルゴリズムで用いる手順の記述がすごいのです。一部を書き写すとこんなんです。著者の偉い先生方々は本当に実装した経験があるんかいとつっこみたくなります。なんか元々ネタの論文から書き写しただけとちゃうんかと。いやはや。

for Πの各グループG do begin
    すべての入力記号 a について,G の状態 s と t とが a による遷移をもち,
        その遷移先がΠの中で,同じグループに属しているとき,そして,
        その場合にかぎって,s と t とが同じ部分グループに属するように
        G を分割する;
    Πnew における G を,いま作ったすべての部分グループで置き換える.
end

図3.45 Πnew の構成法

(コンパイラ―原理・技法・ツール〈1〉 (Information & Computing)、p 170)

これをどう実装するかですが、何パターンか手作業で試してみて、Πのグループ id で遷移先の状態番号を置き換えた遷移表を作り直せば、Πnew とそれに対応する小さくなった DFA の候補が自動的に作れることに気が付きました。
ということで、最小化するメソッドは以下のようにしました。while ループの中が、上の Πnew の構成法に相当します。

sub compact {
    my $self = shift;
    my $Group = [
        [grep { ! $self->include_final($_) } 0 .. $#$self],
        [grep {   $self->include_final($_) } 0 .. $#$self],
    ];
    while (1) {
        my(@NextGroup, %NextGroupId);
        my $compactDFA = DFA->new;
        for my $gid (0 .. $#$Group) {
            for my $state (@{$Group->[$gid]}) {
                my $compact_plist = $self->subst_group($Group, $state);
                my $sig = join ":", $gid, @$compact_plist;
                unless (exists $NextGroupId{$sig}) {
                    push @$compactDFA, {@$compact_plist};
                    push @NextGroup, [];
                    $NextGroupId{$sig} = $#NextGroup;
                }
                push @{$NextGroup[$NextGroupId{$sig}]}, $state;
            }
        }
        if (@$Group == @NextGroup) {
            return $compactDFA;
        }
        $Group = \@NextGroup;
    }
}

Πに相当する配列 @{$Group} に最小化前の DFA の状態番号($state)を無名配列でグループ化して格納してあります。この無名配列を取り出す添え字がグループ id ($gid)です。Πnew は配列 @NextGroup です。
最小化前の DFA$state 番の状態遷移を表すハッシュ(キーは入力記号、値は遷移先の状態番号)の遷移先の状態番号を、遷移先の状態が含まれる @{$Group} のグループの $gid に置き換える subst_group メソッドを呼び出すと、入力記号と遷移先のグループ id の交代リストのリファレンスを返します。これは入力記号でソートしてあります。この交代リストをハッシュにすると最小化された DFA の候補の状態遷移表の列になります。
このとき、$state が含まれるグループの $gid と交代リストのペアが新しく手に入ったときは、新しいグループを @NextGroup に作成し、新しいグループの id を状態番号にした遷移表の列をコンパクト化された DFA に追加します。既にペアがあった場合は、そのグループに元の DFA の状態番号 $state を追加します。
これをループで繰り返し、グループ分けが変化しないとき、グループ id で置き換えた遷移表を最小化された DFA として返します。
このコードを含んだ dfa-0.02 も公開しておきます。これ以外にも、細かなバグ取りとスペルミスの修正などを 0.01 からやってあります。
https://tociyuki.sakura.ne.jp/archive/dfa-0.02/

  1. compact.pl -- DFA 最小化のサンプル・コード。(new)
  2. sample.pl -- サンプル・コード。
  3. DFA.pm -- DFA の遷移表のコンテナ。(compact追加)
  4. NFA.pm -- NFA の遷移表のコンテナ。(スペルミス修正)
  5. FATable.pm -- 上2つのベースクラス。(pushメソッド削除)
  6. NFA2DFA.pm -- NFAからDFAへ。部分集合構成法を使用。(入力記号を状態集合からその都度求めるように変更)
  7. Regexp2NFA.pm -- 正規表現BNFでNFAへ変換。(変化なし)
  8. RegexpScanner.pm -- 正規表現のスキャナ。(変化なし)
  9. Token.pm -- 同上の生成するトークンのクラス。(変化なし)
  10. TopdownParser.pm -- トップ・ダウン構文解析子のベースクラス。(変化なし)

DFA の compose クラス・メソッドを使うと状態数を最小化した遷移表を常に作って返すようになりました。
これを使うと、先の例は次のような出力に変化します。それだけでなく、同じ入力記号にマッチする非決定性な正規表現 /(y|z|xx*z)*xx*y/ であっても、同じ最小化された DFA が得られるようになります。

$ perl -MDFA -e 'print DFA->compose("(y|z)*xx*(z(y|z)*xx*)*y")->inspect'
   0: {"y" => 0,"x" => 1,"z" => 0}
   1: {"y" => 2,"x" => 1,"z" => 0}
   2: {"\0final" => 0}
$ perl -MDFA -e 'print DFA->compose("(y|z|xx*z)*xx*y")->inspect'
   0: {"y" => 0,"x" => 1,"z" => 0}
   1: {"y" => 2,"x" => 1,"z" => 0}
   2: {"\0final" => 0}

ということで、今回は教科書を横目でみながら Perl 化するというわけにいかず、オリジナルで書き起こしたのですが、DFA の遷移状態の最小化でグループ id へ置き換える技を私が最初に思いついたということはありえず、既に誰かが作っているのでしょう。
dfa-0.03 正規表現 → 構文木 → DFA、NFA (構文木経由版)