Mercurial > hg > Papers > 2016 > masa-master

changeset 87:04e333c17c0d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Thu, 18 Feb 2016 06:40:17 +0900
parents 53950092fce4
children 7e2e5f8bc516
files paper/c4.tex paper/master_paper.pdf
diffstat 2 files changed, 72 insertions(+), 99 deletions(-) [+]
line wrap: on
line diff
--- a/paper/c4.tex	Thu Feb 18 05:49:29 2016 +0900
+++ b/paper/c4.tex	Thu Feb 18 06:40:17 2016 +0900
@@ -3,7 +3,7 @@
 \chapter{Cerium による文字列処理の例題}
 本項ではファイルを読み込んで文字列処理を並列処理をする流れと例題を記述する。
 
-Cerium に実装している例題として、単語数を数える Word Countとファイルからあるパターンを検索する正規表現を紹介する。
+Cerium に実装している例題として、Word Count、Boyer-Moore String Search 、正規表現を紹介する。
 
 \section{文字列処理の並列処理}
 文字列処理を並列で処理する場合を考える。
@@ -14,7 +14,7 @@
 
 \begin{figure}[htpb]
   \begin{center}
-    \includegraphics[scale=0.2]{images/example/dividefile.pdf}
+    \includegraphics[scale=0.15]{images/example/dividefile.pdf}
   \end{center}
   \caption{File 読み込みから処理までの流れ}
   \label{fig:dividefile}
@@ -49,50 +49,6 @@
 }
 \end{lstlisting}
 
-\begin{lstlisting}[frame=lrbt,label=src:Exec,caption=文字列処理の記述部分,numbers=left]
-static int
-exec(SchedTask *s, void *rbuf, void *wbuf)
-{
-    // Input Data の設定(FileMapReduceにより自動的に生成される)
-    long task_spwaned = (long)s->get_param(0);
-    long division_size = (long)s->get_param(1);
-    long length = (long)s->get_param(2);
-    long out_size = (long)s->get_param(3);
-    long allocation = task_spwaned + (long)s->x;
-    char* i_data;
-    unsigned long long* o_data;
-    if (division_size) {
-        i_data = (char*)s->get_input(rbuf,0) + allocation*division_size;
-        o_data = (unsigned long long*)s->get_output(wbuf,1) + allocation*out_size;
-    } else {
-        i_data = (char*)s->get_input(0);
-        o_data = (unsigned long long*)s->get_output(0);
-    }
-
-    // 文字列処理をここに記述する。
-
-    // Output Data の設定
-    o_data[0] = (unsigned long long)word_num;
-    o_data[1] = (unsigned long long)line_num;
-    return 0;
-}
-\end{lstlisting}
-
-\begin{lstlisting}[frame=lrbt,label=src:Print,caption=結果を集計する Print ルーチン,numbers=left]
-static int
-run_print(SchedTask *s, void *rbuf, void *wbuf)
-{
-    MapReduce *w = (MapReduce*)s->get_input(0);
-    unsigned long long *idata = w->o_data;
-    int out_task_num = w->task_num;
-
-    // 結果の整合性や print などをここに記述する。
-
-    s->printf("\n");
-    return 0;
-}
-\end{lstlisting}
-
 ファイルを分割して文字列処理を行なった際、分割された部分でそれぞれの例題の整合性が取れなくなってしまうことがある。
 整合性の取り方についてはそれぞれの例題にて述べる。
 
@@ -135,26 +91,9 @@
 
 この問題の解決方法として、分割されたファイルの一つ目が文字で終わり、二つ目のファイルの先頭が改行または空白で始まった場合はそれぞれの単語数の合計数から 1 足すことにより整合性を取ることができる。
 
