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

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

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

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

\newpage

ソースコード\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}


\newpage

ソースコード\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}に文字クラスとグループを加えている。

連接はメタ文字を含まない文字列で構成された正規表現である。
`word' や `automaton' などの文字列も連接のみの正規表現の一部である。
正規表現の演算子には必ず何かしらの記号が割り当てられるのだが、連接だけにはメタ文字が割り振られていない。

繰返しは `*' の直前の文字または正規表現の繰返しを表現するメタ文字である。
`*' の直前の文字や正規表現の 0 回以上の繰返しを表している。
`a*b' という正規表現にマッチする文字列は {b,ab,aab,aaab,aa...b} である。

選択 `\textbar' は`\textbar' 前後の文字または正規表現の選択を表すメタ文字である。
`a\textbar b' という正規表現にマッチする文字列は {a,b} である。

文字クラス`['`]' は`['`]'内に記述した文字の範囲から任意の一文字を選択するメタ文字である。
数字の中から任意の1文字を選択だけの正規表現で表現すると、

$`0 \verb||| 1 \verb||| 2 \verb||| 3 \verb||| 4 \verb||| 5 \verb||| 6 \verb||| 7 \verb||| 8 \verb||| 9'$
となる。
この正規表現でも正しいのだが、とても煩わしい正規表現である。これを簡潔に表現できるのが文字クラスの強みである。
文字クラスで数字の中から任意の一文字を表現すると `[0-9]' と表現することができる。
数字だけではなく、アルファベットの中から任意の一文字も `[A-Za-z]' と表現することができる。

グループ`('`)' は `('`)' 内に記述した正規表現を一旦まとめる機能を持つ。
例えば、word という文字列の 0 回以上の繰返しの正規表現を記述する。
$ `word*' $ と表現すると、`*' の直前の `d' だけに接続される。この正規表現にマッチする文字列は{wor, word, wordd, worddd, wordd...d} となり、word の繰返しではない文字列がマッチする。
`word' という文字列の繰返しを表現するときは、`(word)*'と記述することで表現できる。

これらのメタ文字をまとめた表が以下の表\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 NFA に変換された場合、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.3]{images/regex/regexseq.pdf}
  \end{center}
  \caption{文字の連接}
  \label{fig:regexseq}
\end{figure}

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

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.3]{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.3]{images/regex/regexselect.pdf}
  \end{center}
  \caption{選択}
  \label{fig:regexselect}
\end{figure}


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

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

\newpage

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

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

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

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

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

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

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

オートマトンは、入力に対して状態に対応した処理を行ない結果を出力する仮想的な自動機械である。
オートマトンの身近な例として、朝起きて学校に行くまでの例を挙げる。

図\ref{fig:dfabasic}は、朝起きて学校に向かうまでの状態遷移図である。
状態遷移図の `S' は初期状態を表し、`AC' は受理状態を表す。

私たちの日常でも起床の時間帯によって学校に行くまでの行動が変わる。
もし早起きをしたならば、時間的にゆとりがあるので身なりをしっかり整えて学校に向かうことができる。
この時、 $S -> 1 -> 2 -> AC$と状態が遷移する。

もし寝坊をしてしまった場合、時間的にゆとりがなく身なりを整える余裕がない。
その時は身なりを整える暇もなく学校へ向かうことになってしまう。
この時、 $S -> 3 -> AC$と状態が遷移する。

この例の場合、入力に当たるのは`早起きする'、`寝坊する'、`身なりを整える'、`学校に向かう'のそれぞれの行動であり、出力はその行動後に遷移する状態である。

このように、入力と状態が有限個で、どの状態でもある入力に対して遷移先が一意に決定されるオートマトンを決定性有限オートマトン(Deterministic Finite Automaton: DFA)という。
\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/dfabasic.pdf}
  \end{center}
  \caption{起きてから学校に行くまでの状態遷移図(DFA)}
  \label{fig:dfabasic}
\end{figure}

図\ref{fig:nfabasic}は、朝起きて学校に向かうまでの状態遷移図であるが、図\ref{fig:dfabasic}と違う点は S の状態で入力されるのは`起きる'という入力だけである。

この場合、起きて身なりを整え学校に向かうか起きて学校に向かうかの二択になる。
S の状態のとき、起きてから次の状態に遷移するのは 1 か 2 のときである。

このように入力と状態が有限個で、ある入力に対して複数の遷移先があり一意に決定されないオートマトンを非決定性オートマトン(Non-deterministic Finite Automaton: NFA)という。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/nfabasic.pdf}
  \end{center}
  \caption{起きてから学校に行くまでの状態遷移図(NFA)}
  \label{fig:nfabasic}
