デジタルサーチャー講座

検索を科学する
塩田 紳二

第7回

検索の技法

今回は、検索しているときにコンピュータの中でどのような処理が行われているかについて解説する。この連載でも概念的な部分については解説したが、今回は実際にプログラムがどのような動きをするのかについて解説してみることにする。

解説の前にを 1000001 という 7bit で表現する。これを「アルファベット」と呼ぶ。一般にアルを 10 進数で表すと 65 になる（図 1）。

ファベットとは、英語の abc を意味する

解説する前に、少し用語などについてコンピュータは、メモリーを 8bit 単位、が、コンピュータ関連で文字を扱うときにはっきりさせておこう。コンピュータ関連

16bit 単位といったまとまりで読み書きす

アルファベットというと、文字の種類（文の用語には、きちんと定義されているもるため、実際には、7bit で定義された字集合）を指すことが多い。これもコンのもあれば、曖昧なものもある。しかし、ASCII コードは、8bit のデータとしてピュータのメモリー上で考えれば、ビットコンピュータの動作のような論理的なも「01000001」とメモリーに書き込まれる。

パターンの種類ということになる。のを解説する場合には、個々の用語の意

そうなると、文字列とはメモリー内のコンピュータの文字列の場合、必ずし味は、その文章の中でははっきりしてい連続した領域に書き込まれた文字コードも現実の文字と対応していないこともある。ただ、人によって用語の定義などにのつながりということになる。

る。たとえば、DNA から特定のパターン多少の違いがあり、そのために、複数の文字の種類（文字が何種類あるのか）を見つけるなんて場合にも利用される。

解説を見ると、用語定義が曖昧なように感じることがある。
まずは「文字列」。この連載でも時折実際の文字出る単語だが、これは、文字の並びを意

画面やプリンターに出力する
グラフィックパターン

A=1000001

味する。文章などと同じように文字が並んでいるものだが、文字列といったとき

文字コード表メモリー内のパターン

A
視覚には、文法などには影響されない。たとえば、未完成の文章であったり、文法的には間違っていたり、意味のない羅列でB=100001001000001

C=1000011
・・・・ある可能性もある。

文字データ

フォント

次に「文字」だが、これは、コンピュータ内で一定数のビットから構成されるパターンで、文字コードによって現実の文図1字との対応が行われる。たとえば ASCII表現される。コンピュータがこれを出力するとき、文字の形のグラフィックスを表示する。これを見我々が使っている文字は、文字コード表により、コンピュータの中ではビットパターンとしてて我々は文字を認識する。と呼ばれる文字コードでは、大文字の A

86 │ INTERNET magazine │ 2006 │ 01 │インターネットマガジン／株式会社インプレスR&D©1994-2007 Impress R&Dこのようなとき、アルファベットは AGCTの 4 種類しかない。しかし、対象となる

T h i si s

T h i sp e nap e n . T h i sp e ni sg o o d .

DNA は、長さが 30 億程度（人間の場合）あり、たった 4 種類の文字しかないとはいえ、コンピュータを使わないと検索はT h i s不可能である。

p e n

T h i sp e n・・・
1文字ずつずらしていきながら検索文字列すべてが一致する場所を探す

あるいは効率のため、アルファベットを制限することもある。たとえば、検索をT h i s

簡単にするために小文字だけを使うと

p e n

ここですべて一致いったことである。これは、検索漏れをなくすためにも有効な方法だ。大文字、小文字の違いが意味にかかわってこなけ
れば、このような制限を加えることで検図2

最も簡単な文字列検索は、1 文字ずつ比較を行い、不一致があれば、位置を 1 つずらして再度比較を行っていく方法である。

索漏れを防ぐこともできるわけだ。
次に「終端記号」だが、これは、1 つのこの場合の検索とは、文字列の中に検は n に比例する。このため、上記のやりデータの終わりを意味するもので、具体

索文字列と一致するところがあれば、そ方をそのまま実装しているシステムも少的にはメモリー上のビットパターンに対の場所（文字列先頭からの文字数）を答なくない。

応する。たとえば、文字列をメモリーにえとするものとする。この場合の答えは、ワープロの検索機能などのように、対置くときにその終わりを示すために最後必ず 0 以上（最初が 1 文字目だから）とな

象データもそれほど大きくなく、また、検に終端記号を置く。このとき、終端記号る。もし見つからない場合には、0 を答索がたまにしか使われないのであれば、のパターンには、文字と簡単に区別できえとする。また、検索の条件として、検簡単にプログラムを作ることができるたるようなパターンが使われる。前述の索対象文字列の中に含まれるすべてのめ、Brute Force 方式が使われることもASCII コードでは、改行などを意味する検索文字列を見つけることとする。これある。しかし、検索が頻繁に使われるアコントロールコード（値が 0 から 31 までのは、どんなときでも検索対象文字列を最プリケーションや対象データが巨大にな文字で、機器の制御などに使われる）を後まで調べる必要があることを意味する場合には、もう少し工夫する必要があ使うことが多い。

