\chapter{Cerium による文字列処理の例題}
本項ではファイルを読み込んで文字列処理を並列処理をする流れと例題を記述する。

Cerium に実装している例題として、Word Count、Boyer-Moore String Search 、正規表現を紹介する。

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

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.15]{images/example/dividefile.pdf}
  \end{center}
  \caption{File 読み込みから処理までの流れ}
  \label{fig:dividefile}
\end{figure}

ファイルを読み込んで文字列処理をする流れを1つのクラスとして Cerium 内に組み込んだ。
Cerium で文字列処理の並列処理を記述する際にこのクラスを利用すれば、
自動的にファイルをある程度のサイズに分割し、文字列処理の Task と結果を表示する Print Task の依存関係も設定される。
このクラスは、ファイルをマッピングし処理をすることで小さいデータの集合を出力することから FileMapReduce と名付けた。

Cerium のプログラムを記述する際には TMmain 関数が C の main 関数に相当する。TMmain 関数内に Task の生成や依存関係を設定する。
これまではファイルを分割して読み込む Task や文字列処理の Task を生成し、依存関係を設定するプログラムを記述していた。
FileMapReduce を実装したことにより、FileMapReduce を呼び出すだけでそれらの設定を行うようになった。

\begin{lstlisting}[frame=lrbt,label=src:TMmain,caption=FileMapReduce を利用する際の TMmain の記述,numbers=left]
int
TMmain(TaskManager *manager, int argc, char *argv[])
{
    char *filename = 0;
    FileMapReduce *fmp = new FileMapReduce(manager,TASK_EXEC,TASK_EXEC_DATA_PARALLEL,TASK_PRINT);
    filename = fmp->init(argc, argv);
    if (filename < 0) {
        return -1;
    }
    fmp->division_out_size = sizeof(unsigned long long)*4;
    task_init();
    fmp->run_start(manager, filename);
    return 0;
}
\end{lstlisting}

% 箇条書きで OK
\begin{itemize}
\item \verb+TASK_EXEC+ 計算を行う Task
\item \verb+TASK_EXEC_DATA_PARALLEL+ GPU にて計算を行う Task
\item \verb+TASK_PRINT+ 結果を集計する Task
\end{itemize}

% option を解釈して mmap や bread の説明 OK
ソースコード\ref{src:TMmain}の 7行目の \verb+init+ で option が解釈される。
option では Task を実行するときの CPU 数や、読み込み方法(mmap か Blocked Read)など設定できる。

11行目\verb+division_out_size+ では、計算を行う Task の出力されるデータ数を設定できる。

% run_start を説明する OK?
12行目の \verb+run_start+ によって読み込む Taskと計算を行う Task が生成される。
ここで Task の依存関係が設定される。

文字列処理の Task と結果の整合や表示を行う Print Task をそれぞれ決められたフォーマットに沿って記述すればよい。
ファイルを分割して文字列処理を行なった際、分割された部分でそれぞれの例題の整合性が取れなくなってしまうことがある。

文字列処理や結果の整合性の取り方についてはそれぞれの例題にて述べる。

\section{Word Count}
\label{sec:wc}
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}では単語で分割された場合である。
分割された1つ目のファイルは単語数 1 となる。単語と認識されるためには空白か改行が必要である。
しかし1つ目のファイルには空白または改行が 1 つしか含まれていないため、単語数は 1 となってしまう。
2つ目のファイルは改行が 2 つあるにも関わらず、単語数は 1 となる。
ファイルの先頭に空白、改行が含まれていた場合は単語が現れていないにも関わらず単語数 1 とカウントされてしまう。
この場合は単語数をカウントしないようにする。

分割されたファイルそれぞれの結果を合計すると単語数 2、行数 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 足すことにより整合性を取ることができる。
ソースコード\ref{src:Print}の17-20行目にてその処理を行なっている。

\begin{lstlisting}[frame=lrbt,label=src:Exec,caption=Word Countの記述,numbers=left]
SchedDefineTask1(Exec,wordcount);

static int
wordcount(SchedTask *s, void *rbuf, void *wbuf)
{
    unsigned long long *head_tail_flag = o_data +2;
    head_tail_flag[0] = (i_data[0] != 0x20) && (i_data[0] != 0x0A);
    word_num -= 1-head_tail_flag[0];
    for (; i < length; i++) {
        if (i_data[i] == 0x20) { // 空白
            word_flag = 1;
        } else if (i_data[i] == 0x0A) { // 改行
            line_num += 1;
            word_flag = 1;
        } else {
            word_num += word_flag;
            word_flag = 0;
        }
    }
    word_num += word_flag;
    head_tail_flag[1] = (i_data[i-1] != 0x20) && (i_data[i-1] != 0x0A);
    o_data[0] = (unsigned long long)word_num;
    o_data[1] = (unsigned long long)line_num;
    return 0;
}
\end{lstlisting}

