Engineering Note

プログラミングなどの技術的なメモ

正規表現(決定性有限オートマトンの作成) (Pythonによるアルゴリズムとデータ構造)

brute forcing

本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonアルゴリズムとデータ構造について学習していきます。

今回は、前回作成した非決定性有限オートマトン(Non-Deterministic Finite Automaton)から決定性有限オートマトン(Deterministic Finite Automaton)の作成方法について学んでいきます。

 

 

はじめに

正規表現によるパターンマッチを行うプログラムを作成するにあたり、以下の段階分けを行います。

 

  1. 正規表現を解析し、構文木を作成する
  2. 構文木から非決定性有限オートマトンを作成する
  3. 非決定性有限オートマトンから決定性有限オートマトンを作成する
  4. 決定性有限オートマトンを使いパターンマッチをする

 

今回は上記3の非決定性有限オートマトンから決定性有限オートマトンを作成する方法について学びます。

 

オートマトンとは

正規表現でパターンマッチを行うには、有限オートマトン(Finite Automaton)というものを利用します(以降オートマトンと呼びます)。

オートマトンとは、内部に固有の状態を持った機械装置のようなもので、外部からの入力に応じて、その内部の状態を変化させます(どうやら自動羊肉ではなさそうです)。

 

オートマトンは以下のような状態遷移図(State Transition Diagram)というグラフ構造を使うと視覚的にも解りやすくなります。

 

fig1. 正規表現 [tex:a(a|b)*a] の状態遷移図

fig1. 正規表現 a(a|b)*a の状態遷移図

 

上記fig1は、正規表現 a(a|b)*a の状態遷移図を表したものです。

上記の0を初期状態(Inite State)といい、入力値によって、1、2、そして3へと内部状態を変化させます。

3は二重線となっていますが、これは終了状態(Final State)を表します。

 

今回は、オートマトンを用いて正規表現によるパターンマッチを行うために2つの段階を用意します。

一つ目は、前回で作成した構文木から機械的に非決定性有限性オートマトンに変換します。

二つ目は、非決定性有限性オートマトンを決定性有限オートマトンに変換します。

 

なお、バックトラック法という手法を用いれば、非決定有限オートマトンのみでパターンマッチもできるようですが、決定性有限オートマトンに変換したほうが、トータルの処理時間が短縮できるようです。

 

決定性有限オートマトンとは

前回では非決定性有限オートマトン(以下NFA)について学びました。

 

 

NFAでは \epsilon 遷移と呼ばれるものを利用して、機械的正規表現からオートマトンを作成することができました。

しかし、同じ入力に対して複数の遷移先がある中では、どちらに遷移すべきか分かりません。

