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

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

\newpage

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

\newpage

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

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

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

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

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

\newpage

\subsection{正規表現木の生成}
まずはじめに、図\ref{fig:parser}のように与えられた正規表現から正規表現木に変換する。
与えられた正規表現を頭から一文字ずつ読み込み、読み込んだ文字やメタ文字と呼ばれる正規表現での特殊記号を元に木を構成していく。


\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/parser.pdf}
  \end{center}
  \caption{正規表現から正規表現木への変換の例}
  \label{fig:parser}
\end{figure}

本実装でサポートするメタ文字は、正規表現の基本三演算子\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}

これらの条件踏まえた上で正規表現木を生成していく。

また、以下よりメタ文字を含まない文字や文字クラスのことを文字、文字が連接されている場合を文字列、全ての文字が含まれている場合は正規表現と表現する。

正規表現木は与えられた正規表現を先頭から一文字ずつ読み込み、読み込んだ文字やメタ文字を一定のルールに従って生成していく。
文字やメタ文字、文字クラスは正規表現木のノードとして表現され、メタ文字が現れた時に親子関係が決定される。

文字が読み込まれた場合はノードを生成し、それらが連接された文字は `+' ノードを親ノードとして、左に前の文字、右に後ろの文字が接続される。(図\ref{fig:regexseq})

また、文字列のように連接が連続した場合、連接済みの `+' ノードを左の子ノードとしてさらに `+' ノードで結合していく。(図\ref{fig:regexseq2})

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/regexseq.pdf}
  \end{center}
  \caption{文字の連接}
  \label{fig:regexseq}
\end{figure}

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/regexseq2.pdf}
  \end{center}
  \caption{文字列の連接}
  \label{fig:regexseq2}
\end{figure}

選択 `\textbar' が読み込まれた場合、親ノードを `\textbar'として、 `\textbar' の直前の正規表現は左ノード、直後の正規表現は右ノードとした木が構成される。
`\textbar'は直前と直後の正規表現の関係を表しているので、左右のノードに正規表現の要素を持ったノードとなる。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/regexselect.pdf}
  \end{center}
  \caption{選択}
  \label{fig:regexselect}
\end{figure}

繰返し `*' が読み込まれた場合、`*' の直前の正規表現を左の子ノードとした木が生成される。
また `*' は、`*' の直前の正規表現だけに結合するので、右の子ノードに何かしらのノードが生成されることはない。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/regexasta.pdf}
  \end{center}
  \caption{繰返し}
  \label{fig:regexasta}
\end{figure}


グループ化 `(' `)' が読み込まれた場合、`(' `)'内をひとかたまりの正規表現として木を構成する。
構成後さらに文字列が読み込まれれば、上記のルールにしたがって木が構成される。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/regexgroup.pdf}
  \end{center}
  \caption{グループ}
  \label{fig:regexgroup}
\end{figure}

正規表現が連接した場合も文字の連接と同様に `+' を親ノードとして接続していく。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/regexseqregex.pdf}
  \end{center}
  \caption{正規表現の連接}
  \label{fig:regexseqregex}
\end{figure}


これらのルールに則って正規表現木を構成し、それを元に DFA・NFA を生成していく。

\newpage
\subsection{正規表現木から DFA・NFA の生成}

次に正規表現木から非決定性有限オートマトン(NFA)、決定性有限オートマトン(DFA)を生成する。

オートマトンは、入力に対して状態に対応した処理を行ない結果を出力する仮想的な自動機械である。
正規表現はオートマトンで表現することができるので、状態と入力(ここでは正規表現)が判れば次はどのような状態になるのか示すことができる。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/setstate.pdf}
  \end{center}
  \caption{与えられた正規表現のオートマトンと正規表現木の例}
  \label{fig:set state}
\end{figure}

正規表現木を深さ優先探索にて左から辿っていき、文字のノードにそれぞれ状態を番号で割り振りを行う。
また、状態の振り方は探索した際のメタ文字のノードに沿って割り振りを行う。

それぞれのメタ文字がどのような状態を割り振るか紹介する。
また、番号 1 は初期状態、番号 2 は受理状態を表している。

\newpage

図\ref{fig:stateseq}は連接 `+' で接続されている場合の正規表現である。
受理される文字列の集合は \{ ab \} である。
a が入力されれば別の状態になり、その状態で b が入力されれば受理状態に遷移する。
これより `+' で接続された木の状態割当は、`+' の左ノードの状態とは別の新しい状態を生成して割り当てる。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/stateseq.pdf}
  \end{center}
  \caption{連接の状態割当}
  \label{fig:stateseq}
\end{figure}