ソースコード\ref{src:Exec} の9-19行目で行数と単語数を数えている。
\verb+head_tail_flag+ はファイルの先頭と末尾に空白か改行があればどうかのフラグを立てる。
Word Count Task は単語数、行数、\verb+head_flag+、\verb+tail_flag+ の4つのデータを出力する。

\begin{lstlisting}[frame=lrbt,label=src:Print,caption=Word Count の Print Task,numbers=left]
#define STATUS_NUM 2

static int
run_print(SchedTask *s, void *rbuf, void *wbuf)
{
    long status_num = STATUS_NUM;
    unsigned long long word_data[STATUS_NUM];
    int flag_cal_sum = 0;
    for (int i = 0; i < STATUS_NUM; i++) {
        word_data[i] = 0;
    }
    int out_size = w->division_out_size / sizeof(unsigned long long);
    for (int i = 0; i < out_task_num ; i++) {
        word_data[0] += idata[i*out_size+0];  // 単語数の集計
        word_data[1] += idata[i*out_size+1];  // 行数の集計
        unsigned long long *head_tail_flag = &idata[i*out_size+2];
        if((i!=out_task_num-1)&&
           (head_tail_flag[1] == 1) && (head_tail_flag[4] == 0)) {
            flag_cal_sum++;
        }
    }
    word_data[0] += flag_cal_sum;
}
\end{lstlisting}

ソースコード\ref{src:Print}は、それぞれの Task で出力された結果をまとめる処理がまとめられている。
13-22行目にて Word Count Task で出力された単語数と行数を集計する。
また、\verb+head_tail_flag+の付け合せで分割された部分に関して整合性をとる。
単語数、行数がそれぞれ決定されたのちに結果が Print される。

\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.5\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.5\textwidth]{images/example/bmsearchinlucde.pdf}
\end{center}
\caption{pattern に含まれている文字で不一致になった場合}
\label{fig:bmsearchinclude}
\end{figure}

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

不一致が起きたときの文字によって数文字分だけ後ろにずらす skip table を、文字列探索する前に生成する必要がある。

text 分割時に、分割部分で pattern が含まれる場合が存在する。
その場合は、本来の読み込み部分の text の長さ $L$ に加えて、pattern の長さ $s$ から 1 引いた数だけ多く読みこむように設計することで、正しく結果を算出することができる。
(図\ref{fig:iodivsuc})

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.8\textwidth]{images/example/iodivsuc.pdf}
\end{center}
\caption{分割周りの処理}
\label{fig:iodivsuc}
\end{figure}

\newpage

\begin{lstlisting}[frame=lrbt,label=src:bmTMmain,caption=Boyer-Moore String Search の TMmain,numbers=left]
typedef struct bm {
    int* skip_table;
    unsigned char *search_word;
    int search_word_len;
} BM, *BMPtr;

//Boyer Moore String Search で使用する skip table を作成
static void
create_BMskiptable(BMPtr bm)
{
    bm->skip_table = (int*)malloc(sizeof(int)*256);
    for (int i = 0; i < 256; ++i) {
        bm->skip_table[i] = bm->search_word_len;
    }

    for (int j = 0; j < bm->search_word_len - 1; ++j) {
        bm->skip_table[bm->search_word[j]] = bm->search_word_len - j - 1;
    }
}

int
TMmain(TaskManager *manager, int argc, char *argv[])
{
    BMPtr bm = new BM;
    bm->skip_table = (int*)malloc(sizeof(int)*256);
    for (int i = 1; i < argc; i++) {
        if (strcmp(argv[i],"-sw") == 0) {
            bm->search_word = (unsigned char*)argv[i+1]; i++;
            bm->search_word_len = strlen((const char*)bm->search_word);
            create_BMskiptable(bm);
        }
    }
    fmp->w->global = (void*)bmp;
    fmp->overrap = bmp->search_word_len - 1;
    fmp->division_out_size = sizeof(unsigned long long);
    task_init();
    fmp->run_start(manager, filename);
    return 0;
}
\end{lstlisting}

ソースコード\ref{src:bmTMmain} 27 行目で検索する文字列を取得する。
その後、検索文字列と文字列の長さを取り、それに基いて \verb+skip_table+ を生成する。
そして Boyer-Moore String Search に必要な情報を bm という構造体にまとめ、この構造体をそれぞれの Task に送信している。

