\chapter{例題}
\label{chap:poordirection}

\section{ファイルの読み込みに関する例題}
テキストファイルをある一定のサイズに分割して読み込むプログラムである。このプログラムでは、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}

ハードディスクに保存されている 10GB のテキストファイルを分割して読み込み終わるまでの時間を表\ref{table:preaddata}に示す。
分割サイズとは、1回の読み込み量である。
\begin{tiny}
  \begin{table}[ht]
    \begin{center}
      \label{table:preaddata}
      \small
      \begin{tabular}[t]{c|l}
        \hline
        分割サイズ & 読み込み速度(s)\\
        \hline
        16KB & 391.7 \\
        \hline
        16MB & 123.6 \\
        \hline
      \end{tabular}
      \caption{file read の実行結果}
    \end{center}
  \end{table}
\end{tiny}

分割サイズを大きくすると、pread の呼ばれる回数が少なくなるので読み込むことが速くなる。

\newpage

\section{ファイルに対して処理を行う例題}
読み込んだテキストファイルに対して文字列検索を行う例題として、Boyer-Moore String Search を実装した。
このアルゴリズムは 1977 年に Robert S. Boyer と J Strother Moore が開発した効率的なアルゴリズムである。

Boyer-Moore String Search を紹介する前に、文字列検索で比較的単純なアルゴリズムである力任せ法を紹介する。
なお、テキストファイルに含まれている文字列を text、検索する文字列を pattern と定義する。

力任せ法(総当り法とも呼ばれる)は、text と pattern を先頭から比較していき、
pattern と一致しなければ pattern を1文字分だけ後ろにずらして再度比較をしていくアルゴリズムである。
text の先頭から pattern の先頭を比較していき、文字の不一致が起きた場合は、
pattern を右に 1 つだけずらして、再度 text と pattern の先頭を比較していく。
(図\ref{fig:bruteforth})

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.7\textwidth]{fig/bruteforth.pdf}
\end{center}
\caption{力まかせ法}
\label{fig:bruteforth}
\end{figure}

このアルゴリズムは実装が簡単であり、pattern が text に含まれていれば必ず探しだすことができる。
しかし、text と pattern の文字数が大きくなるにつれて、比較回数も膨大になる恐れがある。
text の文字数を $n$、pattern の文字数を $m$とすると、力任せ法の最悪計算時間は $O(nm)$ となる。

この比較回数を改善したアルゴリズムが Boyer-Moore String Search である。
力任せ法との大きな違いとして、text と pattern を先頭から比較するのではなく、
pattern の末尾から比較していくことである。そして不一致が起こった場合は、
その不一致が起こった text の文字で再度比較する場所が決まる。

まず始めに、比較する場所を着目点とおく。図\ref{fig:bmsearchthink}の場合、
最初に比較する patternの末尾 と、それに対応する text を着目点とする。
(a)ではその着目点で不一致が起こっているので、それ以上比較しなくてもよいことがわかる。
不一致が起こった場合は (b) のように着目点をずらしていく。着目点を1つ右にずらして再度 pattern の末尾から比較していく。これを繰り返しをして、(d) のときに初めて一致することがわかる。

(a)のときに不一致を起こした text の文字に注目する。その文字が pattern に含まれていない文字であるならば、着目点を1つずらしても、2つずらしても一致することはない。pattern に含まれていない文字で不一致になった場合は、pattern の文字数分だけ着目点をずらすことができる。

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.7\textwidth]{fig/bmsearchthink.pdf}
\end{center}
\caption{pattern に含まれていない文字で不一致になった場合}
\label{fig:bmsearchthink}
\end{figure}

\newpage

次に、pattern に含まれている文字で不一致になった場合を紹介する。
図\ref{fig:bmsearchthink}と同様に、文字を比較していく。
図\ref{fig:bmsearchinclude}(a)のときに不一致が起こる。
その時の text の文字列は pattern に含まれている。
この場合は着目点を右に2つずらすと text と pattern が一致する。
もし、pattern に含まれている文字で不一致になった場合は、その text の文字に注目する。
その文字を pattern 内から探し、その文字が pattern の末尾から
どれだけ離れているかで着目点を右にずらす量が決定される。
図\ref{fig:bmsearchinclude}の場合であれば、不一致時の文字が a であれば右に2つ、
b であれば右に1つずらすことができる。

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.7\textwidth]{fig/bmsearchinlucde.pdf}
\end{center}
\caption{pattern に含まれている文字で不一致になった場合}
\label{fig:bmsearchinclude}
\end{figure}

\newpage

pattern に同じ文字が複数入り、その文字で不一致になった場合は図\ref{fig:bmsearchsame}のようになる。
この場合 a という文字が pattern の末尾から 1つ離れている箇所と 3 つ離れている箇所が存在する。
(a) のように、a で不一致が起こった場合は、着目点を右に1つか3つ移動できる。
しかし、着目点を右に3つずらしてしまうと、(b-1)のように text の途中にある "abac" という文字列を見逃してしまう。着目点を右に1つずらせば、(b-2)のように検索漏れを起こすことはなくなる。

