Mercurial > hg > Papers > 2016 > masa-master

changeset 45:cda3a0bc239d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Wed, 10 Feb 2016 22:27:49 +0900
parents cfaafa209424
children e3b528ecef4a
files c4.tex c5.tex images/image.graffle master_paper.pdf memo/result.txt
diffstat 5 files changed, 981 insertions(+), 15 deletions(-) [+]
line wrap: on
line diff
--- a/c4.tex	Wed Feb 10 18:39:39 2016 +0900
+++ b/c4.tex	Wed Feb 10 22:27:49 2016 +0900
@@ -561,17 +561,27 @@
 \end{figure}
 
 \newpage
-\subsection{DFA を元にパターンマッチを行う}
-NFA、DFA の生成後、読み込んだファイルに対してパターンマッチを行う。今回の例題では、
+\subsection{並列処理時の整合性の取り方}
+正規表現をファイル分割して並列処理をする際、本来マッチングする文章がファイル分割によってマッチングしない場合がある。
+
+図\ref{fig:regexdivide}はその一例である。正規表現 ab*c のマッチングする文字列の集合は {ac,abc,abbc,ab..bc} である。
+分割される前はこの文字列 abbbbc は問題なく正規表現 ab*c にマッチングする。
+
+並列処理時、分割されたファイルに対してパターンマッチさせるので、分割された1つ目のファイルの末尾の abb 、2つ目のファイルの先頭に bbc はマッチングしない。
+本来分割される前はマッチングする文字列だが、この場合見逃してしまう。
+それを解決するために、正規表現にマッチングし始めたファイルの場所を覚えておく。
+そして、1つ目のファイルの末尾が状態遷移の途中で終わっていた場合は、結果を集計する際に再度マッチングし始めた場所から正規表現をマッチングさせる。
 
-\begin{itemize}
-\item DFA を生成後(NFA であれば、Subset Construction後)、逐次に状態と遷移先を照らし合わせる。
-\item DFA をkh
-\end{itemize}
 
-on the fly
-subset construction で使わない状態は生成しないで済む
+\begin{figure}[htpb]
+  \begin{center}
+    \includegraphics[scale=0.3]{images/regex/regexdivide.pdf}
+  \end{center}
+  \caption{分割された部分に正規表現がマッチングする場合の処理}
+  \label{fig:regexdivide}
+\end{figure}
 
+\newpage
 
 \subsection{(Word をノードに含める話)}
 
--- a/c5.tex	Wed Feb 10 18:39:39 2016 +0900
+++ b/c5.tex	Wed Feb 10 22:27:49 2016 +0900
@@ -1,4 +1,10 @@
 \chapter{評価・考察}
+
 \section{I/O の測定}
 \section{Word Count}
 \section{正規表現}
+
+\begin{itemize}
+\item DFA を生成後(NFA であれば、Subset Construction後)、逐次にDFAと照らし合わせる。
+\item 並列処理時に NFA・DFA を分割した Task に配りそれぞれの Taskで 照らし合わせる。照らし合わせた際に NFA だとわかった場合にはその場で Subset Construction し DFA を生成する。
+\end{itemize}
--- a/images/image.graffle	Wed Feb 10 18:39:39 2016 +0900
+++ b/images/image.graffle	Wed Feb 10 22:27:49 2016 +0900
@@ -26,7 +26,7 @@
 	<key>MasterSheets</key>
 	<array/>
 	<key>ModificationDate</key>
-	<string>2016-02-10 06:56:47 +0000</string>
+	<string>2016-02-10 12:49:11 +0000</string>
 	<key>Modifier</key>
 	<string>MasaKoha</string>
 	<key>NotesVisible</key>
@@ -59453,6 +59453,932 @@
 			<key>GraphicsList</key>
 			<array>
 				<dict>
