デジタルサーチャー講座

検索を科学する
塩田 紳二

第2回

検索の基本動作

インターネット検索や文字列検索、世の中には、いろいろな検索があるが、その基本になるのはコンピュータのメモリー上での検索処理である。つまり、メモリーの中にあるデータから特定のパターンを見つけるという処理である。今回は、簡単な検索を例にして、コンピュータ内部での検索処理を見ていくことにする。

検索パターンの指定

stays

ることを仮定しているため、一般的な検索

mainlyでは、レコードと呼ばないこともある。ここ検索とは、検索の対象となるデータと、in

では、単に「要素」と呼ぶことにしよう。

検索したい情報を使って行う処理のこと

the

この単語データから、 rain 、 the とだ。簡単にいえば、対象となるデータのplain

いった単語を探すのが、「完全一致」によ中から指定されたパターンと一致するもる検索である。のだけを見つけるというのが検索であ検索の対象となるデータは、通常、複完全一致の場合、検索パターンとデーる。実際の検索では、その対象は、文字数の要素に分かれていることが多い。たタの各要素（この場合は個々の単語）のや文字列だけでなく、複雑なものになる

とえば、上の例では、データは単語ごと一致をデータの先頭から調べていく。すことがある。しかし、コンピュータのメモに分かれている。データベースでは、べてのデータを調べても一致したものがリーの中では、どれも、2 進法で表現さ個々の要素をレコードと呼ぶ。このためなければ、検索は失敗したことになる。

れたビットパターンにすぎない。以後のこうした検索の場合でも個々の要素をレ

たとえば、上記の例で、 cat という検索

検索例では、文字列を使って対象となるコードと呼ぶこともある。しかし、データパターンを探しても見つからない。

データや検索パターンを指定しているベースの場合、レコードは同じ形式であ単語が検索パターンと一致するかどうが、これは、図や文章による表現が簡単だからで、文字列の場合だけを解説してtheいるわけではない。
さて、検索の一番簡単なパターンは、見つけたい文字列そのものを指定することだ。たとえば、次のように複数の英単語からなるデータがあったとする。
therainstaysを探す
場
合in

spain

stays

rain
inthestays↑
一致しない 次の単語へ
rainstays↑
一致しない 次の単語へ
instays↑
一致しない 次の単語へ
spainstays↑↑↑ 一致しない 次の単語へ
一致staysstays↑↑↑↑↑
すべて一致 発見

mainly：：spain
図 1 完全一致での検索パターン

104 │ INTERNET magazine │ 2005 │ 07 │インターネットマガジン／株式会社インプレスR&D©1994-2007 Impress R&D

therainthecat↑
一致しないraincat
↑
一致しない

in：
：：
：
：
：
plain

plaincat
↑
一致しない
最後の要素
検索失敗

次の単語へ

次の単語へ

catを探す場合かは、単語の各文字と検索パターンの各文字を順に調べていく方法で行われる（図 1）。

前方一致、後方一致、部分一致を判定している。

行コードやヌルコードなどが使われる。

この動作は、メモリー内の連続した一また、対象データ自体の最後を判定する

定の領域に置かれたデータ同士（ただために、さらに別の終端記号が置かれるし、双方のサイズは必ずしも一致しなこともある。

い）を順次比較する。

検索の基本動作とは、検索されるデー

通常コンピュータのメモリーは、8bitタ、検索パターンの双方がメモリー上に完全一致は、検索の基本だが、人間がや 16bit といった単位でアドレスが割り当あり、CPU は、その一致を調べるという使うには、ちょっと不便なこともある。な

てられており、CPU はメモリーのアドレ動作である（図 6）。CPU は、アドレスを 1ぜなら、人間は必ずしも検索対象を明確スを指定してその内容を読み書きする。

つずつ、同じ値かどうかを比較することに記述できるとは限らないからである。

パソコンなどで使われている CPU では、を検索パターンすべてについて繰り返

このような単語のデータの場合、たとえアドレスは 8bit をひとまとまりにしたバイす。途中で不一致が見つかればその要ば、最初が S の単語とか、最後が in

ト単位で割り当てられる（図 4）。

素の検索は失敗で、次の要素へ移る。比だったというあいまいな記憶だけが残っ

前の単語検索の例でいえば、個々の単較するときには、終端記号に注意し、こていて、それを見つけたいという場合が語は、それを構成する文字を連続したメれを越えて比較を行わないようにする。

ある。

モリーの領域に置けば表現できる（図 5）。