図\ref{fig:stateselect}は選択 `\textbar' で接続されている場合の正規表現である。
受理される文字列の集合は \{ a, b \}である。
この場合は a か b が入力されれば受理状態に遷移する。
これより `\textbar' で接続された木の状態割当は、`\textbar' の左ノードと右ノードが同じ状態となり、新しい状態は生成されない。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/stateselect.pdf}
  \end{center}
  \caption{選択 `\textbar' で接続されているときの状態割当}
  \label{fig:stateselect}
\end{figure}

\newpage

図\ref{fig:stateselseq}は連接 `+' と選択 `\textbar' の組み合わせで接続されている場合の正規表現である。
受理される文字列の集合は \{ac,bc\} である。
この場合、初期状態に a か b が入力されると次の状態に遷移し、遷移した状態に c が入力されると受理状態に遷移する。
連接 `+' と選択 `\textbar' の状態割当方法の組み合わせにて状態を決定することができる。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/stateselseq.pdf}
  \end{center}
  \caption{選択 `\textbar' と連接の組み合わせの状態割当}
  \label{fig:stateselseq}
\end{figure}

図\ref{fig:stateasta}は連接 `+' の前の文字に繰返し `*' が接続されている場合の正規表現である。
受理される文字列の集合は \{b,ab,aab,aaab,aa...ab\} である。
この場合、初期状態に a が入力されると自分自身の状態に遷移する。遷移先を自分自身にすることによって、繰返しを表現することができる。
その次に b が入力されると受理状態に遷移する。
これより、`+' の左ノードに `*' が接続されていたら、`*' に接続されている木の一番左と `+' の右ノードに同じ状態が割り当てられる。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/stateasta.pdf}
  \end{center}
  \caption{連接の前の文字に `*' が接続されているときの状態割当}
  \label{fig:stateasta}
\end{figure}

\newpage

図\ref{fig:stateafasta}は連接 `+' の後の文字に繰返し `*' が接続されている場合の正規表現である。
受理される文字列の集合は \{a,ab,abb,abb,abb...bb\} である。
この場合、初期状態に a が入力されると受理状態に遷移する。しかし、受理状態でも b がそれ以降に入力されれば、自分自身に状態遷移する。
これより、`+' の右ノードに `*' が接続されていたら、`+' の左ノードに接続されている木の最後の状態に受理状態を付け加える。また、`*' に接続されている木の最後の状態にも受理状態を付け加える。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/stateafasta.pdf}
  \end{center}
  \caption{連接の後ろの文字に `*' が接続されているときの状態割当}
  \label{fig:stateafasta}
\end{figure}

図\ref{fig:stateasta3}は連接 `+' が連続しており、連接の途中で繰返し `*' が接続されている場合の正規表現である。
受理される文字列の集合は \{ac,abc,abbc,abbbc,abb...bbc\} である。
この場合、初期状態に a が入力されると次の状態に遷移する。その状態で b が入力されると自分自身に遷移し、c が入力されると受理状態に遷移する。

これより、連接中に `*' があれば新しい状態を生成し、その状態を `*' の親ノードのさらに親ノードの右ノードに同じ状態にする。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/stateasta3.pdf}
  \end{center}
  \caption{連接中に `*'が接続されているときの状態割当}
  \label{fig:stateasta3}
\end{figure}

\newpage

図\ref{fig:stateselectasta}は選択 `\textbar' がグループ化によって一つの正規表現となり、それ自身が繰り返されている場合の正規表現である。
受理される文字列の集合は \{c,ac,bc,aabc,abbc,a..ab..bc\} である。
この場合、初期状態に a か b が入力されると自分自身の状態に遷移する。その状態で c が入力されると受理状態に遷移する。
これは、選択 `\textbar' と繰返し `*' の状態割当方法の組み合わせにて状態を決定することができる。
まず `a \textbar b' は同じ状態を割り当て、その親ノードが `*' なので `*' の親の右ノードに同じ状態を割り当てる。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/stateselectasta.pdf}
  \end{center}
  \caption{選択 `\textbar' と繰返し `*' の組み合わせの状態割当}
  \label{fig:stateselectasta}
\end{figure}

\newpage

以上の規則で正規表現木を辿った時にノードに対して状態を割り振る。
まとめると、

\begin{itemize}
\item 左子ノードが `*' でない `+' は新しい状態を作る
\item `\textbar'が親ノードの場合、子ノードの最初の状態は同じ状態。
\item `*' があれば、次の状態は `*' に接続されている木の先頭の状態と同じ。次の状態が受理状態なら先頭の状態と受理状態の組み合わせになる。
\end{itemize}

これにより、正規表現木に状態の割り振りを行ない、入力を行なったら状態が遷移するようにできた。
現在の状態(current state)と入力(input)によって次の状態(next state)が一意に決まっており、それをテーブル化して正規表現をファイルにかける。(図\ref{fig:dfaregex})

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

しかし、生成された正規表現木によっては、現在の状態と入力による次の状態が一意に決まらない場合もある。
図\ref{fig:nfaregex}


\subsection{Subset Construction による NFA から DFA の変換と状態遷移テーブルの生成}

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

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

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

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

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


\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/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/regex/ccinsertresult.pdf}
  \end{center}
  \caption{insert 後の Character Class の二分木}
  \label{fig:ccinsertresult}
\end{figure}


現在のステートに含まれる組み合わせ状態をとってくる

組み合わされた個々の charclass をmerge して新しい charclass をつくり、組み合わせ状態に登録する

生成した状態は stateArray に格納する

新しい状態ができなくなったら終了