Binary file tex/prosym-shinya.pdf has changed

--- a/tex/prosym-shinya.tex	Fri Dec 03 17:50:29 2010 +0900
+++ b/tex/prosym-shinya.tex	Fri Dec 03 20:59:26 2010 +0900
@@ -55,25 +55,25 @@
 903-0213 沖縄県中頭郡西原町字千原1\\
 琉球大学情報工学科\\
         TEL: (098)895-8723\qquad FAX: (098)895-8727\\
-        email: shinya@firefly.cr.ie.u-ryukyu.ac.jp}
+        email: shinya@cr.ie.u-ryukyu.ac.jp}
 
 % 和文概要
 \begin{abstract}
-当研究室では, 与えられた正規表現から, 等価な 有限状態オートマトンに変換し,
-オートマトンにおける状態遷遷移をC言語等のコンパイル型言語での関数遷移に
-変換する正規表現コンパイラを Python で開発している.
+与えられた正規表現から, 等価な 有限状態オートマトンに変換し,
+オートマトンにおける状態遷遷移をCや Continuation based C 等のコンパイル型言語での関数遷移に
+変換する正規表現コンパイラを Python で開発した\cite{R}.
 本論文では, その正規表現コンパイラを利用した, テキストファイルに対しパターン
 マッチを行いマッチする行を出力するツールである grep に特化した実装方法を説明し,
 実装した grep の性能を評価する.
 \end{abstract}
 % 英文概要
 \begin{eabstract}
-{\b 英訳 当研究室では}, 与えられた正規表現から, 等価な 有限状態オートマトンに変換し,
-オートマトンにおける状態遷遷移をC言語等のコンパイル型言語での関数遷移に
-変換する正規表現コンパイラを Python で開発している.
-本実験では, その正規表現コンパイラを元に, テキストファイルに対しパターン
-マッチを行いマッチする行を出力するツールである grep に相当するソフトウェ
-アを実装した.
+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}
 
 % 表題などの出力
