Mercurial > hg > Papers > 2016 > masa-master

changeset 84:e89993e15f91

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 03:56:53 +0900
parents 8cde18e9de33
children 678c2bde5010
files paper/c4.tex paper/images/image.graffle paper/images/regex/dfa.pdf paper/master_paper.pdf
diffstat 4 files changed, 40 insertions(+), 293 deletions(-) [+]
line wrap: on
line diff
--- a/paper/c4.tex	Thu Feb 18 02:39:55 2016 +0900
+++ b/paper/c4.tex	Thu Feb 18 03:56:53 2016 +0900
@@ -372,6 +372,7 @@
 
 
 \section{正規表現}
+% 正規表現の話を 2 ページずつぐらいで
 正規表現は文字列のパターンを表現するための方法である。
 
 BOSE という文字列をファイルから検索する場合を例にとる。
@@ -623,6 +624,7 @@
 文字クラスは二分木で構築されており、それぞれの二分木に文字の範囲である Condition を持っている。
 その Condition の範囲内の文字の入力があれば、次の状態 nextState に遷移する。
 
+% charclass 構造体 ソース
 \begin{lstlisting}[frame=lrbt,label=src:cc,caption=文字クラス(charClass)の構造体,numbers=left]
 typedef struct utf8Range {
     unsigned long begin;
@@ -665,35 +667,21 @@
   \label{fig:CharClassMergePattern}
 \end{figure}
 
-\subsection{並列処理時の整合性の取り方}
-正規表現をファイル分割して並列処理をする際、本来マッチングする文章がファイル分割によってマッチングしない場合がある。
-
-図\ref{fig:regexdivide}はその一例である。正規表現 ab*c のマッチングする文字列の集合は {ac,abc,abbc,ab..bc} である。
-分割される前はこの文字列 abbbbc は問題なく正規表現 ab*c にマッチングする。
-
+\subsection{CeriumGrep の実装}
+正規表現から正規表現木を生成し、その木に対して状態を割り振りを行ない、Subset Construction による新しい状態の生成が終わったあとにマッチングを行う。
+なお、Subset Construction による新しい状態の生成はマッチングの前に行うことも可能であるが、マッチング途中で新しい状態を発見したときにその都度生成することも可能である。
+% bit パターンの実装の話
+本研究では、状態を Bit Pattern で実装している。
+Bit Pattern で表現することによって、2つの状態の組み合わせを両状態の Bit Pattern の和を取ることで容易に表現できる。
 
-% bit パターンの実装の話
-% 正規表現の話を 2 ページずつぐらいで
+% state 構造 bitvector の話 配列を MaxState の分のコードの話
+状態は配列で格納されている。
+状態の遷移先は List 構造になっており、その状態に入力が行われたらそのリストを辿って遷移先を状態を判断する。
+あらかじめ配列の大きさのメモリを確保する必要がある。
+Subset Construction による新しい状態生成も考慮しなければならない。
 
-% charclass 構造体 ソース
-% state 構造 bitvector の話 配列を MaxState の分のコードの話
-% はやくなった方法 state bit or 状態 merge に計算できる
 % subset construction の速度 O(mlogn)
 
-並列処理時、分割されたファイルに対してパターンマッチさせるので、分割された1つ目のファイルの末尾の abb 、2つ目のファイルの先頭に bbc はマッチングしない。
-本来分割される前はマッチングする文字列だが、この場合見逃してしまう。
-それを解決するために、正規表現にマッチングし始めたファイルの場所を覚えておく。
-そして、1つ目のファイルの末尾が状態遷移の途中で終わっていた場合は、結果を集計する際に再度マッチングし始めた場所から正規表現をマッチングさせる。
-
-\begin{figure}[htpb]
-  \begin{center}
-    \includegraphics[scale=0.3]{images/regex/regexdivide.pdf}
-  \end{center}
-  \caption{分割された部分に正規表現がマッチングする場合の処理}
-  \label{fig:regexdivide}
-\end{figure}
-% Print の分割部分の話追加 最後
-
 \begin{lstlisting}[frame=lrbt,label=src:result,caption=ceriumGrep の TMmain,numbers=left]
 typedef struct result {
     unsigned char *begin;
@@ -757,6 +745,26 @@
 }
 \end{lstlisting}
 
+% Print の分割部分の話追加 最後
+正規表現をファイル分割して並列処理をする際、本来マッチングする文章がファイル分割によってマッチングしない場合がある。
+
+図\ref{fig:regexdivide}はその一例である。正規表現 ab*c のマッチングする文字列の集合は {ac,abc,abbc,ab..bc} である。
+分割される前はこの文字列 abbbbc は問題なく正規表現 ab*c にマッチングする。
+
+並列処理時、分割されたファイルに対してパターンマッチさせるので、分割された1つ目のファイルの末尾の abb 、2つ目のファイルの先頭に bbc はマッチングしない。
+本来分割される前はマッチングする文字列だが、この場合見逃してしまう。
+それを解決するために、正規表現にマッチングし始めたファイルの場所を覚えておく。
+そして、1つ目のファイルの末尾が状態遷移の途中で終わっていた場合は、結果を集計する際に再度マッチングし始めた場所から正規表現をマッチングさせる。
+
+\begin{figure}[htpb]
+  \begin{center}
+    \includegraphics[scale=0.3]{images/regex/regexdivide.pdf}
+  \end{center}
+  \caption{分割された部分に正規表現がマッチングする場合の処理}
+  \label{fig:regexdivide}
+\end{figure}
+
+
 \begin{lstlisting}[frame=lrbt,label=src:print,caption=結果の整合性,numbers=left]
 static
 TSValue stateSkipOnce(TSValue tsv) {
--- a/paper/images/image.graffle	Thu Feb 18 02:39:55 2016 +0900
+++ b/paper/images/image.graffle	Thu Feb 18 03:56:53 2016 +0900
@@ -26,7 +26,7 @@
 	<key>MasterSheets</key>
 	<array/>
 	<key>ModificationDate</key>
-	<string>2016-02-17 17:16:32 +0000</string>
+	<string>2016-02-17 17:42:59 +0000</string>
 	<key>Modifier</key>
 	<string>MasaKoha</string>
 	<key>NotesVisible</key>
@@ -68576,94 +68576,6 @@
 				</dict>
 				<dict>
 					<key>Bounds</key>
-					<string>{{835.87156913666513, 523.45500819521465}, {35.433071187631356, 34.015748340126095}}</string>
-					<key>Class</key>
-					<string>ShapedGraphic</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>18</real>
-					</dict>
-					<key>ID</key>
-					<integer>723</integer>
-					<key>Shape</key>
-					<string>Circle</string>
-					<key>Style</key>
-					<dict>
-						<key>shadow</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;}
-\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc\partightenfactor0
-
-\f0\fs36 \cf0 2}</string>
-						<key>VerticalPad</key>
-						<real>0.0</real>
-					</dict>
-				</dict>
-				<dict>
-					<key>Bounds</key>
-					<string>{{909.96902383165843, 523.45500819521465}, {35.433071187631356, 34.015748340126095}}</string>
-					<key>Class</key>
-					<string>ShapedGraphic</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>18</real>
-					</dict>
-					<key>ID</key>
-					<integer>722</integer>
-					<key>Shape</key>
-					<string>Circle</string>
-					<key>Style</key>
-					<dict>
-						<key>shadow</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;}
-\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc\partightenfactor0
-
-\f0\fs36 \cf0 4}</string>
-						<key>VerticalPad</key>
-						<real>0.0</real>
-					</dict>
-				</dict>
-				<dict>
-					<key>Bounds</key>
 					<string>{{669.41141966970861, 566.64286085234767}, {92.125985087841514, 30}}</string>
 					<key>Class</key>
 					<string>ShapedGraphic</string>