%check global の説明 IJ
33行目 \verb+w->global+ で検索時に必要な情報を渡している。
\verb+w->global+で設定されたデータは、計算する Task や Print する Task でも利用することが可能になる。

ソースコード\ref{src:bmexec}の 28 行目にて、TMmain で設定した \verb+bmp+ を受け取っている。

\begin{lstlisting}[frame=lrbt,label=src:bmexec,caption=Boyer-Moore String Search の記述,numbers=left]
static int BM_method(unsigned char *text,int text_len,
              unsigned char *pattern,int sw_len,int *skip)
{
    int i = sw_len - 1;
    int match_counter = 0;

    while ( i < text_len){
        int j = sw_len - 1;
        // pattern の末尾から比較していく
        while (text[i] == pattern[j]){
            if (j == 0){
                match_counter++;
            }
            --i;
            --j;
        }
        i = i + max(skip[text[i]],sw_len - j);
    }
    return match_counter;
}

static int
task_exec(SchedTask *s, void *rbuf, void *wbuf)
{
    unsigned char *i_data = (unsigned char *)s->get_input(0);
    int length = (int)s->get_inputSize(0);
    MapReduce *w = (MapReduce*)s->get_param(4);
    BMPtr bm = (BMPtr)w->global;

    unsigned long long *o_data = (unsigned long long*)s->get_output(0);

    o_data[0] = BM_method(i_data,length,bm->search_word,bm->search_word_len,bm->skip_table);
    return 0;
}
\end{lstlisting}
ソースコード\ref{src:bmexec} の3-20行目は Boyer-Moore String Search のメインルーチンである。
pattern の末尾から比較していき、pattern の先頭までマッチしたら、カウンターを 1 増やす。

17行目は比較して一致しなかった場合であり、ミスマッチを起こしたファイルの文字を見て pattern を後ろにいくつずらすか決定される。

\begin{lstlisting}[frame=lrbt,label=src:bmprint,caption=Boyer-Moore String Search の Print Task,numbers=left]
static int
print_task(SchedTask *s, void *rbuf, void *wbuf)
{
    MapReduce *w = (MapReduce*)s->get_input(0);
    unsigned int idata_task_num = w->task_num;
    int match_counter = 0;
    for (int i = 0;i < idata_task_num;i++) {
            match_counter += idata[i];
    }
    return 0;
}
\end{lstlisting}
ソースコード\ref{src:bmprint} で

\section{正規表現}
% 正規表現の話を 2 ページずつぐらいで
正規表現は文字列のパターンを表現するための方法である。

BOSE という文字列をファイルから検索する場合を例にとる。
BOSE という文字列は、そのファイルに Bose もしくは bose と記述されているかもしれない。
もし、BOSE で検索すると小文字が含まれている Bose、bose は検索の対象外となってしまい、それら一つ一つを検索するのは手間が掛かってしまう。

このようなあるパターンで文字列を表現できる場合は、正規表現を利用すればこの問題は簡単に解決することができる。
正規表現にはメタ文字と呼ばれる正規表現内での特殊記号があり、それらを利用することによって BOSE、Bose、bose の 3 つの文字列を一つの正規表現で表現することができる。
(図\ref{fig:regexbasic})

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=0.6\textwidth]{images/regex/regexbasic.pdf}
\end{center}
\caption{3つの表記ゆれの文字列を1つの正規表現にまとめる}
\label{fig:regexbasic}
\end{figure}

\newpage
本実装でサポートするメタ文字は、正規表現の基本三演算子(連接、繰返し、選択)\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}

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

\begin{enumerate}
\item 与えられた正規表現を構文解析し、正規表現木に変換
\item 正規表現木への状態の割当
\item Subset Construction による状態の変換
\item 正規表現マッチャの並列処理の実装
\end{enumerate}

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

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

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

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

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

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

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

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

\newpage

選択 `\textbar' が読み込まれた場合、親ノードを `\textbar'として木を構成していく。
`\textbar' の直前の文字、文字クラスまたは正規表現は左ノード、直後の文字、文字クラスまたは正規表現は右ノードとした木が構成される。
`\textbar'は直前と直後の正規表現の関係を表しているので、左右のノードに正規表現の要素を持ったノードとなる。
(図\ref{fig:regexselect})

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


繰返し `*' が読み込まれた場合、`*' の直前の正規表現を左の子ノードとした木が生成される。
また `*' は、`*' の直前の文字や文字クラス、正規表現だけに結合するので、右の子ノードに何かしらのノードが生成されることはない。
(図\ref{fig:regexasta})

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

\newpage

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

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