@@ -449,7 +449,7 @@
 \begin{small}
 \begin{verbatim}
 void accept(UCHARP beg, UCHARP buf, UCHARP end) {
-  UCHARP ret = (UCHARP)memchr(buf, '\n', (buf - end));
+  UCHARP ret = (UCHARP)memchr(buf,'\n',(buf-end));
   if (ret == NULL) {
     print_line(beg, end);
     return;
@@ -468,6 +468,12 @@
 イラによって末尾呼び出しが適切に最適化された場合, スタック操作の無い高速
 な状態遷移を行なう実行バイナリに変換される.
 
+Intel Compiler で本実装による grep を最適化オプションを付加してコンパイ
+ル,実行したところ, 末尾呼び出し最適化が行なわれず,実行して即座にスタック
+オーバーフローを起こしてしまった. C言語では, 末尾呼び出し最適化を明示的
+に記述することができないので, このような状態遷移ベースのプログラミングは
+Continuation based C による記述が望ましいといえる.
+
 \subsection{固定文字列フィルタリング}
 GNU grep を含むいくつかの grep 実装では, マッチングを高速化するために様々
 な高速化の工夫を行なっている. 正規表現をDFAに変換してのマッチングや, 固
@@ -478,6 +484,15 @@
 て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
 
@@ -599,7 +614,7 @@
 \begin{table}[h]
 \caption{ベンチマーク:grep}
 \label{table:benchmark2}
-\begin{tabular}[t]{l|l|l|l}
+\begin{tabular}[t]{l|l|l}
 \hline\hline
 テストケース & fixed-string & complex-regex\\
 \hline
@@ -621,28 +636,28 @@
 および考察を記す. なお,ここで扱う正規表現の ``複雑さ''とは, DFAに
 変換した時点の状態数, 遷移規則の多さを基準としている.
 
-\begin{description}
-\item[fixed-string]固定文字列によるマッチング\\
+{\bf fixed-string 固定文字列によるマッチング}
 パターン  : ``$Wikipedia$''\\
 マッチ行数: 348936行\\
 GNU grep では, 与えられたパターン内に, 確実に含まれる文字列(固定文字列)
-が存在する場合は, Boyer-Moore-Horspool法 等の高速な文字列探索アルゴリズムを用いて
+が存在する場合は, Boyer-Moore 法 等の高速な文字列探索アルゴリズムを用いて
 フィルタをかけることで, DFAによるマッチングを減らし,高速化している. 本実
 装の grep でも, 同様に固定文字列フィルタによる高速化を行っているが, 単純
 な固定文字列の検索でも, コンパイルすることによる高速化が結果に出ている.
 
-\item[complex-regex]複雑な正規表現でのマッチング\\
+{\bf complex-regex 複雑な正規表現でのマッチング}
 パターン  :``$(Python|Perl|Pascall|Prolog|\\
 PHP|Ruby|Haskell|Lisp|Scheme)$''\\
 マッチ行数: 15030行\\
 このパターンは,9個の単語を和集合演算 ``$|$''で並べたもので,確実に含まれ
-る文字列は存在せず, fixed-stringに比べてGNU grep はマッチングに時間がか
-かっている.
+る文字列は存在しないが, 前述のCommentz-Walter法によるフィルタリングが適
+用できる.
+GNU grep, cgrep 及び本実装において fixed-string のケー
+スよりはマッチングに時間が
 
 さらに, GNU grep 2.5.4 は190秒と, 本実装及びGNU grep 2.6.3に対して非常に
 低速な結果となっているが, これは後述する mbrtowc(3) によるマルチバイト文
 字の変換処理によるオーバーヘッドによるものである.
-\end{description}
 
 2つのテストケースの結果を見てみると, 本実装はそれぞれGNU grep と比べて高
 速な結果となっており, この規模のファイルに対する grep の場合,コンパイル
@@ -652,7 +667,7 @@
 本実験によって実装された正規表現評価器の特徴を, GNU grep との比較をはさ
 みながら説明する.
 
-{\bf 正規表現からの動的なコード生成}\\
+\subsection{正規表現からの動的なコード生成}
 本実装による一番の特徴として, 正規表現から変換を行うことで得られる等価な
 DFAを, C/CbC/LLVM に変換しコンパイルすることで正規表現に応じた実行バイナ
 リを生成することが挙げられる. またコンパイラ理論におけるさまざまな最適化
@@ -665,7 +680,7 @@
 は構造体よって表され, 状態遷移は各状態毎に保持している遷移先ポインタによ
 る配列を,1Byte単位でテーブルルックアップを行うことで実装されている.
 
-{\bf UTF-8対応}
+\subsection{UTF-8対応}
 
 本実装は, マルチバイト文字の代表的な符号化方式であるUTF-8に内部的に対応しており,
 正規表現の演算は1Byte単位ではなく,1文字単位で適用される.
@@ -688,13 +703,13 @@
 2010年3月にリリースされた GNU grep 2.6 から, UTF-8に対して本実装と同様に
 内部的に対応することで, mbrtowc(3)による変換コストが無くなっている.
 
-{\bf 柔軟な実装}\\
+\subsection{柔軟な実装}
 本実験で実装した正規表現評価器は, Pythonによって実装されており,全体
-で3000行程度の軽量なプログラムとなっている. 比較対象のGNU grep は,
-C言語によって実装されており, プログラム全体は15000行程度の規模と
-なっている.
+で3000行程度の軽量なプログラムとなっている. 今回比較対象として利用した
+GNU grep, cgrep, Google RE2 はいずれも1\~2万行の規模のソフトウェアに比べ
+機能の追加やリファクタリングが用意であり, 本実装の優れた点と言えるだろう.
 
-さらに,本実装から動的に生成されるコードも,コードセグメント/関数とswitch
+ここで重要なのは, 本実装から動的に生成されるコードも,コードセグメント/関数とswitch
 を基準としたシンプルな記述で高い可読性を持ちつつ, 細かい最適化をGCC/LLVMの最適
 化技術を利用することで実行速度も非常に高速であることが実験結果から分かった.
 
@@ -708,24 +723,28 @@
 
 \begin{thebibliography}{9}
 
+\bibitem{B} Commentz-Walter, B: A String Matching Algorithm Fast on the
+        Average (1979)
+
 \bibitem{R1} Cox, R : Regular Expression Matching Can Be Simple And
-        Fast, 2007
+        Fast (2007)
 
 \bibitem{R2} Cox, R : Regular Expression Matching: the Virtual Machine
-        Approach, 2009
+        Approach (2009)
 
-\bibitem{R3} Cox, R : Regular Expression Matching in the Wild, 2010
+\bibitem{R3} Cox, R : Regular Expression Matching in the Wild (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, 2004
+        and Infrastructure (2004)
+
+\bibitem{R} 新屋 良磨 : 動的なコード生成を用いた正規表現エンジンの実装 (2010)
 
-\bibitem{K} Thompson, K : Regular Expression Search Algorithm, 1968
+\bibitem{K} Thompson, K : Regular Expression Search Algorithm (1968)
 
-\bibitem{Y} 与儀 健人 : 組込み向け言語Continuation based CのGCC上の実装,
-        2010
+\bibitem{Y} 与儀 健人 : 組込み向け言語Continuation based CのGCC上の実装 (2010)
 
 \end{thebibliography}