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

\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}
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{正規表現}
正規表現は文字列のパターンを表現するための方法である。

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

正規表現を利用すれば、この問題は簡単に解決することができる。
正規表現にはメタ文字と呼ばれる正規表現内での特殊記号があり、それらを利用することによって BOSE、Bose、bose の 3 つの文字列を一つの正規表現で表現することができる。

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

\newpage

また、これらのメタ文字は数式の四則演算のように結合順位を持っている。それぞれのメタ文字の結合順位は表\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}

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

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


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

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

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

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

\newpage

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

\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'は直前と直後の正規表現の関係を表しているので、左右のノードに正規表現の要素を持ったノードとなる。
(図\ref{fig:regexselect})

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

\newpage

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

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


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

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

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

\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.13]{images/regex/allostate.pdf}
  \end{center}
  \caption{与えられた正規表現をオートマトンに変換し、それに基いて正規表現木に状態を割り振る}
  \label{fig:allostate}
\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.18]{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.18]{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.15]{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.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.2]{images/regex/dfaregex.pdf}
  \end{center}
  \caption{どの状態もある入力を与えたとしても遷移先は一意に決定される}
  \label{fig:dfaregex}
\end{figure}

\newpage

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

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


\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{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 するような場面も出てくる。
図\ref{fig:cctreemerge}は、[a-ce-i]と[b-fh-j] の2つの文字クラスを merge する例である。
それぞれの文字クラスは二分木を構成しており、二分木どうしの merge をする必要がある。
その際、全てのパターンについてノードを分け、それらのノードを二分木で再構築する。

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.2]{images/regex/cctreemerge.pdf}
  \end{center}
  \caption{2つの文字クラスの二分木を merge}
  \label{fig:cctreemerge}
\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}

\newpage

\subsection{一つのノードに Word を含める}
これまでの正規表現は一文字ずつ参照して状態を割り振っていった。この状態割り振りの問題として文字列の長さの分だけ状態ができてしまう。


図\ref{fig:word}

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


\newpage


IBM stream processing