\documentclass[private]{ipsjpapers}
\usepackage[dvipdfm]{graphicx}
\usepackage{url}

% 巻数，号数などの設定
\setcounter{巻数}{0}
\setcounter{号数}{0}
\setcounter{volpageoffset}{0}
\受付{2010}{12}{03}
\採録{0}{0}{0}

% ユーザが定義したマクロなど．
\makeatletter
\let\@ARRAY\@array \def\@array{\def\<{\inhibitglue}\@ARRAY}
\def\<{\(\langle\)}
\def\>{\(\rangle\)}
\def\|{\verb|}
\def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline}
\def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\}
\def\LATEX{\iLATEX\Large}
\def\LATEx{\iLATEX\normalsize}
\def\LATex{\iLATEX\small}
\def\iLATEX#1{L\kern-.36em\raise.3ex\hbox{#1\bf A}\kern-.15em
    T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}
\def\LATEXe{\ifx\LaTeXe\undefined \LaTeX 2e\else\LaTeXe\fi}
\def\LATExe{\ifx\LaTeXe\undefined \iLATEX\scriptsize 2e\else\LaTeXe\fi}
\def\Quote{\list{}{}\item[]}
\let\endQuote\endlist
\def\TT{\if@LaTeX@e\tt\fi}
\def\CS#1{\if@LaTeX@e\tt\expandafter\string\csname#1\endcsname\else
        $\backslash$#1\fi}

%\checklines    % 行送りを確認する時に使用