-ソースコード\ref{src:TMmain}はFileMapReduce を利用した文字列処理やファイル読み込みの Task の生成部分である。
-Cerium Task Manager を利用する際の main 関数は TMmain 関数に置き換わる。
-TMmain 関数内で Task の生成や Task の依存関係を記述するのだが、FileMapReduce クラスを利用すると、ファイルを読み込んで文字列処理をするプログラムを容易に実装することができる。
-
-\begin{lstlisting}[frame=lrbt,label=src:TMmain,caption=FileMapReduce による Word Count の生成,numbers=left]
-int
-TMmain(TaskManager *manager, int argc, char *argv[])
-{
-    /* 文字列処理後に出力されるデータの数を設定する。
-     * Word Count では
-     * 行数、単語数、ファイルの先頭に文字があるかどうかの flag、ファイルの末尾に文字があるかどうかの flag
-     * の4つのデータが出力される。
-     */
-    fmp->division_out_size = sizeof(unsigned long long)*4;
-}
-\end{lstlisting}
-
-ソースコード\ref{src:Exec}は分割されたファイルに対して何かしらの文字列処理を記述する部分である。
-22行目から45行目が Word Count のメインルーチン内で、文字列処理を行なっている部分である。
-もし Word Count 以外の文字列処理を記述したいのであれば、メインルーチン内を書き換えてあげればよい。
+ソースコード\ref{src:Exec}は Word Count のメインルーチンである。
+% 分割されたファイルを先頭から見ていき、まずは先頭が空白か改行かどうかをチェックする。
+% 空白や改行が読み込まれるたびに Word Num や Line Num をカウントしていき、最後に分割されたファイルの末尾が空白かどうかをチェックしている。
 
 \begin{lstlisting}[frame=lrbt,label=src:Exec,caption=文字列処理の記述,numbers=left]
 SchedDefineTask1(Exec,wordcount);