CPU によっては、これを 1 つの命令とし最初が sp で始まるもののように、見つただし、単語を単にメモリーに書き込んて実行することはできるが、動作としてける要素の前半だけを検索パターンに指でしまうと、単語と単語がつながってしは、丹念にメモリーのアドレス 1 つ 1 つを定することを「前方一致」による検索といまい、区別ができなくなる。そこで、通比較していくしかない。

う。先ほどの例では、 spain が該当する。

常は、要素の終わりを意味する特殊な文

このとき、完全一致と前方一致では、具体的にはどうやって検索しているの字やビットパターンを使って、個々の要素どこまで比較するかの違いでしかない。

かというと、基本は完全一致の場合と同を分離する。このようなものを「終端記終端記号の直前まで比較を行うのが完じだが、単語全体を調べないだけであ号」や「終端文字」などと呼ぶ。どのよう全一致検索で、検索パターンが短く、そる。検索パターンは、上記の例では 2 文

なビットパターンを使えばいいかは、対れより手前で比較が終わるのが前方一致字しかないので、各単語の先頭の 2 文字象となるデータによって違ってくる。たとである。この動作から見ると、完全一致が一致するかどうかを調べていく（図 2）。

えば文字列だけからなるデータでは、改による検索とは、前方一致検索の特殊な逆に、最後が in になる単語というような検索を行うことを「後方一致」と呼ぶ。この場合は、各単語の最後の 2 文字が一致するかどうかを調べる（図 3）。前
方一致と違う点は、単語によって長さが違うために、最後の 2 文字を見つけるのには手間がかかるという点である。
もう1 つのパターンとして、途中に ai

stays

spain

spain

完
全一致の場
合

spacestays↓×spain
2番目の文字が一致せず
d次の文字を検査
spain
↓↓↓↓↓
spain
すべての文字が一致
d発見
space
↓↓×
spain
3番目の文字が一致せず

stays

sp
前
方一致の場
合

spain

spacestays↓×sp
2番目の文字が一致せず
d
次の文字を検査spain↓↓
sp
2文字が一致 s 発見space↓↓
sp
2文字が一致 s 発見を含む単語という検索方法も考えられる。このような検索を「部分一致」検索と

図 2 前方一致での検索パターン呼ぶ。
stays

さらなる検索の分解

ain

前方一致と完全一致による検索をより細かく見ていこう。前述のように、これらは、対象となるデータと、検索パターンの双方を先頭から順に一致していくかど

後方一致の検
索

spain

stays
↓×ain
2番目の文字が一致せず
d次の文字を検査
spain
↓↓↓
ain
すべての文字が一致d発見

spacespace↓×ain
2文字目が一致せず

rainrain↓↓↓ain
すべての文字が一致
d
発見

うかを調べることで、一致するかどうか
図 3 後方一致での検索パターン

インターネットマガジン／株式会社インプレスR&D

デジタルサーチャー講座
検索を科学する │ INTERNET magazine │ 2005 │ 07 │ 105©1994-2007 Impress
R&D場合、といえるわけだ。
さらに部分一致の検索を考えてみよう。この場合、メモリー内のデータに対と、前方一致や完全一致と同じことにな

こう考えると、あるメモリー範囲の中る。つまり、部分一致検索の特殊な場合から、特定のパターンが連続したものをと考えることができる。

見つけるという部分一致検索の動作が、して、一致するところが見つかるまで、同じように、開始位置を対象データの比較を始める位置をずらしながら一致を最後と検索パターンの最後が一致すると見ていく（図 7）。

ころまでずらしたのが、後方一致検索で検索を始めるところを先頭に固定する的な動作であるといえる。

検索対象データの状態ある。

コンピュータのメモリーとは、一定サイズのビット（この場合は8bitは）をまとめて、それに連続する数字で表されるアドレスを割り振ったもの。

8bit

メモリー内のデータに対する検索の基本

実は、検索は、対象となるデータの状態により、探し方やその効率が変わってくる。先ほどの単語データの例では、

・・・
nn+
1n+2n+3n+4n+
5n+6n+
7n+
8n+
9n+
10n+
11n+
12n+
13n+
14n+
15n+
16n+
17n+
18n+
19n+20アドレス

the が 2 つ入っている。つまり、「完全一致」の場合であっても、1 つだけ見つけたからといって、必ずしもそれで終わり

