% bitencoding or NFA 

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

Cerium に実装している例題として、単語数を数える Word Countとファイルからあるパターンを検索する正規表現を紹介する。

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

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

FileMapReduce の例題として \ref{sec:wc}章の Word Count 内で紹介する。
FileMapReduce のコンストラクタを生成すると、ファイルの分割や文字列処理の 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:TMmain}はFileMapReduce を利用した文字列処理やファイル読み込みの Task の生成部分である。
Cerium Task Manager を利用する際の main 関数は TMmain 関数に置き換わる。
TMmain 関数内で Task の生成や Task の依存関係を記述するのだが、FileMapReduce クラスを利用すると、ファイルを読み込んで文字列処理をするプログラムを容易に実装することができる。

\begin{lstlisting}[frame=lrbt,label=src:TMmain,caption=FileMapReduce による Word Count の生成,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;
    }
    /* 文字列処理後に出力されるデータの数を設定する。
     * Word Count では
     * 行数、単語数、ファイルの先頭に文字があるかどうかの flag、ファイルの末尾に文字があるかどうかの flag
     * の4つのデータが出力される。
     */
    fmp->division_out_size = sizeof(unsigned long long)*4;
    task_init();
    fmp->run_start(manager, filename);
    return 0;
}
\end{lstlisting}

ソースコード\ref{src:Exec}は分割されたファイルに対して何かしらの文字列処理を記述する部分である。
22行目から45行目が Word Count のメインルーチン内で、文字列処理を行なっている部分である。
もし Word Count 以外の文字列処理を記述したいのであれば、メインルーチン内を書き換えてあげればよい。

\begin{lstlisting}[frame=lrbt,label=src:Exec,caption=文字列処理の記述,numbers=left]
SchedDefineTask1(Exec,wordcount);

static int
wordcount(SchedTask *s, void *rbuf, void *wbuf)
{
    // Input Data の設定(FileMapReduceにより自動的に生成される)
    long task_spwaned = (long)s->get_param(0);
    long division_size = (long)s->get_param(1);
    long length = (long)s->get_param(2);
    long out_size = (long)s->get_param(3);
    long allocation = task_spwaned + (long)s->x;
    char* i_data;
    unsigned long long* o_data;
    if (division_size) {
        i_data = (char*)s->get_input(rbuf,0) + allocation*division_size;
        o_data = (unsigned long long*)s->get_output(wbuf,1) + allocation*out_size;
    } else {
        i_data = (char*)s->get_input(0);
        o_data = (unsigned long long*)s->get_output(0);
    }

    // Word Count のメインルーチン
    unsigned long long *head_tail_flag = o_data +2;
    int word_flag = 0;
    int word_num = 0;
    int line_num = 0;
    int i = 0;
    // 先頭が空白か改行かのチェック
    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);
    // Output Data の設定
    o_data[0] = (unsigned long long)word_num;
    o_data[1] = (unsigned long long)line_num;
    return 0;
}
\end{lstlisting}

ソースコード\ref{src:Print}は、それぞれの Task で出力された結果をまとめる処理がまとめられている。
Task それぞれの単語数と行数を集計し、分割された部分に関して整合性をとり単語数を微調整する。
単語数、行数がそれぞれ決定されたのちに結果が print される。

\begin{lstlisting}[frame=lrbt,label=src:Print,caption=結果を集計する Print ルーチン,numbers=left]
#define STATUS_NUM 2

SchedDefineTask1(Print,run_print);

static int
run_print(SchedTask *s, void *rbuf, void *wbuf)
{
    MapReduce *w = (MapReduce*)s->get_input(0);
    unsigned long long *idata = w->o_data;
    long status_num = STATUS_NUM;
    int out_task_num = w->task_num;

    unsigned long long word_data[STATUS_NUM];
    int flag_cal_sum = 0;
    s->printf("start sum\n");
    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;
    for (int i = status_num-1; i >=0; i--) {
        s->printf("%llu ",word_data[i]);
    }
    s->printf("\n");
    return 0;
}
\end{lstlisting}

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


\section{正規表現}
正規表現は文字列のパターンを表現するための方法である。

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}

本実装でサポートするメタ文字は、正規表現の基本三演算子(連接、繰返し、選択)\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 正規表現木から非決定性オートマトン(以下、NFA)か決定性オートマトン(以下、DFA)に変換する。
\item Subset Construction による NFA から DFA への変換をおこなう。
\item DFA を元に文字列検索を行ない結果を返す。
\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.2]{images/regex/regexgroup.pdf}
  \end{center}
  \caption{グループ}
  \label{fig:regexgroup}
