# HG changeset patch
# User Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
# Date 1454751709 -32400
# Node ID e18d8b4b364449d202b8bab657bc722b1d911cdd
# Parent  9e817870489cd5e387e7ac5d9ffdf9a7c8291d43
grep

diff -r 9e817870489c -r e18d8b4b3644 c4.tex
--- a/c4.tex	Sat Feb 06 17:07:04 2016 +0900
+++ b/c4.tex	Sat Feb 06 18:41:49 2016 +0900
@@ -49,6 +49,7 @@
 
 この問題の解決方法として、分割されたファイルの一つ目が文字列で終わり、二つ目のファイルの先頭が文字列で始まった場合はそれぞれの単語数の合計数から 1 引くことにより整合性を取ることができる。
 
+\newpage
 \section{Boyer-Moore String Search}
 
 読み込んだテキストファイルに対してある特定の文字列検索を行う例題として、Boyer-Moore String Search が挙げられる。
@@ -102,7 +103,6 @@
 \label{fig:bmsearchinclude}
 \end{figure}
 
-\newpage
 
 図\ref{fig:bmsearchinclude} は不一致が起こったときの text の文字が pattern に含まれ、その不一致文字が pattern に複数含まれている場合である。
 
@@ -127,7 +127,7 @@
 \end{itemize}
 
 text 分割時に、分割部分で pattern が含まれる場合が存在する。
-その場合は、本来の読み込み部分の text の長さ $L$ に加えて、pattern の長さ $s$ から 1 引いた数だけ多く読みこむように設計することで、この問題を解決することができる。
+その場合は、本来の読み込み部分の text の長さ $L$ に加えて、pattern の長さ $s$ から 1 引いた数だけ多く読みこむように設計することで、正しく結果を算出することができる。
 (図\ref{fig:iodivsuc})
 
 \begin{figure}[htbp]
@@ -138,8 +138,6 @@
 \label{fig:iodivsuc}
 \end{figure}
 
-\newpage
-
 力任せ法と Boyer-Moore String Search を比較してみた。以下に実験環境と結果を示す。(表\ref{table:search})
 
 \begin{itemize}
@@ -168,10 +166,24 @@
 \end{tiny}
 
 Boyer-Moore String Search によって 44\% 改善した。
+
 \section{正規表現}
+(正規表現の簡単な概要をここに)
+
+本研究で実装した正規表現マッチャのアルゴリズムは、
+
+\begin{enumerate}
+\item 与えられた正規表現を構文解析し、正規表現木に変換する。
+\item 正規表現木から非決定性オートマトン(以下、NFA)か決定性オートマトン(以下、DFA)に変換する。
+\item NFA に変換された場合、Subset Construction による NFA から DFA への変換をおこなう。
+\item DFA から状態遷移リストを生成する。
+\item 状態遷移のリストを元に文字列検索を行ない結果を返す。
+\end{enumerate}
+
 \subsection{正規表現木の生成}
-\subsection{正規表現木から NFA の生成}
+\subsection{正規表現木から DFA・NFA の生成}
 \subsection{Subset Construction による NFA から DFA の変換}
+\subsection{DFA から状態遷移リストの生成}
 
 \begin{figure}[htpb]
   \begin{center}
diff -r 9e817870489c -r e18d8b4b3644 master_paper.pdf
Binary file master_paper.pdf has changed