る。

る。

なお、解説では、文字列の検索につい一番簡単な方法は、1 文字ずつ比較すて行うが、実際には、文字だけでなく、る方法である。検索文字列すべてが一さまざまなデータが対象になることがあ致すれば、検索は終了である。一致してる。

いなければ 1 文字ずらして、一致を調べ

検索は、古くからコンピュータが行う

る、これを繰り返す（図 2）。便宜的に不処理の 1 つであったため、いろいろなや一致が起こったときに比較する位置をずり方（アルゴリズム）が提案されてきた。

らすことを「スライド」と呼ぶことにしよこうしたメモリー上の文字列検索についいま、検索対象となる文字列と探したう。比較の開始位置を動かす量（文字ても、効率化する方法がいくつかある。

い文字列（検索文字列）の 2 つがあるとす数）をスライド量とする。この方法はコン

ただし、こうした方法は、検索対象のる。実際には、メモリーのどこかに格納ピュータの性能に頼ったやり方で、「力ず文字の種類（アルファベットの数）や文字されていて、ともに終端記号で終わりがく」（Brute Force）の方法ともいわれる。

列の長さ、検索文字列の最大長といった示されている。話を簡単にするために、検索文字列がすべて検索対象文字列条件により効率に違いが出てくる。このどちらの文字列も ASCII コードからなるに含まれない、つまり 1 文字も一致しなため、よいとされている手法であっても、文字で構成されているとしよう。日本語い検索において、n 文字の中から m 文字

検索対象に合わないと必ずしも効率的の場合、1 文字が 16bit で表され、この中を検索しようとすると、n-m+1 回の比較ではなくなってしまうことがある。に 8bit の文字などが混在してくると処理を行うだけでいい。

メモリー内の文字列から検索がちょっと面倒になるからだ。ただし基本的な考え方は一緒である。

細かな解説は省くが、m に対して n が十分大きな値なら、この処理の実行時間もう少し効率的な方法

最初に解説した方法が非効率なのは 2つ理由がある。1 つは、スライド量が毎回1 と決まっていることである。

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

デジタルサーチャー講座
検索を科学する │ INTERNET magazine │ 2006 │ 01 │ 87
©1994-2007 Impress
R&Dもう 1 つは、前半部分は一致するが、このようにすることで、途中まで一致後ろの方で失敗する場合である。最初した場合でも、不一致のあとに大きくスの 1 文字が一致しなければ、すぐにスラライドさせることが可能になる。

能になる。
たとえば、aabcab という検索文字列で、最後の「ab」まで一致し、c で一致しイドさせて次の場所から開始できるのさらに効率的にするには、検索文字列なかったとき、3 文字ずらして、2 文字目に、途中まで一致しているから、その分の中に含まれる繰り返しパターンに着目からの ab というパターンがそのとき一致スライドを行うまでの比較数が増えてしする。もし、後半部分と同じような文字していたところまでずらすことが可能にまう（図 3）。のパターンが前半にあるなら、一致してなる（図 7）。

これを解消するために考えられたのがいた部分が重なるようにスライドさせるこ

この移動量は、最初の表による移動量BM（Boyer-Moore）法と呼ばれる方法でとで、より大きくスライドさせることが可（この場合は、1）よりも大きく、表を使っある（ちなみに Boyer、Moore は考案者の名前）。
また、この方法は最初に解説した方法

a a a a a a a a a a a a a .............
一致するによく似ているが、比較を検索文字列の先頭からではなく、後ろから行う（図 4）。

aaaaaab不一致
6回の一致のあと不一致で1文字スライド

比較の方向

aaaaaab

このようにすると、文字列の前半部分が一致しているような場合であっても、無aaaaaab

駄な比較を行わずにスライドさせることこれが最後まで繰り返される

aaaaaabができる。
しかし、後半部分が一致したら、やはり結果は同じである。しかし、このとき、

図3前半が一致し、後半で不一致の場合、複数の比較を繰り返すため、検索に時間がかかってしまうことになる。

事前に作っておいた表を使うことで、1文字だけでなく、数文字スライドさせることが可能になるのである。
検索を行う前に、検索文字列につい後ろから比較してみると ･ ･ ･ ･ ･ ･て、各アルファベットが最後から何文字a a a a a a a a a a a a a .............

目に最初に現れるかを表にしておく（図一致する5）。この表を「文字スライド表」と呼ぶこ比較の方向とにする。
この表から、比較で一致しなかった文

aaaaaab不一致

aaaaaab

最後の文字から比較を始めるので比較1回で1文字スライド

aaaaaab字（検索対象文字列中の文字）を探す。

これが最後まで繰り返される