そこで用いるのが、決定性有限オートマトン(Deterministic Finite Automaton:以下DFAになります。

DFAでは、遷移先は一つに決められているため、NFAでの問題点が解消できます。

なお、上記のfig1はDFAになります。

 

PythonDFAを作成する

それでは、PythonDFAを作成します。

 

# dfa.py
from nfa import NfaList, Nfa
import sys

EMPTY = -1
NFA_STATE_MAX = 256
NFA_VECTOR_SIZE = int(NFA_STATE_MAX / 8)
DFA_STATE_MAX = 100

class NfaStateSet:
    def __init__(self):
        self.vec = [0 for _ in range(NFA_VECTOR_SIZE)]

class Dlist:
    def __init__(self):
        self.char = None
        self.dst = NfaStateSet()
        self.next = None

class Dslist:
    def __init__(self):
        self.char = None
        self.dst = Dstate()
        self.next = None

class Dstate:
    def __init__(self):
        self.state = None
        self.visited = None
        self.accepted = None
        self.next = None
        self.to = None

class Dfa:
    def __init__(self, regex, debug=False):
        self.regex = regex
        self.dfa = [Dstate() for _ in range(DFA_STATE_MAX)]
        self.initial_state = NfaStateSet()
        self.initial_dfa_state = Dstate()
        self.state = 0
        self.nfa_state = None
        self.nfa = None
        self.nfa_entry = None
        self.nfa_exit = None
        self.debug = debug

    def check_nfa_state(self, state, s):
        return state.vec[int(s/8)] & (1 << (s%8))

    def dump_state_set(self, p):
        for i in range(self.nfa_state):
            if self.check_nfa_state(p, i):
                print("{} ".format(i), end="")

    def dump_dfa(self):
        for i in range(self.state):
            s = 'A' if self.dfa[i].accepted else ' '
            print("{:2}{}: ".format(i, s), end="")
            l = self.dfa[i].next
            while l:
                print("{}=>{} ".format(l.char, l.dst.to), end="")
                l = l.next
            print()
        for i in range(self.state):
            s = 'A' if self.dfa[i].accepted else ' '
            print("state {:2}{} = {}".format(i, s, '{'), end="")
            self.dump_state_set(self.dfa[i].state)
            print("}")

    def add_nfa_state(self, state, s):
        state.vec[int(s/8)] |= (1 << (s%8))

    def mark_empty_transition(self, state, s):
        self.add_nfa_state(state, s)
        p = self.nfa[s]
        while p:
            if p.char == EMPTY and not self.check_nfa_state(state, p.to):
                self.mark_empty_transition(state, p.to)
            p = p.next

    def collect_empty_transition(self, state):
        for i in range(self.nfa_state):
            if self.check_nfa_state(state, i):
                self.mark_empty_transition(state, i)

    def equal_nfa_state_set(self, a, b):
        for i in range(NFA_VECTOR_SIZE):
            if a.vec[i] != b.vec[i]:
                return 0
        return 1

    def register_dfa_state(self, s):
        for i in range(self.state):
            if self.equal_nfa_state_set(self.dfa[i].state, s):
                return self.dfa[i]
        if self.state > DFA_STATE_MAX:
            print("Too many DFA state.")
            sys.exit(1)

        self.dfa[self.state].state = s
        self.dfa[self.state].visited = 0
        accepted = 1 if self.check_nfa_state(s, self.nfa_exit) else 0
        self.dfa[self.state].accepted = accepted
        self.dfa[self.state].next = None
        self.dfa[self.state].to = self.state
        p = self.dfa[self.state]
        self.state += 1
        return p

    def fetch_unvisited_dfa_state(self):
        for i in range(self.state):
            if self.dfa[i].visited == 0:
                return self.dfa[i]
        return None

    def compute_reachable_nfa_state(self, dstate):
        state = dstate.state
        result = None
        goto = False
        for i in range(self.nfa_state):
            if self.check_nfa_state(state, i):
                p = self.nfa[i]
                while p:
                    if p.char != EMPTY:
                        a = result
                        while a:
                            if a.char == p.char:
                                self.add_nfa_state(a.dst, p.to)
                                goto = True
                                break
                            a = a.next
                        if goto:
                            goto = False
                            p = p.next
                            continue
                        b = Dlist()
                        b.char = p.char
                        self.add_nfa_state(b.dst, p.to)
                        b.next = result
                        result = b
                    p = p.next
        return result

    def init_nfa(self):
        nfa = Nfa(self.regex, self.debug)
        nfa.build_nfa()
        self.nfa_entry = nfa.entry
        self.nfa_exit = nfa.exit
        self.nfa_state = nfa.state
        self.nfa = nfa.nfa

    def convert_nfa_to_dfa(self):
        self.init_nfa()
        self.add_nfa_state(self.initial_state, self.nfa_entry)
        self.collect_empty_transition(self.initial_state)
        self.initial_dfa_state = self.register_dfa_state(self.initial_state)

        t = self.fetch_unvisited_dfa_state()

        while t:
            t.visited = 1
            x = self.compute_reachable_nfa_state(t)
            while x:
                self.collect_empty_transition(x.dst)
                p = Dslist()
                p.char = x.char
                p.dst = self.register_dfa_state(x.dst)
                p.next = t.next
                t.next = p
                x = x.next
            t = self.fetch_unvisited_dfa_state()
        if self.debug:
            print("------ DFA ------")
            self.dump_dfa()

dfa = Dfa("a(a|b)*a", debug=True)
dfa.convert_nfa_to_dfa()

 

動作確認 

それでは上記で作成したスクリプトを実行してみます。

なお、前回作成したNFA(正規表現 a(a|b)*a )からDFAを生成します(状態遷移図はfig1と同じものになります)。

 

 > python dfa.py
 ------ Syntax Tree ------
 (concat (concat 'a' (closure )(or 'a' 'b'))) 'a')
 ------ NFA ------
 state   0:(a . 3)
 state   2:(a . 1)
 state   3:(? . 4)
 state   4:(? . 2) (b . 5) (a . 5)
 state   5:(? . 4)
 ------ DFA ------
  0 : a=>1
  1 : a=>3 b=>2
  2 : a=>3 b=>2
  3A: a=>3 b=>2
 state  0  = {0 }
 state  1  = {2 3 4 }
 state  2  = {2 4 5 }
 state  3A = {1 2 4 5 }

 

ダンプしてみると、問題なくDFAを作成することができました。

 

参考書籍

定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)