Papers/2016/masa-master: c4.tex comparison

comparison c4.tex @ 34:660c8f2365db

fix

author	Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date	Mon, 08 Feb 2016 22:26:29 +0900
parents	67b1a7f36b6c
children	466a8ed9c372

comparison

equal deleted inserted replaced

-:67b1a7f36b6c
+:660c8f2365db
 実装した正規表現マッチャのアルゴリズムは、
 \begin{enumerate}
 \item 与えられた正規表現を構文解析し、正規表現木に変換する。
 \item 正規表現木から非決定性オートマトン(以下、NFA)か決定性オートマトン(以下、DFA)に変換する。
-\item NFA に変換された場合、Subset Construction による NFA から DFA への変換をおこない、状態遷移リストを生成する。
+\item NFA に変換された場合、Subset Construction による NFA から DFA への変換をおこない、状態遷移テーブルを生成する。
-\item 状態遷移のリストを元に文字列検索を行ない結果を返す。
+\item 状態遷移のテーブルを元に文字列検索を行ない結果を返す。
 \end{enumerate}
 となる。本項はそれぞれのアルゴリズムについて述べていく。
 \newpage
 \newpage
 \subsection{正規表現木から DFA・NFA の生成}
 次に正規表現木から非決定性有限オートマトン(NFA)、決定性有限オートマトン(DFA)を生成する。
-オートマトンは、入力に対して状態に対応した処理を行ない結果を出力する(オートマトンの簡単な説明)
+オートマトンは、入力に対して状態に対応した処理を行ない結果を出力する仮想的な自動機械である。
+正規表現はオートマトンで表現することができるので、状態と入力(ここでは正規表現)が判れば次はどのような状態になるのか示すことができる。
 \begin{figure}[htpb]
 \begin{center}
 \includegraphics[scale=0.2]{images/regex/setstate.pdf}
 \end{center}
-\caption{set state}
+\caption{与えられた正規表現のオートマトンと正規表現木の例}
 \label{fig:set state}
 \end{figure}
 正規表現木を深さ優先探索にて左から辿っていき、文字のノードにそれぞれ状態を番号で割り振りを行う。
 また、状態の振り方は探索した際のメタ文字のノードに沿って割り振りを行う。
 \label{fig:stateasta}
 \end{figure}
 \newpage
+図\ref{fig:stateafasta}は連接 `+' の後の文字に繰返し `*' が接続されている場合の正規表現である。
+受理される文字列の集合は \{a,ab,abb,abb,abb...bb\} である。
+この場合、初期状態に a が入力されると受理状態に遷移する。しかし、受理状態でも b がそれ以降に入力されれば、自分自身に状態遷移する。
+これより、`+' の右ノードに `*' が接続されていたら、`+' の左ノードに接続されている木の最後の状態に受理状態を付け加える。また、`*' に接続されている木の最後の状態にも受理状態を付け加える。
 \begin{figure}[htpb]
 \begin{center}
 \includegraphics[scale=0.2]{images/regex/stateafasta.pdf}
 \end{center}
 \caption{連接の後ろの文字に `*' が接続されているときの状態割当}
 \label{fig:stateafasta}
 \end{figure}
+図\ref{fig:stateasta3}は連接 `+' が連続しており、連接の途中で繰返し `*' が接続されている場合の正規表現である。
+受理される文字列の集合は \{ac,abc,abbc,abbbc,abb...bbc\} である。
+この場合、初期状態に a が入力されると次の状態に遷移する。その状態で b が入力されると自分自身に遷移し、c が入力されると受理状態に遷移する。
+これより、連接中に `*' があれば新しい状態を生成し、その状態を `*' の親ノードのさらに親ノードの右ノードに同じ状態にする。
 \begin{figure}[htpb]
 \begin{center}
 \includegraphics[scale=0.2]{images/regex/stateasta3.pdf}
 \end{center}
 \label{fig:stateasta3}
 \end{figure}
 \newpage
