Mercurial > hg > Papers > 2014 > masakoha-thesis > final

comparison paper/chapter3.tex @ 45:c041b9b3bf9d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add image
author Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
date Tue, 18 Feb 2014 19:15:02 +0900
parents cd95400bcaec
children b72aa70d301d
comparison
equal deleted inserted replaced
44:cd95400bcaec 45:c041b9b3bf9d
84 pattern の末尾から比較していくことである。そして不一致が起こった場合は、 84 pattern の末尾から比較していくことである。そして不一致が起こった場合は、
85 その不一致が起こった text の文字で再度比較する場所が決まる。 85 その不一致が起こった text の文字で再度比較する場所が決まる。
86 86
87 87
88 \newpage 88 \newpage
89 まず始めに比較する場所を着目点とおく。図\ref{fig:bmsearthink}の場合、 89 まず始めに、比較する場所を着目点とおく。図\ref{fig:bmsearchthink}の場合、
90 最初に比較する patternの末尾 と、それに対応する text を着目点とする。 90 最初に比較する patternの末尾 と、それに対応する text を着目点とする。
91 (a)ではその着目点で不一致が起こっているので、それ以上比較しなくてもよいことがわかる。 91 (a)ではその着目点で不一致が起こっているので、それ以上比較しなくてもよいことがわかる。
92 不一致が起こった場合は (b) のように着目点をずらしていく。着目点を1つ右にずらして再度 pattern の末尾から比較していく。これを繰り返しをして、(d) のときに初めて一致することがわかる。 92 不一致が起こった場合は (b) のように着目点をずらしていく。着目点を1つ右にずらして再度 pattern の末尾から比較していく。これを繰り返しをして、(d) のときに初めて一致することがわかる。
93 93
94 (a)のときに不一致を起こした text の文字に注目する。その文字が pattern に含まれていない文字であるならば、着目点を1つずらしても、2つずらしても一致することはない。pattern に含まれていない文字で不一致になった場合は、pattern の文字数分だけ着目点をずらすことができる。 94 (a)のときに不一致を起こした text の文字に注目する。その文字が pattern に含まれていない文字であるならば、着目点を1つずらしても、2つずらしても一致することはない。pattern に含まれていない文字で不一致になった場合は、pattern の文字数分だけ着目点をずらすことができる。
96 \begin{figure}[htbp] 96 \begin{figure}[htbp]
97 \begin{center} 97 \begin{center}
98 \includegraphics[width=0.5\textwidth]{fig/bmsearchthink.pdf} 98 \includegraphics[width=0.5\textwidth]{fig/bmsearchthink.pdf}
99 \end{center} 99 \end{center}
100 \caption{pattern に含まれていない文字で不一致になった場合} 100 \caption{pattern に含まれていない文字で不一致になった場合}
101 \label{fig:bmsearthink} 101 \label{fig:bmsearchthink}
102 \end{figure} 102 \end{figure}
103 103
104 次に、pattern に含まれている文字で不一致になった場合を紹介する。 104 次に、pattern に含まれている文字で不一致になった場合を紹介する。
105 図\ref{fig:bmsearthink}と同様に、文字を比較していく。 105 図\ref{fig:bmsearchthink}と同様に、文字を比較していく。
106 \ref{fig:bmsearchinlucde}の場合、(a)のときに不一致が起こった時の text の文字列は pattern に含まれている。 106 図\ref{bmsearchinclude}(a)のときに不一致が起こる。
107 \newpage 107 その時の text の文字列は pattern に含まれている。
108 108 この場合は着目点を右に2つずらすと text と pattern が一致する。
109 109 もし、pattern に含まれている文字で不一致になった場合は、その text の文字に注目する。
110 110 その文字を pattern 内から探し、その文字が pattern の末尾から
111 111 どれだけ離れているかで着目点を右にずらす量が決定される。
112 図\ref{bmsearchinclude}の場合であれば、不一致時の文字が a であれば右に2つ、
113 b であれば右に1つずらすことができる。
112 114
113 \begin{figure}[htbp] 115 \begin{figure}[htbp]
114 \begin{center} 116 \begin{center}
115 \includegraphics[width=0.5\textwidth]{fig/bmsearchinlucde.pdf} 117 \includegraphics[width=0.5\textwidth]{fig/bmsearchinlucde.pdf}
116 \end{center} 118 \end{center}
117 \caption{pattern に含まれている文字で不一致になった場合} 119 \caption{pattern に含まれている文字で不一致になった場合}
118 \label{fig:bmsearchinclude} 120 \label{fig:bmsearchinclude}
119 \end{figure} 121 \end{figure}
120 122
121 123 \newpage
122 図\ref{fig:bmsearchsame} 124
123 125 pattern に同じ文字が複数入り、その文字で不一致になった場合は図\ref{fig:bmsearchsame}のようになる。
126 この場合 a という文字が pattern の末尾から 1つ離れている箇所と 3 つ離れている箇所が存在する。
127 (a) のように、a で不一致が起こった場合は、着目点を右に1つか3つ移動できる。
128 しかし、着目点を右に3つずらしてしまうと、(b-1)のように text の途中にある "abac" という文字列を見逃してしまう。着目点を右に1つずらせば、(b-2)のように検索漏れを起こすことはなくなる。
129
130 このように、pattern に同じ文字が複数入っている場合は、末尾から一番近いほうを適用する。よって、図\ref{fig:bmsearchinclude}では、不一致時の文字が a であれば右に1つ、b であれば右に2つ着目点をずらすことができる。
124 131
125 \begin{figure}[htbp] 132 \begin{figure}[htbp]
126 \begin{center} 133 \begin{center}
127 \includegraphics[width=0.5\textwidth]{fig/bmsearchsame.pdf} 134 \includegraphics[width=0.5\textwidth]{fig/bmsearchsame.pdf}
128 \end{center} 135 \end{center}
129 \caption{pattern に同じ文字が複数入り、その文字で不一致になった場合} 136 \caption{pattern に同じ文字が複数入り、その文字で不一致になった場合}
130 \label{fig:bmsearchsame} 137 \label{fig:bmsearchsame}
131 \end{figure} 138 \end{figure}
132 139
133 140
134 図\ref{fig:bmsearchbasic} 141 \newpage
142 pattern と text と不一致時の処理をまとめると、
143
144 \begin{itemize}
145 \item pattern に含まれていない文字の場合は、 pattern の長さだけ着目点を右にずらす
146 \item pattern に含まれている文字の場合は、 その文字が pattern の末尾から離れている分だけ着目点を右にずらす
147 \item pattern に含まれている文字かつ、その文字が pattern に複数含まれている場合は、 pattern の末尾から一番近い分だけ着目点を右にずらす
148 \end{itemize}
149
150 となる。 図\ref{fig:bmsearchbasic}の例であれば、不一致字の text の文字が a であれば着目点を 2つ、 b であれば 1つ、それ以外の文字列は3つずらすことができる。
135 151
136 \begin{figure}[htbp] 152 \begin{figure}[htbp]
137 \begin{center} 153 \begin{center}
138 \includegraphics[width=0.5\textwidth]{fig/bmsearchbasic.pdf} 154 \includegraphics[width=0.5\textwidth]{fig/bmsearchbasic.pdf}
139 \end{center} 155 \end{center}
140 \caption{Boyer-Moore Search String} 156 \caption{Boyer-Moore Search String}
141 \label{fig:bmsearchbasic} 157 \label{fig:bmsearchbasic}
142 \end{figure} 158 \end{figure}
143 159
160 このように、Boyer-Moore Search String は、不一致が起こった時の text の文字によって着目点をずらすということが起こるので、
161 文字列検索を行う前に、着目点をずらす量を参照するための BMsearch skip table を作成する。
162 "doing" という pattern であれば、そのテーブルは図\ref{bmskiptable1}となる。
163
164 \begin{figure}[htbp]
165 \begin{center}
166 \includegraphics[width=0.8\textwidth]{fig/bmskiptable1.pdf}
167 \end{center}
168 \caption{BMsearch skip table}
169 \label{fig:bmskiptable1}
170 \end{figure}
171
172 \if0
173 文字列検索を行う前に、不一致になったときの文字列によって着目点をいくつ右にずらすかというテーブルを作成しなければならない。
174
175 そのテーブルの作成は次のプログラムで作成できる。
176
177 \newpage
178
179 \begin{verbatim}
180 static int*
181 create_BMskiptable(unsigned char *pattern,
182 int pattern_len,int *skip_table)
183 {
184 for(int i = 0; i < 128; ++i){
185 skip_table[i] = pattern_len;
186 }
187
188 for(int j = 0; j < pattern_len - 1; ++j){
189 skip_table[pattern[j]] = pattern_len - j - 1;
190 }
191
192 return skip_table;
193 }
194 \end{verbatim}
195 このソースでの 128 とは ASCII コード表における最大値である。
196 それぞれの文字に対して pattern の長さ (pattern\_len) を格納する。pattern が "doing" という文字列だと仮定すると、
197 pattern\_len = 5 となる。次に pattern の先頭から文字を調べる。
198 先頭の文字は d であり、d に対応する table に着目点をずらすための移動量を格納する。
199 移動量を格納したら、pattern の次の文字を調べ、そして移動量を格納していく。(図\ref{fig:bmskiptable})
200
201 \begin{figure}[htbp]
202 \begin{center}
203 \includegraphics[width=0.8\textwidth]{fig/bmskiptable.pdf}
204 \end{center}
205 \caption{skip table の 生成時の様子}
206 \label{fig:bmskiptable}
207 \end{figure}
208
209 \fi
210
144 211
145 図\ref{fig:includeiotask} 212 図\ref{fig:includeiotask}
146 213
147 \begin{figure}[htbp] 214 \begin{figure}[htbp]
148 \begin{center} 215 \begin{center}
150 \end{center} 217 \end{center}
151 \caption{IO を含む Task} 218 \caption{IO を含む Task}
152 \label{fig:includeiotask} 219 \label{fig:includeiotask}
153 \end{figure} 220 \end{figure}
154 221
155 ・ IO を含む Task なので、ここで説明
156
157 ・ BM Search の概要
158
159 BM Search は XXX が XXX 年に発表した文字列探索アルゴリズム
160
161 ほかにもいろいろ
162
163 力まかせ法についても少し書くか
164
165 [image]BM Search の skip table の説明と図
166
167 [image]BM Search の実行時の説明と図
168
169 ・ BM Search をテキストにかけて、検索文字列が含まれてい数をカウントする。
170
171 図\ref{fig:includeio}
172
173
174 \begin{figure}[htbp]
175 \begin{center}
176 \includegraphics[width=0.5\textwidth]{fig/includeio.pdf}
177 \end{center}
178 \caption{[image]IO を含む Task の図}
179 \label{fig:includeio}
180 \end{figure}
181
182
183 ・ [image]分割で読み込むときに分割サイズを間違えると正しい結果が返ってこない。
184
185 ・ 実験結果を載っけたい
186
187 実験結果どうしよう
188
189 文字列検索して数を数えるプログラムだが、それに対応する Mac のコマンドが、grep -c [検索文字列]
190
191 比較対象をどうしようかしら