Binary file tex/prosym-shinya.pdf has changed

--- a/tex/prosym-shinya.tex	Fri Dec 03 03:08:47 2010 +0900
+++ b/tex/prosym-shinya.tex	Fri Dec 03 17:50:29 2010 +0900
@@ -43,7 +43,7 @@
 \affilabel{URYUKYU}{琉球大学\\University of the Ryukyu}
 
 % 和文著者名
-\author{新屋 良磨\affiref{URYUKYU}\and
+\author{新屋 良磨\affiref{URYUKYU}\nomember{}\and
         河野 真治\affiref{URYUKYU}\member{19841765}}
 
 % 英文著者名
@@ -62,13 +62,18 @@
 当研究室では, 与えられた正規表現から, 等価な 有限状態オートマトンに変換し,
 オートマトンにおける状態遷遷移をC言語等のコンパイル型言語での関数遷移に
 変換する正規表現コンパイラを Python で開発している.
+本論文では, その正規表現コンパイラを利用した, テキストファイルに対しパターン
+マッチを行いマッチする行を出力するツールである grep に特化した実装方法を説明し,
+実装した grep の性能を評価する.
+\end{abstract}
+% 英文概要
+\begin{eabstract}
+{\b 英訳 当研究室では}, 与えられた正規表現から, 等価な 有限状態オートマトンに変換し,
+オートマトンにおける状態遷遷移をC言語等のコンパイル型言語での関数遷移に
+変換する正規表現コンパイラを Python で開発している.
 本実験では, その正規表現コンパイラを元に, テキストファイルに対しパターン
 マッチを行いマッチする行を出力するツールである grep に相当するソフトウェ
 アを実装した.
-\end{abstract}
-% 英文概要
-\begin{eabstract}
-上の英訳.
 \end{eabstract}
 
 % 表題などの出力
@@ -145,6 +150,7 @@
 \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]
@@ -152,6 +158,7 @@
 \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]
@@ -159,6 +166,7 @@
 \scalebox{0.50}{\includegraphics{fig3.eps}}
 \end{center}
 \caption{``$A$''の閉包}
+%\ecaption{The NFA for the kleene closure ``$A$''}
 \label{figure:star}
 \end{figure}
 
@@ -245,13 +253,16 @@
 長のない, ``引数付きgoto''として継続を実装している.本研究ではgcc-4.5上に
 実装されたCbCコンパイラを用いた.
 
-以下に, 正規表現 ``$(A|B)*C$''に対応するDFAと, DFAの各状態に対応する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}
@@ -259,27 +270,25 @@
 \begin{center}
 \begin{small}
 \begin{verbatim}
