SHOEISHA iD

※旧SEメンバーシップ会員の方は、同じ登録情報(メールアドレス&パスワード)でログインいただけます

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

正規表現エンジンを作ろう

正規表現エンジンを作ろう (5)

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

  • X ポスト
  • このエントリーをはてなブックマークに追加

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の作成に必要なものは、「遷移関数」「開始状態」「受理状態の集合」でした。これら3つを、順番に実装していきます。

 以下、元となる 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の実装が終わり、正規表現エンジンに必要な道具は全て揃いました。いよいよこれらの道具を組み合わせ、正規表現エンジンを完成させます。

次のページ
正規表現エンジンを完成させる

この記事は参考になりましたか?

  • X ポスト
  • このエントリーをはてなブックマークに追加
正規表現エンジンを作ろう連載記事一覧

もっと読む

この記事の著者

hiratara(ヒラタラ)

1977年に苫小牧市で生まれる。北海道大学理学部数学科卒。小学生の頃、両親に買い与えられたMZ-2500でプログラミングを始めた。学生時代、CGIの自作に没頭し、それ以降WEB開発の魅力に憑かれる。社会人になっても数学好きは変わらず、専門書を買い集めるのが最近の趣味。id:hirataraにてblogを執筆...

※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です

この記事は参考になりましたか?

この記事をシェア

  • X ポスト
  • このエントリーをはてなブックマークに追加
CodeZine(コードジン)
https://codezine.jp/article/detail/3168 2008/12/03 08:00

おすすめ

アクセスランキング

アクセスランキング

イベント

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

新規会員登録無料のご案内

  • ・全ての過去記事が閲覧できます
  • ・会員限定メルマガを受信できます

メールバックナンバー

アクセスランキング

アクセスランキング