Mercurial > hg > Papers > 2016 > masa-master

changeset 40:e6ca2c4eedeb

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Wed, 10 Feb 2016 03:04:40 +0900
parents 73dd8d6a66b9
children 8f20ee03cf91
files c4.tex c5.tex master_paper.pdf memo/result.txt
diffstat 4 files changed, 20 insertions(+), 27 deletions(-) [+]
line wrap: on
line diff
--- a/c4.tex	Wed Feb 10 02:41:40 2016 +0900
+++ b/c4.tex	Wed Feb 10 03:04:40 2016 +0900
@@ -320,8 +320,6 @@
 それぞれのメタ文字がどのような状態を割り振るか紹介する。
 また、番号 1 は初期状態、番号 2 は受理状態を表している。
 
-\newpage
-
 図\ref{fig:stateseq}は連接 `+' で接続されている場合の正規表現である。
 受理される文字列の集合は \{ ab \} である。
 a が入力されれば別の状態になり、その状態で b が入力されれば受理状態に遷移する。
@@ -441,7 +439,7 @@
   \begin{center}
     \includegraphics[scale=0.2]{images/regex/dfaregex.pdf}
   \end{center}
-  \caption{dfa}
+  \caption{どの状態もある入力を与えたとしても遷移先は一意に決定される}
   \label{fig:dfaregex}
 \end{figure}
 
@@ -452,6 +450,7 @@
 
 これを解決する方法として Subset Construction を適用する。
 
+
 \begin{figure}[htpb]
   \begin{center}
     \includegraphics[scale=0.2]{images/regex/nfaex.pdf}
@@ -460,6 +459,8 @@
   \label{fig:nfaex}
 \end{figure}
 
+\newpage
+
 \subsection{Subset Construction による NFA から DFA の変換}
 Subset Construction は、ある状態から 1 つの入力に対して複数の状態遷移先がある場合、それらの状態 1 つの新しい状態としてまとめ、その新しい状態から新しい遷移先を構成しそれを繰り返す手法である。
 
@@ -496,22 +497,6 @@
   \label{fig:subsetauto}
 \end{figure}
 
-on the fly
-subset construction で使わない状態は生成しないで済む
-
-\subsection{DFA を元にパターンマッチを行う}
-
-\subsection{(Word をノードに含める話)}
-
-IBM stream processing
-\begin{figure}[htpb]
-  \begin{center}
-    \includegraphics[scale=0.2]{images/regex/transitiontable.pdf}
-  \end{center}
-  \caption{Transition Table}
-  \label{fig:transitiontable}
-\end{figure}
-
 \begin{figure}[htpb]
   \begin{center}
     \includegraphics[scale=0.2]{images/regex/CharClassMergePattern.pdf}
@@ -545,13 +530,19 @@
   \label{fig:ccinsertresult}
 \end{figure}
 
+on the fly
+subset construction で使わない状態は生成しないで済む
 
-現在のステートに含まれる組み合わせ状態をとってくる
+\newpage
+\subsection{DFA を元にパターンマッチを行う}
 
-組み合わされた個々の charclass をmerge して新しい charclass をつくり、組み合わせ状態に登録する
+\subsection{(Word をノードに含める話)}
 
-生成した状態は stateArray に格納する
-
-新しい状態ができなくなったら終了
-
-
+IBM stream processing
+\begin{figure}[htpb]
+  \begin{center}
+    \includegraphics[scale=0.2]{images/regex/transitiontable.pdf}
+  \end{center}
+  \caption{Transition Table}
+  \label{fig:transitiontable}
+\end{figure}
--- a/c5.tex	Wed Feb 10 02:41:40 2016 +0900
+++ b/c5.tex	Wed Feb 10 03:04:40 2016 +0900
@@ -1,5 +1,4 @@
 \chapter{評価・考察}
 \section{I/O の測定}
 \section{Word Count}
-\section{Boyer Moore Search}
 \section{正規表現}
Binary file master_paper.pdf has changed
--- a/memo/result.txt	Wed Feb 10 02:41:40 2016 +0900
+++ b/memo/result.txt	Wed Feb 10 03:04:40 2016 +0900
@@ -1,5 +1,8 @@
 Mon Feb  8 17:24:16 JST 2016
 compare cprep egrep ceriumgrep seqsearch
+500MB.txt '[A-Z][a-zA-Z0-9_]*'
+ab500MB.txt '(a|b)*a(a|b)(a|b)'
+
 
 
 time cgrep -G '[A-Z][a-zA-Z0-9_]*' ../../Game/Cerium/example/bm_search/1GB.txt --no-line-umber --no-filename >/dev/null