正規表現が連接した場合も文字の連接と同様に `+' を親ノードとして接続していく。
(図\ref{fig:regexseqregex})

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

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

\newpage
\subsection{正規表現木への状態の割当}

次に正規表現木に状態を割り当てて、非決定性有限オートマトン(NFA)を生成する。
正規表現木のノードに対して一定のルールに沿って状態を割り当てていく。

% /**
%     pass 1 : 正規表現に必要な状態を探して、それぞれに番号を割り振る
%         前が * でない + は新しく状態を作る
%         * があったら、次の状態はその時の先頭の状態か次の状態が終了状態ならば終了状態との組み合わせになる
%         常に先頭の状態を返す
%         最後が*ならば、それを持ち歩く
%     pass 2: 
%         割り当てられた状態に沿って charclass の行き先を書き換える
%         書き換えた charclass を merge する
%         前の部分に * がない + は新しい状態をつくるので、state を切り替えて生成する
%  */

\begin{lstlisting}[frame=lrbt,label=src:generateTransition,caption=正規表現木の状態割当,numbers=left]
typedef struct tgValue {
    StatePtr asterisk;   // last * state of the expression
    StatePtr startState; // startState of the expression
    StatePtr endState;
    TransitionGeneratorPtr tg;
} TGValue, *TGValuePtr;

TGValue generateTransition(NodePtr n,TGValue tgv, int pass) {
    if (n->tokenType == '+') {
        TGValue tgvLeft = tgv;
        tgvLeft.endState = n->right->state;
        tgvLeft.asterisk = NULL;
        tgvLeft = generateTransition(n->left,tgvLeft,pass);
        TGValue tgvRight = tgv;
        if (tgvLeft.asterisk) {
            n->right->state = tgv.endState;
            tgvRight.startState = tgvLeft.asterisk;
            tgvRight = generateTransition(n->right,tgvRight,pass);
            tgvLeft.asterisk = tgvRight.asterisk;
            return tgvLeft;
        }
        tgvRight.asterisk = NULL;
        if (pass==1) {
            n->right->state = tgvRight.startState = createState(tgvRight,n->right);
        } else {
            tgvRight.startState = n->right->state;
            tgvRight.tg->stateArray[tgvRight.startState->bitState.bitContainer] = tgvRight.startState ;
        }
        tgvRight = generateTransition(n->right,tgvRight,pass);
        if (tgv.endState && tgvRight.asterisk) tgvRight.startState->accept = tgv.endState->accept;
        tgvLeft.asterisk = tgvRight.asterisk;
        return tgvLeft;
    } else if (n->tokenType == '|') {
        TGValue tgv1  = generateTransition(n->left,tgv,pass);
        tgv1.endState = tgv.endState;
        TGValue tgv2 = generateTransition(n->right,tgv1,pass);
        return tgv2;
    } else if (n->tokenType == '*') {
        TGValue tgvAstah = tgv;
        tgvAstah.endState = tgvAstah.startState;
        if (pass==2) tgvAstah.endState->accept = tgv.endState->accept;
        tgvAstah = generateTransition(n->left,tgvAstah,pass);
        tgvAstah.asterisk = tgvAstah.startState;
        return tgvAstah;
    } else if (n->tokenType == 'c' || n->tokenType == 'a'){
        TGValue tgv1 = tgv;
        if (pass==1) {
            n->stateNum = tgv.startState->stateNum;
            n->state = tgv.startState;
        } else {
            int nextState = tgv.endState->stateNum;
            n->nextStateNum = nextState;
            n->nextState = tgv.endState;
            BitVector bi = createBitVector(nextState);
            if (n->nextState->accept) bi = bitSet(bi,1);
            setState(n->cc,bi);
            tgv1.startState->cc = mergeTransition(tgv1.startState,n->cc);
        }
        return tgv1;
    } else {
        return tgv;
    }
}
\end{lstlisting}

ソースコード\ref{src:generateTransition}は、正規表現木を二度通すことによって状態割当と遷移先を設定するルーチンである。
一度目は正規表現に必要な状態を探して、それぞれに状態を振っていく。
\verb+generateTransition+ は \verb+TGValue+ を常に持ち歩いて状態を割り当てる。
9-32行目は `+' ノードが来た時の処理である。
tgv を tgvLeft にコピーしたのち左のノードに降りていく。
もし tgvLeft に asterisk が含まれていたら、endState を`+'ノードの右ノードに割り振る。
そして、左の asteriskの状態 を右の startState に割り振った後に右ノードに降りていく。
右ノードに降りていった際にも asterisk があるかどうか確認し、その情報を左の asterisk にコピーし、左の tgv を返す。
tgvLeft に asterisk が無ければ、新しい状態を生成して tgvRight と右ノードそれぞれに状態割り振る。
その後、右ノードに降りていく。
もし、tgvがendStateで、tgvRight が asterisk であれば、tgvの endState が受理状態を tgvRight.startState にコピーする。
その後 tgvLeft を返す。

34-37行目は `\textbar' ノードが来た時の処理である。
`\textbar' の左ノードに下り、tgv1を生成する。
tgv.endState を tgv1.endState にコピーしたのち、右ノードに下る際に tgv1 を食わせる。
右ノードが下り終わったら tgv2 が返されるので、これを返す。

39-44行目は `*' ノードが来た時の処理である。
tgvAstah は startState と endState を同じ状態にする。
左ノードに下って行く際、tgvAstah を食わせて、その結果を tgvAstah に代入する。
tgvAstah の asterisk の状態を tgvAstah の startState にしたあとに tgvAstah を返す。

