Hopcroft 法で DFA 最小化

DFA の最小化の代表的なアルゴリズムは Hopcroft 法です。 終状態とそうでない状態に 2 分割しておいてから、 さらに分割を進めていくのは Moore 法と同じですが、 再試行なしで幅優先で分割を進めていくため、 理論上の最悪計算量はΟ(n log n) です。 といっても、 集合演算の塊なので、 そこまでの性能をだすのは大変です。

Core regular expression to Deterministic Finite Automata, DFA

Hopcroft の状態分割法を英語版 Wikipedia に合わせると、 ほとんど同じになります。 ワーク・リストの初期値だけが後者とは異なります。 英語版 Wikipedia では F だけを W の初期値にしていますけど、 それだと分割するべき状態集合を触らずに残してしまう場合が生じます。 正しくは、 初期値をパーティションと同じ 2 分割にします。

Q は全状態の集合、 Σは全記号、 δは遷移規則、 q0 は開始状態、 F は終状態集合

入力: DFA (Q、Σ、δ、q0、F)           
Π = {F, Q - F}      // パーティション
W = {F, Q - F}       // ワーク・リスト
while (W が空ではない) {
    S = W 中の集合
    W から S を削除する
    for (a : a ∈ Σ) {
        文字 a で S 中の状態へ遷移する遷移元状態の集合を作る
            つまり式で書くと X = {x| δ(x, a) ∈ S となる状態 x}        
        for (Y : Y ∈ Π で、 Y ∩ X ≠{} かつ Y \ X ≠{} を満たす) {
            Πの Y を Y ∩ X と Y \ X で置換する
            if W が Y を含む
                W の Y を Y ∩ X と Y \ X で置換する
            else
                W に、 Y ∩ X と Y \ X の要素数が少ない方を追加する
        }
    }
}
return Π

例えば、 数値のパターンから DFA を生成すると F の方が Q-F より小さくなります。 そこで、 W の初期値を {F} で最小化をおこなってみると、 分割が中途半端に止まってしまいます。

W = {F, Q - F} のとき
$ ./regexp-to-dfa '-?(0+(.0*)?|.0+)(e-?0+)?'
S0: '-' S1 | '.' S2 | '0' S3
S1: '.' S2 | '0' S3
S2: '0' S4
S3: '.' S4 | '0' S3 | 'e' S5 | #
S4: '0' S4 | 'e' S5 | #
S5: '-' S6 | '0' S7
S6: '0' S7
S7: '0' S7 | #

W= {F} のとき
$ ./regexp-to-dfa '-?(0+(.0*)?|.0+)(e-?0+)?'
S0: '-' S1 | '.' S2 | '0' S3
S1: '.' S2 | '0' S3
S2: '-' S2 | '0' S4
S3: '.' S4 | '0' S3 | 'e' S2 | #
S4: '0' S4 | 'e' S2 | #

Hopcroft 法の実装に入ります。 まず、 Moore 法の最小化メソッドを置き換えます。

void
re_dfa_type::minimize (void)
{
    re_dfa_hopcroft_impl hopcroft (m_transition, m_letter, m_final);
    hopcroft.minimize ();
    hopcroft.reconstruct (m_transition);
}

入れ子ループをくくりだすために計算用構造体を使います。 dfa オブジェクトが渡す DFA 遷移を初期化時に記録します。

typedef std::set<int> re_set_type;
typedef std::shared_ptr<re_set_type> re_set_ptr;

struct re_dfa_hopcroft_impl {
    std::map<int,std::map<int,int> > const& m_transition;
    re_set_type const& m_letter;
    re_set_type const& m_final;
    std::map<int,std::map<int,re_set_type> > m_itran;
    std::deque<re_set_ptr> m_partition;
    std::deque<re_set_ptr> m_worklist;

    explicit re_dfa_hopcroft_impl (
        std::map<int,std::map<int,int> > const& transition,
        re_set_type const& letter, re_set_type const& final
    ) : m_transition (transition), m_letter (letter), m_final (final) {}
    void minimize (void);
    void reconstruct (std::map<int,std::map<int,int> >& transition);

    void inverse_transition (void);
    void init_partition (void);
    bool select_lead_states (int code, re_set_ptr a, re_set_type& x);
    void update_partition (re_set_type const& x);
    void split_group (re_set_ptr y, re_set_type const& x,
        re_set_ptr& reject_x, re_set_ptr& accept_x);
    void update_worklist (re_set_ptr reject_x, re_set_ptr accept_x, re_set_ptr y);
    int intern_group (int state, std::vector<re_set_ptr>& group);
};