\begin{document}%{
% 和文表題
\title[動的なコード生成を用いた正規表現エンジンの実装]%
        {動的なコード生成を用いた正規表現エンジンの実装}

% 英文表題
\etitle{Implimentation of Regular Expression Engine with Dynamic Code Generation.}

% 所属ラベルの定義
\affilabel{URYUKYU}{琉球大学\\University of the Ryukyu}

% 和文著者名
\author{新屋 良磨\affiref{URYUKYU}\nomember{}\and
        河野 真治\affiref{URYUKYU}\member{19841765}}

% 英文著者名
\eauthor{Ryoma SHINYA\affiref{URYUKYU}\and
        Shinji KONO\affiref{URYUKYU}}

% 連絡先（投稿時に必要．製版用では無視される．）
\contact{新屋 良磨\\
903-0213 沖縄県中頭郡西原町字千原1\\
琉球大学情報工学科\\
        TEL: (098)895-8723\qquad FAX: (098)895-8727\\
        email: shinya@cr.ie.u-ryukyu.ac.jp}

% 和文概要
\begin{abstract}
与えられた正規表現から, 等価な 有限状態オートマトンに変換し,
オートマトンにおける状態遷遷移をCや Continuation based C 等のコンパイル型言語での関数遷移に
変換する正規表現コンパイラを Python で開発した\cite{R}.
本論文では, その正規表現コンパイラを利用した, テキストファイルに対しパターン
マッチを行いマッチする行を出力するツールである grep に特化した実装方法を説明し,
実装した grep の性能を評価する.
\end{abstract}
% 英文概要
\begin{eabstract}
We implimented regular expression compiler using Python.
It convertes regular exprssion to equivalence automaton(DFA).
Then, translate automaton transition to functional/code-segmental transition which
 is wirtten in compiled language like C, Continuation based C.
In this paper, we introduce efficient implementation of grep that uses this
 compiler, and evaluate its performance.
\end{eabstract}

% 表題などの出力
\maketitle

%}{

% 本文はここから始まる

\section{はじめに}
コンパイラ理論の発展と共に, コンパイルにかかる時間はより短く, また得られ
るプログラムはアセンブラレベルで最適化が施され, より高速になってきている.

完全に静的なコンパイルが可能な対象として, 正規表現エンジンに着目した.
現在,正規表現のエンジンは, プログラミング言語の組み込み機能やライブラリ等,
さまざまな実装が存在するが, それらの殆どは仮想マシン方式を採用している\cite{R2}.
仮想マシンを採用いた実装でも, 正規表現を内部表現に変換する処理を行ってお
り, それらを ``コンパイル'' と呼ぶことが多い.本研究で実装したエンジンの
``コンパイル''とは, 正規表現を内部形式に変換することではなく, 正規
表現 から実行バイナリを生成することを指す(\ref{subsection:compile}節).
本研究では, 実行バイナリの生成にはコンパイラ基盤であるLLVM, GCC を用い
ており,エンジン生成系はPythonで実装した.

本論文では, まず正規表現のコンパイル方法について説明する. さらに,実装し
たエンジンの性能調査のために, 正規表現を用いてテキストマッチ処理を行う
grep クローンを実装し, GNU grep 等の既存ソフトウェアとの比較を行った.

\section{正規表現}
\subsection{正規表現によるテキストマッチ}
正規表現は与えられた文字列を受理するかどうかを判定できるパターンマッチン
グの機構であり, sed, grep, awk を始めとするテキスト処理ツールに広く利用
されている. 正規表現には定められた文法によって記述され, 例えば,正規表現
``$a*b$''は''$a$''の0回以上の繰り返し直後, ``$b$'' で終わる文字列(``$b$'' , ``$ab$'',
``$aaaab$'')を受理し, ``$a(b|c)$'' は ``$a$''で始まり,直後が ``$b$'' または
``$c$''で終わる文字列(``$ab$'', ``$ac$'') を受理する.

\subsection{正規表現の演算}\label{subsection:regex}

本論文では, 以下に定義された演算をサポートする表現を正規表現として扱う.
\begin{enumerate}
\item {連接} 二つの言語$L$と$M$の連接($LM$)は, $L$に属する列を一つとり, そのあとに$M$に族する列を連
接することによってできる列全体から成る集合である.
\item {集合和} 二つの言語$L$と$M$集合和($L|M$)は, $L$または$M$(もしくはその両方)に属する列全体からなる
集合である.
\item {閉包} 言語$L$の閉包($L*$)とは, $L$の中から有限個の列を重複を許して取り出し,
      それらを連接してできる列全体の集合である.
\end{enumerate}

正規表現は,この3つの演算について閉じておリ,この3つの演算によって定義され
る表現は, 数学的には正則表現と定義されている.
本論文では,特に区別のない限り,正則表現と正規表現を同じものとして扱う.

\section{正規表現エンジンの実装}
正規表現は等価なNFAに, またNFAは等価なDFAに変換することが可能である\cite{U}. 以
下にその変換手方を説明する.

\subsection{正規表現からNFAへの変換}
NFA({\it Non-deterministic Finite Automaton}) は, 入力に対して複数の
遷移先持つ状態の集合であり, 遷移先が非決定的(Non-deterministic)である.
ここでは, NFAを5個組$(Q, \Sigma,, \delta, q_0, F)$で定義する.ただし,
\begin{enumerate}
\item $Q$は状態の有限集合.
\item $\Sigma$は入力記号の有限集合.
\item $q_0$は$Q$の要素で, 開始状態と呼ぶ.
\item $F$は$Q$の部分集合で,受理状態と呼ぶ.
\item $\delta$は,状態と入力記号に対して状態の集合を返す遷移関
      数.($\varepsilon$遷移を許す)
\end{enumerate}
正規表現が, 等価なNFAに変換できるということを,\ref{subsection:regex}で定義
した3つの演算について対応するNFAに変換できることから示す.

\begin{figure}[h]
\begin{center}
\scalebox{0.50}{\includegraphics{fig1.eps}}
\end{center}
\caption{``$A$''と``$B$''の連接}
%\ecaption{The NFA for the concatenation ``$A$'' ``$B$''}
\label{figure:concat}
\end{figure}
\begin{figure}[h]
\begin{center}
\scalebox{0.50}{\includegraphics{fig2.eps}}
\end{center}
\caption{``$A$''と``$B$''の集合和}
%\ecaption{The NFA for the alternation ``$A$'' ``$B$''}
\label{figure:union}
\end{figure}
\begin{figure}[h]
\begin{center}
\scalebox{0.50}{\includegraphics{fig3.eps}}
\end{center}
\caption{``$A$''の閉包}
%\ecaption{The NFA for the kleene closure ``$A$''}
\label{figure:star}
\end{figure}

\begin{enumerate}
\item {連接} 図\ref{figure:concat}は正規表現 ``AB'' に対応するNFA.
\item {集合和} 図\ref{figure:union}は正規表現 ``$A|B$''に対応するNFA.
\item {閉包} 図\ref{figure:star}は正規表現 ``A*''に対応するNFA.
\end{enumerate}

図\ref{figure:union}, \ref{figure:star}において, ラベルのない矢印は無条件
の遷移を現しており,$\varepsilon$遷移と呼ばれる. また, 二重丸で囲まれた
状態は受理状態を現しておリ, NFAにおいて入力が終了した時点で,受理状態を保
持している場合に限り, その文字列を受理したことになる. なお, NFAは同時に
複数の遷移先をもつことがあるので, テキストのマッチング途中で複数の状態を
保持することがある.

現在実装されている正規表現エンジンの多くは, 正規表現を内部的にNFAに変換し
て評価を行っている\cite{R1}. NFAによる実装は, 後述する後方参照や最長一致
に対応しやすいが, 同時に遷移する可能性のある複数の状態を保持する必要があ
るため, 正規表現の複雑度に多じてマッチングの時間が多くなってしまう場合が
ある. 文献\cite{R1}では, ``$a?a?a?aaa$'' のような ``$a?^na^n$'' のように
表現(``$a?$''は''a``か空文字''``を認識する拡張された正規表現お一つ)の評
価において, NFAベースの正規表現エンジンでは遷移する状態の数が増えてしまう
でマッチングにかかる処理時間が$n$の指数的に増加する問題をベンチマーク
結果と共に指摘している. 文献\cite{K} では正規表現からNFAベースで効率的な
マッチング処理を行うエンジンをIBM 7094 機械語で生成する例が紹介されている.

\subsection{NFAからDFAへの変換}
非決定的な遷移を行うNFAから, 決定的な遷移を行うDFA({\it Deterministic
Finite Automaton})に変換する手法を説明する. なお, 遷移が決定的である
ということは, 1つの入力に対して, 遷移する状態がただ1つであるということを
指す.
DFAは, NFAと同様な5個組で$(Q, \Sigma,, \delta, q_0, F)$定義できる. ただ
し,DFAにおいて$\delta$において$\varepsilon$遷移は認められず, また任意
の状態$q$と入力$\sigma$について, $\delta(q, \sigma) = q'$となる$q'$は$Q$
の要素となる. つまり, 遷移先が決定的であるということに他ならない.

以下に$\varepsilon$遷移を許す$\varepsilon$-NFA $E = (Q_E,
\Sigma,\delta_E, q_0, F_E)$ から等価なDFA $D = (Q_D, \Sigma,
\delta_D, q_D, F_D)$を構成する手順を示す.

\begin{enumerate}
\item $Q_D$は$Q_E$の部分集合全から成る集合であり, おの中で$D$において
      到達可能な状態は, $\varepsilon$遷移に関して閉じている$Q_E$の部分
      集合$S$に限られる. ここで, 状態$q$において$\varepsilon$遷移に関し
      て閉じている集合全体を$ECLOSE(q)$と表す. $ECLOSE$を使って$S$を定義
      すると, $S = \displaystyle\bigcup_{q\in{S}}ECLOSE(q)$を満たす$S$.
\item $q_D = ECLOSE(q_0)$. すなわち, $E$の開始状態の$\varepsilon$閉包.
\item $F_D$は$E$の状態の集合で,受理状態を少なくとも一つ含むもの全体から
      なる集合である. すなわち,$F_D = \{S | S \in Q_D \wedge S \cap F_E \ne
      \emptyset\}$
\item $\delta_D(S, a)$は$Q_D$の要素$S$と$\Sigma$の要素$a$に対して次のよ
      うに計算される.
      \begin{enumerate}
       \item $S = \{p_1,p_2,...,p_k\}$とする.
       \item $\displaystyle\bigcup^{k}_{i=1}\delta(p_i,a)$を求め, その結
             果を$\{r_1,r_2,...,r_m\}$とする.
       \item このとき, $\delta_D(S, a) = \displaystyle\bigcup^{m}_{j=1}ECLOSE(r_j)$
      \end{enumerate}
\end{enumerate}
この方法によって得られたDFA $D$はNFA $E$と同等の言語を認識し, またNFAの
元となる正規表現と同等である.

\subsection{DFAからの実行バイナリ生成}\label{subsection:compile}
DFAからの実行バイナリ生成には, 生成するコードについて3種類の実装を行った.

\begin{enumerate}
\item DFA $\rightarrow$ Continuation based C $\rightarrow$ GCCによるコンパ
      イル
\item DFA $\rightarrow$ C $\rightarrow$ GCCによるコンパイル
\item DFA $\rightarrow$ LLVM中間表現 $\rightarrow$ LLVMによるコンパイル
\end{enumerate}
%

以下, Continuation based C, LLVMの説明と, それを利用したDFAからの
実行バイナリ生成の方法を説明する.

\subsubsection{Continuation based C}
Continuation based C(以下CbC)は, プログラミングの基本単位としてコードセ
グメントを持ち, コードセグメント間の軽量継続を基本としたCの下位言語であ
る. 本研究室での先行研究によりCbCコンパイラは, GNU C Compiler上で実装さ
れており\cite{Y}, GCCの末尾再帰最適化を強制することで, 関数と同様の記述
が可能で, かつ関数呼び出しに伴なうリターンアドレスの保存や,スタックの成
長のない, ``引数付きgoto''として継続を実装している.本研究ではgcc-4.5上に
実装されたCbCコンパイラを用いた.

正規表現 ``$(A|B)*C$''に対応するDFAと, DFAの各状態に対応するCbC
のコードセグメントの例を載せる.

\newpage

\begin{figure}[h]
\begin{center}
\scalebox{0.60}{\includegraphics{fig5.eps}}
\caption{正規表現``$(A|B)*C$''に対応するDFA}
%\ecaption{The DFA for ``$(A|B)*C$''}
\label{figure:dfasmaple}
\end{center}
\end{figure}

\begin{center}
\begin{small}
\begin{verbatim}
typedef unsigned char * UCHARP;
__code state_0(UCHARP beg, UCHARP buf, UCHARP end) {
  switch(*buf++) {
    case 65: /* 'A' */
      goto state_0(beg, buf, end);
    case 66: /* 'B' */
      goto state_0(beg, buf, end);
    case 67: /* 'C' */
      goto state_1(beg, buf, end);
    default: goto reject(beg, buf, end);
  }
}

__code state_1(UCHARP beg, UCHARP buf, UCHARP end) {
  goto accept(beg, buf, end);
}
\end{verbatim}
\end{small}
図\ref{figure:dfasmaple}のDFAに対応するCbCコードセグメント
\end{center}

DFAの遷移とは直接関係のない引数(ファイル名やバッファへのポインタ等) が目
立が, CbCでは環境をコードセグメント間で引数として明示的に持ち運ぶ軽量継
続を基盤としたプログラミングスタイルが望ましい. 今回コンパイラによって生
成したCbCソースコードでは,大域変数は持たず,必要な変数は全て引数に載せて
いる.
CbCのstate\_1, state\_0から呼ばれているaccept, rejectはそれぞれ受理と非
受理を表す. accept ではテキスト行を出力して次の行へ, rejectでは次
の文字へと処理を移すコードセグメントへ継続を行う.

生成したCbCソースコードを, GCC上に実装したCbCコンパイラによってコンパイルす
ることで実行バイナリを得る.

\newpage

\subsubsection{C}
Cによる実装では, CbCのコードセグメントに代わり関数を用いてDFAを実装した.

\begin{center}
\begin{small}
\begin{verbatim}
typedef unsigned char * UCHARP;
void state_0(UCHARP beg, UCHARP buf, UCHARP end) {
  switch(*buf++) {
    case 65: /* 'A' */
      return state_0(beg, buf, end);
    case 66: /* 'B' */
      return state_0(beg, buf, end);
    case 67: /* 'C' */
      return state_1(beg, buf, end);
    default: return reject(beg, buf, end);
  }
}

void state_1(UCHARP beg, UCHARP buf, UCHARP end) {
  return accept(beg, buf, end);
}
\end{verbatim}
\end{small}
図\ref{figure:dfasmaple}のDFAに対応するC関数
\end{center}

DFAによる遷移を関数呼び出しで行っているため,実行時のスタックの使用領域や,ス
タック操作によるオーバーヘッドが予想される.

\subsubsection{LLVM}
LLVM(Low Level Virtual Machine) は, さまざまなコード最適化/分析機能を備
えた, モジュール単位で利用可能なコンパイラ基盤である\cite{L}.

CbC/Cによる実装では,DFAからCbC/Cのソースコードに変換し,GCCによってコンパ
イルを行っている. LLVMによる実装では, LLVMの中間表現であるLLVM-IRを,提供
されているAPIを用いて直接操作を行い, コンパイルを経て実行バイナリを得る.
PythonからLLVM APIの利用は, LLVM APIのPythonラッパーであるllvm-py\footnote{http://www.mdevan.org/llvm-py/}を使用した.

\begin{figure}[h]
\begin{center}
\scalebox{0.60}{\includegraphics{fig7.eps}}
\caption{LLVMを用いた実装}
%\ecaption{Implimentation with LLVM}
\label{figure:llvm-impl}
\end{center}
\end{figure}

LLVMによる実装でも, Cによる実装と同様に,DFAの状態遷移をswitch文と関数呼
び出しによって表現している.

\section{grep}
正規表現は, テキストのパターンをシンプルに記述できるという利点から, テキ
ストファイルから, 任意のパターンにマッチするテキストを検索するなどの用途
に使用される.

grep は, それを実現するソフトウェアの一つであり, 多くのの実装が存在する.
引数として与えられたファイルから, 与えられた正規表現にマッチするテキスト
を含む行を出力する機能を持っている.

\subsection{本実装により生成される grep}
grep は, 与えられた正規表現にマッチするテキストを''含む``行を出力する.
ここで重要なのは, grep による正規表現マッチングは行単位で行なわれ, 行頭
から行末までの完全一致ではなく, 基本的に部分一致で行なわれる
\footnote{GNU grep では完全一致を行なう``-x''オプションがある.}.

部分一致を実現する方法として, 与えられた正規表現の先頭に正規表現``.*''を
付加して, 前方一致を行なう. ここで ''.``は''任意の一文字''を表す特殊記号
である.

正規表現 ``$(A|B)*C+$'' に対して, 本実装で生成される grep のコードを示す.
既に説明した通り, grep による部分一致を行なうために正規表現の先頭に
``.*''を追加し, DFAに変換しコードを生成する.

\begin{center}
\begin{small}
\begin{verbatim}
void grep(UCHARP beg, UCHARP buf, UCHARP end) {
  state_1(beg, buf, end);
  return;
}

void state_1(UCHARP beg, UCHARP buf, UCHARP end) {
  switch(*buf++) {
    case 0: /* NUL */
      return reject(beg, buf, end);
    case 65: /* 'A' */
      return state_1(beg, buf, end);
    case 66: /* 'B' */
      return state_1(beg, buf, end);
    case 67: /* 'C' */
      return state_0(beg, buf, end);
    case 10: /* LF */
      return reject(beg, buf, end);
    case 13: /* CR */
      return reject(beg, buf, end);
    default: return state_1(beg, buf, end);
  }
}

void state_0(UCHARP beg, UCHARP buf, UCHARP end) {
  return accept(beg, buf-1, end);
}
\end{verbatim}
\end{small}
\end{center}

本実装では, ``.''に対応する遷移を switch文の default で行なっている.

本実装による grep では, 検索対象となるテキストファイルを mmap でメモリに
マップしている. メモリ上にマップされたテキストファイルを, (改行を含む)1
つの巨大な文字列として関数 grep に与え, マッチングと出力を継続的なコード遷移で行う.

上記のコードでは, 改行文字(LF/CR)及び終端文字(NUL)に対して特殊な状態
$reject$に遷移しているが, この特殊状態 $reject$ では行頭を表す引数 beg を
更新, 再度 grep に遷移する状態である.

\begin{center}
\begin{small}
\begin{verbatim}
void reject(UCHARP beg, UCHARP buf, UCHARP end) {
  if (buf >= end) return;
  beg = buf;
  return grep(beg, buf, end);
}
\end{verbatim}
\end{small}
\end{center}

行頭を更新/保持することによって, マッチ行の出力時には行末のみを気にすれ
ば良い.
受理状態を表す $state\_0$ では, 出力を行なう特殊状態$accept$に直接遷移を
行なう. ここで重要なのは, 本来 $state\_0$ は与えられた正規表現の末尾
``$C+$''に対して``C''字が入力された時点の状態であり, さらに``C''が入力文
字として続く場合の遷移状態も本来保持している. しかし, 本実装では, ``最左最
短一致''で出力を行なうよう実装を行なっているため, 受理状態に遷移した時点
で出力を行なう.

特殊状態 $accept$ では, マッチングに成功した時点でのポインタ変数 buf を基
準に, 行末を memchar で探索し, 出力を行なっている.
\begin{center}
\begin{small}
\begin{verbatim}
void accept(UCHARP beg, UCHARP buf, UCHARP end) {
  UCHARP ret = (UCHARP)memchr(buf,'\n',(buf-end));
  if (ret == NULL) {
    print_line(beg, end);
    return;
  }
  print_line(beg, ret);
  beg = buf = ret + 1;
  return grep(beg, buf, end);
}
\end{verbatim}
\end{small}
\end{center}

出力を行なった時点で, まだファイルの終端に達してない場合は, 出力した行の
次の行頭から, 再度 grep を呼び出している.
このように, 本実装では, 状態遷移及び出力が末尾再帰的に行なわれており, コンパ
イラによって末尾呼び出しが適切に最適化された場合, スタック操作の無い高速
な状態遷移を行なう実行バイナリに変換される.

Intel Compiler で本実装による grep を最適化オプションを付加してコンパイ
ル,実行したところ, 末尾呼び出し最適化が行なわれず,実行して即座にスタック
オーバーフローを起こしてしまった. C言語では, 末尾呼び出し最適化を明示的
に記述することができないので, このような状態遷移ベースのプログラミングは
Continuation based C による記述が望ましいといえる.

\subsection{固定文字列フィルタリング}
GNU grep を含むいくつかの grep 実装では, マッチングを高速化するために様々
な高速化の工夫を行なっている. 正規表現をDFAに変換してのマッチングや, 固
定文字列フィルタリングもその一つである.

与えられた正規表現が, 固定文字列を含む場合, その固定文字列を含む行を探索
し(フィルタリング), 続いてDFAによるマッチングを行なうことで, 全行に対し
てDFAによるマッチングを行なう場合より高速なマッチングが可能となる.これは,
探索する文字列が固定文字列の場合, DFAによる探索よりも, Boyer-Moore 法等
の固定文字列に特化した探索手法が高速なマッチングを行なえるからである.
$n$を被探索文字列の長さ, $m$を探索文字列の長さとした場合, 固定文字列探索
をDFAで行なうと探索時間は単純に入力文字列(被探索文字列)長に比例するので
$\Theta(n)$となる. 一方, Boyer-Moore 法等のアルゴリズムを用いて探索を行
なった場合, 最良で$m$ 文字分探索をスキップできるので, 探索時間は
$\Omega(n/m), O(n)$となる.\\

Boyer-Moore法は, 検索可能な固定文字列は1つのみであるが, これを複数の文字
列に一般化したアルゴリズムとして, Commentz-Walter法\cite{B} があり, GNU
grep, 及び本実装ではこれを採用している.

\newpage

\section{評価}
本実験で実装した正規表現エンジンのCbC/C/LLVMによる三つの実装に対して,
コンパイル時間及びマッチング時間の比較を行った.
なお, GCCによるコンパイルには最適化オプション ``-O3'' を, LLVMのも同様の
最適化オプションを用いてコンパイル/マッチングを行っている.

\subsection{ベンチマーク: コンパイル}
n個の単語を正規表現の和集合演算 ``$|$''で繋げたパターンに対し, 各実装のコンパイル時
間の比較を行った.

{\bf 実験環境}
\begin{itemize}
\item CPU : Core 2 Duo 950 @3.0GHz
\item Memory : 16GB
\item GCC : 4.5.0
\item LLVM: 2.4
\end{itemize}

表\ref{table:benchmark1}に結果を示す.

\begin{table}[h]
\caption{ベンチマーク:compile}
\label{table:benchmark1}
\begin{tabular}[t]{l|l|l|l|l}
\hline\hline
n (単語数)& 1 & 10 & 50 & 100 \\
\hline
DFA変換[ms] & 0.19 & 3.28 & 22.2 & 73.8\\
DFAの状態数 & 8 & 50 & 187 & 381\\
\hline
GCC-C  [s] & 0.34 & 0.78 & 2.18 & 4.27\\
\hline
GCC-CbC[s] & 0.75 & 1.03 & 9.14 & 9.43\\
\hline
LLVM   [s] & 0.044 & 0.08 & 0.246 & 0.472\\
\hline
\end{tabular}
\end{table}

表\ref{table:benchmark1}から, LLVMによるコンパイルがGCCに比べ10倍程高速
に行われている. LLVMMによる実装では,APIを通じて直接LLVMの中間表現を操作
することで, ファイルI/Oやパース等のオーバーヘッドもない.

\subsection{ベンチマーク: grep}
マッチング時間の比較では,様々な正規表現を用いて比較を行った結果, 3つの実
装でマッチング時間にあまり差が見られなかった. 生成されるコードはコードセ
グメント/関数と, switch文によるシンプルな実装であることから, コンパイル
されたバイナリの性能にあまり差が出ていないものだと思われる.

本実装の中で最もマッチングが高速だったGCC-Cで生成した正規表現エンジンを用
いてgrep に相当するプログラムを実装し,実際にテキストファイルからのパター
ンマッチを行い, それぞれの評価を行う. 本実装との比較対象として選択した
grep について説明する.

\subsection{GNU grep}
GNU grep (\url{http://www.gnu.org/software/grep/})は GNU が開発しているOSS(Open Source Software)で, 非常にポピュ
ラーなツールとして様々なOSに標準搭載され使用されている.
GNU grep は POSIX 拡張正規表現に対応した egrep, 固定文字列探索に対応した
fgrepを内包しており, オプションで切り替えることができる.

C言語による1万行程度の実装で, POSIX規定の正規表現,後方参照等さまざまな多
くの機能を有しながら, マッチング自体も高速である.

なお, 今回の実験では GNU grep 2.6.3 及び GNU grep 2.5.4 を用いる. 2つの
バージョンを用いる理由は, GNU grep 2.6 が2010年3月のリリースと比較的最近
で, 現行のほぼすべてのOSでは GNU grep 2.5.x が使用されているからである.
さらに, GNU grep 2.6.x からは UTF-8の対応が改善されている.
\subsection{cgrep}
cgrep (\url{http://sourceforge.net/projects/cgrep/}) は, {\it Bill Tanenbaum} が開発したOSSで, GNU
grep に比べて300-25\%ほど高速なマッチングを行なう\footnote{cgrep の
manpage より抜粋}.
C言語による2万行程度の実装で, 2004/6/30にリリースされたcgrep 8.15 以降開発が止まっている. また, マルチ
バイト文字のサポートなどは行なっていない.

\subsection{Google RE2}
Google RE2 (\verb|http://code.google.com/p/re2/|) は Google の{\it Russ Cox}を中心
に開発されているOSSな正規表現エンジンライブラリで, 正規表現マッチングを行なう複
数のAPIを利用できる.

C++による2万行程度の実装で, UTF-8に対応している.

本実験では, Google RE2 の API である FindAndConsume を使用して, grep ク
ローンを実装した. FindAndConsume はマッチング対象文字列と正規表現, マッ
チした文字列を格納するポインタを引数にとり, マッチングの開始部分を内部的
に更新していくAPIである. 以下が, RE2を用いたgrep実装のメインルーチンであ
る.

\begin{center}
\begin{small}
\begin{verbatim}
void grep(string regexp, UCHARP beg, UCHARP end) {
  RE2 re("(.*"+regexp+".*)");
  re.ok(); // compile;
  string contents = string((const char *)beg, (end - beg));
  StringPiece input(contents);
  string word; // container of printable line.
  while (RE2::FindAndConsume(&input, re, &word)) {
    cout << word << "\n"; //print
  }
  return;
}
\end{verbatim}
\end{small}
\end{center}

{\bf 実験環境}
\begin{itemize}
\item CPU : Core i7 950 @3.0GHz
\item Memory : 16GB
\item GCC : 4.4.1
\item Text : Wikipedia 日本語版全記事\\ (XML, UTF-8, 4.7GB, 8000万行)
\end{itemize}

表\ref{table:benchmark2}に結果を示す.

\begin{table}[h]
\caption{ベンチマーク:grep}
\label{table:benchmark2}
\begin{tabular}[t]{l|l|l}
\hline\hline
テストケース & fixed-string & complex-regex\\
\hline
本実装(GCC-C)[s] & 1.69 & 4.51 \\
(コンパイル[s]) & 0.20 & 0.41 \\
\hline
cgrep 8.15 [s] & 1.85 & 6.48 \\
\hline
GNU grep 2.6.3[s] & 2.93 & 16.08\\
\hline
GNU grep 2.5.4[s] & 2.96 & 188.51\\
\hline
Google RE2 [s] & 30.10 & 16.92\\
\hline
\end{tabular}
\end{table}

以下に, それぞれのテストケースのパターン, grepにマッチした行数,
および考察を記す. なお,ここで扱う正規表現の ``複雑さ''とは, DFAに
変換した時点の状態数, 遷移規則の多さを基準としている.

{\bf fixed-string 固定文字列によるマッチング}
パターン  : ``$Wikipedia$''\\
マッチ行数: 348936行\\
GNU grep では, 与えられたパターン内に, 確実に含まれる文字列(固定文字列)
が存在する場合は, Boyer-Moore 法 等の高速な文字列探索アルゴリズムを用いて
フィルタをかけることで, DFAによるマッチングを減らし,高速化している. 本実
装の grep でも, 同様に固定文字列フィルタによる高速化を行っているが, 単純
な固定文字列の検索でも, コンパイルすることによる高速化が結果に出ている.

{\bf complex-regex 複雑な正規表現でのマッチング}
パターン  :``$(Python|Perl|Pascall|Prolog|\\
PHP|Ruby|Haskell|Lisp|Scheme)$''\\
マッチ行数: 15030行\\
このパターンは,9個の単語を和集合演算 ``$|$''で並べたもので,確実に含まれ
る文字列は存在しないが, 前述のCommentz-Walter法によるフィルタリングが適
用できる.
GNU grep, cgrep 及び本実装において fixed-string のケー
スよりはマッチングに時間が

さらに, GNU grep 2.5.4 は190秒と, 本実装及びGNU grep 2.6.3に対して非常に
低速な結果となっているが, これは後述する mbrtowc(3) によるマルチバイト文
字の変換処理によるオーバーヘッドによるものである.

2つのテストケースの結果を見てみると, 本実装はそれぞれGNU grep と比べて高
速な結果となっており, この規模のファイルに対する grep の場合,コンパイル
時間はマッチングにかかる時間と比べて無視できるほど短い時間であることが分かる.

\section{本実装の特徴}
本実験によって実装された正規表現評価器の特徴を, GNU grep との比較をはさ
みながら説明する.

\subsection{正規表現からの動的なコード生成}
本実装による一番の特徴として, 正規表現から変換を行うことで得られる等価な
DFAを, C/CbC/LLVM に変換しコンパイルすることで正規表現に応じた実行バイナ
リを生成することが挙げられる. またコンパイラ理論におけるさまざまな最適化
が期待される.
grepによる検索のような, 与えられるパターン(正規表現)に対してマッチ対象の
テキストファイルが十分に大きい場合, 正規表現のコンパイルにかかる時間はマッ
チングにかかる時間によって隠される.

GNU grep では, 本実装と同様にDFAベースのマッチングを行うが, DFAの各状態
は構造体よって表され, 状態遷移は各状態毎に保持している遷移先ポインタによ
る配列を,1Byte単位でテーブルルックアップを行うことで実装されている.

\subsection{UTF-8対応}

本実装は, マルチバイト文字の代表的な符号化方式であるUTF-8に内部的に対応しており,
正規表現の演算は1Byte単位ではなく,1文字単位で適用される.
マルチバイト文字を含む正規表現のサンプルとして, ``(あ$|$い)*う''をDFAに
変換した図\ref{figure:multibyte-dfasample}を載せる. 図における
\verb|'\x'|に始まる文字は16進数表記で, \verb|'\x82'|は16進数82を表す.

\begin{figure}[h]
\begin{center}
\scalebox{0.40}{\includegraphics{fig6.eps}}
\caption{正規表現``(あ$|$い)*う''に対応するDFA}
\label{figure:multibyte-dfasample}
\end{center}
\end{figure}

GNU grep 2.5.x では, マルチバイト文字に対応しているものの, プログラム内
部でlibc mbrtowc(3)を用いて固定サイズであるワイド文字に変換して処理を行っ
ており, テストケース complex-regex ではそのオーバーヘッドが顕著に現れて
いる.
2010年3月にリリースされた GNU grep 2.6 から, UTF-8に対して本実装と同様に
内部的に対応することで, mbrtowc(3)による変換コストが無くなっている.

\subsection{柔軟な実装}
本実験で実装した正規表現評価器は, Pythonによって実装されており,全体
で3000行程度の軽量なプログラムとなっている. 今回比較対象として利用した
GNU grep, cgrep, Google RE2 はいずれも1\~2万行の規模のソフトウェアに比べ
機能の追加やリファクタリングが用意であり, 本実装の優れた点と言えるだろう.

ここで重要なのは, 本実装から動的に生成されるコードも,コードセグメント/関数とswitch
を基準としたシンプルな記述で高い可読性を持ちつつ, 細かい最適化をGCC/LLVMの最適
化技術を利用することで実行速度も非常に高速であることが実験結果から分かった.

\section{途中報告と課題}
本研究では, 現段階で正規表現をコードセグメント/関数による状態遷移を行う
コードに変換する手法で正規表現エンジンを実装し, GNU grep との比較を行い
, 非常に良好な結果が得られた.

今後の課題として, 正規表現マッチングのデータ並列な並列アルゴリズムの実装
を目指している.

\begin{thebibliography}{9}

\bibitem{B} Commentz-Walter, B: A String Matching Algorithm Fast on the
        Average, Proc. 6th International Colloquium on Automata, Languages, and Programming (1979)

\bibitem{R1} Cox, R : Regular Expression Matching Can Be Simple And
        Fast, \url{http://swtch.com/~rsc/regexp/regexp1.html} (2007)

\bibitem{R2} Cox, R : Regular Expression Matching: the Virtual Machine
        Approach, \url{http://swtch.com/~rsc/regexp/regexp2.html} (2009)

\bibitem{R3} Cox, R : Regular Expression Matching in the Wild,
        \url{http://swtch.com/~rsc/regexp/regexp3.html} (2010)

\bibitem{U} Hopcroft, J, E. Motowani, R. Ullman, J : オートマトン言
        語理論計算論I (第二版), pp.~39--90.

\bibitem{L} Lattner, Chris. Adve, Vikram : The LLVM Compiler Framework
        and Infrastructure, \url{http://llvm.org/pubs/2004-09-22-LCPCLLVMTutorial.pdf} (2004)

\bibitem{R} 新屋 良磨 : 動的なコード生成を用いた正規表現エンジンの実装,
        日本ソフトウェア科学会第27回大会 (2010)

\bibitem{K} Thompson, K : Regular Expression Search Algorithm,
        Communications of the ACM 11(6) (1968).

\bibitem{Y} 与儀 健人, 河野 真治 : Continuation based Cコンパイラの
        GCC-4.2による実装, 情報処理学会システムソフトウェアとオペレーティ
        ング・システム研究会(OS) (2008)

\end{thebibliography}

\begin{biography}
\member{新屋 良磨}
1988年生.
2007年琉球大学工学部情報工学科入学
%
\member{河野 真治}
1959年生．
1989年東京大学大学院情報工学課程修了 (工学博士)
同年Sony Computer Science Laboratory, Inc.   入社．
1996年より琉球大学工学部准教授
工学博士． ACM会員.
\end{biography}
\end{document}