46-59行目は文字もしくは文字クラスのノードが来た時の処理である。
このとき、ノードに番号と状態を割り振る。

二度目は割り当てられた状態に沿って文字クラスの行き先を書き換え、それを merge する。
前の部分に * がない + は新しい状態をつくるので、state を切り替えて生成する。

%書いててもわからんん・・・・

([a-zA-Z]\textbar ab*)*aa

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.17]{images/regex/allostate.pdf}
  \end{center}
  \caption{与えられた正規表現木に状態を割り振る}
  \label{fig:allostate}
\end{figure}

% これにより、正規表現木に状態の割り振りを行ない、入力を行なったら状態が遷移するようにできた。
% 現在の状態(current state)と入力(input)によって次の状態(next state)が一意に決まっており、それをテーブル化して正規表現をファイルにかける。(図\ref{fig:dfaregex})
% このように、ある状態にある入力を与えると次の状態の遷移先が一意に決まるオートマトンのとこを決定性オートマトン(DFA)という。
% 
% \begin{figure}[htpb]
%   \begin{center}
%     \includegraphics[scale=0.20]{images/regex/dfaregex.pdf}
%   \end{center}
%   \caption{どの状態もある入力を与えたとしても遷移先は一意に決定される(DFA)}
%   \label{fig:dfaregex}
% \end{figure}
% 
% 生成された正規表現木によっては、現在の状態と入力による次の状態が一意に決まらない場合もある。
% 1 つの入力に対して遷移先が複数存在するようなオートマトンを非決定性オートマトン(NFA)という。
% 
% \begin{figure}[htpb]
%   \begin{center}
%     \includegraphics[scale=0.20]{images/regex/nfaex.pdf}
%   \end{center}
%   \caption{1 入力に対して遷移先が複数存在する(NFA)}
%   \label{fig:nfaex}
% \end{figure}
% 
% \newpage

1 入力に対して遷移先が複数存在している場合は、文字によって場合分けをする必要がある。
図\ref{fig:nfa} の
状態 4 は [a-z] が入力されると状態 4 に遷移し、b が入力されると状態 2 に遷移する。このとき、b が入力されると状態 2 か状態 4 のどちらかに遷移することになる。(図\ref{fig:nfa})

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/nfa.pdf}
  \end{center}
  \caption{b が入力されるとどちらに遷移すればいいのかわからない}
  \label{fig:nfa}
\end{figure}

このとき、状態 2 と 4 を組み合わせて一つの状態を新しく作り、その状態に遷移させる。新しく作られる状態の数は状態の組み合わせなので、その状態の組み合わせの和をとっている。
これより、状態 4 に a か [c-z] を入力すると状態 4 に遷移し、b が入力されると新しい状態 2,4 に遷移する。
このような変換をすることによって、入力によって遷移先が一意に決定されるようになる。
(図\ref{fig:dfa})

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/dfa.pdf}
  \end{center}
  \caption{b が入力されたときは新しい状態を作り、新しい状態に遷移させる}
  \label{fig:dfa}
\end{figure}

\subsection{Subset Construction による状態の変換}
組み合わされた状態からそれぞれの状態の場合分けをたどって、さらに別な組み合われた状態が生成される。
新しい状態の組み合わせが出てこなくなるまでこれを繰り返す。
これを Subset Construction と呼ぶ。
ここでは状態の表現に BitVector を用いる。
1つの Bit が正規表現に割り振られた Base 状態に対応する。
組み合わされた状態は、複数の Bit が立っていることにより表される。
状態の組み合わせは、BitVector の論理和によって簡単に計算される。
(図\ref{fig:bitvector})

\newpage

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/bitvector.pdf}
  \end{center}
  \caption{状態の論理和}
  \label{fig:bitvector}
\end{figure}