最小化のメインループです。 パーティション内で状態集合を分割していき、 ワーク・リストには分割を試みていない状態集合が入ります。 このアルゴリズムでは状態集合は分割されていくか分割されずにそのまま残るかの 2 択しかなく、 結合したり、 分割をご破算にして再試行するようなことはありません。 ワーク・リストには手つかずの状態集合が入ります。 ワーク・リストにある状態集合は必ずパーティションにも含まれていなければならず、 そうなるように分割時にワーク・リストを更新します。 そして、 手つかずの状態集合がなくなるまで分割を繰り返します。

ループの中では、 ワーク・リストから状態集合を一つとりだして、 ワーク・リストから削除します。 最小化前の DFA を参照して、 すべての記号ごとに、 とりだした手つかずの状態集合のどれかに遷移する遷移元の状態集合 x を作り、 x を使ってパーティションを更新していきます。 遷移先への遷移元の集合を作って分割を進めていくことからわかるように、 分割を終状態から初状態へと逆戻りでおこなっていきます。

手つかずの集合 a の内容は、 while スコープ中で変化してはいけません。 途中で、 この集合が分割対象になったとしても、 a を書き換えてはいけません。 そのため、 この実装では、 状態集合のスマート・ポインタをパーティションとワーク・リストへ入れる書き方にしています。 パーティション中の状態集合を分割すると書いていても、 実際には分割前の状態集合に手をつけずそのまま残します。 その代わり、 分割された後の 2 つの状態集合を新しく作り、 それらへのスマートポインタに置き換えていった新しいパーティションを作っていきます。 こうすることで、 a は分割の影響を受けずに同じ内容のままでいられます。 また、 状態集合はスマート・ポインタにしているので、 分割されてパーティションから取り除かれても、 メイン・ループのスコープを抜けるまで a は生存し続けることができます。

void
re_dfa_hopcroft_impl::minimize (void)
{
    inverse_transition ();
    init_partition ();
    while (! m_worklist.empty ()) {
        re_set_ptr a = m_worklist.front ();
        m_worklist.pop_front ();
        for (int code : m_letter) {
            re_set_type x;
            if (select_lead_states (code, a, x))
                update_partition (x);
        }
    }
}

上の遷移元状態集合 x を作るときに余計な繰り返しを避けるため、 最初に遷移表をひっくり返して終状態へ文字で遷移できる初状態の集合を作っておきます。

void
re_dfa_hopcroft_impl::inverse_transition (void)
{
    for (auto from : m_transition) {
        for (auto to : from.second) {
            if (to.first >= 0)
                m_itran[to.second][to.first].insert (from.first);
        }
    }
}

続いて、 終状態とそうでない状態へ 2 分割し、 それらでパーティションとワーク・リストを初期化します。 u は状態集合で、 ゴール m_final に含まれない状態を集めたものにします。 初期化後、 パーティションとワーク・リストは同じ内容になります。

void
re_dfa_hopcroft_impl::init_partition (void)
{
    re_set_type u;
    for (auto tran : m_transition) {
        if (m_final.count (tran.first) == 0)
            u.insert (tran.first);
    }
    m_partition.push_back (std::make_shared<re_set_type> (u));
    m_partition.push_back (std::make_shared<re_set_type> (m_final));
    m_worklist = m_partition;
}

最小化前の DFA で、 記号 code で状態集合 a のどれかへ遷移する、 遷移元集合 x を作成します。 初期化時に遷移をひっくりかえして、 遷移先からのマッピングを作ってあるので、 このマッピングから遷移元集合を選び出し和集合を作ります。 戻り値として、遷移元集合に要素が含まれると真を返します。

bool
re_dfa_hopcroft_impl::select_lead_states (int code, re_set_ptr a, re_set_type& x)
{
    for (int state_a : *a) {
        if (m_itran.count (state_a) && m_itran.at (state_a).count (code))
            re_set_union (x, x, m_itran.at (state_a).at (code));
    }
    return ! x.empty ();
}

パーティション・グループを先頭から末尾まで分割可能かどうか調べ、 分割できないときはそのままで、 分割可能なときは分割した 2 つの新しいグループに置き換えていきます。

