DFA 状態の最小化

正規表現から DFA を直接生成すると、 NFA から DFA を作るよりも状態数が少なくなる傾向があります。 しかしながら、 最小の倍以上に状態数が増えて冗長になることもあります。

Core regular expression to Deterministic Finite Automata, DFA

そのような場合は、 最初から DFA の状態遷移を作る方が正規表現を書くよりも楽な場合に生じがちで、 文字クラスのブラケット表記もその一つです。

$ cat bracket-pattern
\[(\]
  |(\[|a)(-(^|\[|a))?(((^|\[|a)-)?(^|\[|a))*-?
  |-((((^|\[|a)-)?(^|\[|a))+-?)?
  |^((\[|a)(-(^|\[|a))?(((^|\[|a)-)?(^|\[|a))*-?
    |-((((^|\[|a)-)?(^|\[|a))+-?)?
    )?
  )\]
$ sed 's/ //g' bracket-pattern | ./regexp-to-dfa

これの最小状態数は下記の 9 状態です。 一方、 DFA からの直接作成法では、 e1 e2 の連結で両方が同じ式で始まったとしても、 別の状態を作るため、 上のように連結だらけの正規表現では状態数が 23 に膨れ上がります。

S0:          '[' S1
S1: '-' S2 | '[' S3 | ']' S4 | '^' S5 | 'a' S3
S2:          '[' S3 | ']' S6 | '^' S3 | 'a' S3
S3: '-' S7 | '[' S3 | ']' S6 | '^' S3 | 'a' S3
S4:                   ']' S6
S5: '-' S2 | '[' S3 | ']' S6          | 'a' S3
S6: #
S7:          '[' S8 | ']' S6 | '^' S8 | 'a' S8
S8: '-' S4 | '[' S3 | ']' S6 | '^' S3 | 'a' S3

DFA 状態の最小化を書いて、 手作業しなくても最小 DFA を得られるようにします。 最小 DFA を得るには状態集合を分割していきます。 まず、 終状態とそうでない状態の 2 つに分割します。

void
re_dfa_type::minimize_init_partition (std::vector<std::set<int> >& partition)
{
    std::set<int> notfinal;
    for (auto from : m_trie) {
        if (m_final.count (from.first) == 0)
            notfinal.insert(from.first);
    }
    partition.push_back(notfinal);
    partition.push_back(m_final);
}

その後は、 分割した状態集合のどれへ分岐していくかで、 さらに状態集合を分割します。 今回のやりかたは Moore のアルゴリズムを乱暴に実装しただけで、 集合にする前の全状態に渡って、 ある遷移元から記号でどの状態集合へ遷移するかを signature へ求めていきます。 この signature が同じ開始状態の集合が分割後の次の状態集合になります。 これを分割が不要になるまで繰り返します。 Moore のアルゴリズムの最悪計算量は入力状態数 n に対して Ο(n^2) にも関わらず、 DFA 最小化では平均計算量 Ο(n log n) で最小化をおこなえることが近年 J. Berstel 等 Minimization of Automata (2010) によって報告されています。 そうはいっても、 この実装は乱暴すぎて速度が落ちてしまっています。

void
re_dfa_type::minimize (void)
{
    std::vector<std::set<int> > partition;
    std::vector<std::vector<int> > transition;

    minimize_init_partition (partition);
    for (;;) {
        std::vector<std::set<int> > partition1;
        transition.clear ();
        for (auto from : m_trie) {
            std::vector<int> signature; // {code => <partition entry no>}
            for (auto to : from.second) {
                signature.push_back (to.first);
                int partno = -1;
                for (int i = 0; partno < 0 && i < partition.size (); ++i) {
                    if (partition[i].count (to.second))
                        partno = i;
                }
                signature.push_back (partno);
            }
            int insert_at = -1;
            for (int i = 0; insert_at == -1 && i < transition.size (); ++i) {
                if (transition[i] == signature)
                    insert_at = i;
            }
            if (insert_at >= 0) {
                partition1[insert_at].insert(from.first);
            }
            else {
                transition.push_back (signature);
                std::set<int> u {from.first};
                partition1.push_back (u);
            }
        }
        if (partition == partition1)
            break;
        std::swap (partition, partition1);
    }
    minimize_to_trie (transition);
}

最後に、遷移表と終状態集合に格納して最小化はおしまいです。

void
re_dfa_type::minimize_to_trie (std::vector<std::vector<int> >& transition)
{
    std::map<int,std::map<int,int> > trie;
    std::set<int> final;
    for (int s = 0; s < transition.size (); ++s) {
        for (int i = 0; i < transition[s].size (); i += 2) {
            if (transition[s][i] == FINCODE)
                final.insert (s);
        }
    }
    for (int s = 0; s < transition.size (); ++s) {
        for (int i = 0; i < transition[s].size (); i += 2) {
            trie[s][transition[s][i]] = transition[s][i + 1];
        }
    }
    std::swap (m_trie, trie);
    std::swap (m_final, final);
}