@@ -162,16 +101,10 @@
 static int
 wordcount(SchedTask *s, void *rbuf, void *wbuf)
 {
-    // Word Count のメインルーチン
     unsigned long long *head_tail_flag = o_data +2;
-    int word_flag = 0;
-    int word_num = 0;
-    int line_num = 0;
-    int i = 0;
     // 先頭が空白か改行かのチェック
     head_tail_flag[0] = (i_data[0] != 0x20) && (i_data[0] != 0x0A);
     word_num -= 1-head_tail_flag[0];
-
     for (; i < length; i++) {
         if (i_data[i] == 0x20) { // 空白
             word_flag = 1;
@@ -194,8 +127,8 @@
 \end{lstlisting}
 
 ソースコード\ref{src:Print}は、それぞれの Task で出力された結果をまとめる処理がまとめられている。
-Task それぞれの単語数と行数を集計し、分割された部分に関して整合性をとり単語数を微調整する。
-単語数、行数がそれぞれ決定されたのちに結果が print される。
+Task それぞれの単語数と行数を集計し、分割された部分に関して整合性をとり単語数を調整する。
+単語数、行数がそれぞれ決定されたのちに結果が Print される。
 
 \begin{lstlisting}[frame=lrbt,label=src:Print,caption=結果を集計する Print ルーチン,numbers=left]
 #define STATUS_NUM 2
@@ -246,7 +179,6 @@
 \label{fig:bruteforth}
 \end{figure}
 
-\newpage
 このアルゴリズムは実装が容易であるが、 text と pattern の文字数が大きくなるにつれて、比較回数も膨大になる恐れがある。
 text の長さを $n$、pattern の長さを $m$とすると、力任せ法の最悪計算時間は $O(nm)$ となる。
 
@@ -301,10 +233,13 @@
 \item pattern に含まれている文字でその文字が pattern に複数含まれている場合は後ろにずらす量も複数現れる。その中の最小の値だけ後ろにずらす。
 \end{itemize}
 
+不一致が起きたときの文字によって数文字分だけ後ろにずらす skip table を、文字列探索する前に生成する必要がある。
+
 text 分割時に、分割部分で pattern が含まれる場合が存在する。
 その場合は、本来の読み込み部分の text の長さ $L$ に加えて、pattern の長さ $s$ から 1 引いた数だけ多く読みこむように設計することで、正しく結果を算出することができる。
 (図\ref{fig:iodivsuc})
 
+
 \begin{figure}[htbp]
 \begin{center}
 \includegraphics[width=1.0\textwidth]{images/example/iodivsuc.pdf}
@@ -313,14 +248,18 @@
 \label{fig:iodivsuc}
 \end{figure}
 
-\begin{lstlisting}[frame=lrbt,label=src:Print,caption=結果を集計する Print ルーチン,numbers=left]
+Boyer-Moore String Search は文字列処理の Task を生成する前に、Skip Table を生成している。
+そして Boyer-Moore String Search に必要な情報を bm という構造体にまとめ、この構造体をそれぞれの Task に送信している。
+(ソースコード\ref{src:bmTMmain})
+
+\begin{lstlisting}[frame=lrbt,label=src:bmTMmain,caption=Task の生成前に Boyer Moore の skip table を生成,numbers=left]
 typedef struct bm {
     int* skip_table;
     unsigned char *search_word;
     int search_word_len;
 } BM, *BMPtr;
 
-//Boyer Moore法に使用するテーブルを作成
+//Boyer Moore String Search で使用する skip table を作成
 static void
 create_BMskiptable(BMPtr bm)
 {
@@ -355,14 +294,52 @@
 }
 \end{lstlisting}
 
-\begin{lstlisting}[frame=lrbt,label=src:Print,caption=結果を集計する Print ルーチン,numbers=left]
+
+
+\begin{lstlisting}[frame=lrbt,label=src:bmexec,caption=Boyer-Moore String Search のメインルーチン,numbers=left]
+static int BM_method(unsigned char *text,int text_len,
+              unsigned char *pattern,int sw_len,int *skip)
+{
+    int i = sw_len - 1;
+    int match_counter = 0;
+
+    while ( i < text_len){
+        int j = sw_len - 1;
+        // pattern の末尾から比較していく
+        while (text[i] == pattern[j]){
+            if (j == 0){
+                match_counter++;
+            }
+            --i;
+            --j;
+        }
+        i = i + max(skip[text[i]],sw_len - j);
+    }
+    return match_counter;
+}
+
+static int
+task_exec(SchedTask *s, void *rbuf, void *wbuf)
+{
+    unsigned char *i_data = (unsigned char *)s->get_input(0);
+    int length = (int)s->get_inputSize(0);
+    MapReduce *w = (MapReduce*)s->get_param(4);
+    BMPtr bm = (BMPtr)w->global;
+
+    unsigned long long *o_data = (unsigned long long*)s->get_output(0);
+
+    o_data[0] = BM_method(i_data,length,bm->search_word,bm->search_word_len,bm->skip_table);
+    return 0;
+}
+\end{lstlisting}
+
+\begin{lstlisting}[frame=lrbt,label=src:bmprint,caption=Boyer-Moore String Search の結果の集計,numbers=left]
 static int
 print_task(SchedTask *s, void *rbuf, void *wbuf)
 {
     MapReduce *w = (MapReduce*)s->get_input(0);
     unsigned int idata_task_num = w->task_num;
     int match_counter = 0;
-
     for (int i = 0;i < idata_task_num;i++) {
             match_counter += idata[i];
     }
@@ -370,7 +347,6 @@
 }
 \end{lstlisting}
 
-
 \section{正規表現}
 % 正規表現の話を 2 ページずつぐらいで
 正規表現は文字列のパターンを表現するための方法である。
@@ -381,7 +357,7 @@
 
 このようなあるパターンで文字列を表現できる場合は、正規表現を利用すればこの問題は簡単に解決することができる。
 正規表現にはメタ文字と呼ばれる正規表現内での特殊記号があり、それらを利用することによって BOSE、Bose、bose の 3 つの文字列を一つの正規表現で表現することができる。
-(表\ref{fig:regexbasic})
+(図\ref{fig:regexbasic})
 
 \begin{figure}[htbp]
 \begin{center}
@@ -391,6 +367,7 @@
 \label{fig:regexbasic}
 \end{figure}
 
+\newpage
 本実装でサポートするメタ文字は、正規表現の基本三演算子(連接、繰返し、選択)\cite{regex}に文字クラスとグループを加えている。 (表\ref{table:metachar})
 
 \begin{tiny}
@@ -528,7 +505,7 @@
 
 \begin{figure}[htpb]
   \begin{center}
-    \includegraphics[scale=0.2]{images/regex/regexgroup.pdf}
+    \includegraphics[scale=0.18]{images/regex/regexgroup.pdf}
   \end{center}
   \caption{グループ}
   \label{fig:regexgroup}
@@ -539,7 +516,7 @@
 
 \begin{figure}[htpb]
   \begin{center}
-    \includegraphics[scale=0.2]{images/regex/regexseqregex.pdf}
+    \includegraphics[scale=0.18]{images/regex/regexseqregex.pdf}
   \end{center}
   \caption{正規表現の連接}
   \label{fig:regexseqregex}
@@ -547,6 +524,7 @@
 
 これらのルールに則って正規表現木を構成し、それを元に DFA・NFA を生成していく。
 
+\newpage
 \subsection{正規表現木から DFA・NFA の生成}
 
 次に正規表現木から非決定性有限オートマトン(NFA)、決定性有限オートマトン(DFA)を生成する。
@@ -558,11 +536,11 @@
 \item `*' があれば、次の状態は `*' に接続されている木の先頭の状態と同じ。次の状態が受理状態なら先頭の状態と受理状態の組み合わせになる。
 \end{itemize}
 
-ノードに状態を割り振りながら次の状態の遷移先を設定することによって、正規表現木からオートマトンによる状態遷移を表現することができる。
+ノードに状態を割り振りながら次の状態の遷移先を設定することによって、オートマトンによる状態遷移を表現することができる。
 
 \begin{figure}[htpb]
   \begin{center}
-    \includegraphics[scale=0.13]{images/regex/allostate.pdf}
+    \includegraphics[scale=0.17]{images/regex/allostate.pdf}
   \end{center}
   \caption{与えられた正規表現木に状態を割り振る}
   \label{fig:allostate}
@@ -591,9 +569,10 @@
   \label{fig:nfaex}
 \end{figure}
 
+\newpage
 
 1 入力に対して遷移先が複数存在している場合は、文字によって場合分けをする必要がある。
-図\ref{fig:dfaregex} の
+図\ref{fig:nfaex} の
 状態 4 は [a-z] が入力されると状態 4 に遷移し、b が入力されると状態 2 に遷移する。このとき、b が入力されると状態 2 か状態 4 のどちらかに遷移することになる。(図\ref{fig:nfa})
 
 \begin{figure}[htpb]
@@ -667,19 +646,19 @@
   \label{fig:CharClassMergePattern}
 \end{figure}
 
-\subsection{並列正規表現マッチャの実装}
+\subsection{正規表現マッチャの並列処理の実装}
 正規表現から正規表現木を生成し、その木に対して状態を割り振りを行ない、Subset Construction による新しい状態の生成が終わったあとにマッチングを行う。
 なお、Subset Construction による新しい状態の生成はマッチングの前に行うことも可能であるが、マッチング途中で新しい状態を発見したときにその都度生成することも可能である。
+
 % bit パターンの実装の話
 本研究の実装では、状態を Bit Pattern で表現している。
 Bit Pattern で状態を持つことで、Subset Construction による状態の組み合わせも Bit Pattern の和を取ることで容易に表現できる。
-
 % state 構造 bitvector の話 配列を MaxState の分のコードの話
-状態は StateArray と呼ばれる配列で格納されており、状態遷移が行われるたびに配列を見に行く。
+その状態は StateArray と呼ばれる配列で格納されており、状態遷移が行われるたびに StateArray を見に行く。
 あらかじめ配列の大きさのメモリを確保する必要があるが、Subset Construction による新しい状態生成も考慮しなければならない。
-正規表現木に状態を割り振った時に最大の状態の Bit は分かっている。その状態の Bit の 2 倍だけ配列を確保しておけば、Bit Pattern が全て 1 までの状態を表現することができる。
+正規表現木に状態を割り振った時に最大の状態の Bit は分かっているので、その状態の Bit の 2 倍だけ配列を確保しておけば、Bit Pattern が全て 1 までの状態を表現することができる。
 状態の遷移先は文字クラスごとの List 構造になっており、その状態に入力が行われたらそのリストを辿って遷移先の状態を判断する。
-図\ref{fig:statearray}
+(図\ref{fig:statearray})
 
 \begin{figure}[htpb]
   \begin{center}
@@ -692,17 +671,11 @@
 % subset construction の速度 O(mlogn)
 
 \begin{lstlisting}[frame=lrbt,label=src:result,caption=ceriumGrep の TMmain,numbers=left]
-typedef struct result {
-    unsigned char *begin;
-    unsigned char *end;
-    struct result *next;
-} Result, *ResultPtr;
-
 int
 TMmain(TaskManager *manager, int argc, char *argv[])
 {
     char *filename = 0;
-    Search s = grep(argc,argv,true);
+    Search s = grep(argc,argv,true);  // 正規表現木の生成、木の状態割り振りを行う
     FileMapReduce *fmp = new FileMapReduce(manager,TASK_EXEC,TASK_EXEC_DATA_PARALLEL,TASK_PRINT);
     filename = fmp->init(argc, argv);
     fmp->w->global = (void*)s.tg;
@@ -716,7 +689,7 @@
 }
 \end{lstlisting}
 
-\begin{lstlisting}[frame=lrbt,label=src:task,caption= Task 側の記述,numbers=left]
+\begin{lstlisting}[frame=lrbt,label=src:task,caption=正規表現のマッチング部分,numbers=left]
 TSValue blockSearch(TSValue tsv,Buffer buff,int task_spawned) {
     tsv.current = tsv.tg->stateStart->tState;
     tsv.blk->result = NULL;
Binary file paper/master_paper.pdf has changed