--- a/c4.tex	Wed Feb 10 16:07:26 2016 +0900
+++ b/c4.tex	Wed Feb 10 17:34:17 2016 +0900
@@ -17,6 +17,8 @@
 \end{figure}
 File 分割時に分割された部分の整合性についてはそれぞれの例題にて述べる。
 
+
+
 \section{Word Count}
 Word Count は読み込んだテキストに対して単語数を数える処理である。
 Input Data には分割されたテキストが対応しており、Output Data には単語数と行数を出力する。
@@ -198,6 +200,8 @@
   \end{table}
 \end{tiny}
 
+\newpage
+
 また、これらのメタ文字は数式の四則演算のように結合順位を持っている。それぞれのメタ文字の結合順位は表\ref{table:bond}のようになる。
 
 \begin{tiny}
@@ -233,8 +237,6 @@
 
 文字が読み込まれた場合はノードを生成し、それらが連接された文字は `+' ノードを親ノードとして、左に前の文字、右に後ろの文字が接続される。(図\ref{fig:regexseq})
 
-また、文字列のように連接が連続した場合、連接済みの `+' ノードを左の子ノードとしてさらに `+' ノードで結合していく。(図\ref{fig:regexseq2})
-
 \begin{figure}[htpb]
   \begin{center}
     \includegraphics[scale=0.2]{images/regex/regexseq.pdf}
@@ -243,6 +245,11 @@
   \label{fig:regexseq}
 \end{figure}
 
+\newpage
+
+また、文字列のように連接が連続した場合、連接済みの `+' ノードを左の子ノードとしてさらに `+' ノードで結合していく。
+(図\ref{fig:regexseq2})
+
 \begin{figure}[htpb]
   \begin{center}
     \includegraphics[scale=0.2]{images/regex/regexseq2.pdf}
@@ -253,6 +260,7 @@
 
 選択 `\textbar' が読み込まれた場合、親ノードを `\textbar'として、 `\textbar' の直前の正規表現は左ノード、直後の正規表現は右ノードとした木が構成される。
 `\textbar'は直前と直後の正規表現の関係を表しているので、左右のノードに正規表現の要素を持ったノードとなる。
+(図\ref{fig:regexselect})
 
 \begin{figure}[htpb]
   \begin{center}
@@ -262,8 +270,11 @@
   \label{fig:regexselect}
 \end{figure}
 
+\newpage
+
 繰返し `*' が読み込まれた場合、`*' の直前の正規表現を左の子ノードとした木が生成される。
 また `*' は、`*' の直前の正規表現だけに結合するので、右の子ノードに何かしらのノードが生成されることはない。
+(図\ref{fig:regexasta})
 
 \begin{figure}[htpb]
   \begin{center}
@@ -276,6 +287,7 @@
 
 グループ化 `(' `)' が読み込まれた場合、`(' `)'内をひとかたまりの正規表現として木を構成する。
 構成後さらに文字列が読み込まれれば、上記のルールにしたがって木が構成される。
+(図\ref{fig:regexgroup})
 
 \begin{figure}[htpb]
   \begin{center}
@@ -285,6 +297,7 @@
   \label{fig:regexgroup}
 \end{figure}
 
+\newpage
 正規表現が連接した場合も文字の連接と同様に `+' を親ノードとして接続していく。
 
 \begin{figure}[htpb]
@@ -306,18 +319,11 @@
 オートマトンは、入力に対して状態に対応した処理を行ない結果を出力する仮想的な自動機械である。
 正規表現はオートマトンで表現することができるので、状態と入力(ここでは正規表現)が判れば次はどのような状態になるのか決定される。
 
-\begin{figure}[htpb]
-  \begin{center}
-    \includegraphics[scale=0.2]{images/regex/setstate.pdf}
-  \end{center}
-  \caption{与えられた正規表現のオートマトンと正規表現木の例}
-  \label{fig:set state}
-\end{figure}
+正規表現木を元にオートマトンを構成する際、深さ優先探索にて木を辿っていく。
+辿っていく際にメタ文字のノードが現れた時に一定のルールに沿って文字のノードに状態を割り振っていく。
+ノードに状態を割り振りながら次の状態の遷移先を設定し、オートマトンを構成する。
 