図 4 アドレスの割り振りというわけではない。このため、どんな場合でも、最後の単語まで調べる必要がある。エディターで、 the という単語をすべ検索対象とするデータの各要素をメモリー内に置く。各要素同士を分離するために、要素の最終に終端記号（赤色の枠）を置き、要素の終わりを示す。て他の単語に置き換えるような場合を考えてみよう。最初の 1 つだけが見つかっ・・・ the?

rain?

in?

spain?

sta ・・・

nn+
1n+
2n+
3n+
4n+
5n+
6n+
7n+
8n+
9n+
10n+
1
1n+
12n+
13n+
14n+
15n+
16n+
17n+
18n+
19n+20ても処理が終わりとは限らないわけだ。となると、このようなデータでは、単語の位置や検索パターンに関係なく、どん図 5 検索対象のデータは終端記号で区切られるな場合でも、対象データすべてを調べることになる。対象データが少ない場合にはいいが、大量になると、検索速度が問

アドレス・・・

the?

rain?

in?

spnn+
1n+
2n+
3n+
4n+
5n+
6n+
7n+
8n+
9n+
10n+
11n+
12n+
13

一致せず一致せず一致せず

n?

stannn+++111456
一致している

n+
17n+
18n+
19発見n+
20ai

題になる。
もし、対象データに単語が重複して登録されていることはないと仮定できるな
ら、検索の効率は上がる。1 つでもデータが見つかれば、そこでやめることがでメモリーの中で、アドレス各アドレスごとに一致するかどうかを調べていく。
検索パターンをすべて調べ終われば、対象を見つけたことになる。

spain?

きるからだ。前述のエディターの例ではmm+
1m+2m+3m+4m+5

これは無理だが、たとえば、名簿のようなそれぞれの要素が重複しないデータと図 6 検索の基本動作いうのは世の中に少なくない。
これでも、前方一致の場合には、すべnn+
1n+2n+3n+4n+5n+
6n+
7n+8n+
9n+
10n+
11n+
12n+
13n+
14n+
15n+
16n+17n+
18n+
19n+20abcdefghijklmnopw

xyzqてのデータを探す必要がある。単語自体は重複していなくても、先頭の数文字が同じという単語がある可能性があるからだ。

？

?

では、さらに、単語がアルファベット順

開始位置をずらしながら比較に並んでいると仮定できると、前方一致
でも、すべてのデータを調べる必要がな
部分一致で検索を行う場合、開始位置からアドレスを1つずつ比較していく。
最初は検索パターンの最初のアドレスと同じ値が見つかるまで開始位置をずらしながら比較していく。

w

xyzmm+1m+2m+3くなる。たとえば、先頭が AB という単語を見つける場合、2 文字目が B より後の C や D で始まる単語に遭遇すれ

図 7 部分一致検索の動作106 │ INTERNET magazine │ 2005 │ 07 │インターネットマガジン／株式会社インプレスR&D©1994-2007 Impress R&Dば、もうそれ以上先に、先頭が AB になる単語がないからだ（図 8）。これを実■ 要素のサイズがわかっているときの後方一致検索
検索対象の大きさは21
はバイトn

現するには、データを辞書順に並べ替え

n+1n+2n+3n+4n+5n+6n+7n+8abcdefg

hn+9 n+10 n+11 n+12 n+13 n+14 n+15 n+16 n+17 n+18 n+19ijkl

mnopw

xyn+21zqzq

21- 4+1=18てしまえばよい。

要素のサイズw

後方一致を効率的に行う方法はあるだろうか？

少なくとも、要素の並べ方

my検索パターンのサイズは4は バイトz■ 要素のサイズがわかっているときの後方一致検索といった方法では、後方一致検索を効率化することはできない。なぜなら、辞書

xm+1 m+2 m+3nn+1n+2n+3n+4n+5n+6n+7n+8abcdefghi

要素のサイズj

検索パターンのサイズは4は バイト順に並べたとしても、同じ語尾を持つ単mn+9 n+10 n+11 n+12 n+13 n+14 n+15 n+16 n+17 n+18klmnopw

x

y

n+21

21バイトある

21-4+1=18バイト目から比較を始めればよい

m+1 m+2 m+3語は全体に分散してしまうからだ。したがって、すべての要素を調べることは避図 9 効率の良い後方一致検索の方法

けられそうにない。
では、各単語の先頭に単語の文字数が入っていたらどうだろうか？

さらに複雑な処理

XABC
ABCX

後方一致検索は、前述したように部分一致検索

