--- a/paper/chapter3.tex	Tue Feb 25 05:08:39 2014 +0900
+++ b/paper/chapter3.tex	Tue Feb 25 14:33:01 2014 +0900
@@ -27,6 +27,61 @@
   \end{table}
 \end{tiny}
 
+この例題の Task 生成部分を以下に示す。
+\\
+\begin{breakbox}
+\begin{verbatim}
+HTaskPtr read = manager->create_task(Read_task);
+read->set_cpu(SPE_ANY);
+
+read->set_param(0,(long)task_number);
+read->set_param(1,(long)division_size);
+if(read_left_size <= division_size){
+    read->set_param(2,(long)left_size);
+}else{
+    read->set_param(2,(long)division_size);
+}
+read->set_param(3,(long)fd);
+
+read->set_outData(0,read_text + task_number*division_size,
+                                            division_size);
+read->spawn();
+
+read_left_size -= division_size;
+task_number++;
+\end{verbatim}
+\end{breakbox}
+
+read という Task を宣言し、Task に CPU Type、パラメータとして生成した Task 番号の task\_number
+1つの Task の読み込み量 division\_size、読み込むファイルのファイルディスクリプタ fd を設定する。
+読み込んだデータの格納先を set\_outData にて設定を行い、そして spawn にて Task を生成する。
+
+Task が生成されると、division\_size分の読み込みを行ったということで、残りの読み込み量 read\_left\_size から division\_size を引き、そして task\_numberを増加させる。
+この Task 生成部分は ファイルサイズ を division\_size で割った数だけ生成され、もし余りがあれば更に1加えた数になる。
+その数が Read Task の数となり、その数だけループ処理を行う。
+中盤にある if 文は、最後の Read Task かどうかで実際に読み込む量が決定される。
+
+read Task の記述を以下に示す。
+\\
+\begin{breakbox}
+\begin{verbatim}
+static int
+read_task(SchedTask *s, void *rbuf, void *wbuf)
+{
+    long task_number = (long)s->get_param(0);
+    long division_size = (long)s->get_param(1);
+    long read_size = (long)s->get_param(2);
+    long fd = (long)s->get_param(3);
+
+    char *read_text = (char*)s->get_output(wbuf,0);
+
+    pread(fd, read_text, (long)read_size , division_size*task_number);
+    return 0;
+}
+\end{verbatim}
+\end{breakbox}
+生成時に設定したデータ群を受け取り、それらのデータを pread の引数に渡す。読み込まれたファイルは read\_text に格納される。
+
 ハードディスクに保存されている 10GB のテキストファイルを分割して読み込み終わるまでの時間を表\ref{table:preaddata}に示す。
 分割サイズとは、1回の読み込み量である。
 \begin{tiny}
@@ -53,12 +108,11 @@
 \newpage
 
 \section{ファイルに対して処理を行う例題}
-読み込んだテキストファイルに対して文字列検索を行う例題として、Boyer-Moore String Search を実装した。
-このアルゴリズムは 1977 年に Robert S. Boyer と J Strother Moore が開発した効率的なアルゴリズムである。
-
-Boyer-Moore String Search を紹介する前に、文字列検索で比較的単純なアルゴリズムである力任せ法を紹介する。
+読み込んだテキストファイルに対して文字列検索を行う例題として、力任せ法と Boyer-Moore String Search を実装した。
+Boyer-Moore String Search は 1977 年に Robert S. Boyer と J Strother Moore が開発した効率的なアルゴリズムである。
 なお、テキストファイルに含まれている文字列を text、検索する文字列を pattern と定義する。
 
+\subsection{力任せ法}
 力任せ法(総当り法とも呼ばれる)は、text と pattern を先頭から比較していき、
 pattern と一致しなければ pattern を1文字分だけ後ろにずらして再度比較をしていくアルゴリズムである。
 text の先頭から pattern の先頭を比較していき、文字の不一致が起きた場合は、
@@ -73,11 +127,13 @@
 \label{fig:bruteforth}
 \end{figure}
 
+\newpage
 このアルゴリズムは実装が簡単であり、pattern が text に含まれていれば必ず探しだすことができる。
 しかし、text と pattern の文字数が大きくなるにつれて、比較回数も膨大になる恐れがある。
 text の文字数を $n$、pattern の文字数を $m$とすると、力任せ法の最悪計算時間は $O(nm)$ となる。
 
-この比較回数を改善したアルゴリズムが Boyer-Moore String Search である。
+\subsection{Boyer-Moore String Search Algorithm}
+力任せ法の比較回数を改善したアルゴリズムが Boyer-Moore String Search である。
 力任せ法との大きな違いとして、text と pattern を先頭から比較するのではなく、
 pattern の末尾から比較していくことである。そして不一致が起こった場合は、
 その不一致が起こった text の文字で再度比較する場所が決まる。
