changeset 71:c01a514d33f7

add bm_search
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Wed, 17 Feb 2016 00:07:04 +0900
parents f8c66cefe63e
children 69742d52fd7d
files paper/c4.tex paper/c5.tex paper/c6.tex paper/master_paper.bib paper/master_paper.pdf paper/memo/data.txt
diffstat 6 files changed, 363 insertions(+), 53 deletions(-) [+]
line wrap: on
line diff
--- a/paper/c4.tex	Tue Feb 16 18:17:55 2016 +0900
+++ b/paper/c4.tex	Wed Feb 17 00:07:04 2016 +0900
@@ -202,7 +202,98 @@
 }
 \end{lstlisting}
 
+\section{Boyer-Moore String Search}
+
+読み込んだテキストファイルに対してある特定の文字列検索を行う例題として、Boyer-Moore String Search が挙げられる。
+Boyer-Moore String Search は 1977 年に Robert S. Boyer と J Strother Moore が開発した効率的なアルゴリズムである。\cite{bmsearch}
+
+以下、テキストファイルに含まれている文字列を text、検索する文字列を pattern と定義する。
+
+原始的な検索アルゴリズムとして力任せ法が挙げられる。
+力任せ法は text と pattern を先頭から比較していき、
+pattern と一致しなければ pattern を1文字分だけ後ろにずらして再度比較をしていくアルゴリズムである。
+text の先頭から pattern の先頭を比較していき、文字の不一致が起きた場合は pattern を後ろに 1 つだけずらして再比較を行う。
+(図\ref{fig:bruteforth})
+
+\begin{figure}[htbp]
+\begin{center}
+\includegraphics[width=0.7\textwidth]{images/example/bruteforth.pdf}
+\end{center}
+\caption{力まかせ法}
+\label{fig:bruteforth}
+\end{figure}
+
 \newpage
