\chapter{Cerium による文字列処理の例題}
本項ではファイルを読み込んで処理する流れとそれの例題を記述する。例題として、単語数を数える Word Count、文字列探索を行う Boyer Moore Search、正規表現を挙げる。

\section{File 読み込みを含んだ並列処理(File Map Reduce?)}
文字列処理を並列で処理する場合を考える。
まずファイルを読み込み、ファイルをある一定の大きさで分割する(divide a file)。
そして、分割されたファイル(Input Data)に対して文字列処理(Task)をおこない、それぞれの分割単位で結果を出力する(Output Data)。
それらの Output Data の結果が出力されたあとに、結果をまとめる処理を行う(Print Task)。
(図\ref{fig:dividefile})

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/example/dividefile.pdf}
  \end{center}
  \caption{File 読み込みから処理までの流れ}
  \label{fig:dividefile}
\end{figure}
File 分割時に分割された部分の整合性についてはそれぞれの例題にて述べる。

\section{Word Count}
Word Count は読み込んだテキストに対して単語数を数える処理である。
Input Data には分割されたテキストが対応しており、Output Data には単語数と行数を出力する。

読み込んだテキストを先頭から見ていき、単語の末端に空白文字か改行文字があれば単語数、改行文字があれば行数を数えることができる。

分割された部分に単語が含まれた場合、単語数や行数について整合性を取る必要がある。
図\ref{fig:wordcountline} ではファイル分割無しの Word Count である。

分割しない状態では単語数(Word Num) 3、行数(Line Num) 2 となる。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/example/wordcountline.pdf}
  \end{center}
  \caption{ファイル分割無しの Word Count}
  \label{fig:wordcountline}
\end{figure}

図\ref{fig:wordcountseparate}では単語で分割された場合である。
分割されたファイルそれぞれの結果を合計すると単語数 4、行数 2 となり、分割されていない時と結果が変わってしまう。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/example/wordcountseparate.pdf}
  \end{center}
  \caption{ファイル分割有りの Word Count}
  \label{fig:wordcountseparate}
\end{figure}

この問題の解決方法として、分割されたファイルの一つ目が文字列で終わり、二つ目のファイルの先頭が文字列で始まった場合はそれぞれの単語数の合計数から 1 引くことにより整合性を取ることができる。

\newpage
\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}

このアルゴリズムは実装が容易であるが、 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.5\textwidth]{images/example/bmsearchthink.pdf}
\end{center}
\caption{pattern に含まれていない文字で不一致になった場合}
\label{fig:bmsearchthink}
\end{figure}

図\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}


図\ref{fig:bmsearchinclude} は不一致が起こったときの 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}

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

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

\section{正規表現}
(正規表現の簡単な概要をここに)

実装した正規表現マッチャのアルゴリズムは、

\begin{enumerate}
\item 与えられた正規表現を構文解析し、正規表現木に変換する。
\item 正規表現木から非決定性オートマトン(以下、NFA)か決定性オートマトン(以下、DFA)に変換する。
\item NFA に変換された場合、Subset Construction による NFA から DFA への変換をおこなう。
\item DFA から状態遷移リストを生成する。
\item 状態遷移のリストを元に文字列検索を行ない結果を返す。
\end{enumerate}

となる。本項はそれぞれのアルゴリズムについて述べていく。

\subsection{正規表現木の生成}
与えられた正規表現から正規表現木を生成していく。
本実装でサポートするメタ文字は、正規表現の基本三演算子\cite{regex}に文字クラスとグループを加えている。
(表\ref{table:metachar})

\begin{tiny}
  \begin{table}[ht]
    \begin{center}
      \begin{tabular}[t]{c|l}
        \hline
        AB & 連続した文字(連接)\\
        \hline
        A* & 直前の文字の 0 回以上の繰返し\\
        \hline
        A\textbar B & A または B(選択)\\
        \hline
        [A-Z] & A-Zの範囲の任意の一文字(文字クラス)\\
        \hline
        ( )& 演算の優先度の明示(グループ) \\
        \hline
      \end{tabular}
      \caption{サポートしているメタ文字一覧}
      \label{table:metachar}
    \end{center}
  \end{table}
\end{tiny}

また、それぞれの記号の結合順位を表\ref{table:bond}のようになっている。

\begin{tiny}
  \begin{table}[ht]
    \begin{center}
      \begin{tabular}[t]{l|l}
        \hline
        結合順位 & メタ文字\\
        \hline
        高 & () (グループ化)\\
        \hline
         & [ ] (文字クラス) \\
        \hline
         & * 繰返し\\
        \hline
         & 連接\\
        \hline
        低 & \textbar 選択\\
        \hline
      \end{tabular}
      \caption{サポートしているメタ文字一覧}
      \label{table:bond}
    \end{center}
  \end{table}
\end{tiny}



\subsection{正規表現木から DFA・NFA の生成}
\subsection{Subset Construction による NFA から DFA の変換}
\subsection{DFA から状態遷移リストの生成}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/implementation/CharClassMergePattern.pdf}
  \end{center}
  \caption{2つの Character Class を merge するときの全パターン}
  \label{fig:CharClassMergePattern}
\end{figure}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/implementation/ccinsert1.pdf}
  \end{center}
  \caption{Character Class を二分木で表示}
  \label{fig:ccinsert1}
\end{figure}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/implementation/ccinsert2.pdf}
  \end{center}
  \caption{ある Character Class の二分木に対して、新しい Character Class を insert}
  \label{fig:ccinsert2}
\end{figure}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/implementation/ccinsertresult.pdf}
  \end{center}
  \caption{insert 後の Character Class の二分木}
  \label{fig:ccinsertresult}
\end{figure}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/implementation/dfa.pdf}
  \end{center}
  \caption{dfa}
  \label{fig:dfa}
\end{figure}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/implementation/nfa.pdf}
  \end{center}
  \caption{nfa}
  \label{fig:nfa}
\end{figure}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/implementation/parser.pdf}
  \end{center}
  \caption{parser}
  \label{fig:parser}
\end{figure}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/implementation/setstate.pdf}
  \end{center}
  \caption{set state}
  \label{fig:set state}
\end{figure}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/implementation/transitiontable.pdf}
  \end{center}
  \caption{Transition Table}
  \label{fig:transitiontable}
\end{figure}