本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。
今回は、前回作成した非決定性有限オートマトン(Non-Deterministic Finite Automaton)から決定性有限オートマトン(Deterministic Finite Automaton)の作成方法について学んでいきます。
はじめに
正規表現によるパターンマッチを行うプログラムを作成するにあたり、以下の段階分けを行います。
今回は上記3の非決定性有限オートマトンから決定性有限オートマトンを作成する方法について学びます。
オートマトンとは
正規表現でパターンマッチを行うには、有限オートマトン(Finite Automaton)というものを利用します(以降オートマトンと呼びます)。
オートマトンとは、内部に固有の状態を持った機械装置のようなもので、外部からの入力に応じて、その内部の状態を変化させます(どうやら自動羊肉ではなさそうです)。
オートマトンは以下のような状態遷移図(State Transition Diagram)というグラフ構造を使うと視覚的にも解りやすくなります。
上記fig1は、正規表現 の状態遷移図を表したものです。
上記の0を初期状態(Inite State)といい、入力値によって、1、2、そして3へと内部状態を変化させます。
3は二重線となっていますが、これは終了状態(Final State)を表します。
今回は、オートマトンを用いて正規表現によるパターンマッチを行うために2つの段階を用意します。
一つ目は、前回で作成した構文木から機械的に非決定性有限性オートマトンに変換します。
二つ目は、非決定性有限性オートマトンを決定性有限オートマトンに変換します。
なお、バックトラック法という手法を用いれば、非決定有限オートマトンのみでパターンマッチもできるようですが、決定性有限オートマトンに変換したほうが、トータルの処理時間が短縮できるようです。
決定性有限オートマトンとは
前回では非決定性有限オートマトン(以下NFA)について学びました。
NFAでは 遷移と呼ばれるものを利用して、機械的に正規表現からオートマトンを作成することができました。
しかし、同じ入力に対して複数の遷移先がある中では、どちらに遷移すべきか分かりません。
そこで用いるのが、決定性有限オートマトン(Deterministic Finite Automaton:以下DFA)になります。
DFAでは、遷移先は一つに決められているため、NFAでの問題点が解消できます。
なお、上記のfig1はDFAになります。
PythonでDFAを作成する
# 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(正規表現 )から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を作成することができました。