+図\ref{fig:stateselectasta}は選択 `\textbar' がグループ化によって一つの正規表現となり、それ自身が繰り返されている場合の正規表現である。
+受理される文字列の集合は \{c,ac,bc,aabc,abbc,a..ab..bc\} である。
+この場合、初期状態に a か b が入力されると自分自身の状態に遷移する。その状態で c が入力されると受理状態に遷移する。
+これは、選択 `\textbar' と繰返し `*' の状態割当方法の組み合わせにて状態を決定することができる。
+まず `a \textbar b' は同じ状態を割り当て、その親ノードが `*' なので `*' の親の右ノードに同じ状態を割り当てる。
 \begin{figure}[htpb]
 \begin{center}
 \includegraphics[scale=0.2]{images/regex/stateselectasta.pdf}
 \end{center}
 \caption{選択 `\textbar' と繰返し `*' の組み合わせの状態割当}
 \label{fig:stateselectasta}
 \end{figure}
+\newpage
-たどっていきながら、次の状態の遷移先と遷移条件をそれぞれの状態に設定していく。
+以上の規則で正規表現木を辿った時にノードに対して状態を割り振る。
+まとめると、
+\begin{itemize}
-前が `*' でない `+' は新しい状態を作る。
+\item 左子ノードが `*' でない `+' は新しい状態を作る
+\item `\textbar'が親ノードの場合、子ノードの最初の状態は同じ状態。
-`*' があれば、次の状態はその時の先頭の状態か次の状態が終了状態ならば終了状態との組み合わせになる。
+\item `*' があれば、次の状態は `*' に接続されている木の先頭の状態と同じ。次の状態が受理状態なら先頭の状態と受理状態の組み合わせになる。
+\end{itemize}
-割り当てられた状態に沿って charclass の行き先を書き換える
+これにより、正規表現木に状態の割り振りを行ない、入力を行なったら状態が遷移するようにできた。
-書き換えた charclass を merge する
+現在の状態(current state)と入力(input)によって次の状態(next state)が一意に決まっており、それをテーブル化して正規表現をファイルにかける。(図\ref{fig:dfaregex})
-前の部分に * がない + は新しい状態をつくるので、state を切り替えて生成する
+\begin{figure}[htpb]
+\begin{center}
-\subsection{Subset Construction による NFA から DFA の変換と状態遷移リストの生成}
+\includegraphics[scale=0.2]{images/regex/dfaregex.pdf}
+\end{center}
+\caption{dfa}
+\label{fig:dfaregex}
+\end{figure}
+しかし、生成された正規表現木によっては、現在の状態と入力による次の状態が一意に決まらない場合もある。
+図\ref{fig:nfaregex}
+\subsection{Subset Construction による NFA から DFA の変換と状態遷移テーブルの生成}
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.2]{images/regex/dfa.pdf}
+\end{center}
+\caption{dfa}
+\label{fig:dfa}
+\end{figure}
+\begin{figure}[htpb]
+\begin{center}
+\includegraphics[scale=0.2]{images/regex/nfa.pdf}
+\end{center}
+\caption{nfa}
+\label{fig:nfa}
+\end{figure}
 \begin{figure}[htpb]
 \begin{center}
 \includegraphics[scale=0.2]{images/regex/transitiontable.pdf}
 \end{center}
 \caption{Transition Table}
 \label{fig:transitiontable}
 \end{figure}
-現在のステートに含まれる組み合わせ状態をとってくる
-組み合わされた個々の charclass をmerge して新しい charclass をつくり、組み合わせ状態に登録する
-生成した状態は stateArray に格納する
-新しい状態ができなくなったら終了
 \begin{figure}[htpb]
 \begin{center}
 \includegraphics[scale=0.2]{images/regex/CharClassMergePattern.pdf}
 \end{center}
 \caption{2つの Character Class を merge するときの全パターン}
 \end{center}
 \caption{Character Class を二分木で表示}
 \label{fig:ccinsert1}
 \end{figure}
 \begin{figure}[htpb]
 \begin{center}
 \includegraphics[scale=0.2]{images/regex/ccinsert2.pdf}
 \end{center}
 \caption{ある Character Class の二分木に対して、新しい Character Class を insert}
 \end{center}
 \caption{insert 後の Character Class の二分木}
 \label{fig:ccinsertresult}
 \end{figure}
-\begin{figure}[htpb]
-\begin{center}
+現在のステートに含まれる組み合わせ状態をとってくる
-\includegraphics[scale=0.2]{images/regex/dfa.pdf}
-\end{center}
+組み合わされた個々の charclass をmerge して新しい charclass をつくり、組み合わせ状態に登録する
-\caption{dfa}
-\label{fig:dfa}
+生成した状態は stateArray に格納する
-\end{figure}
+新しい状態ができなくなったら終了
-\begin{figure}[htpb]
-\begin{center}
-\includegraphics[scale=0.2]{images/regex/nfa.pdf}
-\end{center}
-\caption{nfa}
-\label{fig:nfa}
-\end{figure}

Mercurial > hg > Papers > 2016 > masa-master

comparison c4.tex @ 34:660c8f2365db