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

annotate paper/chapter3.tex @ 68:9c5f2ffbeb4e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix preliminary
author Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
date Mon, 24 Feb 2014 19:41:40 +0900
parents 663ef31f734f
children 3988365f6f03
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
44
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
1 \chapter{例題}
0
9bf2694ed231 add some files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 \label{chap:poordirection}
9bf2694ed231 add some files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3
47
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
4 \section{ファイルの読み込みに関する例題}
43
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
5 テキストファイルをある一定のサイズに分割して読み込むプログラムである。このプログラムでは、pread という関数で実装した。
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
6 pread 関数は UNIX 標準に関するヘッダファイル、unistd.h に含まれている関数である。(表\ref{table:pread})
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
7 読み込んだテキストファイルはバッファに格納されるが、その格納先は TaskManager の API でメモリを確保する。
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
8 \begin{tiny}
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
9 \begin{table}[ht]
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
10 \begin{center}
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
11 \label{table:pread}
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
12 \small
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
13 ssize\_t pread(int fd, void *buf, size\_t nbyte, off\_t offset);
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
14 \begin{tabular}[t]{c|l}
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
15 \hline
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
16 int fd & 読み込むファイルディスクリプタ \\
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
17 \hline
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
18 void *buf & 予め用意したバッファへの書き込み \\
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
19 \hline
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
20 size\_t nbyte & 読み込むサイズ \\
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
21 \hline
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
22 off\_t offset& ファイルの先頭からのオフセット \\
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
23 \hline
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
24 \end{tabular}
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
25 \caption{pread 関数の概要}
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
26 \end{center}
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
27 \end{table}
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
28 \end{tiny}
37
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
29
68
9c5f2ffbeb4e fix preliminary
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
30 ハードディスクに保存されている 10GB のテキストファイルを分割して読み込み終わるまでの時間を表\ref{table:preaddata}に示す。
9c5f2ffbeb4e fix preliminary
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
31 分割サイズとは、1回の読み込み量である。
43
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
32 \begin{tiny}
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
33 \begin{table}[ht]
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
34 \begin{center}
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
35 \label{table:preaddata}
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
36 \small
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
37 \begin{tabular}[t]{c|l}
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
38 \hline
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
39 分割サイズ & 読み込み速度(s)\\
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
40 \hline
68
9c5f2ffbeb4e fix preliminary
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
41 16KB & 391.7 \\
43
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
42 \hline
68
9c5f2ffbeb4e fix preliminary
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
43 16MB & 123.6 \\
43
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
44 \hline
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
45 \end{tabular}
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
46 \caption{file read の実行結果}
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
47 \end{center}
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
48 \end{table}
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
49 \end{tiny}
37
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
50
43
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
51 分割サイズを大きくすると、pread の呼ばれる回数が少なくなるので読み込むことが速くなる。
37
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
52
44
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
53 \newpage
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
54
47
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
55 \section{ファイルに対して処理を行う例題}
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
56 読み込んだテキストファイルに対して文字列検索を行う例題として、Boyer-Moore String Search を実装した。
43
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
57 このアルゴリズムは 1977 年に Robert S. Boyer と J Strother Moore が開発した効率的なアルゴリズムである。
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
58
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
59 Boyer-Moore String Search を紹介する前に、文字列検索で比較的単純なアルゴリズムである力任せ法を紹介する。
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
60 なお、テキストファイルに含まれている文字列を text、検索する文字列を pattern と定義する。
c153591bb3f7 add some image files
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 42
diff changeset
61
44
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
62 力任せ法(総当り法とも呼ばれる)は、text と pattern を先頭から比較していき、
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
63 pattern と一致しなければ pattern を1文字分だけ後ろにずらして再度比較をしていくアルゴリズムである。
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
64 text の先頭から pattern の先頭を比較していき、文字の不一致が起きた場合は、
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
65 pattern を右に 1 つだけずらして、再度 text と pattern の先頭を比較していく。
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
66 (図\ref{fig:bruteforth})
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
67
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
68 \begin{figure}[htbp]
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
69 \begin{center}
68
9c5f2ffbeb4e fix preliminary
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
70 \includegraphics[width=0.7\textwidth]{fig/bruteforth.pdf}
44
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
71 \end{center}
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
72 \caption{力まかせ法}
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
73 \label{fig:bruteforth}
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
74 \end{figure}
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
75
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
76 このアルゴリズムは実装が簡単であり、pattern が text に含まれていれば必ず探しだすことができる。
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
77 しかし、text と pattern の文字数が大きくなるにつれて、比較回数も膨大になる恐れがある。
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
78 text の文字数を $n$、pattern の文字数を $m$とすると、力任せ法の最悪計算時間は $O(nm)$ となる。
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
79
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
80 この比較回数を改善したアルゴリズムが Boyer-Moore String Search である。
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
81 力任せ法との大きな違いとして、text と pattern を先頭から比較するのではなく、
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
82 pattern の末尾から比較していくことである。そして不一致が起こった場合は、
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
83 その不一致が起こった text の文字で再度比較する場所が決まる。
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
84
45
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
85 まず始めに、比較する場所を着目点とおく。図\ref{fig:bmsearchthink}の場合、
44
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
86 最初に比較する patternの末尾 と、それに対応する text を着目点とする。
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
87 (a)ではその着目点で不一致が起こっているので、それ以上比較しなくてもよいことがわかる。
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
88 不一致が起こった場合は (b) のように着目点をずらしていく。着目点を1つ右にずらして再度 pattern の末尾から比較していく。これを繰り返しをして、(d) のときに初めて一致することがわかる。
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
89
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
90 (a)のときに不一致を起こした text の文字に注目する。その文字が pattern に含まれていない文字であるならば、着目点を1つずらしても、2つずらしても一致することはない。pattern に含まれていない文字で不一致になった場合は、pattern の文字数分だけ着目点をずらすことができる。
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
91
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
92 \begin{figure}[htbp]
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
93 \begin{center}
68
9c5f2ffbeb4e fix preliminary
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
94 \includegraphics[width=0.7\textwidth]{fig/bmsearchthink.pdf}
44
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
95 \end{center}
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
96 \caption{pattern に含まれていない文字で不一致になった場合}
45
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
97 \label{fig:bmsearchthink}
44
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
98 \end{figure}
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
99
68
9c5f2ffbeb4e fix preliminary
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
100 \newpage
9c5f2ffbeb4e fix preliminary
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
101
44
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
102 次に、pattern に含まれている文字で不一致になった場合を紹介する。
45
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
103 図\ref{fig:bmsearchthink}と同様に、文字を比較していく。
46
b72aa70d301d write BMsearch
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 45
diff changeset
104 図\ref{fig:bmsearchinclude}(a)のときに不一致が起こる。
45
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
105 その時の text の文字列は pattern に含まれている。
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
106 この場合は着目点を右に2つずらすと text と pattern が一致する。
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
107 もし、pattern に含まれている文字で不一致になった場合は、その text の文字に注目する。
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
108 その文字を pattern 内から探し、その文字が pattern の末尾から
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
109 どれだけ離れているかで着目点を右にずらす量が決定される。
46
b72aa70d301d write BMsearch
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 45
diff changeset
110 図\ref{fig:bmsearchinclude}の場合であれば、不一致時の文字が a であれば右に2つ、
45
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
111 b であれば右に1つずらすことができる。
44
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
112
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
113 \begin{figure}[htbp]
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
114 \begin{center}
68
9c5f2ffbeb4e fix preliminary
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
115 \includegraphics[width=0.7\textwidth]{fig/bmsearchinlucde.pdf}
44
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
116 \end{center}
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
117 \caption{pattern に含まれている文字で不一致になった場合}
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
118 \label{fig:bmsearchinclude}
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
119 \end{figure}
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
120
45
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
121 \newpage
44
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
122
45
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
123 pattern に同じ文字が複数入り、その文字で不一致になった場合は図\ref{fig:bmsearchsame}のようになる。
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
124 この場合 a という文字が pattern の末尾から 1つ離れている箇所と 3 つ離れている箇所が存在する。
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
125 (a) のように、a で不一致が起こった場合は、着目点を右に1つか3つ移動できる。
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
126 しかし、着目点を右に3つずらしてしまうと、(b-1)のように text の途中にある "abac" という文字列を見逃してしまう。着目点を右に1つずらせば、(b-2)のように検索漏れを起こすことはなくなる。
44
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
127
45
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
128 このように、pattern に同じ文字が複数入っている場合は、末尾から一番近いほうを適用する。よって、図\ref{fig:bmsearchinclude}では、不一致時の文字が a であれば右に1つ、b であれば右に2つ着目点をずらすことができる。
44
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
129
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
130 \begin{figure}[htbp]
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
131 \begin{center}
68
9c5f2ffbeb4e fix preliminary
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
132 \includegraphics[width=0.7\textwidth]{fig/bmsearchsame.pdf}
44
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
133 \end{center}
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
134 \caption{pattern に同じ文字が複数入り、その文字で不一致になった場合}
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
135 \label{fig:bmsearchsame}
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
136 \end{figure}
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
137
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
138
45
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
139 \newpage
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
140 pattern と text と不一致時の処理をまとめると、
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
141
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
142 \begin{itemize}
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
143 \item pattern に含まれていない文字の場合は、 pattern の長さだけ着目点を右にずらす
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
144 \item pattern に含まれている文字の場合は、 その文字が pattern の末尾から離れている分だけ着目点を右にずらす
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
145 \item pattern に含まれている文字かつ、その文字が pattern に複数含まれている場合は、 pattern の末尾から一番近い分だけ着目点を右にずらす
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
146 \end{itemize}
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
147
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
148 となる。 図\ref{fig:bmsearchbasic}の例であれば、不一致字の text の文字が a であれば着目点を 2つ、 b であれば 1つ、それ以外の文字列は3つずらすことができる。
44
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
149
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
150 \begin{figure}[htbp]
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
151 \begin{center}
68
9c5f2ffbeb4e fix preliminary
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
152 \includegraphics[width=0.7\textwidth]{fig/bmsearchbasic.pdf}
44
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
153 \end{center}
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
154 \caption{Boyer-Moore Search String}
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
155 \label{fig:bmsearchbasic}
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
156 \end{figure}
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
157
68
9c5f2ffbeb4e fix preliminary
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 64
diff changeset
158 \newpage
45
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
159 このように、Boyer-Moore Search String は、不一致が起こった時の text の文字によって着目点をずらすということが起こるので、
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
160 文字列検索を行う前に、着目点をずらす量を参照するための BMsearch skip table を作成する。
46
b72aa70d301d write BMsearch
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 45
diff changeset
161 "doing" という pattern であれば、そのテーブルは図\ref{fig:bmskiptable1}となる。
45
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
162
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
163 \begin{figure}[htbp]
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
164 \begin{center}
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
165 \includegraphics[width=0.8\textwidth]{fig/bmskiptable1.pdf}
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
166 \end{center}
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
167 \caption{BMsearch skip table}
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
168 \label{fig:bmskiptable1}
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
169 \end{figure}
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
170
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
171 \if0
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
172 文字列検索を行う前に、不一致になったときの文字列によって着目点をいくつ右にずらすかというテーブルを作成しなければならない。
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
173
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
174 そのテーブルの作成は次のプログラムで作成できる。
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
175
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
176 \newpage
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
177
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
178 \begin{verbatim}
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
179 static int*
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
180 create_BMskiptable(unsigned char *pattern,
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
181 int pattern_len,int *skip_table)
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
182 {
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
183 for(int i = 0; i < 128; ++i){
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
184 skip_table[i] = pattern_len;
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
185 }
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
186
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
187 for(int j = 0; j < pattern_len - 1; ++j){
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
188 skip_table[pattern[j]] = pattern_len - j - 1;
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
189 }
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
190
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
191 return skip_table;
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
192 }
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
193 \end{verbatim}
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
194 このソースでの 128 とは ASCII コード表における最大値である。
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
195 それぞれの文字に対して pattern の長さ (pattern\_len) を格納する。pattern が "doing" という文字列だと仮定すると、
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
196 pattern\_len = 5 となる。次に pattern の先頭から文字を調べる。
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
197 先頭の文字は d であり、d に対応する table に着目点をずらすための移動量を格納する。
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
198 移動量を格納したら、pattern の次の文字を調べ、そして移動量を格納していく。(図\ref{fig:bmskiptable})
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
199
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
200 \begin{figure}[htbp]
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
201 \begin{center}
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
202 \includegraphics[width=0.8\textwidth]{fig/bmskiptable.pdf}
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
203 \end{center}
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
204 \caption{skip table の 生成時の様子}
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
205 \label{fig:bmskiptable}
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
206 \end{figure}
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
207
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
208 \fi
c041b9b3bf9d add image
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 44
diff changeset
209
46
b72aa70d301d write BMsearch
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 45
diff changeset
210 \newpage
b72aa70d301d write BMsearch
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 45
diff changeset
211
44
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
212
47
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
213 この例題ではファイルを読み込んで一定の大きさでファイルを分割する。分割したものにそれぞれ Boyer-Moore String Search を行う。
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
214 それぞれの結果は pattern が含まれている個数が返ってくるので、最後に集計をして個数を表示する。このような一つ一つの処理を Task と呼ぶ。
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
215 図\ref{fig:includeiotask}では、ファイルの読み込みが File Read、分割したものに Boyer-Moore String Search することが Run Tasks、
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
216 返した結果が Output Data、それぞれの結果の集計が Run resultTask に相当する。
44
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
217
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
218 \begin{figure}[htbp]
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
219 \begin{center}
47
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
220 \includegraphics[width=1.0\textwidth]{fig/includeiotask.pdf}
44
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
221 \end{center}
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
222 \caption{IO を含む Task}
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
223 \label{fig:includeiotask}
cd95400bcaec write BM search (not finish)
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 43
diff changeset
224 \end{figure}
37
ce985cabf699 add OUTLINE chapter4
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 36
diff changeset
225
47
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
226 ファイルを分割したときに、分割される部分で pattern が含まれる場合が存在する。
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
227 その場合は、本来の読み込み部分の text の長さ $L$ に加えて、pattern の長さ $s$ だけ多く読みこむように設計することでこの問題は解決できる。
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
228 しかし、1 つの Search Task の text の長さが $L+s$ の場合だと、pattern が Search Task 1 に含まれ、Search Task 2 にも含まれてしまう。
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
229 (図\ref{fig:includeiotask})
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
230
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
231 \begin{figure}[htbp]
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
232 \begin{center}
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
233 \includegraphics[width=1.0\textwidth]{fig/iodivfail.pdf}
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
234 \end{center}
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
235 \caption{分割周りの処理・失敗時 (例:doing の検索)}
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
236 \label{fig:includeiotask}
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
237 \end{figure}
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
238
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
239 それを解決するために、1つの Search task の text の長さに pattern の長さを加えてから 1 引いた数だけ読み込むようにすればそのような問題は起こらない。よって、読み込むデータ量は $ L + s -1 $となる。
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
240
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
241 \begin{figure}[htbp]
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
242 \begin{center}
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
243 \includegraphics[width=1.0\textwidth]{fig/iodivsuc.pdf}
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
244 \end{center}
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
245 \caption{分割周りの処理・成功時 (例:doing の検索)}
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
246 \label{fig:includeiotask}
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
247 \end{figure}
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
248
64
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 48
diff changeset
249 力任せ法と Boyer-Moore String Search を比較してみた。以下に実験環境と結果を示す。(表\ref{table:search})
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 48
diff changeset
250 \begin{itemize}
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 48
diff changeset
251 \item Mac OS X 10.9.1
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 48
diff changeset
252 \item 2*2.66 GHz 6-Core Intel Xeon
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 48
diff changeset
253 \item file size 10GB
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 48
diff changeset
254 \end{itemize}
47
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
255
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
256 \begin{tiny}
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
257 \begin{table}[ht]
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
258 \begin{center}
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
259 \label{table:search}
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
260 \small
64
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 48
diff changeset
261 \begin{tabular}[t]{c|r}
47
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
262 \hline
64
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 48
diff changeset
263 文字列検索アルゴリズム & 処理速度(s)\\
47
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
264 \hline
48
masa
parents: 47
diff changeset
265 力任せ法 & 11.792 \\
47
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
266 \hline
48
masa
parents: 47
diff changeset
267 Boyer-Moore String Search & 6.508 \\
47
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
268 \hline
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
269 \end{tabular}
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
270 \caption{文字列検索アルゴリズムの比較}
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
271 \end{center}
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
272 \end{table}
6cb2ab3726bf chapter3 ok
Masataka Kohagura <e085726@ie.u-ryukyu.ac.jp>
parents: 46
diff changeset
273 \end{tiny}
48
masa
parents: 47
diff changeset
274
masa
parents: 47
diff changeset
275 Boyer-Moore String Search によって 44\% 改善した。