-正規表現木を深さ優先探索にて左から辿っていき、文字のノードにそれぞれ状態を番号で割り振りを行う。
-また、状態の振り方は探索した際のメタ文字のノードに沿って割り振りを行う。
-
-それぞれのメタ文字がどのような状態を割り振るか紹介する。
+それぞれのメタ文字が現れた際、どのような状態を割り振るか以下で紹介する。
 また、番号 1 は初期状態、番号 2 は受理状態を表している。
 
 図\ref{fig:stateseq}は連接 `+' で接続されている場合の正規表現である。
@@ -333,6 +339,8 @@
   \label{fig:stateseq}
 \end{figure}
 
+\newpage
+
 図\ref{fig:stateselect}は選択 `\textbar' で接続されている場合の正規表現である。
 受理される文字列の集合は \{ a, b \}である。
 この場合は a か b が入力されれば受理状態に遷移する。
@@ -346,8 +354,6 @@
   \label{fig:stateselect}
 \end{figure}
 
-\newpage
-
 図\ref{fig:stateselseq}は連接 `+' と選択 `\textbar' の組み合わせで接続されている場合の正規表現である。
 受理される文字列の集合は \{ac,bc\} である。
 この場合、初期状態に a か b が入力されると次の状態に遷移し、遷移した状態に c が入力されると受理状態に遷移する。
@@ -361,6 +367,8 @@
   \label{fig:stateselseq}
 \end{figure}
 
+\newpage
+
 図\ref{fig:stateasta}は連接 `+' の前の文字に繰返し `*' が接続されている場合の正規表現である。
 受理される文字列の集合は \{b,ab,aab,aaab,aa...ab\} である。
 この場合、初期状態に a が入力されると自分自身の状態に遷移する。遷移先を自分自身にすることによって、繰返しを表現することができる。
@@ -369,14 +377,12 @@
 
 \begin{figure}[htpb]
   \begin{center}
