Googleはなぜ的確に探せるのか？ ― 第3回

悟空、キーワードを電光石火で切り出す

2008年12月15日 17時25分更新

文● 清田陽司／東京大学情報基盤センター図書館電子化研究部門助教

キーワードをすばやく探し出す方法その1　～二分探索法～

　大量のキーワードの列から目当てのキーワードを探し出すのに、私たちは無意識のうちにすばやく探せる方法を使っています。国語辞典をひくときです。


国語辞典では、言葉の読みの位置から範囲を絞っていくことですばやくキーワードを探し出しています（写真は角川書店の「角川国語辞典」）

　たとえば、「パソコン」という言葉を国語辞典でひいてみましょう。まずは見出しを使って「は」のページを開くことでしょう。読みが「は」（または「ば」「ぱ」）で始まる言葉が五十音順で山ほど並んでいます。そんなとき、私たちは「は」のページ束の真ん中あたりのページを開いて、そのページに現れる言葉の読みを調べます。もしそれが「はし」で始まる言葉（たとえば「はしか」）であれば、「『パソコン』の『はそ』はここより後ろのページだな」と判断して、もう少し後ろのページをめくるでしょう。そのページの言葉の読みが「はち」（例えば「蜂蜜」）であれば、「ちょっと行きすぎたな」と判断して、「はし」と「はち」の中間あたりのページを開くでしょう。このようにして、調べたい言葉「パソコン」といま開いているページに載っている言葉の読みを比べながら、「パソコン」が載っているページの範囲を絞り込んでいきます。この方法で、1ページずつめくっていくよりもずっと早く「パソコン」を探し出せます。

　パソコンがメモリー上のキーワード列から目当てのキーワードを探し出す際にも、全く同じやり方が使えます。ただし条件が2つあります。「キーワード列が辞書順に並んでいること」と、「キーワード列の末尾の番号（つまりキーワードの数-1）があらかじめ分かっていること」です。

　下の図を見てください。32個のキーワード列が辞書順（ABC順）に並んでメモリーに格納されています（ここでは説明を簡単にするために表を使っていますが、実際にはメモリーに格納されていることを忘れないでください）。また、キーワード列の末尾の番号も「31番」と分かっています。

　人間が国語辞典を引く方法をパソコンで模倣する手順は以下のように書けるでしょう（この手順のことを「アルゴリズムY」と呼ぶことにしましょう）。

探したいキーワードをメモリーの別のエリアに格納しておきます。
キーワード列の探索範囲（先頭の番号～末尾の番号）を覚えておきます。最初は0番～31番です。
探索範囲の中央にあたるキーワードを調べます。中央の番号は、探索範囲の先頭の番号と末尾の番号から計算できます。
探索範囲中央の番号＝（末尾の番号+先頭の番号）÷2（小数点未満は切り捨て）
探索範囲中央のキーワードと、探したいキーワードを比較します。

探したいキーワードが探索範囲中央のキーワードよりもアルファベット順で前にあたる場合：

探索範囲の末尾の番号を以下の計算式で更新します。
新しい末尾の番号＝現在の探索範囲中央の番号－1

探したいキーワードが探索範囲中央のキーワードよりもアルファベット順で後ろにあたる場合：

探索範囲の先頭の番号を以下の計算式で更新します。
新しい先頭の番号＝現在の探索範囲中央の番号＋1

探したいキーワードが探索範囲中央のキーワードと一致する場合：

ビンゴ！現在の探索範囲中央の番号が、探していたキーワードの番号です。ここでアルゴリズムを終了します。

先頭の番号が末尾の番号よりも大きくなってしまった場合

探したいキーワードはキーワード列の中に存在しないものと判断し、アルゴリズムを終了します。たとえば先頭の番号が5番、末尾の番号が4番になっている場合は、探索範囲自体が存在しないことになります。
3に戻ります。

　探したいキーワードが「ITALY」であるとき、アルゴリズムYを前の図に適用した様子を図に示します。探索範囲が徐々に絞り込まれていく様子が分かります。

　実は「アルゴリズムY」は、あらかじめ並べられたデータの配列を高速に検索できる有名なアルゴリズムで、探索範囲を二つずつに分割して絞り込んでいく様子から、「アルゴリズムY」のことを「二分探索法」と呼んでいます。

　「こんな方法ですばやくキーワードを探し出せるの？　たとえばキーワード列の長さが100万個あったらけっこう長い時間がかかりそうに思うけど？」―――それでは、100個のキーワード列に二分探索法を適用したとき、探索範囲の大きさがどう変化していくかをシミュレートしてみましょう。下の図にその結果を示します。

　探索範囲の大きさが半分ずつになっていくので、最悪の場合でも19巡目で探索が終了してしまいます（ほとんどの場合はこれより早く終わるはずです）。たとえ1兆個（！）のキーワード列でもせいぜい38巡目で終わってしまいます。現代のパソコンであれば一瞬です。

　二分探索法の基本的な考え方は、「大きな問題（探索範囲の中から探したいキーワードを見つける）をより小さな問題（探索範囲を半分に絞り込んだ中から探したいキーワードに見つける）に分割する操作を繰り返すことで、大きな問題を解く」というものです。この考え方を「分割統治法」と呼びます。分割統治法をうまく使うと、とても複雑な処理がいとも簡単にできてしまったりします。ぜひ覚えておいてください。

「そういえば、キーワード列を並びかえるのはいったいどうやるんだっけ？」―――そう、二分探索法の前提は「キーワード列が辞書順に並んでいること」でしたね。実は、「データを並びかえる」ためのアルゴリズムが世の中にはたくさん存在します。「バブルソート法」「クイックソート法」「ヒープソート法」などです。この連載では説明しませんが、もし興味があればぜひ調べてみてください。アルゴリズムの世界の面白さと奥深さがわかりますよ。

　さて、二分探索法には重大な欠点があります。キーワード列の更新が頻繁に起こるときに使いづらいのです。たとえば、先ほどの図のキーワード列に「JAPAN」を追加しようとすると、どういうことが起きるでしょうか。「JORDAN」よりも後ろのキーワードをすべて1つずつ後ろにずらす必要が生じます。