\
% charclass 構造体 ソース
\begin{lstlisting}[frame=lrbt,label=src:cc,caption=文字クラス(charClass)の構造体,numbers=left]
typedef struct utf8Range {
    unsigned long begin;
    unsigned long end;
} RangeList , *RangeListPtr;

typedef struct condition {
    RangeList range;
    Word w;
} Condition, *ConditionList;

typedef struct charClass {
    struct charClass *left;
    struct charClass *right;
    Condition cond;
    int stateNum;
    BitVector nextState;
} CharClass, *CharClassPtr;
\end{lstlisting}
%ソースコードの説明 OK
ソースコード\ref{src:cc}は文字クラスの構造体である。正規表現木の各ノードそれぞれにこの構造体を持っている。
文字クラスは二分木で構築されている。
文字クラスの範囲は Condition 内の RangeList の begin と end に設定される。
それぞれの二分木に文字の範囲である Condition を持っている。
その Condition の範囲内の文字の入力があれば、次の状態 nextState に遷移する。

% Condition には Word も格納できるようにしている。
% 現段階の実装では、BitVector の最大数は 64 で制限されている。
% 一つ一つの文字に状態を割り振るとすぐに上限に達する恐れがある。
% 
% 状態数を節約する工夫として、文字列を 1 の状態として割り当てることにより、文字列の長さ分だけ節約することができる。
% 図\ref{fig:wordstate}は、`word' という文字列の正規表現の正規表現木、DFA 及び状態遷移テーブルである。
% \begin{figure}[htpb]
%   \begin{center}
%     \includegraphics[scale=0.17]{images/regex/wordstate.pdf}
%   \end{center}
%   \caption{状態割当を一文字から文字列にすることにより、状態数を節約できる。}
%   \label{fig:wordstate}
% \end{figure}

図\ref{fig:sc} に2つの状態があり、それぞれに入力と遷移先がある。
これら 2 つの状態を一つの状態として表現し、新しく状態遷移図を生成する。
もし、文字クラスの範囲が重なっている場合は、遷移先の状態を組み合わせて新しい状態を生成する。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/sc.pdf}
  \end{center}
  \caption{Subset Construction による新しい状態の生成}
  \label{fig:sc}
\end{figure}

ある文字クラスの範囲に別の文字クラスの範囲が重なり、さらにそれぞれの文字クラスの遷移先が異なる場合、図\ref{fig:CharClassMergePattern}のような 13 パターンの場合分けを考慮しなければならない。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/CharClassMergePattern.pdf}
  \end{center}
  \caption{複数の文字クラスを Merge するときの全パターン}
  \label{fig:CharClassMergePattern}
\end{figure}

\subsection{正規表現マッチャの並列処理の実装}

% % bit パターンの実装の話
% 今回の実装では、状態それぞれを Bit Pattern で表現している。
% Bit Pattern で状態を持つことで、Subset Construction による状態の組み合わせも Bit Pattern の和を取ることで容易に表現できる。
% % state 構造 bitvector の話 配列を MaxState の分のコードの話
% それらの状態は StateArray と呼ばれる配列で格納されており、状態遷移が行われるたびに StateArray を見に行く。
% あらかじめ配列の大きさのメモリを確保する必要があるが、Subset Construction による新しい状態生成も考慮しなければならない。
% 正規表現木に状態を割り振った時に最大の状態の Bit は分かっているので、その状態の Bit の 2 倍だけ配列を確保しておけば、Bit Pattern が全て 1 までの状態を表現することができる。
% 
% StateArray を見れば、ある状態に対して入力をすると状態の遷移先をチェックすることができる。
% 状態の遷移先は文字クラスごとの List 構造になっており、入力された文字をチェックしながらリストを辿って状態の遷移先を判断する。
% (図\ref{fig:statearray})
% 
% \begin{figure}[htpb]
%   \begin{center}
%     \includegraphics[scale=0.2]{images/regex/statearray.pdf}
%   \end{center}
%   \caption{StateArray による状態遷移}
%   \label{fig:statearray}
% \end{figure}

% subset construction の速度 O(mlogn)

\begin{lstlisting}[frame=lrbt,label=src:ceriumTMmain,caption=ceriumGrep の TMmain,numbers=left]
typedef struct transitionGenerator {
    long totalStateCount;
    long totalBasicState;
    StateStackPtr stack;
    StatePtr stateEnd;
    StatePtr stateStart;   // start state without accept flag
    StatePtr *stateArray;
    StatePtr stateList;
    StatePtr anyState;
    tsValue (*stateSkip)(tsValue tsv);
    tsValue (*stateMatch)(tsValue tsv);
    tsValue (*stateNothing)(tsValue tsv);
} TransitionGenerator, *TransitionGeneratorPtr;

void
ceriumCreateAnyState(TransitionGeneratorPtr tg) {
    tg->stateSkip = stateSkip;
    tg->stateMatch = stateMatch;
    tg->stateNothing = stateNothing;
    createAnyState(tg);
    generateTState(tg->anyState,tg);
    // generateTState for startState. It is used in stateMatch.
    generateTState(tg->stateList,tg);
    tg->stateStart = NEW(State);
    *tg->stateStart = *tg->stateList;
    tg->stateStart->accept = false; // Start state never accept
    generateTState(tg->stateStart,tg);
}

int
TMmain(TaskManager *manager, int argc, char *argv[])
{
    char *filename = 0;
    Search s = grep(argc,argv,true);  // 正規表現木の生成、木の状態割り振りを行う
    FileMapReduce *fmp = new FileMapReduce(manager,TASK_EXEC,TASK_EXEC_DATA_PARALLEL,TASK_PRINT);

    ceriumCreateAnyState(s.tg);

    filename = fmp->init(argc, argv);
    fmp->w->global = (void*)s.tg;
    if (filename < 0) {
        return -1;
    }
    fmp->division_out_size = sizeof(void*)*3; // *Result,*blockBegin,*blockEnd
    task_init();
    fmp->run_start(manager, filename);
    return 0;
}
\end{lstlisting}

ソースコード\ref{src:ceriumTMmain}は、ceriumGrep の Task 生成部分である。
34行目で正規表現木の生成や状態割り振り、NFAの生成を行う。
40行目に初期状態や受理状態、マッチした時の関数ポインタなど状態遷移に関する情報がまとまった \verb+TransitionGenerator+ を Task 側に渡す。

\begin{lstlisting}[frame=lrbt,label=src:ceriumGreptask,caption=ceriumGrep Task,numbers=left]
TSValue blockSearch(TSValue tsv,Buffer buff,int task_spawned) {
    tsv.current = tsv.tg->stateStart->tState;
    tsv.blk->result = NULL;
    ResultPtr result = NULL;
    tsv.blk->resultEnd = &result;
    tsv.blk->blockBegin = tsv.current;
    addResult(tsv,true,buff.buff,buff.buffend);  // entire buffer
    tsv = tSearch(tsv);  // Matching
    tsv.blk->blockEnd = tsv.current;
    if (tsv.blk->blockEnd->state->bitState.bitContainer != 1) {
        if (tsv.matchBegin != tsv.buff.buffptr) {
            // partial match case at block end.
            addResult(tsv,true,tsv.matchBegin,tsv.matchEnd);
        }
    }
    tsv.blk->result = result;
    return tsv;
}

static int
blockedGrep(SchedTask *s, void *rbuf, void *wbuf)
{
    TransitionGeneratorPtr tg = (TransitionGeneratorPtr)w->global;
    Buffer buff;
    buff.buff = buff.buffptr = i_data;
    buff.buffend = buff.buff + length;
    BlockOutput blk;
    TSValue tsv = createTSValue(tg,buff);
    tsv.blk = &blk;
    tsv = blockSearch(tsv,buff,task_spawned);
    o_data[0] = (unsigned long)tsv.blk->result;
    o_data[1] = (unsigned long)tsv.blk->blockBegin->state;  // never used now
    o_data[2] = (unsigned long)tsv.blk->blockEnd->state;
    return 0;
}
\end{lstlisting}

ソースコード\ref{src:ceriumGreptask}は、並列実行でマッチングを行う Task である。
文字列と正規表現のマッチングは 8 行目の \verb+tSearch+ で行われている。

%tSearch の話
\begin{lstlisting}[frame=lrbt,label=src:tSearch,caption=tSearch,numbers=left]
TSValue tSearch(TSValue tsv) {
    next: while (tsv.buff.buffptr < tsv.buff.buffend) {
        tsv = tsv.current->stateMatch(tsv);
        if (tsv.current->ccvSize==0) {
            // matched start again
            tsv.current = tsv.tg->stateStart->tState;
        }
        unsigned char c = *tsv.buff.buffptr++;
        for (int i = 0; i < tsv.current->ccvSize; i++) {
            CCVPtr ccv = &tsv.current->ccv[i];
            if (c<ccv->begin) {
                tsv.current = tsv.tg->stateStart->tState;
                tsv = tsv.current->stateSkip(tsv);
                goto next;
            } else if (c<=ccv->end) {
                // range matched.
                if (ccv->w.word) {
                    // match the word.
                    // if (not match) continue;
                }
                if (ccv->tState) {
                    tsv.current = ccv->tState;
                } else {
                    tsv.current = nextTState(ccv->state,tsv.tg);
                    ccv->tState = tsv.current;
                }
                goto next;
            }
        }
        tsv.current = tsv.tg->stateStart->tState;
        tsv = tsv.current->stateSkip(tsv);
    }
    return tsv;
}
\end{lstlisting}
ソースコード\ref{src:tSearch}は、正規表現のマッチングを行う関数である。


% Print の分割部分の話追加 最後
分割されたファイルに対して正規表現によるマッチングを行う。
\begin{lstlisting}[frame=lrbt,label=src:result,caption=Resultの構造体,numbers=left]
typedef struct result {
    unsigned char *begin;
    unsigned char *end;
    bool continued;
    struct result *next;
} Result, *ResultPtr;
\end{lstlisting}
ソースコード\ref{src:result}では、
マッチングの始まりのファイルの場所と終わりのファイルの場所を保存する。
マッチングの数だけこの構造体が生成され、これらは List 構造として結果をまとめていく。

全ての分割されたファイルに対してマッチングが終了すると、Print Task にてまとめてマッチした部分を表示する。

正規表現をファイル分割して並列処理をする際、本来マッチングする文章がファイル分割によってマッチングしない場合がある。
図\ref{fig:regexdivide}はその一例である。
並列処理時、分割されたファイルに対してパターンマッチさせるので、分割された1つ目のファイルの末尾の abb 、2つ目のファイルの先頭に bbc はマッチングしない。
本来分割される前はマッチングする文字列だが、この場合見逃してしまう。
それを解決するために、正規表現にマッチングし始めたファイルの場所を覚えておく。

そして、1つ目のファイルの末尾が状態遷移の途中で終わっていた場合(状態 1 でない場合)は、結果を集計する際に再度マッチングし始めた場所から正規表現をマッチングさせる。

\newpage
\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.3]{images/regex/regexdivide.pdf}
  \end{center}
  \caption{分割された部分に正規表現がマッチングする場合の処理}
  \label{fig:regexdivide}
\end{figure}


\newpage
\begin{lstlisting}[frame=lrbt,label=src:regexprint,caption=マッチした結果を Print する,numbers=left]
static
TSValue stateSkipOnce(TSValue tsv) {
    if (tsv.matchEnd) {
        addResult(tsv,false,tsv.matchBegin,tsv.matchEnd);
    }
    tsv.buff.buffend = tsv.buff.buffptr;    // end search
    return tsv;
}

static int
run_print(SchedTask *s, void *rbuf, void *wbuf)
{
    ResultPtr prev = NULL;
    for (int i = 0; i < out_task_num ; i++) {
        ResultPtr r = (ResultPtr)w->o_data[i*out_size+0];
        //  first reply contains block begin and block end
        unsigned char *begin = r->begin;
        unsigned char *end = r->end;
        r = r->next;
        if (r == NULL) {
            prev = NULL;
            continue;
        }
        if (prev) {
            if (i >= out_task_num) break;
            // 最後のブロックでなく、前の prevBlockEnd が state 1 でない場合)
            StatePtr prevBlockEnd = (StatePtr)w->o_data[i*out_size-1];
            if (prevBlockEnd->bitState.bitContainer !=1) {
                // そこから最初の stateSkip までやり直し。マッチしたら表示。
                TransitionGeneratorPtr tg = (TransitionGeneratorPtr)w->global;
                tg->stateSkip = stateSkipOnce;
                Buffer buff;
                buff.buff = buff.buffptr  = begin;
                buff.buffend = end;
                TSValue tsv = createTSValue(tg,buff);
                BlockOutput blk;
                tsv.blk = &blk;
                tsv.current = prevBlockEnd->tState;
                tsv.blk->result = NULL;
                ResultPtr result = NULL;
                tsv.blk->resultEnd = &result;
                tsv.matchBegin = prev->begin;
                tsv.matchEnd = prev->end;
                tsv = tSearch(tsv);
                if (result) {
                    resultPrint(result,"Print");
                }
            }
        }
        prev = resultPrint(r,"Print");
    }
    return 0;
}
\end{lstlisting}

ソースコード\ref{src:regexprint}ではそれぞれの Task でマッチングした文字列を出力する。
27-48行目がファイルの末尾が状態遷移の途中で終わった時の処理である。
マッチングし始めたときのファイルの場所から再度マッチングするかどうか確認する。
そして、マッチングしたら 46 行目で Print する。

このマッチングは Print Task にて実行されるので、single thread で処理される。
そのため、分割された部分で状態遷移の途中で終わっている場合が多ければそれだけ集計時の処理が重くなる。