\end{figure}

正規表現はオートマトンで表現することができるので、状態と入力(ここでは正規表現)が判れば次はどのような状態になるのか決定される。
そのオートマトンの状態を、変換された正規表現木に状態を割り振っていく。

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

実際には正規表現木を元にオートマトンを構成していく。その際、深さ優先探索にて木を辿っていき、
メタ文字のノードが現れた時に一定のルールに沿って文字のノードに状態を割り振っていく。
ノードに状態を割り振りながら次の状態の遷移先を設定することによって、正規表現木からオートマトンによる状態遷移を表現することができる。

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

\newpage

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

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

\newpage

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

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


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

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

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

\newpage

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


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


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

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

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

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


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

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

\newpage

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

\newpage

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

図\ref{fig:nfaex}内で入力によって複数の状態に遷移する状態 4 だけに着目する。
状態 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}

図\ref{fig:nfaex}で与えられた NFA を Subset Construction にて DFA に変換すると、図\ref{fig:subsetauto}のようになる。
この図より、一度 a が入力されたあとは、aか[c-z]の入力と b の入力で状態 4,6 を循環することがわかる。このときの受理状態 2 を含んでいる状態 6 に状態遷移したときこのオートマトンは受理される。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/subsetauto.pdf}
  \end{center}
  \caption{Subset Construction 後のオートマトンの変化}
  \label{fig:subsetauto}
\end{figure}

\newpage

文字クラスは正規表現木のノード内では二分木として構成されている。
例えば、文字クラス[A-Za-z0-9]はノード内では図\ref{fig:cctree}のような二分木で構成されている。
文字クラスの二分木は、左から ASCII 文字コードの小さい文字を並べていく。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/cctree.pdf}
  \end{center}
  \caption{ノード内での文字クラスの二分木}
  \label{fig:cctree}
\end{figure}

\newpage
Subset Construction 時に文字クラス [a-z] と b が merge されている。
Subset Construction で文字クラスによって入力と遷移先が変化した場合、ノード内の文字クラスもその入力の文字クラスによって文字クラスの二分木も再構築される。
(図\ref{fig:cctreeex})

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/cctreeex.pdf}
  \end{center}
  \caption{図\ref{fig:nfaex}での Subset Construction 後の文字クラスの二分木の変化}
  \label{fig:cctreeex}
\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}

図\ref{fig:CharClassMergePattern}のパターン 3 の状況を考える。
ある状態に`[g-k]'が入力されると状態1に、`[c-h]'が入力されると状態4に遷移すると仮定する。
2つの文字クラスの範囲が`[g-h]'で重複しており、この重複している部分に関しては merge を行う必要がある。
この2つの文字クラスは`[c-f]'、`[g-h]'、`[i-k]' 3 つの文字クラスに分けることができる。
なお、重複した文字クラスの状態は状態の組み合わせを取り、新しい状態を作る。
(図\ref{fig:cctreemergeex})

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/cctreemergeex.pdf}
  \end{center}
  \caption{1つの文字クラスに対して文字クラスを merge する}
  \label{fig:cctreemergeex}
\end{figure}

図\ref{fig:cctreemergeex2} は元の文字クラスが複数存在し、それに対して1つの文字クラスを merge する状況である。
まず、文字クラスの二分木の先頭ノードの文字クラス`[g-k]'に対して`[c-h]'の merge を行う。
`[c-f]'、`[g-h]'、`[i-k]'それぞれ文字クラスに分けることができた。しかし、merge 元の文字クラス `[a-d]' と先頭の文字クラスの merge 後に生成された `[c-f]' も文字クラスの範囲が重複している。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/cctreemergeex2.pdf}
  \end{center}
  \caption{merge したが、文字クラスの範囲がまだ重複している}
  \label{fig:cctreemergeex2}
\end{figure}

文字クラスの範囲の重複が無くなるまで merge を繰り返す必要がある。
この場合、`[a-d]'と`[c-f]' は `[c-d]' で重複しているので、範囲が重複しないように文字クラスを再構築する必要がある。
(図\ref{fig:cctreemergeex3})

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/cctreemergeex3.pdf}
  \end{center}
  \caption{文字クラスの範囲の重複がなくなった}
  \label{fig:cctreemergeex3}
\end{figure}

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

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

並列処理時、分割されたファイルに対してパターンマッチさせるので、分割された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}