Mercurial > hg > Papers > 2016 > masa-master

changeset 86:53950092fce4

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 05:49:29 +0900
parents 678c2bde5010
children 04e333c17c0d
files paper/c4.tex paper/images/image.graffle paper/master_paper.pdf
diffstat 3 files changed, 118 insertions(+), 19 deletions(-) [+]
line wrap: on
line diff
--- a/paper/c4.tex	Thu Feb 18 05:14:58 2016 +0900
+++ b/paper/c4.tex	Thu Feb 18 05:49:29 2016 +0900
@@ -667,7 +667,7 @@
   \label{fig:CharClassMergePattern}
 \end{figure}
 
-\subsection{CeriumGrep の実装}
+\subsection{並列正規表現マッチャの実装}
 正規表現から正規表現木を生成し、その木に対して状態を割り振りを行ない、Subset Construction による新しい状態の生成が終わったあとにマッチングを行う。
 なお、Subset Construction による新しい状態の生成はマッチングの前に行うことも可能であるが、マッチング途中で新しい状態を発見したときにその都度生成することも可能である。
 % bit パターンの実装の話
@@ -676,16 +676,17 @@
 
 % state 構造 bitvector の話 配列を MaxState の分のコードの話
 状態は StateArray と呼ばれる配列で格納されており、状態遷移が行われるたびに配列を見に行く。
+あらかじめ配列の大きさのメモリを確保する必要があるが、Subset Construction による新しい状態生成も考慮しなければならない。
+正規表現木に状態を割り振った時に最大の状態の Bit は分かっている。その状態の Bit の 2 倍だけ配列を確保しておけば、Bit Pattern が全て 1 までの状態を表現することができる。
 状態の遷移先は文字クラスごとの List 構造になっており、その状態に入力が行われたらそのリストを辿って遷移先の状態を判断する。
-あらかじめ配列の大きさのメモリを確保する必要がある。
-Subset Construction による新しい状態生成も考慮しなければならない。
+図\ref{fig:statearray}
 
 \begin{figure}[htpb]
   \begin{center}
-    \includegraphics[scale=0.2]{images/regex/CharClassMergePattern.pdf}
+    \includegraphics[scale=0.2]{images/regex/statearray.pdf}
   \end{center}
   \caption{StateArray による状態遷移}
-  \label{fig:CharClassMergePattern}
+  \label{fig:statearray}
 \end{figure}
 
 % subset construction の速度 O(mlogn)
@@ -754,15 +755,28 @@
 \end{lstlisting}
 
 % Print の分割部分の話追加 最後
-正規表現をファイル分割して並列処理をする際、本来マッチングする文章がファイル分割によってマッチングしない場合がある。
+分割されたファイルに対して正規表現によるマッチングを行う。
+マッチングすると、マッチングの始まりのファイルの場所と終わりのファイルの場所を Result という構造体に格納する。
+マッチングの数だけこの構造体が生成され、これらは List 構造として結果をまとめていく。 (ソースコード\ref{src:result})
+\begin{lstlisting}[frame=lrbt,label=src:result,caption=Resultの構造体,numbers=left]
+typedef struct result {
+    unsigned char *begin;
+    unsigned char *end;
+    bool continued;
+    struct result *next;
+} Result, *ResultPtr;
+\end{lstlisting}
 
-図\ref{fig:regexdivide}はその一例である。正規表現 ab*c のマッチングする文字列の集合は {ac,abc,abbc,ab..bc} である。
-分割される前はこの文字列 abbbbc は問題なく正規表現 ab*c にマッチングする。
+全ての分割されたファイルに対してマッチングが終了すると、Print Task にてまとめてマッチした部分を表示する。
 
+正規表現をファイル分割して並列処理をする際、本来マッチングする文章がファイル分割によってマッチングしない場合がある。
+図\ref{fig:regexdivide}はその一例である。
 並列処理時、分割されたファイルに対してパターンマッチさせるので、分割された1つ目のファイルの末尾の abb 、2つ目のファイルの先頭に bbc はマッチングしない。
 本来分割される前はマッチングする文字列だが、この場合見逃してしまう。
 それを解決するために、正規表現にマッチングし始めたファイルの場所を覚えておく。
-そして、1つ目のファイルの末尾が状態遷移の途中で終わっていた場合は、結果を集計する際に再度マッチングし始めた場所から正規表現をマッチングさせる。
+そして、1つ目のファイルの末尾が状態遷移の途中で終わっていた場合(状態 1 でない場合)は、結果を集計する際に再度マッチングし始めた場所から正規表現をマッチングさせる。
+
+このマッチングは結果を集計する Print Task にて実行されるので、single thread で処理される。
 
 \begin{figure}[htpb]
   \begin{center}
@@ -772,7 +786,6 @@
   \label{fig:regexdivide}
 \end{figure}
 
-
 \begin{lstlisting}[frame=lrbt,label=src:print,caption=結果の整合性,numbers=left]
 static
 TSValue stateSkipOnce(TSValue tsv) {
@@ -783,13 +796,9 @@
     return tsv;
 }
 