+このアルゴリズムは実装が容易であるが、 text と pattern の文字数が大きくなるにつれて、比較回数も膨大になる恐れがある。
+text の長さを $n$、pattern の長さを $m$とすると、力任せ法の最悪計算時間は $O(nm)$ となる。
+
+力任せ法の比較回数を改善したアルゴリズムが Boyer-Moore String Search である。
+力任せ法との大きな違いとして、text と pattern を先頭から比較するのではなく、 pattern の末尾から比較していくことである。
+さらに不一致が起こった場合は、その不一致が起こった text の文字で再度比較する場所が決まる。
+
+図\ref{fig:bmsearchthink}は、text と pattern の末尾が不一致を起こして、そのときの text が pattern に含まれていない場合である。
+不一致した text の文字が pattern に含まれていない場合は、pattern を比較する場所に match することはないので、pattern の長さ分だけ後ろにずらすことができる。
+
+\begin{figure}[htbp]
+\begin{center}
+\includegraphics[width=0.7\textwidth]{images/example/bmsearchthink.pdf}
+\end{center}
+\caption{pattern に含まれていない文字で不一致になった場合}
+\label{fig:bmsearchthink}
+\end{figure}
+
+\newpage
+
+図\ref{fig:bmsearchinclude} は不一致が起こったときの text の文字が pattern に含まれている場合である。
+この場合は pattern を後ろに2つずらすと text と pattern が一致する。
+
+不一致したときの text の文字が pattern に含まれていた場合の後ろにずらす量は、pattern の長さから含まれていた文字が pattern の何文字目に含まれているかを引いた値となる。
+この場合、pattern の文字列の長さは 3 で text で不一致を起こした文字 `a' が pattern の 1 文字目に含まれているので、2 文字分だけ後ろにずらすことができる。
+
+\begin{figure}[htbp]
+\begin{center}
+\includegraphics[width=0.7\textwidth]{images/example/bmsearchinlucde.pdf}
+\end{center}
+\caption{pattern に含まれている文字で不一致になった場合}
+\label{fig:bmsearchinclude}
+\end{figure}
+
+\newpage
+
+図\ref{fig:bmsearchsame} は不一致が起こったときの text の文字が pattern に含まれ、その不一致文字が pattern に複数含まれている場合である。
+
+pattern の長さは 4 で、不一致を起こした時の text の文字 `a' は pattern の 1 番目と 3 番目に含まれている。
+pattern を後ろにずらす量は 1 か 3 となる。
+ずらす量を 3 にすると、pattern が含まれている text を見逃す可能性があるので、この場合 `a' で不一致したときは最小の値 1 をとる。
+
+\begin{figure}[htbp]
+\begin{center}
+\includegraphics[width=0.7\textwidth]{images/example/bmsearchsame.pdf}
+\end{center}
+\caption{pattern に同じ文字が複数入り、その文字で不一致になった場合}
+\label{fig:bmsearchsame}
+\end{figure}
+
+pattern と text と不一致時の処理をまとめると、
+
+\begin{itemize}
+\item pattern に含まれていない文字で不一致した場合は、 pattern の長さだけ後ろにずらす。
+\item pattern に含まれている文字の場合は、pattern の長さから pattern に含まれている文字の位置を引いた数だけ後ろにずらす。
+\item pattern に含まれている文字でその文字が pattern に複数含まれている場合は後ろにずらす量も複数現れる。その中の最小の値だけ後ろにずらす。
+\end{itemize}
+
+text 分割時に、分割部分で pattern が含まれる場合が存在する。
+その場合は、本来の読み込み部分の text の長さ $L$ に加えて、pattern の長さ $s$ から 1 引いた数だけ多く読みこむように設計することで、正しく結果を算出することができる。
+(図\ref{fig:iodivsuc})
+
+\begin{figure}[htbp]
+\begin{center}
+\includegraphics[width=1.0\textwidth]{images/example/iodivsuc.pdf}
+\end{center}
+\caption{分割周りの処理}
+\label{fig:iodivsuc}
+\end{figure}
+
 
 \section{正規表現}
 正規表現は文字列のパターンを表現するための方法である。
--- a/paper/c5.tex	Tue Feb 16 18:17:55 2016 +0900
+++ b/paper/c5.tex	Wed Feb 17 00:07:04 2016 +0900
@@ -88,17 +88,18 @@
 \begin{tiny}
   \begin{table}[ht]
     \begin{center}
-      \begin{tabular}[t]{|c|r|r|r|}
+        正規表現 '[A-Z][A-Za-z0-9]*s'
+      \begin{tabular}[t]{|c|r|r|r|r|}
         \hline
-        実行方式/File Size(Match Num) & 500MB(536万) & 1GB(1072万) \\
-        \hline
-        CGrep & 20.62 & 40.10\\
+        実行方式/File Size(Match Num)    & 50MB(54万) & 100MB(107万) & 500MB(536万) & 1GB(1072万) \\
         \hline
-        CeriumGrep(CPU 12) mmap  & 18.00 & 26.96\\
+        CGrep                            & 4.51 &  9.42 & 20.62 & 40.10\\
+        \hline
+        CeriumGrep(CPU 12) mmap          & 8.97 & 10.79 & 18.00 & 29.16\\
         \hline
-        CeriumGrep(CPU 12) bread & 12.48 & 21.14\\
+        CeriumGrep(CPU 12) bread         & 7.75 & 10.49 & 15.76 & 26.83\\
         \hline
-        egrep & 59.51 & 119.23\\
+        egrep                            & 6.42 & 12.80 & 59.51 & 119.23\\
         \hline
       \end{tabular}
   \caption{ファイルサイズを変化させた各 grep の結果}
@@ -119,13 +120,13 @@
         \hline
         実行方式 & ファイル読み込み有 & ファイル読み込み無\\
         \hline
-        CGrep & 21.171 & 16.150\\
+        CGrep & 21.17 & 16.15\\
         \hline
-        CeriumGrep(CPU 2) & 27.061 & 15.401\\
+        CeriumGrep(CPU 2) & 27.06 & 15.40\\
         \hline
-        CeriumGrep(CPU 12) & 12.48 & 7.386\\
+        CeriumGrep(CPU 12) & 12.48 & 7.39\\
         \hline
-        egrep & 59.51 & --- \\
+        egrep & 59.51 & 59.51 \\
         \hline
       \end{tabular}
       \caption{ファイル読み込み有りと無しを変化させた各 grep の結果}
@@ -136,7 +137,7 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 表\ref{table:abab}
-aとb が多く含まれている約500MB(単語数約2300万)のファイルに対して、正規表現の状態数を変化させてみた。
+aとb が多く含まれている約500MB(単語数約2400万)のファイルに対して、正規表現の状態数を変化させてみた。
 これは読み込みを含んでいる結果で、CeriumGrep のファイル読み込みは Blocked Read、CPU 数 12 にて実行した。
 
 \begin{tiny}
@@ -146,13 +147,13 @@
         \hline
         正規表現 & マッチ数 & CeriumGrep time (s) & egrep time(s)\\
         \hline
-        '(a \textbar b)*a(a \textbar b)(a \textbar b)'                  & 約1950万  & 38.67 &  86.66 \\
+        '(a \textbar b)*a(a \textbar b)(a \textbar b)z'                                               & 約10万 & 26.58 &  70.11 \\
         \hline
-        '(a \textbar b)*a(a \textbar b)(a \textbar b)(a \textbar b)'             & 約1640万  & 38.72 &  94.25 \\
+        '(a \textbar b)*a(a \textbar b)(a \textbar b)(a \textbar b)z'                                 & 約10000 & 27.89 &  76.78 \\
         \hline
-        '(a \textbar b)*a(a \textbar b)(a \textbar b)(a \textbar b)(a \textbar b)'        & 約1640万  & 39.59 & 100.98 \\
+        '(a \textbar b)*a(a \textbar b)(a \textbar b)(a \textbar b)(a \textbar b)z'                   &  約7000 &  & 81.88 \\
         \hline
-        '(a \textbar b)*a(a \textbar b)(a \textbar b)(a \textbar b)(a \textbar b)(a \textbar b)'   & 約1550万 & 38.68 & 104.82 \\
+        '(a \textbar b)*a(a \textbar b)(a \textbar b)(a \textbar b)(a \textbar b)(a \textbar b)z'     &  約4000 &  & 86.93 \\
         \hline
       \end{tabular}
   \caption{正規表現の状態数を増やした Grep の結果}
@@ -173,13 +174,13 @@
         \hline
         実行方式/File Size(Match Num) & time (s)\\
         \hline
-        CGrep & 27.130\\
+        CGrep & 27.13\\
         \hline
-        CeriumGrep(CPU 12) mmap  & 21.576\\
+        CeriumGrep(CPU 12) mmap  & 21.58\\
         \hline
-        CeriumGrep(CPU 12) bread & 19.986\\
+        CeriumGrep(CPU 12) bread & 19.99\\
         \hline
-        egrep & 28.332\\
+        egrep & 28.33\\
         \hline
       \end{tabular}
   \caption{全くマッチングしないパターンを grep した結果}
@@ -187,30 +188,3 @@
     \end{center}
   \end{table}
 \end{tiny}
-
-% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-% 
-% 表\ref{table:abab}
-% 
-% \begin{tiny}
-%   \begin{table}[ht]
-%     \begin{center}
-%       \begin{tabular}[t]{|r|r|r|r|}
-%         \hline
-%         CPU Num / 実行方式 & egrep & mmap & Blocked Read\\
-%         \hline
-%         1 & 83.09   & 57.65 & 40.49 \\
-%         \hline
-%         2 & ---     & 43.96 & 33.72 \\
-%         \hline
-%         4 & ---     & 33.37 & 34.26 \\
-%         \hline
-%         8 & ---     & 35.48 & 32.46 \\
-%         \hline
-%       \end{tabular}
-%   \caption{abab}
-%   \label{table:abab}
-%     \end{center}
-%   \end{table}
-% \end{tiny}
-% 
--- a/paper/c6.tex	Tue Feb 16 18:17:55 2016 +0900
+++ b/paper/c6.tex	Wed Feb 17 00:07:04 2016 +0900
@@ -1,7 +1,6 @@
 \chapter{結論}
 \section{---}
 \section{今後の課題}
-\subsection{一つのノードに Word を含める}
 これまでの正規表現は一文字ずつ参照して状態を割り振っていった。この状態割り振りの問題として文字列の長さの分だけ状態ができてしまう。
 状態が長くなればなるほど、ファイルと正規表現のマッチング時の状態遷移数もそれだけ多くなってしまう。
 状態遷移数が多くなると、それだけ状態と入力を見て次の状態に遷移するという動作を何度も繰り返すことになってしまうので、処理的にも重くなってしまう。
--- a/paper/master_paper.bib	Tue Feb 16 18:17:55 2016 +0900
+++ b/paper/master_paper.bib	Wed Feb 17 00:07:04 2016 +0900
@@ -6,15 +6,15 @@
     year = 2012
 }
 
-@article{yuhi:2015,
-	author = "渡真利 勇飛",
-	title = "マルチプラットフォーム対応並列プログラミングフレームワーク",
+@article{ yuhi:2015,
+    author = "渡真利 勇飛",
+    title = "マルチプラットフォーム対応並列プログラミングフレームワーク",
     journal = "琉球大学大学院理工学研究科情報工学専攻平成 26 年度学位論文(修士)",
-	year = 2013
+    year = 2013
 }
 
 @article{ prosym_shinya,
-    author = "新屋 良磨,河野 真治",
+    author = "新屋 良磨 河野 真治",
     title = "動的なコード生成を用いた正規表現マッチャの実装",
     journal = "第52回プログラミング・シンポジウム",
     month = "January",
@@ -27,6 +27,13 @@
     year = 2015
 }
 
+@manual{ automaton,
+    author = "{Michael Sipser ・阿部 正幸・植田 広樹・藤岡 淳・渡辺 治著・太田 和夫・田中 圭介監訳}",
+    title ="{計算理論の基礎 [原著第2版](共立出版)}",
+    month = "May",
+    year = 2008
+}
+
 @manual{ bmsearch,
     author = "J.S.Moore, R.S. Boyer.",
     title ="A Fast String Searching Algorithm",
Binary file paper/master_paper.pdf has changed
--- a/paper/memo/data.txt	Tue Feb 16 18:17:55 2016 +0900
+++ b/paper/memo/data.txt	Wed Feb 17 00:07:04 2016 +0900
@@ -1,3 +1,242 @@
++firefly+one ./time.pl './cerium/ceriumGrep -br -cpu 12 -subset -regex '\''(a|b)*a(a|b)(a|b)(a|b)z'\'' -file file/ab500MB.txt' 10
+------setting------
+    command  = ./cerium/ceriumGrep -br -cpu 12 -subset -regex '(a|b)*a(a|b)(a|b)(a|b)z' -file file/ab500MB.txt
+    loop     = 10
+------result(s)---
+       19.95 real        23.11 user         0.72 sys
+       31.30 real        23.11 user         0.72 sys
+       32.13 real        23.42 user         0.74 sys
+       26.97 real        23.77 user         0.74 sys
+       27.89 real        23.16 user         0.75 sys
+       29.50 real        23.15 user         0.74 sys
+       28.30 real        24.00 user         0.74 sys
+       29.45 real        23.12 user         0.73 sys
+       27.17 real        23.08 user         0.73 sys
+       27.22 real        23.09 user         0.74 sys
+
++firefly+one ./time.pl './cerium/ceriumGrep -br -cpu 12 -subset -regex '\''(a|b)*a(a|b)(a|b)z'\'' -file file/ab500MB.txt' 10
+------setting------
+    command  = ./cerium/ceriumGrep -br -cpu 12 -subset -regex '(a|b)*a(a|b)(a|b)z' -file file/ab500MB.txt
+    loop     = 10
+------result(s)---
+       13.33 real        23.48 user         0.69 sys
+       27.24 real        23.16 user         0.74 sys
+       26.58 real        23.18 user         0.73 sys
+       29.65 real        23.91 user         0.75 sys
+       27.37 real        23.78 user         0.74 sys
+       27.96 real        23.22 user         0.74 sys
+       27.43 real        23.47 user         0.73 sys
+       28.55 real        23.16 user         0.73 sys
+       26.59 real        23.10 user         0.74 sys
+       25.57 real        23.13 user         0.74 sys
+
+
++firefly+one ./time.pl 'egrep -o '\''(a|b)*a(a|b)(a|b)'\'' file/ab500MB.txt' 10
+------setting------
+    command  = egrep -o '(a|b)*a(a|b)(a|b)' file/ab500MB.txt
+    loop     = 10
+------result(s)---
+       46.28 real        45.97 user         0.23 sys
+       45.06 real        44.53 user         0.21 sys
+       48.13 real        47.74 user         0.21 sys
+       45.16 real        44.64 user         0.21 sys
+       44.51 real        44.23 user         0.21 sys
+
++firefly+one ./time.pl './cerium/ceriumGrep -cpu 12 -subset -regex '\''[A-Z][A-Za-z0-9]*s'\'' -file  file/1GB.txt' 10 
+------setting------
+    command  = ./cerium/ceriumGrep -cpu 12 -subset -regex '[A-Z][A-Za-z0-9]*s' -file  file/1GB.txt
+    loop     = 10
+------result(s)---
+       25.37 real        47.58 user         1.35 sys
+       27.91 real        47.41 user         1.37 sys
+       31.90 real        47.96 user         1.36 sys
+       28.89 real        48.10 user         1.37 sys
+       29.04 real        47.40 user         1.39 sys
+       34.83 real        47.43 user         1.38 sys
+       28.21 real        48.59 user         1.41 sys
+       25.03 real        47.49 user         1.39 sys
+       29.21 real        47.56 user         1.37 sys
+       31.16 real        47.58 user         1.37 sys
+
++firefly+one ./time.pl './cerium/ceriumGrep -br -cpu 12 -subset -regex '\''[A-Z][A-Za-z0-9]*s'\'' -file  file/1GB.txt' 10
+------setting------
+    command  = ./cerium/ceriumGrep -br -cpu 12 -subset -regex '[A-Z][A-Za-z0-9]*s' -file  file/1GB.txt
+    loop     = 10
+------result(s)---
+       21.50 real        47.36 user         1.56 sys
+       26.84 real        47.37 user         1.57 sys
+       27.61 real        47.75 user         1.60 sys
+       27.20 real        47.30 user         1.57 sys
+       28.27 real        49.94 user         1.60 sys
+       26.24 real        47.39 user         1.57 sys
+       30.20 real        47.34 user         1.57 sys
+
++firefly+one ./time.pl './cerium/ceriumGrep -br -cpu 12 -subset -regex '\''[A-Z][A-Za-z0-9]*s'\'' -file  file/500MB.txt' 10
+------setting------
+    command  = ./cerium/ceriumGrep -br -cpu 12 -subset -regex '[A-Z][A-Za-z0-9]*s' -file  file/500MB.txt
+    loop     = 10
+------result(s)---
+       15.14 real        24.24 user         0.81 sys
+       15.36 real        24.76 user         0.83 sys
+       17.06 real        23.67 user         0.82 sys
+       17.98 real        23.71 user         0.83 sys
+       18.51 real        24.20 user         0.81 sys
+       19.87 real        23.73 user         0.82 sys
+       18.71 real        23.77 user         0.82 sys
+       17.13 real        23.68 user         0.81 sys
+       17.86 real        23.68 user         0.82 sys
+       17.70 real        23.71 user         0.82 sys
+
++firefly+one ./time.pl './cerium/ceriumGrep -cpu 12 -subset -regex '\''[A-Z][A-Za-z0-9]*s'\'' -file  file/500MB.txt' 10
+------setting------
+    command  = ./cerium/ceriumGrep -cpu 12 -subset -regex '[A-Z][A-Za-z0-9]*s' -file  file/500MB.txt
+    loop     = 10
+------result(s)---
+       12.62 real        23.84 user         0.71 sys
+       18.44 real        25.20 user         0.70 sys
+       20.74 real        23.76 user         0.72 sys
+       18.63 real        23.78 user         0.71 sys
+       20.64 real        25.28 user         0.71 sys
+       19.19 real        23.74 user         0.74 sys
+       17.53 real        23.76 user         0.72 sys
+       20.37 real        23.77 user         0.72 sys
+       18.53 real        23.85 user         0.71 sys
+       17.24 real        23.77 user         0.72 sys
+
++firefly+one ./time.pl 'egrep -o '\''[A-Z][A-Za-z0-9]*s'\'' file/100MB.txt' 10
+------setting------
+    command  = egrep -o '[A-Z][A-Za-z0-9]*s' file/100MB.txt
+    loop     = 10
+------result(s)---
+       12.85 real        12.57 user         0.04 sys
+       12.94 real        12.61 user         0.04 sys
+       12.90 real        12.70 user         0.05 sys
+       12.80 real        12.64 user         0.04 sys
+       12.69 real        12.57 user         0.04 sys
+       12.89 real        12.71 user         0.04 sys
+       12.77 real        12.68 user         0.05 sys
+       12.65 real        12.56 user         0.04 sys
+       12.79 real        12.68 user         0.04 sys
+       12.77 real        12.51 user         0.04 sys
+
++firefly+one ./time.pl './regexParser -regex '\''[A-Z][A-Za-z0-9]*s'\'' -ts -file file/100MB.txt' 10
+------setting------
+    command  = ./regexParser -regex '[A-Z][A-Za-z0-9]*s' -ts -file file/100MB.txt
+    loop     = 10
+------result(s)---
+        8.44 real         3.26 user         0.05 sys
+        9.05 real         3.25 user         0.04 sys
+        8.08 real         3.26 user         0.05 sys
+        6.99 real         3.26 user         0.05 sys
+        7.11 real         3.25 user         0.04 sys
+        8.45 real         3.26 user         0.05 sys
+        9.43 real         3.25 user         0.05 sys
+        8.58 real         3.25 user         0.05 sys
+        8.18 real         3.25 user         0.05 sys
+        9.88 real         3.25 user         0.04 sys
+
+
++firefly+one ./time.pl './cerium/ceriumGrep -cpu 12 -subset -regex '\''[A-Z][A-Za-z0-9]*s'\'' -file  file/100MB.txt' 10
+------setting------
+    command  = ./cerium/ceriumGrep -cpu 12 -subset -regex '[A-Z][A-Za-z0-9]*s' -file  file/100MB.txt
+    loop     = 10
+------result(s)---
+        9.12 real         5.08 user         0.20 sys
+        6.98 real         5.05 user         0.20 sys
+       12.85 real         5.07 user         0.20 sys
+       13.08 real         5.05 user         0.20 sys
+       13.13 real         5.08 user         0.20 sys
+       11.14 real         5.18 user         0.20 sys
+        7.18 real         5.07 user         0.22 sys
+       11.35 real         5.06 user         0.21 sys
+       10.20 real         5.06 user         0.21 sys
+       12.89 real         5.07 user         0.21 sys
+
+
++firefly+one ./time.pl './cerium/ceriumGrep -br -cpu 12 -subset -regex '\''[A-Z][A-Za-z0-9]*s'\'' -file  file/100MB.txt' 10
+------setting------
+    command  = ./cerium/ceriumGrep -br -cpu 12 -subset -regex '[A-Z][A-Za-z0-9]*s' -file  file/100MB.txt
+    loop     = 10
+------result(s)---
+        8.49 real         5.08 user         0.22 sys
+        8.47 real         5.19 user         0.24 sys
+       11.68 real         5.08 user         0.24 sys
+        8.83 real         5.09 user         0.24 sys
+       10.72 real         5.14 user         0.24 sys
+       12.14 real         5.09 user         0.24 sys
+       11.89 real         5.08 user         0.24 sys
+       10.28 real         5.39 user         0.24 sys
+       13.52 real         5.09 user         0.23 sys
+        8.88 real         5.10 user         0.23 sys
+
++firefly+one ./time.pl 'egrep -o '\''[A-Z][A-Za-z0-9]*s'\'' file/50MB.txt' 10 
+------setting------
+    command  = egrep -o '[A-Z][A-Za-z0-9]*s' file/50MB.txt
+    loop     = 10
+------result(s)---
+        6.36 real         6.24 user         0.02 sys
+        6.38 real         6.27 user         0.02 sys
+        6.52 real         6.32 user         0.02 sys
+        6.37 real         6.25 user         0.02 sys
+        6.31 real         6.24 user         0.02 sys
+        6.43 real         6.35 user         0.02 sys
+        6.35 real         6.28 user         0.02 sys
+        6.37 real         6.30 user         0.02 sys
+        6.63 real         6.38 user         0.02 sys
+        6.44 real         6.30 user         0.02 sys
+
+
++firefly+one ./time.pl './cerium/ceriumGrep -br -cpu 12 -subset -regex '\''[A-Z][A-Za-z0-9]*s'\'' -file  file/50MB.txt' 10
+------setting------
+    command  = ./cerium/ceriumGrep -br -cpu 12 -subset -regex '[A-Z][A-Za-z0-9]*s' -file  file/50MB.txt
+    loop     = 10
+------result(s)---
+        4.68 real         2.56 user         0.14 sys
+        6.66 real         2.54 user         0.15 sys
+        8.99 real         2.60 user         0.15 sys
+        7.85 real         2.56 user         0.15 sys
+        9.12 real         2.70 user         0.15 sys
+       10.15 real         2.55 user         0.15 sys
+        8.47 real         2.68 user         0.15 sys
+        8.15 real         2.55 user         0.14 sys
+        5.49 real         2.55 user         0.16 sys
+        7.94 real         2.55 user         0.16 sys
+
++firefly+one ./time.pl './cerium/ceriumGrep -cpu 12 -subset -regex '\''[A-Z][A-Za-z0-9]*s'\'' -file  file/50MB.txt' 10
+------setting------
+    command  = ./cerium/ceriumGrep -cpu 12 -subset -regex '[A-Z][A-Za-z0-9]*s' -file  file/50MB.txt
+    loop     = 10
+------result(s)---
+        7.13 real         2.55 user         0.14 sys
+       11.09 real         2.55 user         0.13 sys
+        8.04 real         2.68 user         0.14 sys
+        9.46 real         2.55 user         0.14 sys
+        8.48 real         2.55 user         0.15 sys
+       11.81 real         2.55 user         0.13 sys
+        7.15 real         2.55 user         0.15 sys
+       11.05 real         2.56 user         0.14 sys
+        9.25 real         2.55 user         0.14 sys
+        6.27 real         2.55 user         0.15 sys
+
+
++firefly+one ./time.pl './regexParser -regex '\''[A-Z][A-Za-z0-9]*s'\'' -ts -file file/50MB.txt' 10
+------setting------
+    command  = ./regexParser -regex '[A-Z][A-Za-z0-9]*s' -ts -file file/50MB.txt
+    loop     = 10
+------result(s)---
+        3.25 real         1.62 user         0.02 sys
+        4.32 real         1.62 user         0.02 sys
+        4.36 real         1.62 user         0.02 sys
+        4.78 real         1.62 user         0.02 sys
+        5.63 real         1.62 user         0.02 sys
+        4.58 real         1.62 user         0.02 sys
+        4.48 real         1.62 user         0.02 sys
+        4.54 real         1.63 user         0.02 sys
+        4.74 real         1.63 user         0.02 sys
+        4.42 real         1.62 user         0.02 sys
+
+
+
 +firefly+one ./time.pl './regexParser -regex '\''(W|w)ord'\'' -ts -file file/ab500MB.txt' 10
 ------setting------
     command  = ./regexParser -regex '(W|w)ord' -ts -file file/ab500MB.txt