Mercurial > hg > Papers > 2016 > masa-master
changeset 36:466a8ed9c372
fix
author | Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 09 Feb 2016 18:59:23 +0900 (2016-02-09) |
parents | daee752a04d0 |
children | 49614a7deaaa |
files | c4.tex master_paper.pdf memo/result.txt |
diffstat | 3 files changed, 10 insertions(+), 6 deletions(-) [+] |
line wrap: on
line diff
--- a/c4.tex Tue Feb 09 17:12:59 2016 +0900 +++ b/c4.tex Tue Feb 09 18:59:23 2016 +0900 @@ -1,7 +1,7 @@ \chapter{Cerium による文字列処理の例題} 本項ではファイルを読み込んで処理する流れとそれの例題を記述する。例題として、単語数を数える Word Count、文字列探索を行う Boyer Moore Search、正規表現を挙げる。 -\section{File 読み込みを含んだ並列処理(File Map Reduce?)} +\section{文字列処理の並列処理} 文字列処理を並列で処理する場合を考える。 まずファイルを読み込み、ファイルをある一定の大きさで分割する(divide a file)。 そして、分割されたファイル(Input Data)に対して文字列処理(Task)をおこない、それぞれの分割単位で結果を出力する(Output Data)。 @@ -152,8 +152,8 @@ \begin{enumerate} \item 与えられた正規表現を構文解析し、正規表現木に変換する。 \item 正規表現木から非決定性オートマトン(以下、NFA)か決定性オートマトン(以下、DFA)に変換する。 -\item NFA に変換された場合、Subset Construction による NFA から DFA への変換をおこない、状態遷移テーブルを生成する。 -\item 状態遷移のテーブルを元に文字列検索を行ない結果を返す。 +\item NFA に変換された場合、Subset Construction による NFA から DFA への変換をおこなう。 +\item DFA を元に文字列検索を行ない結果を返す。 \end{enumerate} となる。本項はそれぞれのアルゴリズムについて述べていく。 @@ -448,7 +448,9 @@ 図\ref{fig:nfaregex} -\subsection{Subset Construction による NFA から DFA の変換と状態遷移テーブルの生成} +\subsection{Subset Construction による NFA から DFA の変換} + +\subsection{DFA を元にパターンマッチを行う} \begin{figure}[htpb] \begin{center}
--- a/memo/result.txt Tue Feb 09 17:12:59 2016 +0900 +++ b/memo/result.txt Tue Feb 09 18:59:23 2016 +0900 @@ -1,7 +1,9 @@ Mon Feb 8 17:24:16 JST 2016 -time cgrep -G '[A-Z][a-zA-Z0-9_]*' ../../Game/Cerium/example/bm_search/1GB.txt --no-line-umber --no-filename +compare cprep egrep ceriumgrep seqsearch + -Wed Feb 3 18:04:02 JST 2016 +time cgrep -G '[A-Z][a-zA-Z0-9_]*' ../../Game/Cerium/example/bm_search/1GB.txt --no-line-umber --no-filename >/dev/null + [word count] firefly cpu time