このように、pattern に同じ文字が複数入っている場合は、末尾から一番近いほうを適用する。よって、図\ref{fig:bmsearchinclude}では、不一致時の文字が a であれば右に1つ、b であれば右に2つ着目点をずらすことができる。

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.7\textwidth]{fig/bmsearchsame.pdf}
\end{center}
\caption{pattern に同じ文字が複数入り、その文字で不一致になった場合}
\label{fig:bmsearchsame}
\end{figure}


\newpage
pattern と text と不一致時の処理をまとめると、

\begin{itemize}
\item pattern に含まれていない文字の場合は、 pattern の長さだけ着目点を右にずらす
\item pattern に含まれている文字の場合は、 その文字が pattern の末尾から離れている分だけ着目点を右にずらす
\item pattern に含まれている文字かつ、その文字が pattern に複数含まれている場合は、 pattern の末尾から一番近い分だけ着目点を右にずらす
\end{itemize}

となる。 図\ref{fig:bmsearchbasic}の例であれば、不一致字の text の文字が a であれば着目点を 2つ、 b であれば 1つ、それ以外の文字列は3つずらすことができる。

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.7\textwidth]{fig/bmsearchbasic.pdf}
\end{center}
\caption{Boyer-Moore Search String}
\label{fig:bmsearchbasic}
\end{figure}

\newpage
このように、Boyer-Moore Search String は、不一致が起こった時の text の文字によって着目点をずらすということが起こるので、
文字列検索を行う前に、着目点をずらす量を参照するための BMsearch skip table を作成する。
"doing" という pattern であれば、そのテーブルは図\ref{fig:bmskiptable1}となる。

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.8\textwidth]{fig/bmskiptable1.pdf}
\end{center}
\caption{BMsearch skip table}
\label{fig:bmskiptable1}
\end{figure}

\if0
文字列検索を行う前に、不一致になったときの文字列によって着目点をいくつ右にずらすかというテーブルを作成しなければならない。

そのテーブルの作成は次のプログラムで作成できる。

\newpage

\begin{verbatim}
static int*
create_BMskiptable(unsigned char *pattern,
                    int pattern_len,int *skip_table)
{
    for(int i = 0; i < 128; ++i){
        skip_table[i] = pattern_len;
    }

    for(int j = 0; j < pattern_len - 1; ++j){
        skip_table[pattern[j]] = pattern_len - j - 1;
    }

    return skip_table;
}
\end{verbatim}
このソースでの 128 とは ASCII コード表における最大値である。
それぞれの文字に対して pattern の長さ (pattern\_len) を格納する。pattern が "doing" という文字列だと仮定すると、
pattern\_len = 5 となる。次に pattern の先頭から文字を調べる。
先頭の文字は d であり、d に対応する table に着目点をずらすための移動量を格納する。
移動量を格納したら、pattern の次の文字を調べ、そして移動量を格納していく。(図\ref{fig:bmskiptable})

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.8\textwidth]{fig/bmskiptable.pdf}
\end{center}
\caption{skip table の 生成時の様子}
\label{fig:bmskiptable}
\end{figure}

\fi

\newpage


この例題ではファイルを読み込んで一定の大きさでファイルを分割する。分割したものにそれぞれ Boyer-Moore String Search を行う。
それぞれの結果は pattern が含まれている個数が返ってくるので、最後に集計をして個数を表示する。このような一つ一つの処理を Task と呼ぶ。
図\ref{fig:includeiotask}では、ファイルの読み込みが File Read、分割したものに Boyer-Moore String Search することが Run Tasks、
返した結果が Output Data、それぞれの結果の集計が Run resultTask に相当する。

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=1.0\textwidth]{fig/includeiotask.pdf}
\end{center}
\caption{IO を含む Task}
\label{fig:includeiotask}
\end{figure}

ファイルを分割したときに、分割される部分で pattern が含まれる場合が存在する。
その場合は、本来の読み込み部分の text の長さ $L$ に加えて、pattern の長さ $s$ だけ多く読みこむように設計することでこの問題は解決できる。
しかし、1 つの Search Task の text の長さが $L+s$ の場合だと、pattern が Search Task 1 に含まれ、Search Task 2 にも含まれてしまう。
(図\ref{fig:includeiotask})

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=1.0\textwidth]{fig/iodivfail.pdf}
\end{center}
\caption{分割周りの処理・失敗時 (例:doing の検索)}
\label{fig:includeiotask}
\end{figure}

それを解決するために、1つの Search task の text の長さに pattern の長さを加えてから 1 引いた数だけ読み込むようにすればそのような問題は起こらない。よって、読み込むデータ量は $ L + s -1 $となる。

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=1.0\textwidth]{fig/iodivsuc.pdf}
\end{center}
\caption{分割周りの処理・成功時 (例:doing の検索)}
\label{fig:includeiotask}
\end{figure}

力任せ法と 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
\end{itemize}

\begin{tiny}
  \begin{table}[ht]
    \begin{center}
      \label{table:search}
      \small
      \begin{tabular}[t]{c|r}
        \hline
        文字列検索アルゴリズム & 処理速度(s)\\
        \hline
        力任せ法 & 11.792 \\
        \hline
        Boyer-Moore String Search & 6.508 \\
        \hline
      \end{tabular}
      \caption{文字列検索アルゴリズムの比較}
    \end{center}
  \end{table}
\end{tiny}

Boyer-Moore String Search によって 44\% 改善した。