-    \includegraphics[scale=0.2]{images/regex/stateasta.pdf}
+    \includegraphics[scale=0.18]{images/regex/stateasta.pdf}
   \end{center}
   \caption{連接の前の文字に `*' が接続されているときの状態割当}
   \label{fig:stateasta}
 \end{figure}
 
-\newpage
-
 図\ref{fig:stateafasta}は連接 `+' の後の文字に繰返し `*' が接続されている場合の正規表現である。
 受理される文字列の集合は \{a,ab,abb,abb,abb...bb\} である。
 この場合、初期状態に a が入力されると受理状態に遷移する。しかし、受理状態でも b がそれ以降に入力されれば、自分自身に状態遷移する。
@@ -384,12 +390,14 @@
 
 \begin{figure}[htpb]
   \begin{center}
-    \includegraphics[scale=0.2]{images/regex/stateafasta.pdf}
+    \includegraphics[scale=0.18]{images/regex/stateafasta.pdf}
   \end{center}
   \caption{連接の後ろの文字に `*' が接続されているときの状態割当}
   \label{fig:stateafasta}
 \end{figure}
 
+\newpage
+
 図\ref{fig:stateasta3}は連接 `+' が連続しており、連接の途中で繰返し `*' が接続されている場合の正規表現である。
 受理される文字列の集合は \{ac,abc,abbc,abbbc,abb...bbc\} である。
 この場合、初期状態に a が入力されると次の状態に遷移する。その状態で b が入力されると自分自身に遷移し、c が入力されると受理状態に遷移する。
@@ -398,13 +406,12 @@
 
 \begin{figure}[htpb]
   \begin{center}
-    \includegraphics[scale=0.2]{images/regex/stateasta3.pdf}
+    \includegraphics[scale=0.15]{images/regex/stateasta3.pdf}
   \end{center}
   \caption{連接中に `*'が接続されているときの状態割当}
   \label{fig:stateasta3}
 \end{figure}
 
-\newpage
 
 図\ref{fig:stateselectasta}は選択 `\textbar' がグループ化によって一つの正規表現となり、それ自身が繰り返されている場合の正規表現である。
 受理される文字列の集合は \{c,ac,bc,aabc,abbc,a..ab..bc\} である。
@@ -412,9 +419,10 @@
 これは、選択 `\textbar' と繰返し `*' の状態割当方法の組み合わせにて状態を決定することができる。
 まず `a \textbar b' は同じ状態を割り当て、その親ノードが `*' なので `*' の親の右ノードに同じ状態を割り当てる。
 
+
 \begin{figure}[htpb]
   \begin{center}
-    \includegraphics[scale=0.2]{images/regex/stateselectasta.pdf}
+    \includegraphics[scale=0.15]{images/regex/stateselectasta.pdf}
   \end{center}
   \caption{選択 `\textbar' と繰返し `*' の組み合わせの状態割当}
   \label{fig:stateselectasta}
@@ -487,8 +495,11 @@
   \label{fig:dfa}
 \end{figure}
 
+\newpage
+
 新しい状態が作られたならば、その状態に入力を加えた際の状態遷移も生成する必要がある。
-その状態遷移を生成するには、新しい状態の状態の組み合わせの遷移先を組み合わせることによって遷移先が決定される。\ref{fig:subset}
+その状態遷移を生成するには、新しい状態の状態の組み合わせの遷移先を組み合わせることによって遷移先が決定される。
+(図\ref{fig:subset})
 
 \begin{figure}[htpb]
   \begin{center}
@@ -498,7 +509,7 @@
   \label{fig:subset}
 \end{figure}
 
-\ref{fig:nfaex}で与えられた NFA を Subset Construction にて DFA に変換すると、図\ref{fig:subsetauto}のようになる。
+図\ref{fig:nfaex}で与えられた NFA を Subset Construction にて DFA に変換すると、図\ref{fig:subsetauto}のようになる。
 この図より、一度 a が入力されたあとは、aか[c-z]の入力と b の入力で状態 4,6 を循環することがわかる。このときの受理状態 2 を含んでいる状態 6 に状態遷移したときこのオートマトンは受理される。
 
 \begin{figure}[htpb]
@@ -509,6 +520,8 @@
   \label{fig:subsetauto}
 \end{figure}
 
+\newpage
+
 文字クラスは正規表現木のノード内では二分木として構成されている。
 例えば、文字クラス[A-Za-z0-9]はノード内では図\ref{fig:cctree}のような二分木で構成されている。
 文字クラスの二分木は、左から ASCII 文字コードの小さい文字を並べていく。
@@ -521,9 +534,10 @@
   \label{fig:cctree}
 \end{figure}
 
+\newpage 
 Subset Construction 時に文字クラス [a-z] と b が merge されている。
 Subset Construction で文字クラスによって入力と遷移先が変化した場合、ノード内の文字クラスもその入力の文字クラスによって文字クラスの二分木も再構築される。
-\ref{fig:cctreeex}
+(図\ref{fig:cctreeex})
 
 \begin{figure}[htpb]
   \begin{center}
@@ -546,14 +560,6 @@
   \label{fig:cctreemerge}
 \end{figure}
 
-\begin{figure}[htpb]
-  \begin{center}
-    \includegraphics[scale=0.2]{images/regex/ccinsertresult.pdf}
-  \end{center}
-  \caption{insert 後の Character Class の二分木}
-  \label{fig:ccinsertresult}
-\end{figure}
-
 on the fly
 subset construction で使わない状態は生成しないで済む
 
@@ -563,10 +569,3 @@
 \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}

Binary file master_paper.pdf has changed

--- a/memo/result.txt	Wed Feb 10 16:07:26 2016 +0900
+++ b/memo/result.txt	Wed Feb 10 17:34:17 2016 +0900
@@ -1,6 +1,46 @@
 Wed Feb 10 11:06:12 JST 2016
 
+./cerium/ceriumGrep -regex '[A-Z][a-zA-Z0-9_]*' -file file/500MB.txt >   25.29s user 0.53s system 100% cpu 25.721 total
 
+[キャッシュ有]
+cpu time
+ 1  25.721
+ 2  15.518
+ 3  12.260
+ 4  11.165
+ 5   9.659
+ 6   9.183
+ 7   8.551
+ 8   8.180
+
+[キャッシュ無 : bread]
+ 1  30.682
+ 2  19.841
+ 3  17.822
+ 4  16.497
+ 5  16.491
+ 6  14.145
+ 7  16.375
+ 8  15.907
+
+[キャッシュ無 : mmap]
+ 1  35.783
+ 2  22.758
+ 3  19.466
+ 4  17.189
+ 5  15.653
+ 6  16.141
+ 7  15.388
+ 8  15.901
+
+[キャッシュ無]
+./regexParser -subset -regex '[A-Z][a-zA-Z0-9_]*' -ts -file file/500MB.txt >   16.06s user 0.22s system 77% cpu 21.139 total
+
+[キャッシュ有]
+./regexParser -subset -regex '[A-Z][a-zA-Z0-9_]*' -ts -file file/500MB.txt >   16.05s user 0.19s system 99% cpu 16.246 total
+
+cgrep -G '[A-Z][a-zA-Z0-9_]*' file/500MB.txt --no-line-umber --no-filename >/dev/null
+測れない(2時間ぐらいぶんまわしてた)
 
 egrep -o '(a|b)*a(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)' file/ab500MB.txt >   113.08s user 0.21s system 99% cpu 1:53.29 total
 12503552