-__code state_0(unsigned char *s, unsigned
-        char* cur, unsigned char* buf, FILE
-        *f, char* filename) {
-  switch(*s++) {
-    case 65: /* match A */
-      goto state_0(s, cur, buf, f, filename);
-    case 66: /* match B */
-      goto state_0(s, cur, buf, f, filename);
-    case 67: /* match C */
-      goto state_1(s, cur, buf, f, filename);
-    default: goto reject(s, cur, buf, f, filename);
+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(unsigned char *s, unsigned
-        char* cur, unsigned char* buf, FILE
-         *f, char* filename) {
-  goto accept(s, cur, buf, f, filename);
+
+__code state_1(UCHARP beg, UCHARP buf, UCHARP end) {
+  goto accept(beg, buf, end);
 }
 \end{verbatim}
 \end{small}
-{\bf 図\ref{figure:dfasmaple}のDFAに対応するCbCコードセグメント}
+図\ref{figure:dfasmaple}のDFAに対応するCbCコードセグメント
 \end{center}
 
 DFAの遷移とは直接関係のない引数(ファイル名やバッファへのポインタ等) が目
@@ -294,8 +303,35 @@
 生成した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による遷移を関数呼び出しで行っているため,実行時のスタックの使用領域や,ス
 タック操作によるオーバーヘッドが予想される.
 
@@ -312,6 +348,7 @@
 \begin{center}
 \scalebox{0.60}{\includegraphics{fig7.eps}}
 \caption{LLVMを用いた実装}
+%\ecaption{Implimentation with LLVM}
 \label{figure:llvm-impl}
 \end{center}
 \end{figure}
@@ -324,17 +361,136 @@
 ストファイルから, 任意のパターンにマッチするテキストを検索するなどの用途
 に使用される.
 
-GNU 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 を呼び出している.
+このように, 本実装では, 状態遷移及び出力が末尾再帰的に行なわれており, コンパ
+イラによって末尾呼び出しが適切に最適化された場合, スタック操作の無い高速
+な状態遷移を行なう実行バイナリに変換される.
+
+\subsection{固定文字列フィルタリング}
+GNU grep を含むいくつかの grep 実装では, マッチングを高速化するために様々
+な高速化の工夫を行なっている. 正規表現をDFAに変換してのマッチングや, 固
+定文字列フィルタリングもその一つである.
+
+与えられた正規表現が, 固定文字列を含む場合, その固定文字列を含む行を探索
+し(フィルタリング), 続いてDFAによるマッチングを行なうことで, 全行に対し
+てDFAによるマッチングを行なう場合より高速なマッチングが可能となる.これは,
+探索する文字列が固定文字列の場合, DFAによる探索よりも, Boyer-Moore 法等
+の固定文字列に特化した探索手法が高速なマッチングを行なえるからである.
+
+\newpage
 
 \section{評価}
-\subsection{実験}
 本実験で実装した正規表現エンジンのCbC/C/LLVMによる三つの実装に対して,
-コンパイル時間及びマッチングにかかる時間の比較を行った.
+コンパイル時間及びマッチング時間の比較を行った.
 なお, GCCによるコンパイルには最適化オプション ``-O3'' を, LLVMのも同様の
 最適化オプションを用いてコンパイル/マッチングを行っている.
 
+\subsection{ベンチマーク: コンパイル}
+n個の単語を正規表現の和集合演算 ``$|$''で繋げたパターンに対し, 各実装のコンパイル時
+間の比較を行った.
+
 {\bf 実験環境}
 \begin{itemize}
 \item CPU : Core 2 Duo 950 @3.0GHz
@@ -343,9 +499,7 @@
 \item LLVM: 2.4
 \end{itemize}
 
-{\bf コンパイル}\\
-n個の単語を正規表現の和集合演算 ``$|$''で繋げたパターンに対し, 各実装のコンパイル時
-間の比較を行った.
+表\ref{table:benchmark1}に結果を示す.
 
 \begin{table}[h]
 \caption{ベンチマーク:compile}
@@ -370,7 +524,7 @@
 に行われている. LLVMMによる実装では,APIを通じて直接LLVMの中間表現を操作
 することで, ファイルI/Oやパース等のオーバーヘッドもない.
 
-{\bf マッチング}\\
+\subsection{ベンチマーク: grep}
 マッチング時間の比較では,様々な正規表現を用いて比較を行った結果, 3つの実
 装でマッチング時間にあまり差が見られなかった. 生成されるコードはコードセ
 グメント/関数と, switch文によるシンプルな実装であることから, コンパイル
@@ -378,15 +532,61 @@
 
 本実装の中で最もマッチングが高速だったGCC-Cで生成した正規表現エンジンを用
 いてgrep に相当するプログラムを実装し,実際にテキストファイルからのパター
-ンマッチを行い, それぞれの評価を行う. 本実装との比較対象として,
+ンマッチを行い, それぞれの評価を行う. 本実装との比較対象として選択した
+grep について説明する.
+
+\subsection{GNU grep}
+GNU grep (\verb|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 (\verb|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を利用できる.
 
-\begin{description}
-\item[GNU grep] hoge
-\item[cgrep] fuga
-\item[Google RE2] piyo
-\end{description}
+C++による2万行程度の実装で, UTF-8に対応している.
+
+本実験では, Google RE2 の API である FindAndConsume を使用して, grep ク
+ローンを実装した. FindAndConsume はマッチング対象文字列と正規表現, マッ
+チした文字列を格納するポインタを引数にとり, マッチングの開始部分を内部的
+に更新していくAPIである. 以下が, RE2を用いたgrep実装のメインルーチンであ
+る.
 
-{\bf 実験環境}\\
+\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
@@ -406,12 +606,12 @@
 本実装(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
-cgrep 8.15 [s] & 1.85 & 6.48 \\
-\hline
 Google RE2 [s] & 30.10 & 16.92\\
 \hline
 \end{tabular}
@@ -445,10 +645,10 @@
 \end{description}
 
 2つのテストケースの結果を見てみると, 本実装はそれぞれGNU grep と比べて高
-速な結果となっており, コンパイル時間はマッチングにかかる時間と比べて無視
-できるほど短い時間である.
+速な結果となっており, この規模のファイルに対する grep の場合,コンパイル
+時間はマッチングにかかる時間と比べて無視できるほど短い時間であることが分かる.
 
-\subsection{特徴}
+\section{本実装の特徴}
 本実験によって実装された正規表現評価器の特徴を, GNU grep との比較をはさ
 みながら説明する.
 
@@ -531,7 +731,7 @@
 
 \begin{biography}
 \member{新屋 良磨}
-1988年生
+1988年生.
 %
 \member{河野 真治}
 1959年生．