\end{figure}

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

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

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.13]{images/regex/allostate.pdf}
  \end{center}
  \caption{与えられた正規表現をオートマトンに変換し、それに基いて正規表現木に状態を割り振る}
  \label{fig:allostate}
\end{figure}

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

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.20]{images/regex/dfaregex.pdf}
  \end{center}
  \caption{どの状態もある入力を与えたとしても遷移先は一意に決定される}
  \label{fig:dfaregex}
\end{figure}


\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.20]{images/regex/nfaex.pdf}
  \end{center}
  \caption{1 入力に対して遷移先が複数存在する(NFA)}
  \label{fig:nfaex}
\end{figure}

\subsection{Subset Construction による NFA から DFA の変換}

生成された正規表現木によっては、現在の状態と入力による次の状態が一意に決まらない場合もある。
図\ref{fig:nfaex}はある状態にある文字を入力すると遷移先が複数存在する場合である。状態 4 に `b' が入力されると状態 2 か状態 4 に遷移する。
このように 1 つの入力に対して遷移先が複数存在すると、どの状態に遷移をしたらよいのかわからくなる。
このようなオートマトンを非決定性オートマトンという。

これを解決する方法として Subset Construction を適用する。

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

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

typedef struct charClass {
    struct charClass *left;
    struct charClass *right;
    Condition cond;
    int stateNum;
    BitVector nextState;
} CharClass, *CharClassPtr;
\end{lstlisting}

Subset Construction は、ある状態から 1 つの入力に対して複数の状態遷移先がある場合、それらの状態 1 つの新しい状態としてまとめ、その新しい状態から新しい遷移先を構成しそれを繰り返す手法である。

状態 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{NFA の例}
  \label{fig:nfa}
\end{figure}

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

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/dfa.pdf}
  \end{center}
  \caption{NFA を Subset Construction によって DFA に変換}
  \label{fig:dfa}
\end{figure}

\newpage

新しい状態が作られたならば、その状態に入力を加えた際の状態遷移も生成する必要がある。
その状態遷移を生成するには、新しい状態の状態の組み合わせの遷移先を組み合わせることによって遷移先が決定される。
(図\ref{fig:subset})

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/subset.pdf}
  \end{center}
  \caption{Subset Construction によって新しく生成された状態の状態遷移の生成}
  \label{fig:subset}
\end{figure}

上の例では文字クラスとある一文字の merge 例になるが、複数の文字クラスを merge するような場面も出てくる。
ある文字クラスに別の文字クラスを merge する場合、図\ref{fig:CharClassMergePattern}のように 13 パターンの場合を考慮しなければならない。
ccRange.Begin は元の文字クラスの先頭、ccRange.End は元の文字クラスの末尾である。元の文字クラスに対して別の文字クラスを merge する。
merge する文字クラスの先頭は insert Character Class Begin、merge する文字クラスの末尾は insert Character Class End である。

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

\newpage
\subsection{並列処理時の整合性の取り方}
正規表現をファイル分割して並列処理をする際、本来マッチングする文章がファイル分割によってマッチングしない場合がある。

図\ref{fig:regexdivide}はその一例である。正規表現 ab*c のマッチングする文字列の集合は {ac,abc,abbc,ab..bc} である。
分割される前はこの文字列 abbbbc は問題なく正規表現 ab*c にマッチングする。


% bit パターンの実装の話
% 正規表現の話を 2 ページずつぐらいで

% charclass 構造体 ソース
% state 構造 bitvector の話 配列を MaxState の分のコードの話
% はやくなった方法 state bit or 状態 merge に計算できる
% subset construction の速度 O(mlogn)

並列処理時、分割されたファイルに対してパターンマッチさせるので、分割された1つ目のファイルの末尾の abb 、2つ目のファイルの先頭に bbc はマッチングしない。
本来分割される前はマッチングする文字列だが、この場合見逃してしまう。
それを解決するために、正規表現にマッチングし始めたファイルの場所を覚えておく。
そして、1つ目のファイルの末尾が状態遷移の途中で終わっていた場合は、結果を集計する際に再度マッチングし始めた場所から正規表現をマッチングさせる。

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