+					<key>Bounds</key>
+					<string>{{1294.7364710322211, 461.41689793228198}, {55, 30}}</string>
+					<key>Class</key>
+					<string>ShapedGraphic</string>
+					<key>FitText</key>
+					<string>YES</string>
+					<key>Flow</key>
+					<string>Resize</string>
+					<key>FontInfo</key>
+					<dict>
+						<key>Color</key>
+						<dict>
+							<key>b</key>
+							<string>0</string>
+							<key>g</key>
+							<string>0</string>
+							<key>r</key>
+							<string>0</string>
+						</dict>
+					</dict>
+					<key>ID</key>
+					<integer>816</integer>
+					<key>Style</key>
+					<dict>
+						<key>fill</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+						<key>shadow</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+						<key>stroke</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+					</dict>
+					<key>Text</key>
+					<dict>
+						<key>Align</key>
+						<integer>0</integer>
+						<key>Text</key>
+						<string>{\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340
+{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;}
+{\colortbl;\red255\green255\blue255;}
+\deftab720
+\pard\pardeftab720\partightenfactor0
+
+\f0\fs32 \cf0 match}</string>
+					</dict>
+					<key>Wrap</key>
+					<string>NO</string>
+				</dict>
+				<dict>
+					<key>Bounds</key>
+					<string>{{1336.535445197454, 357.42771265156341}, {188.50393871819915, 60}}</string>
+					<key>Class</key>
+					<string>ShapedGraphic</string>
+					<key>FitText</key>
+					<string>Vertical</string>
+					<key>Flow</key>
+					<string>Resize</string>
+					<key>FontInfo</key>
+					<dict>
+						<key>Color</key>
+						<dict>
+							<key>b</key>
+							<string>0</string>
+							<key>g</key>
+							<string>0</string>
+							<key>r</key>
+							<string>0</string>
+						</dict>
+						<key>Size</key>
+						<real>11</real>
+					</dict>
+					<key>ID</key>
+					<integer>815</integer>
+					<key>Style</key>
+					<dict>
+						<key>fill</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+						<key>shadow</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+						<key>stroke</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+					</dict>
+					<key>Text</key>
+					<dict>
+						<key>Align</key>
+						<integer>0</integer>
+						<key>Text</key>
+						<string>{\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340
+{\fonttbl\f0\fnil\fcharset128 HiraginoSans-W3;}
+{\colortbl;\red255\green255\blue255;}
+\deftab720
+\pard\pardeftab720\partightenfactor0
+
+\f0\fs22 \cf0 \'8f\'f3\'91\'d4\'91\'4a\'88\'da\'82\'cc\'93\'72\'92\'86\'82\'c5\'8f\'49\'97\'b9\'82\'b5\'82\'c4\'82\'a2\'82\'e9\'8f\'ea\'8d\'87\'82\'cd\'81\'41match \'82\'b5\'8e\'6e\'82\'df\'82\'bd\'82\'c6\'82\'ab\'82\'cc\'90\'e6\'93\'aa\'82\'f0\'8a\'6f\'82\'a6\'82\'c4\'8d\'c4\'93\'78\'83\'7d\'83\'62\'83\'60\'83\'93\'83\'4f\'82\'b3\'82\'b9\'82\'e9\'81\'42}</string>
+					</dict>
+				</dict>
+				<dict>
+					<key>Class</key>
+					<string>LineGraphic</string>
+					<key>FontInfo</key>
+					<dict>
+						<key>Font</key>
+						<string>Helvetica</string>
+						<key>Size</key>
+						<real>12</real>
+					</dict>
+					<key>ID</key>
+					<integer>814</integer>
+					<key>Points</key>
+					<array>
+						<string>{1319.5275710273913, 358.58268041882923}</string>
+						<string>{1319.5275710273913, 410.87468727359089}</string>
+					</array>
+					<key>Style</key>
+					<dict>
+						<key>shadow</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+						<key>stroke</key>
+						<dict>
+							<key>HeadArrow</key>
+							<string>FilledArrow</string>
+							<key>Legacy</key>
+							<false/>
+							<key>LineType</key>
+							<integer>1</integer>
+							<key>TailArrow</key>
+							<string>0</string>
+						</dict>
+					</dict>
+				</dict>
+				<dict>
+					<key>Class</key>
+					<string>Group</string>
+					<key>Graphics</key>
+					<array>
+						<dict>
+							<key>Bounds</key>
+							<string>{{1286.9057624222426, 428.03149994658668}, {70.866142375262825, 30}}</string>
+							<key>Class</key>
+							<string>ShapedGraphic</string>
+							<key>FitText</key>
+							<string>Vertical</string>
+							<key>Flow</key>
+							<string>Resize</string>
+							<key>FontInfo</key>
+							<dict>
+								<key>Color</key>
+								<dict>
+									<key>b</key>
+									<string>0</string>
+									<key>g</key>
+									<string>0</string>
+									<key>r</key>
+									<string>0</string>
+								</dict>
+							</dict>
+							<key>ID</key>
+							<integer>812</integer>
+							<key>Style</key>
+							<dict>
+								<key>fill</key>
+								<dict>
+									<key>Draws</key>
+									<string>NO</string>
+								</dict>
+								<key>shadow</key>
+								<dict>
+									<key>Draws</key>
+									<string>NO</string>
+								</dict>
+								<key>stroke</key>
+								<dict>
+									<key>Draws</key>
+									<string>NO</string>
+								</dict>
+							</dict>
+							<key>Text</key>
+							<dict>
+								<key>Text</key>
+								<string>{\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340
+{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;}
+{\colortbl;\red255\green255\blue255;}
+\deftab720
+\pard\pardeftab720\qc\partightenfactor0
+
+\f0\fs32 \cf0 abbbbc}</string>
+							</dict>
+						</dict>
+						<dict>
+							<key>Bounds</key>
+							<string>{{1274.1732399072239, 431.05879826062301}, {96.331187405300398, 23.945403371927398}}</string>
+							<key>Class</key>
+							<string>ShapedGraphic</string>
+							<key>ID</key>
+							<integer>813</integer>
+							<key>Style</key>
+							<dict>
+								<key>shadow</key>
+								<dict>
+									<key>Draws</key>
+									<string>NO</string>
+								</dict>
+							</dict>
+						</dict>
+					</array>
+					<key>ID</key>
+					<integer>811</integer>
+				</dict>
+				<dict>
+					<key>Class</key>
+					<string>LineGraphic</string>
+					<key>FontInfo</key>
+					<dict>
+						<key>Font</key>
+						<string>Helvetica</string>
+						<key>Size</key>
+						<real>12</real>
+					</dict>
+					<key>Head</key>
+					<dict>
+						<key>ID</key>
+						<integer>800</integer>
+					</dict>
+					<key>ID</key>
+					<integer>806</integer>
+					<key>Points</key>
+					<array>
+						<string>{1424.40946174278, 210.50393871819878}</string>
+						<string>{1354.4606422150227, 271.46582568488111}</string>
+					</array>
+					<key>Style</key>
+					<dict>
+						<key>shadow</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+						<key>stroke</key>
+						<dict>
+							<key>HeadArrow</key>
+							<string>FilledArrow</string>
+							<key>Legacy</key>
+							<false/>
+							<key>LineType</key>
+							<integer>1</integer>
+							<key>TailArrow</key>
+							<string>0</string>
+						</dict>
+					</dict>
+					<key>Tail</key>
+					<dict>
+						<key>ID</key>
+						<integer>804</integer>
+					</dict>
+				</dict>
+				<dict>
+					<key>Class</key>
+					<string>LineGraphic</string>
+					<key>FontInfo</key>
+					<dict>
+						<key>Font</key>
+						<string>Helvetica</string>
+						<key>Size</key>
+						<real>12</real>
+					</dict>
+					<key>Head</key>
+					<dict>
+						<key>ID</key>
+						<integer>799</integer>
+					</dict>
+					<key>ID</key>
+					<integer>805</integer>
+					<key>Points</key>
+					<array>
+						<string>{1247.2441058046234, 214.25197017568303}</string>
+						<string>{1299.1850511623179, 271.46582568488111}</string>
+					</array>
+					<key>Style</key>
+					<dict>
+						<key>shadow</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+						<key>stroke</key>
+						<dict>
+							<key>HeadArrow</key>
+							<string>FilledArrow</string>
+							<key>Legacy</key>
+							<false/>
+							<key>LineType</key>
+							<integer>1</integer>
+							<key>TailArrow</key>
+							<string>0</string>
+						</dict>
+					</dict>
+					<key>Tail</key>
+					<dict>
+						<key>ID</key>
+						<integer>803</integer>
+					</dict>
+				</dict>
+				<dict>
+					<key>Bounds</key>
+					<string>{{1340.7874137399701, 188.50393871819878}, {167.24409600561989, 44}}</string>
+					<key>Class</key>
+					<string>ShapedGraphic</string>
+					<key>FitText</key>
+					<string>Vertical</string>
+					<key>Flow</key>
+					<string>Resize</string>
+					<key>FontInfo</key>
+					<dict>
+						<key>Color</key>
+						<dict>
+							<key>b</key>
+							<string>0</string>
+							<key>g</key>
+							<string>0</string>
+							<key>r</key>
+							<string>0</string>
+						</dict>
+						<key>Size</key>
+						<real>11</real>
+					</dict>
+					<key>ID</key>
+					<integer>804</integer>
+					<key>Style</key>
+					<dict>
+						<key>fill</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+						<key>shadow</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+						<key>stroke</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+					</dict>
+					<key>Text</key>
+					<dict>
+						<key>Align</key>
+						<integer>0</integer>
+						<key>Text</key>
+						<string>{\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340
+{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;\f1\fnil\fcharset128 HiraginoSans-W3;}
+{\colortbl;\red255\green255\blue255;}
+\deftab720
+\pard\pardeftab720\partightenfactor0
+
+\f0\fs22 \cf0 bbc 
+\f1 \'82\'b5\'82\'a9\'93\'c7\'82\'df\'82\'c8\'82\'a2\'82\'cc\'82\'c5\'81\'41\
+\'90\'b3\'8b\'4b\'95\'5c\'8c\'bb\'82\'c9\'82\'cdmatch \'82\'b5\'82\'c8\'82\'a2}</string>
+					</dict>
+				</dict>
+				<dict>
+					<key>Bounds</key>
+					<string>{{1159.3700892592976, 184.25197017568303}, {175.74803309065146, 60}}</string>
+					<key>Class</key>
+					<string>ShapedGraphic</string>
+					<key>FitText</key>
+					<string>Vertical</string>
+					<key>Flow</key>
+					<string>Resize</string>
+					<key>FontInfo</key>
+					<dict>
+						<key>Color</key>
+						<dict>
+							<key>b</key>
+							<string>0</string>
+							<key>g</key>
+							<string>0</string>
+							<key>r</key>
+							<string>0</string>
+						</dict>
+						<key>Size</key>
+						<real>11</real>
+					</dict>
+					<key>ID</key>
+					<integer>803</integer>
+					<key>Style</key>
+					<dict>
+						<key>fill</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+						<key>shadow</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+						<key>stroke</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+					</dict>
+					<key>Text</key>
+					<dict>
+						<key>Align</key>
+						<integer>0</integer>
+						<key>Text</key>
+						<string>{\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340
+{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;\f1\fnil\fcharset128 HiraginoSans-W3;}
+{\colortbl;\red255\green255\blue255;}
+\deftab720
+\pard\pardeftab720\partightenfactor0
+
+\f0\fs22 \cf0 abb 
+\f1 \'82\'b5\'82\'a9\'93\'c7\'82\'df\'82\'c8\'82\'a2\'82\'cc\'82\'c5\
+\'90\'b3\'8b\'4b\'95\'5c\'8c\'bb\'82\'c9\'82\'cdmatch \'82\'b5\'82\'c8\'82\'a2\'82\'aa\'81\'41\'8f\'f3\'91\'d4\'91\'4a\'88\'da\'82\'cc\'93\'72\'92\'86\'82\'c5\'8f\'49\'97\'b9\'82\'b5\'82\'c4\'82\'a2\'82\'e9}</string>
+					</dict>
+				</dict>
+				<dict>
+					<key>Bounds</key>
+					<string>{{1375.2204849276015, 283.43852737084484}, {82, 30}}</string>
+					<key>Class</key>
+					<string>ShapedGraphic</string>
+					<key>FitText</key>
+					<string>YES</string>
+					<key>Flow</key>
+					<string>Resize</string>
+					<key>FontInfo</key>
+					<dict>
+						<key>Color</key>
+						<dict>
+							<key>b</key>
+							<string>0</string>
+							<key>g</key>
+							<string>0</string>
+							<key>r</key>
+							<string>0</string>
+						</dict>
+					</dict>
+					<key>ID</key>
+					<integer>802</integer>
+					<key>Style</key>
+					<dict>
+						<key>fill</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+						<key>shadow</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+						<key>stroke</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+					</dict>
+					<key>Text</key>
+					<dict>
+						<key>Align</key>
+						<integer>0</integer>
+						<key>Text</key>
+						<string>{\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340
+{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;}
+{\colortbl;\red255\green255\blue255;}
+\deftab720
+\pard\pardeftab720\partightenfactor0
+
+\f0\fs32 \cf0  no match}</string>
+					</dict>
+					<key>Wrap</key>
+					<string>NO</string>
+				</dict>
+				<dict>
+					<key>Bounds</key>
+					<string>{{1192.0708773295707, 283.43852737084484}, {82, 30}}</string>
+					<key>Class</key>
+					<string>ShapedGraphic</string>
+					<key>FitText</key>
+					<string>YES</string>
+					<key>Flow</key>
+					<string>Resize</string>
+					<key>FontInfo</key>
+					<dict>
+						<key>Color</key>
+						<dict>
+							<key>b</key>
+							<string>0</string>
+							<key>g</key>
+							<string>0</string>
+							<key>r</key>
+							<string>0</string>
+						</dict>
+					</dict>
+					<key>ID</key>
+					<integer>801</integer>
+					<key>Style</key>
+					<dict>
+						<key>fill</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+						<key>shadow</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+						<key>stroke</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+					</dict>
+					<key>Text</key>
+					<dict>
+						<key>Align</key>
+						<integer>0</integer>
+						<key>Text</key>
+						<string>{\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340
+{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;}
+{\colortbl;\red255\green255\blue255;}
+\deftab720
+\pard\pardeftab720\partightenfactor0
+
+\f0\fs32 \cf0  no match}</string>
+					</dict>
+					<key>Wrap</key>
+					<string>NO</string>
+				</dict>
+				<dict>
+					<key>Bounds</key>
+					<string>{{1333.7007995024439, 256.46582568488111}, {41.519685425157604, 30}}</string>
+					<key>Class</key>
+					<string>ShapedGraphic</string>
+					<key>FitText</key>
+					<string>Vertical</string>
+					<key>Flow</key>
+					<string>Resize</string>
+					<key>FontInfo</key>
+					<dict>
+						<key>Color</key>
+						<dict>
+							<key>b</key>
+							<string>0</string>
+							<key>g</key>
+							<string>0</string>
+							<key>r</key>
+							<string>0</string>
+						</dict>
+					</dict>
+					<key>ID</key>
+					<integer>800</integer>
+					<key>Style</key>
+					<dict>
+						<key>fill</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+						<key>shadow</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+						<key>stroke</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+					</dict>
+					<key>Text</key>
+					<dict>
+						<key>Align</key>
+						<integer>0</integer>
+						<key>Text</key>
+						<string>{\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340
+{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;}
+{\colortbl;\red255\green255\blue255;}
+\deftab720
+\pard\pardeftab720\partightenfactor0
+
+\f0\fs32 \cf0 bbc}</string>
+					</dict>
+				</dict>
+				<dict>
+					<key>Bounds</key>
+					<string>{{1278.4252084497391, 256.46582568488111}, {41.519685425157604, 30}}</string>
+					<key>Class</key>
+					<string>ShapedGraphic</string>
+					<key>FitText</key>
+					<string>Vertical</string>
+					<key>Flow</key>
+					<string>Resize</string>
+					<key>FontInfo</key>
+					<dict>
+						<key>Color</key>
+						<dict>
+							<key>b</key>
+							<string>0</string>
+							<key>g</key>
+							<string>0</string>
+							<key>r</key>
+							<string>0</string>
+						</dict>
+					</dict>
+					<key>ID</key>
+					<integer>799</integer>
+					<key>Style</key>
+					<dict>
+						<key>fill</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+						<key>shadow</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+						<key>stroke</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+					</dict>
+					<key>Text</key>
+					<dict>
+						<key>Align</key>
+						<integer>0</integer>
+						<key>Text</key>
+						<string>{\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340
+{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;}
+{\colortbl;\red255\green255\blue255;}
+\deftab720
+\pard\pardeftab720\partightenfactor0
+
+\f0\fs32 \cf0 abb}</string>
+					</dict>
+				</dict>
+				<dict>
+					<key>Bounds</key>
+					<string>{{1148.0315064792558, 143.14960759803066}, {133.22834766549408, 36}}</string>
+					<key>Class</key>
+					<string>ShapedGraphic</string>
+					<key>FitText</key>
+					<string>Vertical</string>
+					<key>Flow</key>
+					<string>Resize</string>
+					<key>FontInfo</key>
+					<dict>
+						<key>Color</key>
+						<dict>
+							<key>b</key>
+							<string>0</string>
+							<key>g</key>
+							<string>0</string>
+							<key>r</key>
+							<string>0</string>
+						</dict>
+					</dict>
+					<key>ID</key>
+					<integer>798</integer>
+					<key>Style</key>
+					<dict>
+						<key>fill</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+						<key>shadow</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+						<key>stroke</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+					</dict>
+					<key>Text</key>
+					<dict>
+						<key>Align</key>
+						<integer>0</integer>
+						<key>Text</key>
+						<string>{\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340
+{\fonttbl\f0\fnil\fcharset128 HiraginoSans-W3;\f1\fnil\fcharset0 HelveticaNeue;}
+{\colortbl;\red255\green255\blue255;}
+\deftab720
+\pard\pardeftab720\partightenfactor0
+
+\f0\fs32 \cf0 \'90\'b3\'8b\'4b\'95\'5c\'8c\'bb : 
+\f1 ab*c}</string>
+					</dict>
+				</dict>
+				<dict>
+					<key>Class</key>
+					<string>LineGraphic</string>
+					<key>FontInfo</key>
+					<dict>
+						<key>Font</key>
+						<string>Helvetica</string>
+						<key>Size</key>
+						<real>12</real>
+					</dict>
+					<key>ID</key>
+					<integer>797</integer>
+					<key>Points</key>
+					<array>
+						<string>{1369.5044273125243, 252.43255189159709}</string>
+						<string>{1369.5044273125243, 283.43852737084484}</string>
+					</array>
+					<key>Style</key>
+					<dict>
+						<key>shadow</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+						<key>stroke</key>
+						<dict>
+							<key>HeadArrow</key>
+							<string>0</string>
+							<key>Legacy</key>
+							<false/>
+							<key>LineType</key>
+							<integer>1</integer>
+							<key>Pattern</key>
+							<integer>1</integer>
+							<key>TailArrow</key>
+							<string>0</string>
+						</dict>
+					</dict>
+				</dict>
+				<dict>
+					<key>Class</key>
+					<string>LineGraphic</string>
+					<key>FontInfo</key>
+					<dict>
+						<key>Font</key>
+						<string>Helvetica</string>
+						<key>Size</key>
+						<real>12</real>
+					</dict>
+					<key>ID</key>
+					<integer>795</integer>
+					<key>Points</key>
+					<array>
+						<string>{1274.1732399072232, 252.43255189159714}</string>
+						<string>{1274.1732399072232, 283.43852737084484}</string>
+					</array>
+					<key>Style</key>
+					<dict>
+						<key>shadow</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+						<key>stroke</key>
+						<dict>
+							<key>HeadArrow</key>
+							<string>0</string>
+							<key>Legacy</key>
+							<false/>
+							<key>LineType</key>
+							<integer>1</integer>
+							<key>Pattern</key>
+							<integer>1</integer>
+							<key>TailArrow</key>
+							<string>0</string>
+						</dict>
+					</dict>
+				</dict>
+				<dict>
+					<key>Bounds</key>
+					<string>{{1274.1732399072232, 310.42771265156341}, {107.66977018534249, 47}}</string>
+					<key>Class</key>
+					<string>ShapedGraphic</string>
+					<key>FitText</key>
+					<string>Vertical</string>
+					<key>Flow</key>
+					<string>Resize</string>
+					<key>FontInfo</key>
+					<dict>
+						<key>Color</key>
+						<dict>
+							<key>b</key>
+							<string>0</string>
+							<key>g</key>
+							<string>0</string>
+							<key>r</key>
+							<string>0</string>
+						</dict>
+						<key>Size</key>
+						<real>12</real>
+					</dict>
+					<key>ID</key>
+					<integer>793</integer>
+					<key>Style</key>
+					<dict>
+						<key>fill</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+						<key>shadow</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+						<key>stroke</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+					</dict>
+					<key>Text</key>
+					<dict>
+						<key>Align</key>
+						<integer>0</integer>
+						<key>Text</key>
+						<string>{\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340
+{\fonttbl\f0\fnil\fcharset128 HiraginoSans-W3;}
+{\colortbl;\red255\green255\blue255;}
+\deftab720
+\pard\pardeftab720\partightenfactor0
+
+\f0\fs24 \cf0 \'83\'7d\'83\'62\'83\'60\'82\'b7\'82\'e9\'95\'94\'95\'aa\'82\'aa\
+\'95\'aa\'8a\'84\'82\'b3\'82\'ea\'82\'c4\'82\'a2\'82\'e9}</string>
+					</dict>
+				</dict>
+				<dict>
+					<key>Class</key>
+					<string>LineGraphic</string>
+					<key>FontInfo</key>
+					<dict>
+						<key>Font</key>
+						<string>Helvetica</string>
+						<key>Size</key>
+						<real>12</real>
+					</dict>
+					<key>ID</key>
+					<integer>792</integer>
+					<key>Points</key>
+					<array>
+						<string>{1274.0708773295707, 306.14173506113485}</string>
+						<string>{1370.4020647348714, 306.14173506113485}</string>
+					</array>
+					<key>Style</key>
+					<dict>
+						<key>shadow</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+						<key>stroke</key>
+						<dict>
+							<key>HeadArrow</key>
+							<string>DimensionArrow</string>
+							<key>Legacy</key>
+							<false/>
+							<key>LineType</key>
+							<integer>1</integer>
+							<key>TailArrow</key>
+							<string>DimensionArrow</string>
+						</dict>
+					</dict>
+				</dict>
+				<dict>
+					<key>Bounds</key>
+					<string>{{1333.7007995024439, 259.49312399891738}, {144.56693044553572, 23.945403371927398}}</string>
+					<key>Class</key>
+					<string>ShapedGraphic</string>
+					<key>ID</key>
+					<integer>788</integer>
+					<key>Style</key>
+					<dict>
+						<key>shadow</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+					</dict>
+				</dict>
+				<dict>
+					<key>Bounds</key>
+					<string>{{1166.4567034968238, 259.49312399891738}, {150.23622183555699, 23.945403371927398}}</string>
+					<key>Class</key>
+					<string>ShapedGraphic</string>
+					<key>ID</key>
+					<integer>1</integer>
+					<key>Style</key>
+					<dict>
+						<key>shadow</key>
+						<dict>
+							<key>Draws</key>
+							<string>NO</string>
+						</dict>
+					</dict>
+				</dict>
+				<dict>
 					<key>Class</key>
 					<string>LineGraphic</string>
 					<key>FontInfo</key>
@@ -63567,9 +64493,9 @@
 		<key>TopSlabHeight</key>
 		<real>682</real>
 		<key>VisibleRegion</key>
-		<string>{{0, -295}, {1318.9655172413793, 1374.1379310344828}}</string>
+		<string>{{1053.8461925010017, 70.979023582516049}, {534.96505458743627, 557.34267778586491}}</string>
 		<key>Zoom</key>
-		<real>0.57999999999999996</real>
+		<real>1.4299999475479126</real>
 		<key>ZoomValues</key>
 		<array>
 			<array>
@@ -63654,8 +64580,8 @@
 			</array>
 			<array>
 				<string>cctree</string>
-				<real>0.57999999999999996</real>
-				<real>0.59000000000000008</real>
+				<real>1.4299999475479126</real>
+				<real>1.4300000000000002</real>
 			</array>
 		</array>
 	</dict>
Binary file master_paper.pdf has changed
--- a/memo/result.txt	Wed Feb 10 18:39:39 2016 +0900
+++ b/memo/result.txt	Wed Feb 10 22:27:49 2016 +0900
@@ -1,10 +1,29 @@
 Wed Feb 10 11:06:12 JST 2016
 
-egrep -o '(a|b)*a(a|b)(a|b)' file/ab500MB.txt > /dev/null
+cpu 6
+
+./cerium/ceriumGrep -regex '(a|b)*a(a|b)(a|b)' -br -file file/ab500MB.txt -cp  32.90s user 1.28s system 99% cpu 34.514 total
+cache 17.625
+
+./cerium/ceriumGrep -regex '(a|b)*a(a|b)(a|b)(a|b)' -br -file file/ab500MB.tx  31.77s user 1.18s system 109% cpu 30.167 total
+cache 19.153
+
+./cerium/ceriumGrep -regex '(a|b)*a(a|b)(a|b)(a|b)(a|b)' -br -file  -cpu 6 >   31.82s user 1.17s system 113% cpu 29.160 total
+17.193
+
+./cerium/ceriumGrep -regex '(a|b)*a(a|b)(a|b)(a|b)(a|b)(a|b)' -br -file  -cpu  33.98s user 1.36s system 97% cpu 36.390 total
+19.701
+
 82.88s user 0.20s system 99% cpu 1:23.09 total
 egrep 83.09
 
-./cerium/ceriumGrep -regex '(a|b)*a(a|b)(a|b)' -file file/ab500MB.txt -cpu 8   32.82s user 0.85s system 202% cpu 16.595 total
+状態数を増やしてみたけど、速度には影響を与えない??
+
+egrep -o '(a|b)*a(a|b)(a|b)' file/ab500MB.txt > /dev/null
+
+./cerium/ceriumGrep -regex '(a|b)*a(a|b)(a|b)' -file file/ab500MB.txt -cpu 6   32.82s user 0.85s system 202% cpu 16.595 total
+
+
 [キャッシュ有]
 cpu time
  1 29.053
@@ -28,6 +47,10 @@
 
 ./cerium/ceriumGrep -regex '[A-Z][a-zA-Z0-9_]*' -file file/500MB.txt >   25.29s user 0.53s system 100% cpu 25.721 total
 
+egrep -o '[A-Z][a-zA-Z0-9_]*' 500MB.txt > /dev/null
+56.34s user 0.16s system 99% cpu 56.506 total
+line:13260580
+
 [キャッシュ有]
 cpu time
  1  25.721
@@ -39,6 +62,7 @@
  7   8.551
  8   8.180
 
+egrep 56.506
 [キャッシュ無 : bread]
  1  30.682
  2  19.841