@@ -68826,7 +68738,7 @@
 					<key>Points</key>
 					<array>
 						<string>{661.06889245538218, 535.67829380104774}</string>
-						<string>{779.25394035136583, 535.67829380104774}</string>
+						<string>{784.70571391777241, 535.67829380104774}</string>
 					</array>
 					<key>Style</key>
 					<dict>
@@ -68902,7 +68814,7 @@
 				</dict>
 				<dict>
 					<key>Bounds</key>
-					<string>{{761.53740475755012, 518.67041963098472}, {35.433071187631356, 34.015748340126095}}</string>
+					<string>{{761.53740475755012, 518.67041963098472}, {46.336618320444586, 34.015748340126095}}</string>
 					<key>Class</key>
 					<string>ShapedGraphic</string>
 					<key>FontInfo</key>
@@ -68939,7 +68851,7 @@
 {\colortbl;\red255\green255\blue255;\red177\green0\blue28;}
 \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc\partightenfactor0
 
-\f0\fs36 \cf2 6}</string>
+\f0\fs36 \cf2 2,4}</string>
 						<key>VerticalPad</key>
 						<real>0.0</real>
 					</dict>
@@ -69366,179 +69278,6 @@
 				</dict>
 				<dict>
 					<key>Bounds</key>
-					<string>{{878.13683207797749, 523.45500819521465}, {25, 30}}</string>
-					<key>Class</key>
-					<string>ShapedGraphic</string>
-					<key>FitText</key>
-					<string>YES</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>
-					</dict>
-					<key>ID</key>
-					<integer>714</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\fs32 \cf0 or}</string>
-					</dict>
-					<key>Wrap</key>
-					<string>NO</string>
-				</dict>
-				<dict>
-					<key>Bounds</key>
-					<string>{{948.58762749750338, 495.1782938010478}, {24, 81}}</string>
-					<key>Class</key>
-					<string>ShapedGraphic</string>
-					<key>FitText</key>
-					<string>YES</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>Font</key>
-						<string>HelveticaNeue-UltraLight</string>
-						<key>Size</key>
-						<real>60</real>
-					</dict>
-					<key>ID</key>
-					<integer>106</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-UltraLight;}
-{\colortbl;\red255\green255\blue255;}
-\deftab720
-\pard\pardeftab720\qc\partightenfactor0
-
-\f0\fs120 \cf0 )}</string>
-					</dict>
-					<key>Wrap</key>
-					<string>NO</string>
-				</dict>
-				<dict>
-					<key>Bounds</key>
-					<string>{{805.03937738298418, 495.1782938010478}, {24, 81}}</string>
-					<key>Class</key>
-					<string>ShapedGraphic</string>
-					<key>FitText</key>
-					<string>YES</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>Font</key>
-						<string>HelveticaNeue-UltraLight</string>
-						<key>Size</key>
-						<real>60</real>
-					</dict>
-					<key>ID</key>
-					<integer>719</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-UltraLight;}
-{\colortbl;\red255\green255\blue255;}
-\deftab720
-\pard\pardeftab720\qc\partightenfactor0
-
-\f0\fs120 \cf0 (}</string>
-					</dict>
-					<key>Wrap</key>
-					<string>NO</string>
-				</dict>
-				<dict>
-					<key>Bounds</key>
 					<string>{{569.7637846971121, 440.78740557413397}, {71.377953630357183, 35}}</string>
 					<key>Class</key>
 					<string>ShapedGraphic</string>
@@ -83182,7 +82921,7 @@
 	<key>WindowInfo</key>
 	<dict>
 		<key>CurrentSheet</key>
-		<integer>20</integer>
+		<integer>16</integer>
 		<key>Expanded_Canvases</key>
 		<array>
 			<string>cctree</string>
@@ -83201,9 +82940,9 @@
 		<key>TopSlabHeight</key>
 		<real>682</real>
 		<key>VisibleRegion</key>
-		<string>{{11, -99}, {605, 981}}</string>
+		<string>{{429.62961255768266, -62}, {560.18516292542677, 908.33329723941097}}</string>
 		<key>Zoom</key>
-		<real>1</real>
+		<real>1.0800000429153442</real>
 		<key>ZoomValues</key>
 		<array>
 			<array>
Binary file paper/images/regex/dfa.pdf has changed
Binary file paper/master_paper.pdf has changed