aaaaaabあれば、表にある数字だけスライドさせることができる（図 6）。つまり、文字 x がだけど後半が一致するパターンでは同じ一致しなかったら、検索文字列の中の xa a a a a a a a a a a a a .............の位置がそこに来るようにスライドさせ不一致ることができるのだ。もし、文字 x が検索比較の方向文字列に含まれていなければ、その部分を飛ばして、x の次の文字に検索文字列

baaaaaabaaaaaabaaaaaaの先頭が来るまでスライドさせることができる。

6回の一致のあと不一致で1文字スライド

これが最後まで繰り返される

baaaaaa

検索文字列の長さを m とし、先頭からi 文字目で不一致が起こったとき、一致した部分の長さは m-i なので、文字スライド

図4表から調べた値から引けば、スライド量半が一致するような場合に非効率になるだろう。しかし、BM 法はいくつかの方法を使って効率的にを求めることができる。

88 │ INTERNET magazine │ 2006 │ 01 │BM 法では、比較を後ろから行う。前半が一致するような場合でも比較回数が増えないが、後スライドできるようにしてある。

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

た場合よりも効率的になる。
このbの位置は表に入れない（後ろにもbがあるから） 543210

このためには、やはり表を作らねばならない（こちらの表はパターンスライド表

検索文字列 bdcbaaaaaと呼ぶことにする）。このパターンスライ

一番最後の文字から見て、その文字が最初に現れる位置

ここにbはない

ド表は、検索文字列と同じ長さで、一致以下同じように計算しなかった場所とそのときのスライド量

文字スライド表を表すものだ。
実際のプログラムでは、不一致が起文字abcdefg

スライド量1567999

こったときに、文字スライド表とパターンスライド表からそれぞれスライド量を求1め、大きなほうの値を採用する。

0z9

検索文字列に現れない文字はすべてスライド量を検索文字列の長さとする
一番最後の文字から見て、その文字が最初に現れる位置

検索文字列 bdcbaaaaa

このようにすることで、毎回のスライド...
...

このaは無視（後ろにもaがあるから）量を大きくできるため、最初に紹介した単純な方法よりも速く検索できる可能性が高くなる。また、最悪の場合でも、スラ

図5

文字スライド表は、検索文字列に現れる文字の種類とその最後の出現位置を記録したもの。これを使うことで、不一致が起こったときの文字を見て、スライド量を計算できる。

イド量は 1 となり、最初の方法よりも悪くなる可能性もない。
文字列を最後まで調べるには、検索文

文字スライド表文字abcdefg

スライド量

15

67

9

9

9

字列の最初まで比較が行われたときの位置を結果として出力し、そこからさらに検索対象文字列スライド量を求めて検索を続行する。そしてスライドしたときに検索文字列が後ろにはみ出すようならば、そこで検索が...
...

z
9aaaaabaaaaaaaaa
一致

不一致はb

検索文字列
bdcbaaaaa

検索文字列

bdcbaaaaa

スライド量

不一致の場所（6文字目）検索文字列の長さ=9終了する。

bdcbaaaaabがここにくるまでスライドできる
スライド量＝表の値−検索文字列の長さ＋不一致の場所＝5−9＋6＝2

その他の方法
この BM 法は効率がよく、多くのプロ

図 6 検索中で不一致が起こったら、そのときの検索対象文字列側の文字から文字スライド表を引く。

グラムで利用されている。また、これを得られた数字と検索文字列の長さ、検索文字列内の不一致が起こった位置からスライド量を計算できベースに改良したアルゴリズムもあるよる。

うだ。たとえば、繰り返しパターンをもう少し詳細に分析しておいて、スライド量文字スライド表を増やすやり方がある。

文字abc

これ以外の文字量

13

26

検索はコンピュータの基本的な処理でもあり、これまでさまざまな研究が行わ3番まで一致（abが一致、Cが不一致）

不一致文字はa a b a a a b a b a b a b a

れてきた。しかし、インターネットやデス不一致

クトップ検索が最近になって脚光を浴びaabcab
パターンスライド
aabcab
表によるスライド

たように、これからもさまざまな分野に応用 されて いく技 術 で ある 。また 、コン

文字スライド
表によるスライドピュータの性能などが向上することで、

aabcab

パターンスライド表
番号012345文字

aabcab

量

66636

1

スライド量は3文字
スライド量は1文字（1-6+1+3=-1となるためスライド量は1となる）

過去には不可能だった方法が実現できたり、新しい方法が日々開発されたりしている。新しい技術が今後もさまざまな検索を可能にしていくことだろう。

図7

パターンスライド表を使うと、文字スライド表よりもさらに大きくスライドさせることが可能になる。

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

デジタルサーチャー講座
検索を科学する │ INTERNET magazine │ 2006 │ 01 │ 89
©1994-2007 ImpressR&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.