--- a/paper/chapter3.tex	Sun Feb 16 16:01:41 2014 +0900
+++ b/paper/chapter3.tex	Mon Feb 17 22:51:58 2014 +0900
@@ -2,23 +2,80 @@
 \label{chap:poordirection}
 
 \section{File Read}
-・ ファイルを分割して読み込むプログラム
-
-・ Task Manager 側でメモリを確保して、Task 側で読み込んだファイルをそのメモリに格納していく。
-
-・ C の ファイル読み込みの API である pread を使用する。
+テキストファイルをある一定のサイズに分割して読み込むプログラムである。このプログラムでは、pread という関数で実装した。
+pread 関数は UNIX 標準に関するヘッダファイル、unistd.h に含まれている関数である。(表\ref{table:pread})
+読み込んだテキストファイルはバッファに格納されるが、その格納先は TaskManager の API でメモリを確保する。
+\begin{tiny}
+  \begin{table}[ht]
+    \begin{center}
+      \label{table:pread}
+      \small
+        ssize\_t pread(int fd, void *buf, size\_t nbyte, off\_t offset);
+      \begin{tabular}[t]{c|l}
+        \hline
+        int fd & 読み込むファイルディスクリプタ \\
+        \hline
+        void *buf & 予め用意したバッファへの書き込み \\
+        \hline
+        size\_t nbyte & 読み込むサイズ \\
+        \hline
+        off\_t offset& ファイルの先頭からのオフセット \\
+        \hline
+      \end{tabular}
+      \caption{pread 関数の概要}
+    \end{center}
+  \end{table}
+\end{tiny}
 
-・ [image](File Read の図でもいれようかしら)
+1GB のテキストファイルを分割して読み込み終わるまでの時間を表\ref{table:preaddata}に示す。
+\begin{tiny}
+  \begin{table}[ht]
+    \begin{center}
+      \label{table:preaddata}
+      \small
+      \begin{tabular}[t]{c|l}
+        \hline
+        分割サイズ & 読み込み速度(s)\\
+        \hline
+        16KB & XX.XXX \\
+        \hline
+        16MB & XX.XXX \\
+        \hline
+        256MB & XX.XXX \\
+        \hline
+      \end{tabular}
+      \caption{file read の実行結果}
+    \end{center}
+  \end{table}
+\end{tiny}
 
-・ 実験結果の載っける
-
-・ 分割を少なくしたほうが、pread (System call)が呼ばれる回数がすくなくなるので無駄がすくなくなる。
-
+分割サイズを大きくすると、pread の呼ばれる回数が少なくなるので読み込むことが速くなる。
+しかし、ある一定以上の大きさになると I/O ネックが勝ってしまい、読み込み速度が変わらない。
 
 \section{Boyer-Moore String Search Algorithm}
+読み込んだテキストファイルに対して文字列検索を行う。文字列検索のアルゴリズムとして、Boyer-Moore String Search を実装した。
+このアルゴリズムは 1977 年に Robert S. Boyer と J Strother Moore が開発した効率的なアルゴリズムである。
+
+Boyer-Moore String Search を紹介する前に、文字列検索で比較的単純なアルゴリズムである力任せ法を紹介する。
+なお、テキストファイルに含まれている文字列を text、検索する文字列を pattern と定義する。
+
+力任せ法(総当り法とも呼ばれる)は、text と pattern を先頭から比較していき、pattern と一致しなければ pattern を1文字分だけ後ろにずらして再度比較をしていくアルゴリズムである。
 
 ・ IO を含む Task なので、ここで説明
 
+・ BM Search の概要
+
+    BM Search は XXX が XXX 年に発表した文字列探索アルゴリズム
+
+    ほかにもいろいろ
+
+    力まかせ法についても少し書くか
+
+    [image]BM Search の skip table の説明と図
+
+    [image]BM Search の実行時の説明と図
+
+・ BM Search をテキストにかけて、検索文字列が含まれてい数をカウントする。
 
 図\ref{fig:includeio}
 
@@ -31,17 +88,6 @@
 \label{fig:includeio}
 \end{figure}
 
-・ BM Search の概要
-
-    BM Search は XXX が XXX 年に発表した文字列探索アルゴリズム
-
-    ほかにもいろいろ
-
-    [image]BM Search の skip table の説明と図
-
-    [image]BM Search の実行時の説明と図
-
-・ BM Search をテキストにかけて、検索文字列が含まれてい数をカウントする。
 
 ・ [image]分割で読み込むときに分割サイズを間違えると正しい結果が返ってこない。