正規表現エンジンを作ろう （5）

NFAをDFAに変換し、正規表現エンジンを完成させる

NonDisjointSetsクラス

　NonDisjointSetsクラスは、ある集合と交わるような集合の集合（入れ子のfrozensetのようなもの）です。このクラスはDFAの受理状態を作るのに使います。

　DFAの受理状態（frozenset型）は前述したように、NFAの受理状態（整数型）を1つでも含んでいるようなDFAの状態（frozenset型）となります。よって、「NFAの受理状態の集合（frozenset型）」のNonDisjointSetsを考えると、NonDisjointSetsに含まれるfrozensetは全てNFAの受理状態（整数型）を1つ以上含んでいますので、このfrozensetはDFAの受理状態となります。

　それでは、NonDisjointSetsの実装について説明します。前述したように、NonDisjointSetsは集合の集合です。なので、入れ子のfrozensetでも表現が可能のように思えます。しかし、これは得策ではありません。一つ例を考えてみましょう。{1, 2, ..., 20} の20個からなるNFAの受理状態が{ 1 }とします。この{ 1 }のNonDisjointSetsを考えてみます。例えば、{ 1, 2 } { 1, 3, 4 } { 1, 12, 15, 20 } 等はこのNonDisjointSetsに含まれます。他の要素もあわせて含まれる要素を全て数えると、何個くらいあると思いますか？ 1は含まれるので固定で、残りの19個の要素の任意個数の組み合わせとなりますので……答えは2の19乗、524,288個です。このようにNonDisjointSetsは2のベキ乗個の要素を持つ集合であるため、素直にfrozensetの入れ子として実装すると大変なことになってしまいます。これが、第2回のコラムで述べたDFAの状態数が膨らんでしまうと言う問題です。

　そこでNonDisjointSetsを、frozensetと同じように振る舞うものとして実装します。そのために、Pythonの強力なダックタイピングの特性を利用します。NonDisjointSetsはfrozensetと継承関係を持ちませんが、代わりにfrozensetと同様な操作を持たせます。ただし、frozensetの持つ操作全てを実装するのは大変なので、ここでは一部の操作だけを実装します。

　DFAを動作させるとき、受理状態に対して行う操作は以下だけでした。

受理状態を扱う操作（再掲）

def is_accept_state(self):
    return self.cur_state in self.DFA.accepts

　NonDisjointSetsはDFAの受理状態としてしか使いませんので、このin（メンバシップテスト演算子）さえ実現できれば用は足りそうです。inの振る舞いは、特殊メソッドである__contains__によって実装できます。

　結果として、NonDisjointSetsクラスの実装は以下のようになります。

NonDisjointSetsクラス

class NonDisjointSets(object):
    def __init__(self, sub):
        self.sub   = sub
    def __contains__(self, a_set):
        return a_set & self.sub

　元となる集合を、self.sub に保存します。このself.subと交点を持つ集合であれば、このSubsetIncludingElemの要素となります。SubsetIncludingElemのイメージは入れ子のfrozensetですから、その要素もfrozensetです。つまり、in演算子で比較対象になる要素（__contains__の引数）も、frozenset型となりますので、& 演算子によって積集合を求めて、元となる集合との交点のあるなしを求めています。

部分集合構成法の実装

　これで道具は揃いました。実際のこの部分集合構成法を実装し、NFAをDFAに変換してみましょう。DFAの作成に必要なものは、「遷移関数」「開始状態」「受理状態の集合」でした。これら３つを、順番に実装していきます。

　以下、元となる NondeterministicFiniteAutomaton クラスのインスタンスを nfa とします。

遷移関数

　nfa.transitionから、新たなtransitionを定義します。以下のように実装します。

遷移関数

def transition(set_, alpha):
    ret = set()
    for elem in set_:
        ret |= nfa.transition(elem, alpha)
    return nfa.epsilon_expand( frozenset(ret) )

　遷移関数はDFAの要素を引数として取りますが、DFAの要素はNFAの状態の集合でした。つまり、遷移関数にはfrozenset型が渡ってきます。

　このfrozenset型の要素はNFAの状態なので、それぞれを nfa.transition で遷移させることができます。そして、nfa.transition の戻り値として返ってくる「次に取りうる状態の集合」を、全て和集合として集めた物が DFA上で次に遷移すべき状態となります。frozensetにおいて、和集合は |演算子 で計算できますので、各要素に対して nfa.transition をした結果を、 |演算子 で和をとっています。

　最後に、前述したように空文字列遷移をさせる必要があります。これは既にepsilon_expandメソッドとして実装済みですので、このメソッドを利用して拡張した状態集合を戻り値とします。

開始状態

　これは、NFAの開始状態のみからなる集合です。が、開始状態から空文字列の遷移がある場合は、他の文字による遷移の前にこの遷移を処理しなければなりません。そこで、開始状態もepsilon_expandメソッドで拡張します。

開始状態

nfa.epsilon_expand( frozenset([ nfa.start ]) ),

受理状態の集合

　前述したように、DFAの状態として表されるNFAで取りうる状態の集合の中に、1つでもNFAの受理状態が含まれていれば、そのDFAの状態は受理状態と言うことになります。

　この要件を満たすために、NonDisjointSetsを実装したのでした。nfa.acceptsに対する NonDisjointSetsインスタンスを作成すると、nfa.acceptsの要素を1つ以上含むNFAの状態の集合（DFAの状態）の集合となります。

開始状態

NonDisjointSets(nfa.accepts)

　以上をまとめると、nfa2dfaの実装は以下のようになります。

nfa2dfa関数

def nfa2dfa(nfa):
    def transition(set_, alpha):
        ret = set()
        for elem in set_:
            ret |= nfa.transition(elem, alpha)
        return nfa.epsilon_expand( frozenset(ret) )

    return DeterministicFiniteAutomaton(
            transition,
            nfa.epsilon_expand( frozenset([ nfa.start ]) ),
            NonDisjointSets(nfa.accepts)
            )

　これで部分集合構成法nfa2dfaの実装が終わり、正規表現エンジンに必要な道具は全て揃いました。いよいよこれらの道具を組み合わせ、正規表現エンジンを完成させます。