@@ -91,7 +147,7 @@
 
 \begin{figure}[htbp]
 \begin{center}
-\includegraphics[width=0.7\textwidth]{fig/bmsearchthink.pdf}
+\includegraphics[width=0.5\textwidth]{fig/bmsearchthink.pdf}
 \end{center}
 \caption{pattern に含まれていない文字で不一致になった場合}
 \label{fig:bmsearchthink}
@@ -168,13 +224,10 @@
 \label{fig:bmskiptable1}
 \end{figure}
 
-\if0
-文字列検索を行う前に、不一致になったときの文字列によって着目点をいくつ右にずらすかというテーブルを作成しなければならない。
-
-そのテーブルの作成は次のプログラムで作成できる。
-
-\newpage
-
+このようなテーブルを、文字列検索を行う前に生成する必要がある。
+そのテーブル生成プログラムは以下のようになる。
+\\
+\begin{breakbox}
 \begin{verbatim}
 static int*
 create_BMskiptable(unsigned char *pattern,
@@ -191,8 +244,9 @@
     return skip_table;
 }
 \end{verbatim}
+\end{breakbox}
 このソースでの 128 とは ASCII コード表における最大値である。
-それぞれの文字に対して pattern の長さ (pattern\_len) を格納する。pattern が "doing" という文字列だと仮定すると、
+それぞれの文字に対して pattern の長さであるpattern\_lenを格納する。pattern が "doing" という文字列だと仮定すると、
 pattern\_len = 5 となる。次に pattern の先頭から文字を調べる。
 先頭の文字は d であり、d に対応する table に着目点をずらすための移動量を格納する。
 移動量を格納したら、pattern の次の文字を調べ、そして移動量を格納していく。(図\ref{fig:bmskiptable})
@@ -205,12 +259,37 @@
 \label{fig:bmskiptable}
 \end{figure}
 
-\fi
-
+\newpage
+生成したテーブルを利用して文字列検索を行うアルゴリズムを以下に示す。
+\\
+\begin{breakbox}
+\begin{verbatim}
+int i = pattern_len - 1;
+int match_counter = 0;
 
-この例題ではファイルを読み込んで一定の大きさでファイルを分割する。分割したものにそれぞれ Boyer-Moore String Search を行う。
+while ( i < text_len){
+    int j = pattern_len - 1;
+    while (text[i] == pattern[j]){
+        if (j == 0){
+            match_counter++;
+        }
+        --i;
+        --j;
+    }
+    i = i + max(skip_table[text[i]],pattern_len - j);
+}
+\end{verbatim}
+\end{breakbox}
+読み込まれたテキストファイル text[i] と、検索文字列 pattern[j]を末尾から比較していく。
+一致していれば参照する場所を先頭方向にずらしていき、先頭まで完全一致した場合は、
+検索文字列を発見したということで、ここではマッチした数 match\_counter を増やしている。
+
+もし途中で不一致が起こった場合は、その不一致が起こった時の text[i] の文字列か pattern の長さから j 引いたものの最大値の分だけ text の参照先をずらす。
+
+\subsection{ファイル分割時の処理の注意点}
+この例題ではファイルを読み込んで一定の大きさでファイルを分割する。分割したものにそれぞれ文字列検索を行う。
 それぞれの結果は pattern が含まれている個数が返ってくるので、最後に集計をして個数を表示する。このような一つ一つの処理を Task と呼ぶ。
-図\ref{fig:includeiotask}では、ファイルの読み込みが File Read、分割したものに Boyer-Moore String Search することが Run Tasks、
+図\ref{fig:includeiotask}では、ファイルの読み込みが File Read、分割したものに文字列検索を行うことが Run Tasks、
 返した結果が Output Data、それぞれの結果の集計が Run resultTask に相当する。
 
 \begin{figure}[htbp]
@@ -236,6 +315,7 @@
 \label{fig:includeiotask}
 \end{figure}
 
+\newpage
 それを解決するために、1つの Search task の text の長さに pattern の長さを加えてから 1 引いた数だけ読み込むようにすればそのような問題は起こらない。よって、読み込むデータ量は $ L + s -1 $となる。
 
 \begin{figure}[htbp]
@@ -246,12 +326,11 @@
 \label{fig:includeiotask}
 \end{figure}
 
-\newpage
 力任せ法と Boyer-Moore String Search を比較してみた。以下に実験環境と結果を示す。(表\ref{table:search})
 \begin{itemize}
 \item Mac OS X 10.9.1
 \item 2*2.66 GHz 6-Core Intel Xeon
-\item file size 10GB
+\item File Size 10GB
 \end{itemize}
 
 \begin{tiny}

Binary file paper/thesis-paper.pdf has changed