Mercurial > hg > Papers > 2016 > masa-master
changeset 24:beadec12c1e7
write bm_search
line wrap: on
line diff
--- a/c4.tex Fri Feb 05 01:20:20 2016 +0900 +++ b/c4.tex Fri Feb 05 17:07:52 2016 +0900 @@ -21,6 +21,254 @@ Word Count は読み込んだファイルに対して単語数を数える処理である。 Input Data には分割されたファイルが対応しており、Output Data には単語数と行数を \section{Boyer Moore Search} + +読み込んだテキストファイルに対して文字列検索を行う例題として、力任せ法と Boyer-Moore String Search を実装した。 +Boyer-Moore String Search は 1977 年に Robert S. Boyer と J Strother Moore が開発した効率的なアルゴリズムである。\cite{bmsearch} + +以下、テキストファイルに含まれている文字列を text、検索する文字列を pattern と定義する。 + +\subsection{力任せ法} +力任せ法(総当り法とも呼ばれる)は、text と pattern を先頭から比較していき、 +pattern と一致しなければ pattern を1文字分だけ後ろにずらして再度比較をしていくアルゴリズムである。 +text の先頭から pattern の先頭を比較していき、文字の不一致が起きた場合は、 +pattern を右に 1 つだけずらして、再度 text と pattern の先頭を比較していく。 +(図\ref{fig:bruteforth}) + +\begin{figure}[htbp] +\begin{center} +\includegraphics[width=0.7\textwidth]{images/example/bruteforth.pdf} +\end{center} +\caption{力まかせ法} +\label{fig:bruteforth} +\end{figure} + +\newpage +このアルゴリズムは実装が簡単であり、pattern が text に含まれていれば必ず探しだすことができる。 +しかし、text と pattern の文字数が大きくなるにつれて、比較回数も膨大になる恐れがある。 +text の文字数を $n$、pattern の文字数を $m$とすると、力任せ法の最悪計算時間は $O(nm)$ となる。 + +\subsection{Boyer-Moore String Search Algorithm} +力任せ法の比較回数を改善したアルゴリズムが Boyer-Moore String Search である。 +力任せ法との大きな違いとして、text と pattern を先頭から比較するのではなく、 +pattern の末尾から比較していくことである。そして不一致が起こった場合は、 +その不一致が起こった text の文字で再度比較する場所が決まる。 + +まず始めに、比較する場所を着目点とおく。図\ref{fig:bmsearchthink}の場合、 +最初に比較する patternの末尾 と、それに対応する text を着目点とする。 +(a)ではその着目点で不一致が起こっているので、それ以上比較しなくてもよいことがわかる。 +不一致が起こった場合は (b) のように着目点をずらしていく。着目点を1つ右にずらして再度 pattern の末尾から比較していく。これを繰り返しをして、(d) のときに初めて一致することがわかる。 + +(a)のときに不一致を起こした text の文字に注目する。その文字が pattern に含まれていない文字であるならば、着目点を1つずらしても、2つずらしても一致することはない。pattern に含まれていない文字で不一致になった場合は、pattern の文字数分だけ着目点をずらすことができる。 + +\begin{figure}[htbp] +\begin{center} +\includegraphics[width=0.5\textwidth]{images/example/bmsearchthink.pdf} +\end{center} +\caption{pattern に含まれていない文字で不一致になった場合} +\label{fig:bmsearchthink} +\end{figure} + +\newpage + +次に、pattern に含まれている文字で不一致になった場合を紹介する。 +図\ref{fig:bmsearchthink}と同様に、文字を比較していく。 +図\ref{fig:bmsearchinclude}(a)のときに不一致が起こる。 +その時の text の文字列は pattern に含まれている。 +この場合は着目点を右に2つずらすと text と pattern が一致する。 +もし、pattern に含まれている文字で不一致になった場合は、その text の文字に注目する。 +その文字を pattern 内から探し、その文字が pattern の末尾から +どれだけ離れているかで着目点を右にずらす量が決定される。 +図\ref{fig:bmsearchinclude}の場合であれば、不一致時の文字が a であれば右に2つ、 +b であれば右に1つずらすことができる。 + +\begin{figure}[htbp] +\begin{center} +\includegraphics[width=0.7\textwidth]{images/example/bmsearchinlucde.pdf} +\end{center} +\caption{pattern に含まれている文字で不一致になった場合} +\label{fig:bmsearchinclude} +\end{figure} + +\newpage + +pattern に同じ文字が複数入り、その文字で不一致になった場合は図\ref{fig:bmsearchsame}のようになる。 +この場合 a という文字が pattern の末尾から 1つ離れている箇所と 3 つ離れている箇所が存在する。 +(a) のように、a で不一致が起こった場合は、着目点を右に1つか3つ移動できる。 +しかし、着目点を右に3つずらしてしまうと、(b-1)のように text の途中にある "abac" という文字列を見逃してしまう。着目点を右に1つずらせば、(b-2)のように検索漏れを起こすことはなくなる。 + +このように、pattern に同じ文字が複数入っている場合は、末尾から一番近いほうを適用する。よって、図\ref{fig:bmsearchsame}では、不一致時の文字が a であれば右に1つ、b であれば右に2つ着目点をずらすことができる。 + +\begin{figure}[htbp] +\begin{center} +\includegraphics[width=0.7\textwidth]{images/example/bmsearchsame.pdf} +\end{center} +\caption{pattern に同じ文字が複数入り、その文字で不一致になった場合} +\label{fig:bmsearchsame} +\end{figure} + + +\newpage +pattern と text と不一致時の処理をまとめると、 + +\begin{itemize} +\item pattern に含まれていない文字の場合は、 pattern の長さだけ着目点を右にずらす +\item pattern に含まれている文字の場合は、 その文字が pattern の末尾から離れている分だけ着目点を右にずらす +\item pattern に含まれている文字かつ、その文字が pattern に複数含まれている場合は、 pattern の末尾から一番近い分だけ着目点を右にずらす +\end{itemize} + +となる。 図\ref{fig:bmsearchbasic}の例であれば、不一致字の text の文字が a であれば着目点を 2つ、 b であれば 1つ、それ以外の文字列は3つずらすことができる。 + +\begin{figure}[htbp] +\begin{center} +\includegraphics[width=0.7\textwidth]{images/example/bmsearchbasic.pdf} +\end{center} +\caption{Boyer-Moore Search String} +\label{fig:bmsearchbasic} +\end{figure} + +\newpage +このように、Boyer-Moore Search String は、不一致が起こった時の text の文字によって着目点をずらすということが起こるので、 +文字列検索を行う前に、着目点をずらす量を参照するための BMsearch skip table を作成する。 +"doing" という pattern であれば、そのテーブルは図\ref{fig:bmskiptable1}となる。 + +\begin{figure}[htbp] +\begin{center} +\includegraphics[width=0.8\textwidth]{images/example/bmskiptable1.pdf} +\end{center} +\caption{BMsearch skip table のまとめ} +\label{fig:bmskiptable1} +\end{figure} + +このようなテーブルを、文字列検索を行う前に生成する必要がある。 +そのテーブル生成プログラムは以下のようになる。 + +\begin{lstlisting}[frame=lrbt,label=src:createTask,caption=Task の生成,numbers=left] +static int* +create_BMskiptable(unsigned char *pattern, + int pattern_len,int *skip_table) +{ + for(int i = 0; i < 128; ++i){ + skip_table[i] = pattern_len; + } + + for(int j = 0; j < pattern_len - 1; ++j){ + skip_table[pattern[j]] = pattern_len - j - 1; + } + + return skip_table; +} +\end{lstlisting} + +このソースでの 128 とは ASCII コード表における最大値である。 +それぞれの文字に対して pattern の長さであるpattern\_lenを格納する。pattern が "doing" という文字列だと仮定すると、 +pattern\_len = 5 となる。次に pattern の先頭から文字を調べる。 +先頭の文字は d であり、d に対応する table に着目点をずらすための移動量を格納する。 +移動量を格納したら、pattern の次の文字を調べ、そして移動量を格納していく。(図\ref{fig:bmskiptable}) + +\begin{figure}[htbp] +\begin{center} +\includegraphics[width=0.8\textwidth]{images/example/bmskiptable.pdf} +\end{center} +\caption{skip table の 生成時の様子} +\label{fig:bmskiptable} +\end{figure} + +\newpage +生成したテーブルを利用して文字列検索を行うアルゴリズムを以下に示す。 +\begin{lstlisting}[frame=lrbt,label=src:createTask,caption=Task の生成,numbers=left] +int i = pattern_len - 1; +int match_counter = 0; + +while ( i < text_len){ + int j = pattern_len - 1; + while (text[i] == pattern[j]){ + if (j == 0){ + match_counter++; + } + --i; + --j; + } + i = i + max(skip_table[text[i]],pattern_len - j); +} +\end{lstlisting} + +読み込まれたテキストファイル text[i] と、検索文字列 pattern[j]を末尾から比較していく。 +一致していれば参照する場所を先頭方向にずらしていき、先頭まで完全一致した場合は、 +検索文字列を発見したということで、ここではマッチした数 match\_counter を増やしている。 + +もし途中で不一致が起こった場合は、その不一致が起こった時の text[i] の文字列か pattern の長さから j 引いたものの最大値の分だけ text の参照先をずらす。 + +\newpage +\subsection{ファイル分割時の処理の注意点} +この例題ではファイルを読み込んで一定の大きさでファイルを分割する。分割したものにそれぞれ文字列検索を行う。 +それぞれの結果は pattern が含まれている個数が返ってくるので、最後に集計をして個数を表示する。このような一つ一つの処理を Task と呼ぶ。 +図\ref{fig:includeiotask}では、ファイルの読み込みが File Read、分割したものに文字列検索を行うことが Run Tasks、 +返した結果が Output Data、それぞれの結果の集計が Run resultTask に相当する。 + +\begin{figure}[htbp] +\begin{center} +\includegraphics[width=1.0\textwidth]{images/example/includeiotask.pdf} +\end{center} +\caption{IO を含む Task} +\label{fig:includeiotask} +\end{figure} + +\newpage + +ファイルを分割したときに、分割される部分で pattern が含まれる場合が存在する。 +その場合は、本来の読み込み部分の text の長さ $L$ に加えて、pattern の長さ $s$ だけ多く読みこむように設計することでこの問題は解決できる。 +しかし、1 つの Search Task の text の長さが $L+s$ の場合だと、pattern が Search Task 1 に含まれ、Search Task 2 にも含まれてしまう。 +(図\ref{fig:iodivfail}) + +\begin{figure}[htbp] +\begin{center} +\includegraphics[width=1.0\textwidth]{images/example/iodivfail.pdf} +\end{center} +\caption{分割周りの処理・失敗時 (例:doing の検索)} +\label{fig:iodivfail} +\end{figure} + +それを解決するために、1つの Search task の text の長さに pattern の長さを加えてから 1 引いた数だけ読み込むようにすればそのような問題は起こらない。よって、読み込むデータ量は $ L + s -1 $となる。 +(図\ref{fig:iodivsuc}) + +\begin{figure}[htbp] +\begin{center} +\includegraphics[width=1.0\textwidth]{images/example/iodivsuc.pdf} +\end{center} +\caption{分割周りの処理・成功時 (例:doing の検索)} +\label{fig:iodivsuc} +\end{figure} + +\newpage + +力任せ法と Boyer-Moore String Search を比較してみた。以下に実験環境と結果を示す。(表\ref{table:search}) + +\begin{itemize} +\item Mac OS X 10.9.1 +\item 2*2.66 GHz 6-Core Intel Xeon +\item File Size 10GB +\end{itemize} + +\begin{tiny} + \begin{table}[ht] + \begin{center} + \label{table:search} + \small + \begin{tabular}[t]{c|r} + \hline + 文字列検索アルゴリズム & 処理速度(s)\\ + \hline + 力任せ法 & 11.792 \\ + \hline + Boyer-Moore String Search & 6.508 \\ + \hline + \end{tabular} + \caption{文字列検索アルゴリズムの比較} + \end{center} + \end{table} +\end{tiny} + +Boyer-Moore String Search によって 44\% 改善した。 \section{正規表現} \subsection{正規表現木の生成} \subsection{正規表現木から NFA の生成}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/images/cerium/blockedread.bb Fri Feb 05 17:07:52 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: images/cerium/blockedread.pdf +%%Creator: extractbb 20150315 +%%BoundingBox: 0 0 839 260 +%%CreationDate: Thu Feb 4 20:55:03 2016 +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/images/cerium/blockedreadimage.bb Fri Feb 05 17:07:52 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: images/cerium/blockedreadimage.pdf +%%Creator: extractbb 20150315 +%%BoundingBox: 0 0 439 235 +%%CreationDate: Thu Feb 4 20:55:03 2016 +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/images/cerium/createTask.bb Fri Feb 05 17:07:52 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: images/cerium/createTask.pdf +%%Creator: extractbb 20150315 +%%BoundingBox: 0 0 512 391 +%%CreationDate: Thu Feb 4 20:55:03 2016 +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/images/cerium/iothread.bb Fri Feb 05 17:07:52 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: images/cerium/iothread.pdf +%%Creator: extractbb 20150315 +%%BoundingBox: 0 0 715 112 +%%CreationDate: Thu Feb 4 20:55:03 2016 +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/images/cerium/mmap.bb Fri Feb 05 17:07:52 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: images/cerium/mmap.pdf +%%Creator: extractbb 20150315 +%%BoundingBox: 0 0 334 272 +%%CreationDate: Thu Feb 4 20:55:03 2016 +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/images/cerium/speblockedread.bb Fri Feb 05 17:07:52 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: images/cerium/speblockedread.pdf +%%Creator: extractbb 20150315 +%%BoundingBox: 0 0 651 112 +%%CreationDate: Thu Feb 4 20:55:03 2016 +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/images/example/bmsearchbasic.bb Fri Feb 05 17:07:52 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: images/example/bmsearchbasic.pdf +%%Creator: extractbb 20150315 +%%BoundingBox: 0 0 309 270 +%%CreationDate: Fri Feb 5 17:02:19 2016 +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/images/example/bmsearchinlucde.bb Fri Feb 05 17:07:52 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: images/example/bmsearchinlucde.pdf +%%Creator: extractbb 20150315 +%%BoundingBox: 0 0 239 201 +%%CreationDate: Fri Feb 5 17:02:19 2016 +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/images/example/bmsearchsame.bb Fri Feb 05 17:07:52 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: images/example/bmsearchsame.pdf +%%Creator: extractbb 20150315 +%%BoundingBox: 0 0 292 233 +%%CreationDate: Fri Feb 5 17:02:19 2016 +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/images/example/bmsearchthink.bb Fri Feb 05 17:07:52 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: images/example/bmsearchthink.pdf +%%Creator: extractbb 20150315 +%%BoundingBox: 0 0 234 259 +%%CreationDate: Fri Feb 5 17:02:19 2016 +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/images/example/bmskiptable.bb Fri Feb 05 17:07:52 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: images/example/bmskiptable.pdf +%%Creator: extractbb 20150315 +%%BoundingBox: 0 0 348 480 +%%CreationDate: Fri Feb 5 17:02:19 2016 +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/images/example/bmskiptable1.bb Fri Feb 05 17:07:52 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: images/example/bmskiptable1.pdf +%%Creator: extractbb 20150315 +%%BoundingBox: 0 0 318 67 +%%CreationDate: Fri Feb 5 17:02:19 2016 +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/images/example/bruteforth.bb Fri Feb 05 17:07:52 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: images/example/bruteforth.pdf +%%Creator: extractbb 20150315 +%%BoundingBox: 0 0 246 252 +%%CreationDate: Fri Feb 5 17:02:19 2016 +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/images/example/dividefile.bb Fri Feb 05 17:07:52 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: images/example/dividefile.pdf +%%Creator: extractbb 20150315 +%%BoundingBox: 0 0 2124 1236 +%%CreationDate: Fri Feb 5 17:02:19 2016 +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/images/example/includeiotask.bb Fri Feb 05 17:07:52 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: images/example/includeiotask.pdf +%%Creator: extractbb 20150315 +%%BoundingBox: 0 0 385 245 +%%CreationDate: Fri Feb 5 17:02:19 2016 +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/images/example/iodivfail.bb Fri Feb 05 17:07:52 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: images/example/iodivfail.pdf +%%Creator: extractbb 20150315 +%%BoundingBox: 0 0 666 215 +%%CreationDate: Fri Feb 5 17:02:19 2016 +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/images/example/iodivsuc.bb Fri Feb 05 17:07:52 2016 +0900 @@ -0,0 +1,5 @@ +%%Title: images/example/iodivsuc.pdf +%%Creator: extractbb 20150315 +%%BoundingBox: 0 0 664 215 +%%CreationDate: Fri Feb 5 17:02:19 2016 +
--- a/images/image.graffle Fri Feb 05 01:20:20 2016 +0900 +++ b/images/image.graffle Fri Feb 05 17:07:52 2016 +0900 @@ -26,7 +26,7 @@ <key>MasterSheets</key> <array/> <key>ModificationDate</key> - <string>2016-02-04 11:36:27 +0000</string> + <string>2016-02-05 05:11:00 +0000</string> <key>Modifier</key> <string>MasaKoha</string> <key>NotesVisible</key> @@ -24586,6 +24586,340 @@ <key>GraphicsList</key> <array> <dict> + <key>Bounds</key> + <string>{{1468.3464700154432, 84.598425492620834}, {70.866142375262598, 43}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>Vertical</string> + <key>Flow</key> + <string>Resize</string> + <key>FontInfo</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0</string> + <key>g</key> + <string>0</string> + <key>r</key> + <string>0</string> + </dict> + <key>Size</key> + <real>14</real> + </dict> + <key>ID</key> + <integer>649</integer> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;} +{\colortbl;\red255\green255\blue255;} +\deftab720 +\pard\pardeftab720\qc\partightenfactor0 + +\f0\fs28 \cf0 next\ +state}</string> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{1405.9842647252121, 93.098425492620834}, {76.535433765283642, 27}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>Vertical</string> + <key>Flow</key> + <string>Resize</string> + <key>FontInfo</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0</string> + <key>g</key> + <string>0</string> + <key>r</key> + <string>0</string> + </dict> + <key>Size</key> + <real>14</real> + </dict> + <key>ID</key> + <integer>648</integer> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;} +{\colortbl;\red255\green255\blue255;} +\deftab720 +\pard\pardeftab720\qc\partightenfactor0 + +\f0\fs28 \cf0 condition}</string> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{1349.2913508250017, 84.598425492620834}, {70.866142375262598, 43}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>Vertical</string> + <key>Flow</key> + <string>Resize</string> + <key>FontInfo</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0</string> + <key>g</key> + <string>0</string> + <key>r</key> + <string>0</string> + </dict> + <key>Size</key> + <real>14</real> + </dict> + <key>ID</key> + <integer>647</integer> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;} +{\colortbl;\red255\green255\blue255;} +\deftab720 +\pard\pardeftab720\qc\partightenfactor0 + +\f0\fs28 \cf0 current\ +state}</string> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{1268.5039485172024, 84.098425492620834}, {70.866142375262598, 43}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>Vertical</string> + <key>Flow</key> + <string>Resize</string> + <key>FontInfo</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0</string> + <key>g</key> + <string>0</string> + <key>r</key> + <string>0</string> + </dict> + <key>Size</key> + <real>14</real> + </dict> + <key>ID</key> + <integer>646</integer> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;} +{\colortbl;\red255\green255\blue255;} +\deftab720 +\pard\pardeftab720\qc\partightenfactor0 + +\f0\fs28 \cf0 next\ +state}</string> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{1206.1417432269714, 92.598425492620834}, {76.535433765283642, 27}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>Vertical</string> + <key>Flow</key> + <string>Resize</string> + <key>FontInfo</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0</string> + <key>g</key> + <string>0</string> + <key>r</key> + <string>0</string> + </dict> + <key>Size</key> + <real>14</real> + </dict> + <key>ID</key> + <integer>645</integer> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;} +{\colortbl;\red255\green255\blue255;} +\deftab720 +\pard\pardeftab720\qc\partightenfactor0 + +\f0\fs28 \cf0 condition}</string> + </dict> + </dict> + <dict> + <key>Bounds</key> + <string>{{1149.4488293267609, 84.098425492620834}, {70.866142375262598, 43}}</string> + <key>Class</key> + <string>ShapedGraphic</string> + <key>FitText</key> + <string>Vertical</string> + <key>Flow</key> + <string>Resize</string> + <key>FontInfo</key> + <dict> + <key>Color</key> + <dict> + <key>b</key> + <string>0</string> + <key>g</key> + <string>0</string> + <key>r</key> + <string>0</string> + </dict> + <key>Size</key> + <real>14</real> + </dict> + <key>ID</key> + <integer>644</integer> + <key>Style</key> + <dict> + <key>fill</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>shadow</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + <key>stroke</key> + <dict> + <key>Draws</key> + <string>NO</string> + </dict> + </dict> + <key>Text</key> + <dict> + <key>Text</key> + <string>{\rtf1\ansi\ansicpg932\cocoartf1404\cocoasubrtf340 +{\fonttbl\f0\fnil\fcharset0 HelveticaNeue;} +{\colortbl;\red255\green255\blue255;} +\deftab720 +\pard\pardeftab720\qc\partightenfactor0 + +\f0\fs28 \cf0 current\ +state}</string> + </dict> + </dict> + <dict> <key>Class</key> <string>Group</string> <key>Graphics</key> @@ -29610,7 +29944,7 @@ <key>TopSlabHeight</key> <real>682</real> <key>VisibleRegion</key> - <string>{{0, -12}, {684, 808}}</string> + <string>{{939, -12}, {684, 808}}</string> <key>Zoom</key> <real>1</real> <key>ZoomValues</key>
--- a/images/implementation/CharClassMergePattern.bb Fri Feb 05 01:20:20 2016 +0900 +++ b/images/implementation/CharClassMergePattern.bb Fri Feb 05 17:07:52 2016 +0900 @@ -1,5 +1,5 @@ %%Title: images/implementation/CharClassMergePattern.pdf %%Creator: extractbb 20150315 %%BoundingBox: 0 0 1422 1908 -%%CreationDate: Thu Feb 4 20:55:04 2016 +%%CreationDate: Fri Feb 5 16:53:53 2016
--- a/images/implementation/ccinsert1.bb Fri Feb 05 01:20:20 2016 +0900 +++ b/images/implementation/ccinsert1.bb Fri Feb 05 17:07:52 2016 +0900 @@ -1,5 +1,5 @@ %%Title: images/implementation/ccinsert1.pdf %%Creator: extractbb 20150315 %%BoundingBox: 0 0 1068 1050 -%%CreationDate: Thu Feb 4 20:55:04 2016 +%%CreationDate: Fri Feb 5 16:53:53 2016
--- a/images/implementation/ccinsert2.bb Fri Feb 05 01:20:20 2016 +0900 +++ b/images/implementation/ccinsert2.bb Fri Feb 05 17:07:52 2016 +0900 @@ -1,5 +1,5 @@ %%Title: images/implementation/ccinsert2.pdf %%Creator: extractbb 20150315 %%BoundingBox: 0 0 1464 1116 -%%CreationDate: Thu Feb 4 20:55:04 2016 +%%CreationDate: Fri Feb 5 16:53:53 2016
--- a/images/implementation/ccinsertresult.bb Fri Feb 05 01:20:20 2016 +0900 +++ b/images/implementation/ccinsertresult.bb Fri Feb 05 17:07:52 2016 +0900 @@ -1,5 +1,5 @@ %%Title: images/implementation/ccinsertresult.pdf %%Creator: extractbb 20150315 %%BoundingBox: 0 0 756 777 -%%CreationDate: Thu Feb 4 20:55:04 2016 +%%CreationDate: Fri Feb 5 16:53:53 2016
--- a/images/implementation/cfab.bb Fri Feb 05 01:20:20 2016 +0900 +++ b/images/implementation/cfab.bb Fri Feb 05 17:07:52 2016 +0900 @@ -1,5 +1,5 @@ %%Title: images/implementation/cfab.pdf %%Creator: extractbb 20150315 %%BoundingBox: 0 0 768 399 -%%CreationDate: Thu Feb 4 20:55:04 2016 +%%CreationDate: Fri Feb 5 16:53:53 2016
--- a/images/implementation/cfdg.bb Fri Feb 05 01:20:20 2016 +0900 +++ b/images/implementation/cfdg.bb Fri Feb 05 17:07:52 2016 +0900 @@ -1,5 +1,5 @@ %%Title: images/implementation/cfdg.pdf %%Creator: extractbb 20150315 %%BoundingBox: 0 0 768 300 -%%CreationDate: Thu Feb 4 20:55:04 2016 +%%CreationDate: Fri Feb 5 16:53:53 2016
--- a/images/implementation/cfdgab.bb Fri Feb 05 01:20:20 2016 +0900 +++ b/images/implementation/cfdgab.bb Fri Feb 05 17:07:52 2016 +0900 @@ -1,5 +1,5 @@ %%Title: images/implementation/cfdgab.pdf %%Creator: extractbb 20150315 %%BoundingBox: 0 0 1278 396 -%%CreationDate: Thu Feb 4 20:55:04 2016 +%%CreationDate: Fri Feb 5 16:53:53 2016
--- a/images/implementation/dfa.bb Fri Feb 05 01:20:20 2016 +0900 +++ b/images/implementation/dfa.bb Fri Feb 05 17:07:52 2016 +0900 @@ -1,5 +1,5 @@ %%Title: images/implementation/dfa.pdf %%Creator: extractbb 20150315 %%BoundingBox: 0 0 1614 900 -%%CreationDate: Thu Feb 4 20:55:04 2016 +%%CreationDate: Fri Feb 5 16:53:53 2016
--- a/images/implementation/efgi.bb Fri Feb 05 01:20:20 2016 +0900 +++ b/images/implementation/efgi.bb Fri Feb 05 17:07:52 2016 +0900 @@ -1,5 +1,5 @@ %%Title: images/implementation/efgi.pdf %%Creator: extractbb 20150315 %%BoundingBox: 0 0 888 360 -%%CreationDate: Thu Feb 4 20:55:04 2016 +%%CreationDate: Fri Feb 5 16:53:53 2016
--- a/images/implementation/nfa.bb Fri Feb 05 01:20:20 2016 +0900 +++ b/images/implementation/nfa.bb Fri Feb 05 17:07:52 2016 +0900 @@ -1,5 +1,5 @@ %%Title: images/implementation/nfa.pdf %%Creator: extractbb 20150315 %%BoundingBox: 0 0 1440 615 -%%CreationDate: Thu Feb 4 20:55:04 2016 +%%CreationDate: Fri Feb 5 16:53:53 2016
--- a/images/implementation/parser.bb Fri Feb 05 01:20:20 2016 +0900 +++ b/images/implementation/parser.bb Fri Feb 05 17:07:52 2016 +0900 @@ -1,5 +1,5 @@ %%Title: images/implementation/parser.pdf %%Creator: extractbb 20150315 %%BoundingBox: 0 0 1707 1671 -%%CreationDate: Thu Feb 4 20:55:04 2016 +%%CreationDate: Fri Feb 5 16:53:53 2016
--- a/images/implementation/setstate.bb Fri Feb 05 01:20:20 2016 +0900 +++ b/images/implementation/setstate.bb Fri Feb 05 17:07:52 2016 +0900 @@ -1,5 +1,5 @@ %%Title: images/implementation/setstate.pdf %%Creator: extractbb 20150315 %%BoundingBox: 0 0 1716 1443 -%%CreationDate: Thu Feb 4 20:55:04 2016 +%%CreationDate: Fri Feb 5 16:53:53 2016
--- a/images/implementation/transitiontable.bb Fri Feb 05 01:20:20 2016 +0900 +++ b/images/implementation/transitiontable.bb Fri Feb 05 17:07:52 2016 +0900 @@ -1,5 +1,5 @@ %%Title: images/implementation/transitiontable.pdf %%Creator: extractbb 20150315 -%%BoundingBox: 0 0 1191 987 -%%CreationDate: Thu Feb 4 20:55:04 2016 +%%BoundingBox: 0 0 1227 1131 +%%CreationDate: Fri Feb 5 16:53:53 2016