# HG changeset patch # User Masataka Kohagura # Date 1455557592 -32400 # Node ID 6415e51788a64eb8bd071d670c091e0d523f3dc5 # Parent 0d13c52a54fd4efbf9569f6d3f13e8a623461665 add diff -r 0d13c52a54fd -r 6415e51788a6 paper/c3.tex --- a/paper/c3.tex Mon Feb 15 20:56:13 2016 +0900 +++ b/paper/c3.tex Tue Feb 16 02:33:12 2016 +0900 @@ -25,7 +25,7 @@ \begin{figure}[htpb] \begin{center} - \includegraphics[scale=0.15]{images/cerium/mmap.pdf} + \includegraphics[scale=0.20]{images/cerium/mmap.pdf} \end{center} \caption{mmap Model} \label{fig:mmap} diff -r 0d13c52a54fd -r 6415e51788a6 paper/c4.tex --- a/paper/c4.tex Mon Feb 15 20:56:13 2016 +0900 +++ b/paper/c4.tex Tue Feb 16 02:33:12 2016 +0900 @@ -18,39 +18,21 @@ \label{fig:dividefile} \end{figure} +\newpage ファイルを読み込んで文字列処理をする流れを1つのクラスとして Cerium 内に組み込んだ。 Cerium で文字列処理の並列処理を記述する際にこのクラスを利用すれば、 自動的にファイルをある程度のサイズに分割し、文字列処理の Task と結果を表示する Print Task の依存関係も設定される。 このクラスは、ファイルをマッピングし処理をすることで小さいデータの集合を出力することから FileMapReduce と名付けた。 -% FileMapReduce の例題として WordCount を紹介する。 -% File を -% \begin{lstlisting}[frame=lrbt,label=src:createTask,caption=FileMapReduce による Word Count の生成,numbers=left] -% int -% TMmain(TaskManager *manager, int argc, char *argv[]) -% { -% char *filename = 0; -% FileMapReduce *fmp = new FileMapReduce(manager,TASK_EXEC,TASK_EXEC_DATA_PARALLEL,TASK_PRINT); -% filename = fmp->init(argc, argv); -% if (filename < 0) { -% return -1; -% } -% /* 文字列処理後に出力されるデータの数を設定する。 -% * Word Count では -% * 行数、単語数、ファイルの先頭に文字があるかどうかの flag、ファイルの末尾に文字があるかどうかの flag -% * の4つのデータが出力される。 -% */ -% fmp->division_out_size = sizeof(unsigned long long)*4; -% task_init(); -% fmp->run_start(manager, filename); -% return 0; -% } -% \end{lstlisting} +FileMapReduce の例題として \ref{sec:wc}章の Word Count 内で紹介する。 +FileMapReduce のコンストラクタを生成すると、ファイルの分割や文字列処理の Task と Print Task の依存関係を設定してくれる。 + ファイルを分割して文字列処理を行なった際、分割された部分でそれぞれの例題の整合性が取れなくなってしまうことがある。 整合性の取り方についてはそれぞれの例題にて述べる。 \section{Word Count} +\label{sec:wc} Word Count は読み込んだテキストに対して単語数を数える処理である。 Input Data には分割されたテキストが対応しており、Output Data には単語数と行数を出力する。 @@ -88,8 +70,137 @@ この問題の解決方法として、分割されたファイルの一つ目が文字で終わり、二つ目のファイルの先頭が改行または空白で始まった場合はそれぞれの単語数の合計数から 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[]) +{ + char *filename = 0; + FileMapReduce *fmp = new FileMapReduce(manager,TASK_EXEC,TASK_EXEC_DATA_PARALLEL,TASK_PRINT); + filename = fmp->init(argc, argv); + if (filename < 0) { + return -1; + } + /* 文字列処理後に出力されるデータの数を設定する。 + * Word Count では + * 行数、単語数、ファイルの先頭に文字があるかどうかの flag、ファイルの末尾に文字があるかどうかの flag + * の4つのデータが出力される。 + */ + fmp->division_out_size = sizeof(unsigned long long)*4; + task_init(); + fmp->run_start(manager, filename); + return 0; +} +\end{lstlisting} + \newpage +ソースコード\ref{src:Exec}は分割されたファイルに対して何かしらの文字列処理を記述する部分である。 +22行目から45行目が Word Count のメインルーチン内で、文字列処理を行なっている部分である。 +もし Word Count 以外の文字列処理を記述したいのであれば、メインルーチン内を書き換えてあげればよい。 + +\begin{lstlisting}[frame=lrbt,label=src:Exec,caption=文字列処理の記述,numbers=left] +SchedDefineTask1(Exec,wordcount); + +static int +wordcount(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); + } + + // 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; + } else if (i_data[i] == 0x0A) { // 改行 + line_num += 1; + word_flag = 1; + } else { + word_num += word_flag; + word_flag = 0; + } + } + word_num += word_flag; + // ファイルの末尾が空白か改行かのチェック + head_tail_flag[1] = (i_data[i-1] != 0x20) && (i_data[i-1] != 0x0A); + // Output Data の設定 + o_data[0] = (unsigned long long)word_num; + o_data[1] = (unsigned long long)line_num; + return 0; +} +\end{lstlisting} + + +\newpage + +ソースコード\ref{src:Print}は、それぞれの Task で出力された結果をまとめる処理がまとめられている。 + +\begin{lstlisting}[frame=lrbt,label=src:Print,caption=結果を集計する Print ルーチン,numbers=left] +#define STATUS_NUM 2 + +SchedDefineTask1(Print,run_print); + +static int +run_print(SchedTask *s, void *rbuf, void *wbuf) +{ + MapReduce *w = (MapReduce*)s->get_input(0); + unsigned long long *idata = w->o_data; + long status_num = STATUS_NUM; + int out_task_num = w->task_num; + + unsigned long long word_data[STATUS_NUM]; + int flag_cal_sum = 0; + s->printf("start sum\n"); + for (int i = 0; i < STATUS_NUM; i++) { + word_data[i] = 0; + } + int out_size = w->division_out_size / sizeof(unsigned long long); + // 結果の整合性を取りながら、行数と単語数をカウントする。 + for (int i = 0; i < out_task_num ; i++) { + word_data[0] += idata[i*out_size+0]; // 単語数の集計 + word_data[1] += idata[i*out_size+1]; // 行数の集計 + // 前のファイルの末尾と次のファイルの先頭を比較し単語数の集計を微調整 + unsigned long long *head_tail_flag = &idata[i*out_size+2]; + if((i!=out_task_num-1)&& + (head_tail_flag[1] == 1) && (head_tail_flag[4] == 0)) { + flag_cal_sum++; + } + } + word_data[0] += flag_cal_sum; + for (int i = status_num-1; i >=0; i--) { + s->printf("%llu ",word_data[i]); + } + s->printf("\n"); + return 0; +} +\end{lstlisting} + + \section{正規表現} 正規表現は文字列のパターンを表現するための方法である。 @@ -97,8 +208,9 @@ BOSE という文字列は、そのファイルに Bose もしくは bose と記述されているかもしれない。 もし、BOSE で検索すると小文字が含まれている Bose、bose は検索の対象外となってしまい、それら一つ一つを検索するのは手間が掛かってしまう。 -正規表現を利用すれば、この問題は簡単に解決することができる。 +このようなあるパターンで文字列を表現できる場合は、正規表現を利用すればこの問題は簡単に解決することができる。 正規表現にはメタ文字と呼ばれる正規表現内での特殊記号があり、それらを利用することによって BOSE、Bose、bose の 3 つの文字列を一つの正規表現で表現することができる。 +(表\ref{fig:regexbasic}) \begin{figure}[htbp] \begin{center} @@ -109,7 +221,33 @@ \end{figure} 本実装でサポートするメタ文字は、正規表現の基本三演算子(連接、繰返し、選択)\cite{regex}に文字クラスとグループを加えている。 -(表\ref{table:metachar}) + +連接はメタ文字を含まない文字列で構成された正規表現である。 +`word' や `automaton' などの文字列も連接のみの正規表現の一部である。 +正規表現の演算子には必ず何かしらの記号が割り当てられるのだが、連接だけにはメタ文字が割り振られていない。 + +繰返しは `*' の直前の文字または正規表現の繰返しを表現するメタ文字である。 +`*' の直前の文字や正規表現の 0 回以上の繰返しを表している。 +`a*b' という正規表現にマッチする文字列は {b,ab,aab,aaab,aa...b} である。 + +選択 `\textbar' は`\textbar' 前後の文字または正規表現の選択を表すメタ文字である。 +`a\textbar b' という正規表現にマッチする文字列は {a,b} である。 + +文字クラス`['`]' は`['`]'内に記述した文字の範囲から任意の一文字を選択するメタ文字である。 +数字の中から任意の1文字を選択だけの正規表現で表現すると、 + +$`0 \verb||| 1 \verb||| 2 \verb||| 3 \verb||| 4 \verb||| 5 \verb||| 6 \verb||| 7 \verb||| 8 \verb||| 9'$ +となる。 +この正規表現でも正しいのだが、とても煩わしい正規表現である。これを簡潔に表現できるのが文字クラスの強みである。 +文字クラスで数字の中から任意の一文字を表現すると `[0-9]' と表現することができる。 +数字だけではなく、アルファベットの中から任意の一文字も `[A-Za-z]' と表現することができる。 + +グループ`('`)' は `('`)' 内に記述した正規表現を一旦まとめる機能を持つ。 +例えば、word という文字列の 0 回以上の繰返しの正規表現を記述する。 +$ `word*' $ と表現すると、`*' の直前の `d' だけに接続される。この正規表現にマッチする文字列は{wor, word, wordd, worddd, wordd...d} となり、word の繰返しではない文字列がマッチする。 +`word' という文字列の繰返しを表現するときは、`(word)*'と記述することで表現できる。 + +これらのメタ文字をまとめた表が以下の表\ref{table:metachar}である。 \begin{tiny} \begin{table}[ht] @@ -133,8 +271,6 @@ \end{table} \end{tiny} -\newpage - また、これらのメタ文字は数式の四則演算のように結合順位を持っている。それぞれのメタ文字の結合順位は表\ref{table:bond}のようになる。 \begin{tiny} @@ -161,7 +297,9 @@ \end{table} \end{tiny} -今回実装した正規表現マッチャのアルゴリズムは、 +\newpage + +例題として実装した正規表現マッチャのアルゴリズムは、 \begin{enumerate} \item 与えられた正規表現を構文解析し、正規表現木に変換する。 @@ -172,24 +310,18 @@ となる。本項はそれぞれのアルゴリズムについて述べていく。 -\newpage - \subsection{正規表現木の生成} まずはじめに、図\ref{fig:parser}のように与えられた正規表現から正規表現木に変換する。 与えられた正規表現を頭から一文字ずつ読み込み、読み込んだ文字やメタ文字と呼ばれる正規表現での特殊記号を元に木を構成していく。 - \begin{figure}[htpb] \begin{center} - \includegraphics[scale=0.2]{images/regex/parser.pdf} + \includegraphics[scale=0.16]{images/regex/parser.pdf} \end{center} \caption{正規表現から正規表現木への変換の例} \label{fig:parser} \end{figure} - -また、以下よりメタ文字を含まない文字や文字クラスのことを文字、文字が連接されている場合を文字列、全ての文字が含まれている場合は正規表現と表現する。 - 正規表現木は与えられた正規表現を先頭から一文字ずつ読み込み、読み込んだ文字やメタ文字を一定のルールに従って生成していく。 文字やメタ文字、文字クラスは正規表現木のノードとして表現され、メタ文字が現れた時に親子関係が決定される。 @@ -203,8 +335,6 @@ \label{fig:regexseq} \end{figure} -\newpage - また、文字列のように連接が連続した場合、連接済みの `+' ノードを左の子ノードとしてさらに `+' ノードで結合していく。 (図\ref{fig:regexseq2}) @@ -216,6 +346,8 @@ \label{fig:regexseq2} \end{figure} +\newpage + 選択 `\textbar' が読み込まれた場合、親ノードを `\textbar'として、 `\textbar' の直前の正規表現は左ノード、直後の正規表現は右ノードとした木が構成される。 `\textbar'は直前と直後の正規表現の関係を表しているので、左右のノードに正規表現の要素を持ったノードとなる。 (図\ref{fig:regexselect}) @@ -228,7 +360,6 @@ \label{fig:regexselect} \end{figure} -\newpage 繰返し `*' が読み込まれた場合、`*' の直前の正規表現を左の子ノードとした木が生成される。 また `*' は、`*' の直前の正規表現だけに結合するので、右の子ノードに何かしらのノードが生成されることはない。 @@ -242,6 +373,7 @@ \label{fig:regexasta} \end{figure} +\newpage グループ化 `(' `)' が読み込まれた場合、`(' `)'内をひとかたまりの正規表現として木を構成する。 構成後さらに文字列が読み込まれれば、上記のルールにしたがって木が構成される。 @@ -255,8 +387,8 @@ \label{fig:regexgroup} \end{figure} -\newpage 正規表現が連接した場合も文字の連接と同様に `+' を親ノードとして接続していく。 +(図\ref{fig:regexseqregex}) \begin{figure}[htpb] \begin{center} @@ -267,13 +399,52 @@ \end{figure} これらのルールに則って正規表現木を構成し、それを元に DFA・NFA を生成していく。 +\newpage -\newpage \subsection{正規表現木から DFA・NFA の生成} 次に正規表現木から非決定性有限オートマトン(NFA)、決定性有限オートマトン(DFA)を生成する。 オートマトンは、入力に対して状態に対応した処理を行ない結果を出力する仮想的な自動機械である。 +オートマトンの身近な例として、朝起きて学校に行くまでの例を挙げる。 + +図\ref{fig:dfabasic}は、朝起きて学校に向かうまでの状態遷移図である。 +状態遷移図の `S' は初期状態を表し、`AC' は受理状態を表す。 + +私たちの日常でも起床の時間帯によって学校に行くまでの行動が変わる。 +もし早起きをしたならば、時間的にゆとりがあるので身なりをしっかり整えて学校に向かうことができる。 +この時、 $S -> 1 -> 2 -> AC$と状態が遷移する。 + +もし寝坊をしてしまった場合、時間的にゆとりがなく身なりを整える余裕がない。 +その時は身なりを整える暇もなく学校へ向かうことになってしまう。 +この時、 $S -> 3 -> AC$と状態が遷移する。 + +この例の場合、入力に当たるのは`早起きする'、`寝坊する'、`身なりを整える'、`学校に向かう'のそれぞれの行動であり、出力はその行動後に遷移する状態である。 + +このように、入力と状態が有限個で、どの状態でもある入力に対して遷移先が一意に決定されるオートマトンを決定性有限オートマトン(Deterministic Finite Automaton: DFA)という。 +\begin{figure}[htpb] + \begin{center} + \includegraphics[scale=0.2]{images/regex/dfabasic.pdf} + \end{center} + \caption{起きてから学校に行くまでの状態遷移図(DFA)} + \label{fig:dfabasic} +\end{figure} + +図\ref{fig:nfabasic}は、朝起きて学校に向かうまでの状態遷移図であるが、図\ref{fig:dfabasic}と違う点は S の状態で入力されるのは`起きる'という入力だけである。 + +この場合、起きて身なりを整え学校に向かうか起きて学校に向かうかの二択になる。 +S の状態のとき、起きてから次の状態に遷移するのは 1 か 2 のときである。 + +このように入力と状態が有限個で、ある入力に対して複数の遷移先があり一意に決定されないオートマトンを非決定性オートマトン(Non-deterministic Finite Automaton: NFA)という。 + +\begin{figure}[htpb] + \begin{center} + \includegraphics[scale=0.2]{images/regex/nfabasic.pdf} + \end{center} + \caption{起きてから学校に行くまでの状態遷移図(NFA)} + \label{fig:nfabasic} +\end{figure} + 正規表現はオートマトンで表現することができるので、状態と入力(ここでは正規表現)が判れば次はどのような状態になるのか決定される。 そのオートマトンの状態を、変換された正規表現木に状態を割り振っていく。 diff -r 0d13c52a54fd -r 6415e51788a6 paper/images/image.graffle --- a/paper/images/image.graffle Mon Feb 15 20:56:13 2016 +0900 +++ b/paper/images/image.graffle Tue Feb 16 02:33:12 2016 +0900 @@ -26,7 +26,7 @@ MasterSheets ModificationDate - 2016-02-15 11:38:39 +0000 + 2016-02-15 15:39:23 +0000 Modifier MasaKoha NotesVisible @@ -45045,7 +45045,969 @@ Bounds - {{103.22047084153401, 508.81890225438616}, {172.913387395641, 35}} + {{249.44882116092475, 305.5314985175653}, {94.960630782851936, 59}} + Class + ShapedGraphic + FitText + Vertical + Flow + Resize + FontInfo + + Color + + b + 0 + g + 0 + r + 0 + + + ID + 392 + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Align + 0 + Text + {\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset128 HiraginoSans-W3;} +{\colortbl;\red255\green255\blue255;} +\deftab720 +\pard\pardeftab720\partightenfactor0 + +\f0\fs32 \cf0 \'90\'67\'82\'c8\'82\'e8\'82\'f0\ +\'90\'ae\'82\'a6\'82\'e9} + + + + Bounds + {{104.74802737456594, 368.99606618130269}, {94.960630782851936, 35}} + Class + ShapedGraphic + FitText + Vertical + Flow + Resize + FontInfo + + Color + + b + 0 + g + 0 + r + 0 + + + ID + 391 + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Align + 0 + Text + {\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset128 HiraginoSans-W3;} +{\colortbl;\red255\green255\blue255;} +\deftab720 +\pard\pardeftab720\partightenfactor0 + +\f0\fs32 \cf0 \'8b\'4e\'82\'ab\'82\'e9} + + + + Bounds + {{104.74802737456594, 479.79331120168092}, {77.95275661278896, 35}} + Class + ShapedGraphic + FitText + Vertical + Flow + Resize + FontInfo + + Color + + b + 0 + g + 0 + r + 0 + + + ID + 390 + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Align + 0 + Text + {\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset128 HiraginoSans-W3;} +{\colortbl;\red255\green255\blue255;} +\deftab720 +\pard\pardeftab720\partightenfactor0 + +\f0\fs32 \cf0 \'8b\'4e\'82\'ab\'82\'e9} + + + + Bounds + {{396.85039730147116, 360.80708957027014}, {116.22047349543087, 35}} + Class + ShapedGraphic + FitText + Vertical + Flow + Resize + FontInfo + + Color + + b + 0 + g + 0 + r + 0 + + + ID + 389 + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Align + 0 + Text + {\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset128 HiraginoSans-W3;} +{\colortbl;\red255\green255\blue255;} +\deftab720 +\pard\pardeftab720\partightenfactor0 + +\f0\fs32 \cf0 \'8a\'77\'8d\'5a\'82\'c9\'8c\'fc\'82\'a9\'82\'a4} + + + + Bounds + {{297.63779797610334, 494.03543723576388}, {116.22047349543087, 35}} + Class + ShapedGraphic + FitText + Vertical + Flow + Resize + FontInfo + + Color + + b + 0 + g + 0 + r + 0 + + + ID + 388 + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Align + 0 + Text + {\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset128 HiraginoSans-W3;} +{\colortbl;\red255\green255\blue255;} +\deftab720 +\pard\pardeftab720\partightenfactor0 + +\f0\fs32 \cf0 \'8a\'77\'8d\'5a\'82\'c9\'8c\'fc\'82\'a9\'82\'a4} + + + + Class + LineGraphic + FontInfo + + Font + Helvetica + Size + 12 + + Head + + ID + 382 + + ID + 387 + Points + + {350.36614237526271, 360.27559350245565} + {449.57874170063053, 438.22835011524467} + + Style + + shadow + + Draws + NO + + stroke + + HeadArrow + FilledArrow + Legacy + + LineType + 1 + TailArrow + 0 + + + Tail + + ID + 380 + + + + Class + LineGraphic + FontInfo + + Font + Helvetica + Size + 12 + + Head + + ID + 382 + + ID + 386 + Points + + {224.57873965917133, 516.18110672803346} + {449.57874170063053, 438.22835011524467} + + Style + + shadow + + Draws + NO + + stroke + + HeadArrow + FilledArrow + Legacy + + LineType + 1 + TailArrow + 0 + + + Tail + + ID + 381 + + + + Class + LineGraphic + FontInfo + + Font + Helvetica + Size + 12 + + Head + + ID + 381 + + ID + 385 + Points + + {109.42125829936965, 438.22835011524467} + {224.57873965917133, 516.18110672803346} + + Style + + shadow + + Draws + NO + + stroke + + HeadArrow + FilledArrow + Legacy + + LineType + 1 + TailArrow + 0 + + + Tail + + ID + 378 + + + + Class + LineGraphic + FontInfo + + Font + Helvetica + Size + 12 + + Head + + ID + 380 + + ID + 384 + Points + + {224.57873965917133, 360.27559350245565} + {350.36614237526271, 360.27559350245565} + + Style + + shadow + + Draws + NO + + stroke + + HeadArrow + FilledArrow + Legacy + + LineType + 1 + TailArrow + 0 + + + Tail + + ID + 379 + + + + Class + LineGraphic + FontInfo + + Font + Helvetica + Size + 12 + + Head + + ID + 379 + + ID + 383 + Points + + {109.42125829936965, 438.22835011524467} + {224.57873965917133, 360.27559350245565} + + Style + + shadow + + Draws + NO + + stroke + + HeadArrow + FilledArrow + Legacy + + LineType + 1 + TailArrow + 0 + + + Tail + + ID + 378 + + + + Bounds + {{427.43307220836095, 416.08268062297509}, {44.291338984539124, 44.291338984539109}} + Class + ShapedGraphic + FontInfo + + Size + 18 + + ID + 382 + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc\partightenfactor0 + +\f0\fs36 \cf0 AC} + VerticalPad + 0.0 + + + + Bounds + {{202.43307016690176, 494.03543723576388}, {44.291338984539124, 44.291338984539109}} + Class + ShapedGraphic + FontInfo + + Size + 18 + + ID + 381 + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc\partightenfactor0 + +\f0\fs36 \cf0 3} + VerticalPad + 0.0 + + + + Bounds + {{328.22047288299314, 338.12992401018607}, {44.291338984539124, 44.291338984539109}} + Class + ShapedGraphic + FontInfo + + Size + 18 + + ID + 380 + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc\partightenfactor0 + +\f0\fs36 \cf0 2} + VerticalPad + 0.0 + + + + Bounds + {{202.43307016690176, 338.12992401018607}, {44.291338984539124, 44.291338984539109}} + Class + ShapedGraphic + FontInfo + + Size + 18 + + ID + 379 + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc\partightenfactor0 + +\f0\fs36 \cf0 1} + VerticalPad + 0.0 + + + + Bounds + {{87.275588807100092, 416.08268062297509}, {44.291338984539124, 44.291338984539109}} + Class + ShapedGraphic + FontInfo + + Size + 18 + + ID + 378 + Shape + Circle + Style + + shadow + + Draws + NO + + + Text + + Text + {\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc\partightenfactor0 + +\f0\fs36 \cf0 S} + VerticalPad + 0.0 + + + + Bounds + {{249.44882116092469, 45.354331120168126}, {94.960630782851936, 59}} + Class + ShapedGraphic + FitText + Vertical + Flow + Resize + FontInfo + + Color + + b + 0 + g + 0 + r + 0 + + + ID + 377 + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Align + 0 + Text + {\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset128 HiraginoSans-W3;} +{\colortbl;\red255\green255\blue255;} +\deftab720 +\pard\pardeftab720\partightenfactor0 + +\f0\fs32 \cf0 \'90\'67\'82\'c8\'82\'e8\'82\'f0\ +\'90\'ae\'82\'a6\'82\'e9} + + + + Bounds + {{87.874016545325787, 100.62992217287302}, {94.960630782851936, 35}} + Class + ShapedGraphic + FitText + Vertical + Flow + Resize + FontInfo + + Color + + b + 0 + g + 0 + r + 0 + + + ID + 376 + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Align + 0 + Text + {\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset128 HiraginoSans-W3;} +{\colortbl;\red255\green255\blue255;} +\deftab720 +\pard\pardeftab720\partightenfactor0 + +\f0\fs32 \cf0 \'91\'81\'8b\'4e\'82\'ab\'82\'b7\'82\'e9} + + + + Bounds + {{96.377953630357268, 218.26771851580912}, {77.95275661278896, 35}} + Class + ShapedGraphic + FitText + Vertical + Flow + Resize + FontInfo + + Color + + b + 0 + g + 0 + r + 0 + + + ID + 375 + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Align + 0 + Text + {\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset128 HiraginoSans-W3;} +{\colortbl;\red255\green255\blue255;} +\deftab720 +\pard\pardeftab720\partightenfactor0 + +\f0\fs32 \cf0 \'90\'51\'96\'56\'82\'b7\'82\'e9} + + + + Bounds + {{396.85039730147111, 100.62992217287302}, {116.22047349543087, 35}} + Class + ShapedGraphic + FitText + Vertical + Flow + Resize + FontInfo + + Color + + b + 0 + g + 0 + r + 0 + + + ID + 374 + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Align + 0 + Text + {\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset128 HiraginoSans-W3;} +{\colortbl;\red255\green255\blue255;} +\deftab720 +\pard\pardeftab720\partightenfactor0 + +\f0\fs32 \cf0 \'8a\'77\'8d\'5a\'82\'c9\'8c\'fc\'82\'a9\'82\'a4} + + + + Bounds + {{297.63779797610334, 233.85826983836677}, {116.22047349543087, 35}} + Class + ShapedGraphic + FitText + Vertical + Flow + Resize + FontInfo + + Color + + b + 0 + g + 0 + r + 0 + + + ID + 373 + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Align + 0 + Text + {\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset128 HiraginoSans-W3;} +{\colortbl;\red255\green255\blue255;} +\deftab720 +\pard\pardeftab720\partightenfactor0 + +\f0\fs32 \cf0 \'8a\'77\'8d\'5a\'82\'c9\'8c\'fc\'82\'a9\'82\'a4} + + + + Bounds + {{125.07874129233859, 590.59055622205915}, {172.913387395641, 35}} Class ShapedGraphic FitText @@ -45117,9 +46079,9 @@ 371 Points - {262.08267827529727, 586.24016279936063} - {183, 542} - {109.42125829936953, 586.24016279936063} + {283.94094872610185, 668.01181676703357} + {204.85827045080458, 623.77165396767282} + {131.27952875017411, 668.01181676703357} Style @@ -45148,7 +46110,7 @@ Bounds - {{208.34645858327232, 650.55118700491153}, {123.30708773295729, 35}} + {{230.20472903407688, 732.32284097258434}, {123.30708773295729, 35}} Class ShapedGraphic FitText @@ -45203,7 +46165,7 @@ Bounds - {{284.22834776756679, 555.59055622205949}, {116.22047349543087, 35}} + {{306.08661821837137, 637.36221018973242}, {116.22047349543087, 35}} Class ShapedGraphic FitText @@ -45258,7 +46220,7 @@ Bounds - {{131.5669277916391, 555.59055622205949}, {116.22047349543087, 35}} + {{153.42519824244368, 637.36221018973242}, {116.22047349543087, 35}} Class ShapedGraphic FitText @@ -45330,9 +46292,9 @@ 367 Points - {414.74409825122495, 586.24016279936063} - {263, 649} - {109.42125829936953, 586.24016279936063} + {436.60236870202954, 668.01181676703357} + {284.85827045080458, 730.77165396767282} + {131.27952875017411, 668.01181676703357} Style @@ -45378,8 +46340,8 @@ 366 Points - {262.08267827529727, 586.24016279936063} - {414.74409825122495, 586.24016279936063} + {283.94094872610185, 668.01181676703357} + {436.60236870202954, 668.01181676703357} Style @@ -45425,8 +46387,8 @@ 365 Points - {109.42125829936953, 586.24016279936063} - {262.08267827529727, 586.24016279936063} + {131.27952875017411, 668.01181676703357} + {283.94094872610185, 668.01181676703357} Style @@ -45455,7 +46417,7 @@ Bounds - {{392.59842875895538, 564.09449330709106}, {44.291338984539124, 44.291338984539109}} + {{414.45669920975996, 645.86614727476399}, {44.291338984539124, 44.291338984539109}} Class ShapedGraphic FontInfo @@ -45483,7 +46445,7 @@ Bounds - {{239.93700878302769, 564.09449330709106}, {44.291338984539124, 44.291338984539109}} + {{261.79527923383228, 645.86614727476399}, {44.291338984539124, 44.291338984539109}} Class ShapedGraphic FontInfo @@ -45511,7 +46473,7 @@ Bounds - {{87.275588807099965, 564.09449330709106}, {44.291338984539124, 44.291338984539109}} + {{109.13385925790455, 645.86614727476399}, {44.291338984539124, 44.291338984539109}} Class ShapedGraphic FontInfo @@ -45838,6 +46800,13 @@ Text + Text + {\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc\partightenfactor0 + +\f0\fs36 \cf0 3} VerticalPad 0.0 @@ -45866,6 +46835,13 @@ Text + Text + {\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc\partightenfactor0 + +\f0\fs36 \cf0 2} VerticalPad 0.0 @@ -45894,6 +46870,13 @@ Text + Text + {\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;} +{\colortbl;\red255\green255\blue255;} +\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc\partightenfactor0 + +\f0\fs36 \cf0 1} VerticalPad 0.0 @@ -66171,7 +67154,7 @@ ActiveLayerIndex - 0 + 1 AutoAdjust BackgroundGraphic @@ -75585,14 +76568,14 @@ WindowInfo CurrentSheet - 6 + 12 Expanded_Canvases cctree キャンバス 7 Frame - {{12, 38}, {1279, 1139}} + {{40, 38}, {1279, 1139}} ShowInfo ShowRuler @@ -75600,13 +76583,13 @@ Sidebar SidebarWidth - 200 + 360 TopSlabHeight 682 VisibleRegion - {{-56, -38}, {670.17544700608482, 860.52632658765606}} + {{-23, -99}, {605, 981}} Zoom - 1.1399999856948853 + 1 ZoomValues @@ -75656,8 +76639,8 @@ キャンバス 12 + 1.2599999904632568 1.26 - 1.1800000000000002 bmsearch diff -r 0d13c52a54fd -r 6415e51788a6 paper/images/regex/cctreesub.bb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/images/regex/cctreesub.bb Tue Feb 16 02:33:12 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: images/regex/cctreesub.pdf +%%Creator: extractbb 20150315 +%%BoundingBox: 0 0 1545 747 +%%CreationDate: Mon Feb 15 20:48:00 2016 + diff -r 0d13c52a54fd -r 6415e51788a6 paper/images/regex/dfabasic.bb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/images/regex/dfabasic.bb Tue Feb 16 02:33:12 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: images/regex/dfabasic.pdf +%%Creator: extractbb 20150315 +%%BoundingBox: 0 0 1341 762 +%%CreationDate: Tue Feb 16 00:31:40 2016 + diff -r 0d13c52a54fd -r 6415e51788a6 paper/images/regex/dfabasic.pdf Binary file paper/images/regex/dfabasic.pdf has changed diff -r 0d13c52a54fd -r 6415e51788a6 paper/images/regex/dfaregex.pdf Binary file paper/images/regex/dfaregex.pdf has changed diff -r 0d13c52a54fd -r 6415e51788a6 paper/images/regex/nfabasic.bb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/paper/images/regex/nfabasic.bb Tue Feb 16 02:33:12 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: images/regex/nfabasic.pdf +%%Creator: extractbb 20150315 +%%BoundingBox: 0 0 1341 762 +%%CreationDate: Tue Feb 16 00:31:36 2016 + diff -r 0d13c52a54fd -r 6415e51788a6 paper/images/regex/nfabasic.pdf Binary file paper/images/regex/nfabasic.pdf has changed diff -r 0d13c52a54fd -r 6415e51788a6 paper/master_paper.pdf Binary file paper/master_paper.pdf has changed