文書検索の種明かし
ここまで読んできて、パソコンの中に入っている文書がどんなものかイメージできたでしょうか？ 「うーん、個々の説明は何となくわかるんだけど、いまいちイメージできないなぁ」―――それでは、別のたとえ話で説明してみましょう。
昔の子供向けSF番組で、こんなシーンがありました。隊員が集まっている司令室内で、コンピューターが突然動き始めて、そこから長い紙テープが吐き出されてきます。その紙テープにはたくさんの穴が空けられています。隊員のひとりがその紙テープを手に取って端から順に手繰り寄せながら、穴の模様に目を通していきます。実は、その紙テープには地球の本部からの指令文が書かれていて、この隊員は穴の模様を目で見てそこに書かれた文字列を読み取れる特殊能力を持っていたのでした。隊員は、「○○●●○●○●」という穴の組み合わせは「ア」という文字を表すといった共通の約束事を知っていたのです。
パソコンの中の文書も、隊員が手に取った紙テープと全く同じように理解できます。紙テープには、「穴が空いている」「穴が空いていない」の2つの状態があって、その組み合わせによって情報を表現しています。パソコンのメモリーにも「スイッチがON」「スイッチがOFF」の2つの状態があって、スイッチの組み合わせによって情報(数値)を表していることはすでに説明しました。穴の組み合わせがどの文字を表すかという約束事が存在するのと同じように、パソコンのメモリー内の1バイトのスイッチの組み合わせと文字の対応についての約束事も存在しています。
また、紙テープの上に表現された指令文はテープを端から手繰っていくことで順番に読んでいけるように、パソコンのメモリーの中に入っている文書も、メモリーの先頭から順に（例えば100階から始めて101階、102階、……という感じで）バイトの列を取り出していくことで読むことができます。
それでは、この隊員さんにお願いして、指令文の中に含まれている「スパゲティ」というキーワードを探してもらいましょう。彼はどのようにして探してくれるでしょうか？ あ、いつもと同じように紙テープの端を手にとって、順に手繰り寄せて目を通してますよ。紙テープを50メートルほど手繰ったところで、「発見しました。『スパゲティを無重力空間で食べる方法を発明した』と書いてあります」と教えてくれました。
「どうやって探したんですか」と彼に尋ねてみましょう。彼はこんな風に説明してくれました。
- 紙テープの先頭を手にとって、そこに視線を合わせます。
- 『ス』という文字を、テープを手繰りながらひたすら探していきます。
- もし『ス』という文字を発見したら、『ス』の次の文字が何であるかを確かめます。
- 『パ』以外の文字ならば、視線をそこに合わせたまま2に戻ります(『ス』を探す作業を再開します)。
- 『パ』ならば、『パ』の次の文字が何であるかを確かめます。
- 『ゲ』以外の文字ならば、視線をそこに合わせたまま2に戻ります。
- 『ゲ』ならば、『ゲ』の次の文字が何であるかを確かめます。
- 『テ』以外の文字ならば、視線をそこに合わせたまま2に戻ります。
- 『テ』ならば、『テ』の次の文字が何であるかを確かめます。
- 『ィ』以外の文字ならば、視線をそこに合わせたまま2に戻ります。
- 『ィ』ならば、『発見しました』と言います。
- 紙テープの末端まで手繰り終わったら、『発見できませんでした』と言います。
とっても簡単なやり方ですよね。
パソコンの中の文書検索も、まったく同じ方法で実現できます。メモリービルの10001階～20000階に私の日記が収納されているならば、10001階から順番に1バイトずつ取り出して、「ス」「パ」「ゲ」「テ」「ィ」という文字が並んでいるところを見つけるまでこの方法を繰り返せばいいわけです。もし20000階まで探しても見つからなければ、その文書の中に「スパゲティ」という単語は存在しないことになります。ちなみに、紙テープを手繰るかのようなこの探し方のことを、線形探索（リニアサーチ）と呼んでいます。
「その線形探索っていうやり方はすごく時間がかかったりしない？ たとえば10年分書いた日記を探すときとか」―――それでは、パソコンで書いた日記を線形探索するときにかかる時間を見積もってみましょう。日記を1日180文字書いたとすると、10年間では180×365×10=66万文字となります。1文字3バイトとすれば、66万×3=約200万バイトです。一方、現代のパソコンは1秒間に10億バイト以上のデータを探索できる性能がありますので、2ミリ秒 （1000分の2秒）で日記全文を探し終える計算になります。
パソコンの文書を探す性能がどれだけすごいものなのかを、紙テープに置き換えてイメージしてみましょう。仮に、1バイトの情報を記録するのに5ミリメートルの長さを使うとすると、10年分の日記を表現するには約10キロメートルの紙テープが必要になります。現代のパソコンは、10キロメートルの紙テープをたったの2ミリ秒、秒速5000キロメートル（8秒で地球一周する速さ）で探し終えてしまう性能をもっているのです！ 驚きではありませんか？
変更履歴：記事掲載当初、「現代のパソコンは～中略～（8秒で地球一周する速さ）」の数値に誤りがありましたので修正しました(2008年11月17日）。
