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

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

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 の呼ばれる回数が少なくなるので読み込むことが速くなる。
しかし、ある一定以上の大きさになると I/O ネックが勝ってしまい、読み込み速度が変わらない。

\newpage

\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文字分だけ後ろにずらして再度比較をしていくアルゴリズムである。
text の先頭から pattern の先頭を比較していき、文字の不一致が起きた場合は、
pattern を右に 1 つだけずらして、再度 text と pattern の先頭を比較していく。
(図\ref{fig:bruteforth})

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.5\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 の文字で再度比較する場所が決まる。


\newpage
まず始めに、比較する場所を着目点とおく。図\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.5\textwidth]{fig/bmsearchthink.pdf}
\end{center}
\caption{pattern に含まれていない文字で不一致になった場合}
\label{fig:bmsearchthink}
\end{figure}

次に、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.5\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.5\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.5\textwidth]{fig/bmsearchbasic.pdf}
\end{center}
\caption{Boyer-Moore Search String}
\label{fig:bmsearchbasic}
\end{figure}

このように、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


図\ref{fig:includeiotask}

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