検索などでは、もう少し複雑なパターの特殊な場合に相当する。このとき、後ンを表現する「ワイルドカード」が使われなどに一致する。注意するのは、文字方一致となるように検索を開始する場所ることがある。ワイルドカードとは、どん数が 0、つまり存在しない文字にも一致をすばやく決めることができれば、検索な文字にでも、何文字でも一致する記号することである。たとえば、この例では、効率は多少ではあるが上がることになのことなどをいう。また、これを使ったABC などがその例になる。 ＊ ABC ＊る。単語の先頭に単語の文字数が書か検索をワイルドカード検索ということがあは部分一致検索であるが、その特殊な場れている場合、後方一致検索を行うためる。記号としてアスタリスク
（＊）
を使うこ

合が前方一致検索や後方一致検索であに比較を開始する場所は、単語の長さをとが多い。

ることを考えると、存在しない文字にもn、検索パターンの長さ m をとすれば、単語の先頭から、n − m ＋ 1 文字目からこれを使うと、前方一致、後方一致、一致することは妥当な解釈方法である。

部分一致は、

さらに ＊ ABC ＊ XYZ ＊ といった複比較を始めればよい（図 9）。

雑な検索も、 ABC 、 XYZ の 2 つの部

もし、単語の長さが不明の場合、終端前方一致 pattern ＊分一致検索を行うことで処理できる。つ記号を見つけるまで、単語の先頭から後方一致 ＊ pattern

まり、最初に ABC で部分一致検索をデータの大きさを数える必要がある。し部分一致 ＊ pattern ＊行い、発見したら、 ABC の直後からかし、単語の先頭にその大きさが記述してあれば、この手間を省けるわけだ。
さらに、単語の長さがわかれば、前方XYZ による部分一致検索が成功すると表 現 できる 。たとえ ば 、パターンをかどうかで、複雑な検索を処理できる

ABC としたとき、 ＊ ABC ＊ は、（図 10）。

一致検索で、比較が成功しなかったとさまざまな技法はあるが、1 つ 1 つ比き、次の単語へ進む処理を同じように簡AAABCCCC較していくのがコンピュータの検索の基単にできる。

ABC本なのである。

AAAAAAABAABB
ABCABDACB
ADD・・・・・

図8?

maabcdefghijklmnopw

xyzq?

部分一致検索一致一致
部分一致検索abc

アルファベット順なので、これ以降に ab で始まる要素はありえない

AB を前方一致検索する場合

xyz

2つの部分一致検索に分解
検索パターン ＊abc＊xyz

図 10

ワイルドカードを使った複雑な検索であっても、これを複数の部分一致検索に分解して実行できる

インターネットマガジン／株式会社インプレスR&D

デジタルサーチャー講座
検索を科学する │ INTERNET magazine │ 2005 │ 07 │ 107©1994-2007 Impress
R&D［インターネットマガジン バックナンバーアーカイブ］ ご利用上の注意
この PDF ファイルは、株式会社インプレス R&D（株式会社インプレスから分割）が 1994 年～2006 年まで発行した月刊誌『インターネットマガジン』の誌面を PDF 化し、「インターネットマガジン バックナンバーアーカイブ」として以下のウェブサイト「All-in-One INTERNET magazine 2.0」で公開しているものです。

http://i.impressRD.jp/bn
このファイルをご利用いただくにあたり、下記の注意事項を必ずお読みください。
z 記載されている内容（技術解説、URL、団体・企業名、商品名、価格、プレゼント募集、アンケートなど）は発行当時のものです。
z 収録されている内容は著作権法上の保護を受けています。著作権はそれぞれの記事の著作者（執筆者、写真の撮影者、イラストの作成者、編集部など）が保持しています。
z 著作者から許諾が得られなかった著作物は収録されていない場合があります。
z このファイルやその内容を改変したり、商用を目的として再利用することはできません。あくまで個人や企業の非商用利用での閲覧、複製、送信に限られます。
z 収録されている内容を何らかの媒体に引用としてご利用する際は、出典として媒体名および月号、該当ページ番号、発行元（株式会社インプレス R&D）、コピーライトなどの情報をご明記ください。
z オリジナルの雑誌の発行時点では、株式会社インプレス R&D（当時は株式会社インプレス）と著作権者は内容が正確なものであるように最大限に努めましたが、すべての情報が完全に正確であることは保証できません。このファイルの内容に起因する直接的および間接的な損害に対して、一切の責任を負いません。お客様個人の責任においてご利用ください。

このファイルに関するお問い合わせ先
All-in-One INTERNET magazine 編集部
im-info@impress.co.jp
Copyright © 1994-2007 Impress R&D, an Impress Group company. All rights reserved.