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

\section{File 読み込みを含んだ並列処理}
文字列処理を並列で処理する場合を考える。
まずファイルを読み込み、ファイルをある一定の大きさで分割する(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}

\section{Word Count}
Word Count は読み込んだファイルに対して単語数を数える処理である。
Input Data には分割されたファイルが対応しており、Output Data には単語数と行数を
\section{Boyer Moore Search}
\section{正規表現}
\subsection{正規表現木の生成}
\subsection{正規表現木から NFA の生成}
\subsection{Subset Construction による NFA から 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/cfab.pdf}
  \end{center}
  \caption{cfab}
  \label{fig:cfab}
\end{figure}

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

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

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/implementation/efgi.pdf}
  \end{center}
  \caption{efgi}
  \label{fig:efgi}
\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}