-
 static int
 run_print(SchedTask *s, void *rbuf, void *wbuf)
 {
-    MapReduce *w = (MapReduce*)s->get_input(0);
-    int out_size = w->division_out_size / sizeof(unsigned long long);
-    int out_task_num = w->task_num;
     ResultPtr prev = NULL;
     for (int i = 0; i < out_task_num ; i++) {
         ResultPtr r = (ResultPtr)w->o_data[i*out_size+0];
@@ -802,7 +811,7 @@
             continue;
         }
         if (prev) {
-            if (i >= out_task_num) break; 
+            if (i >= out_task_num) break;
             // 最後のブロックでなく、前の prevBlockEnd が state 1 でない場合)
             StatePtr prevBlockEnd = (StatePtr)w->o_data[i*out_size-1];
             if (prevBlockEnd->bitState.bitContainer !=1) {
--- a/paper/images/image.graffle	Thu Feb 18 05:14:58 2016 +0900
+++ b/paper/images/image.graffle	Thu Feb 18 05:49:29 2016 +0900
@@ -26,7 +26,7 @@
 	<key>MasterSheets</key>
 	<array/>
 	<key>ModificationDate</key>
-	<string>2016-02-17 20:10:54 +0000</string>
+	<string>2016-02-17 20:32:10 +0000</string>
 	<key>Modifier</key>
 	<string>MasaKoha</string>
 	<key>NotesVisible</key>
@@ -85762,6 +85762,91 @@
 			<key>VPages</key>
 			<integer>1</integer>
 		</dict>
+		<dict>
+			<key>ActiveLayerIndex</key>
+			<integer>0</integer>
+			<key>AutoAdjust</key>
+			<false/>
+			<key>BackgroundGraphic</key>
+			<dict>
+				<key>Bounds</key>
+				<string>{{0, 0}, {1118, 783}}</string>
+				<key>Class</key>
+				<string>SolidGraphic</string>
+				<key>ID</key>
+				<integer>2</integer>
+				<key>Style</key>
+				<dict>
+					<key>stroke</key>
+					<dict>
+						<key>Draws</key>
+						<string>NO</string>
+					</dict>
+				</dict>
+			</dict>
+			<key>BaseZoom</key>
+			<integer>0</integer>
+			<key>CanvasOrigin</key>
+			<string>{0, 0}</string>
+			<key>ColumnAlign</key>
+			<integer>1</integer>
+			<key>ColumnSpacing</key>
+			<real>36</real>
+			<key>DisplayScale</key>
+			<string>1.0000 cm = 10.0000 cm</string>
+			<key>GraphicsList</key>
+			<array/>
+			<key>GridInfo</key>
+			<dict/>
+			<key>HPages</key>
+			<integer>2</integer>
+			<key>KeepToScale</key>
+			<true/>
+			<key>Layers</key>
+			<array>
+				<dict>
+					<key>Lock</key>
+					<string>NO</string>
+					<key>Name</key>
+					<string>レイヤー 1</string>
+					<key>Print</key>
+					<string>YES</string>
+					<key>View</key>
+					<string>YES</string>
+				</dict>
+			</array>
+			<key>LayoutInfo</key>
+			<dict>
+				<key>Animate</key>
+				<string>NO</string>
+				<key>circoMinDist</key>
+				<real>18</real>
+				<key>circoSeparation</key>
+				<real>0.0</real>
+				<key>layoutEngine</key>
+				<string>dot</string>
+				<key>neatoLineLength</key>
+				<real>0.20000000298023224</real>
+				<key>neatoSeparation</key>
+				<real>0.0</real>
+				<key>twopiSeparation</key>
+				<real>0.0</real>
+			</dict>
+			<key>Orientation</key>
+			<integer>2</integer>
+			<key>PrintOnePage</key>
+			<false/>
+			<key>RowAlign</key>
+			<integer>1</integer>
+			<key>RowSpacing</key>
+			<real>36</real>
+			<key>SheetTitle</key>
+			<string>キャンバス 22</string>
+			<key>UniqueID</key>
+			<integer>29</integer>
+			<key>VPages</key>
+			<integer>1</integer>
+		</dict>
 	</array>
 	<key>SmartAlignmentGuidesActive</key>
 	<string>YES</string>
@@ -85772,7 +85857,7 @@
 	<key>WindowInfo</key>
 	<dict>
 		<key>CurrentSheet</key>
-		<integer>4</integer>
+		<integer>11</integer>
 		<key>Expanded_Canvases</key>
 		<array>
 			<string>cctree</string>
@@ -85791,9 +85876,9 @@
 		<key>TopSlabHeight</key>
 		<real>682</real>
 		<key>VisibleRegion</key>
-		<string>{{469.88636363636357, -165}, {687.5, 1114.772727272727}}</string>
+		<string>{{542.99062758785806, -66}, {565.42053303038585, 916.82238496331979}}</string>
 		<key>Zoom</key>
-		<real>0.88000000000000012</real>
+		<real>1.0700000524520874</real>
 		<key>ZoomValues</key>
 		<array>
 			<array>
@@ -85901,6 +85986,11 @@
 				<real>1</real>
 				<real>1</real>
 			</array>
+			<array>
+				<string>キャンバス 22</string>
+				<real>1</real>
+				<real>1</real>
+			</array>
 		</array>
 	</dict>
 </dict>
Binary file paper/master_paper.pdf has changed