void
re_dfa_hopcroft_impl::update_partition (re_set_type const& x)
{
    std::deque<re_set_ptr> result;
    for (auto it = m_partition.begin (); it != m_partition.end (); ++it) {
        re_set_ptr reject_x = std::make_shared<re_set_type> ();
        re_set_ptr accept_x = std::make_shared<re_set_type> ();
        split_group (*it, x, reject_x, accept_x);
        if (reject_x->empty () || accept_x->empty ()) {
            result.push_back (*it);
        }
        else {
            result.push_back (reject_x);
            result.push_back (accept_x);
            update_worklist (reject_x, accept_x, *it);
        }
    }
    std::swap (m_partition, result);
}

状態の分割をおこないます。 y はパーティション中の分割対象になっている状態集合です。 x はワーク・リストからとりだした手つかずだった状態集合内の状態へ、 現在着目している記号 code で遷移する遷移元の状態を集めた集合です。 y の分割では、 x に含まれる状態があるかないかで、 y の状態を仕分けします。 y と x の両方に含まれる状態を accept_x へ集め、 y の中で x に含まれない状態を reject_x へ集めます。

void
re_dfa_hopcroft_impl::split_group (re_set_ptr y, re_set_type const& x,
    re_set_ptr& reject_x, re_set_ptr& accept_x)
{
    for (int ystate : *y) {
        if (x.count (ystate))
            accept_x->insert (ystate);
        else
            reject_x->insert (ystate);
    }
}

ワーク・リストを更新します。 ワーク・リスト中の状態集合は、 パーティションにも含まれていないといけないので、 分割対象の状態集合 y がワーク・リストにあるときは、 ワーク・リスト中のそれも分割した 2 つの状態集合 reject_x と accept_x へ置き換えます。 ワーク・リストにないときは、 reject_x と accept_x のうち要素数が少ない方をワーク・リストへ追加します。

void
re_dfa_hopcroft_impl::update_worklist (re_set_ptr reject_x, re_set_ptr accept_x, re_set_ptr y)
{
    auto w = std::find (m_worklist.begin (), m_worklist.end (), y);
    if (w != m_worklist.end ()) {
        *w = accept_x;
        m_worklist.insert (w, reject_x);
    }
    else if (accept_x->size () < reject_x->size ()) {
        m_worklist.push_back (accept_x);
    }
    else {
        m_worklist.push_back (reject_x);
    }
}

ここまでが最小化部分です。 残りで遷移表の再構成をおこないます。 今回は Moore 法と同じ方式で、 最適化を考えずに、 素朴に表を埋めていきます。 最小化前の遷移表を先頭から末尾までたどっていき、 遷移元、 遷移先のそれぞれが含まれる、 分割後の状態集合へ置き換えていきます。 分割後の状態集合には置き換えをおこなっていく順に番号をふることにします。 番号をふりおえた状態集合を group へ記録して同じ状態集合には同じ番号を使うようにします。

void
re_dfa_hopcroft_impl::reconstruct (std::map<int,std::map<int,int> >& transition)
{
    std::map<int,std::map<int,int> > result;
    std::vector<re_set_ptr> group;

    for (auto from : m_transition) {
        for (auto to : from.second) {
            int group_from = intern_group (from.first, group);
            if (to.first >= 0) {
                int group_to = intern_group (to.second, group);
                result[group_from][to.first] = group_to;
            }
            else {
                result[group_from][to.first] = to.second;
            }
        }
    }
    std::swap (transition, result);
}

状態集合にユニークな番号を与えてそれを求めます。 状態集合が group に記録済みのときは、 既に番号が決まっているので、 それを返します。 group はベクタであり、 番号はベクタの要素番号にしています。 group に記録していないときは、 group の末尾へ状態集合を追加して、 末尾の要素番号を返します。

int
re_dfa_hopcroft_impl::intern_group (int state, std::vector<re_set_ptr>& group)
{
    int id = -1;
    for (int i = 0; -1 == id && i < group.size (); ++i) {
        if (group.at (i)->count (state))
            id = i;
    }
    if (-1 == id) {
        for (auto y = m_partition.begin (); -1 == id && y != m_partition.end (); ++y) {
            if ((*y)->count (state)) {
                id = group.size ();
                group.push_back (*y);
            }
        }
    }
    return id;
}