PR

 こうしろうは,4月21日の基本情報技術者試験に向けた勉強を分厚い参考書と問題集で続けている。数値表現の章を終え,現在はアルゴリズムについて学んでいる。その勉強の様子を見て思った。「こいつ,本を読むスピードが遅い!」

 私は,割と本を読むのが速い方である。というか,仕事に関係する本はサッーと流して読んで,どこに何が書いてあるかだけを覚えておいて,理解できなかったことは,後から読み返すようにしている。読書としては,面白くもなんともない方法であるが,同時に数冊の本を読むのには便利である。この読み方が癖になってしまって最近,気に入っている重松 清さんの短編集などをコンピュータ関係の本を読むのと同じ方法で読んでしまって,『ビタミンF』やら『リビング』,『日曜日の夕刊』などのストーリーがごっちゃになって困っている。

 こうしろうは遅い。1ページを舐めるように読んでいて,1時間近い時間を掛けることもある。4月21日までに読み終えなくてはならない量を考えると「サッーと流して読め」と言いたくなるのであるが,これがこの人のスタイルなんだと,喉元まで上がってくる言葉を飲み込んでいる。基本情報技術者『標準教科書』のアルゴリズムの章は10数ページあり,もう1週間近い日数をかけ読んでいる。

 さて,アルゴリズムとは何か。

 データがある。別にデジタルで表現されたコンピュータ向けのデータでなくても構わないのであるが,あるデータの固まりがあって,何らかの処理をしなくてはならない時に,これをどうやったら正確かつ効率的に処理できるかを考え,考え出された手法をアルゴリズムという。

 例として文字列処理のアルゴリズムを紹介しよう。「こんにちはのなかりかちゃん。わたしはほのぼのとしたほのかです。」という文書がデータファイルとして保存されているとする。他にも内容の違う文書がたくさん保存されている。それらの中から「ほのか」という文字列が含まれている文書を探さなくてはいけない。どうやって被探索文字列(こんにちはのなかりかちゃん…)のなかに探索文字列(ほのか)が含まれているかを正確かつ効率的に調べるにはアルゴリズムが必要になる。

単純探索法
 法と名前を付ける必要があるんかいと言いたくなるほど単純な方法である。「こんにちはのなかりかちゃん。わたしはほのぼのとしたほのかです。」に「ほのか」が含まれているから,先頭から一文字ずつ比較していく方法である。



まず探索文字列(ほのか)の1文字目(ほ)に一致するかを調べ,一致しなければ1文字ずつシフトしていく。一致した場合は2文字目,3文字目が一致するか調べていく。これじゃ,非効率だろうとボイヤーさんとムーアさんが考えたのが次の方法である。

ボイヤー・ムーア法
 ボイヤー,シピンだと昔の大洋ホエールズ(現横浜ベイ・スターズ)である。古すぎて知ってる人は少ないかもしれないが,あの頃のホエールズには中塚さんとか個性的な選手が多くおもしろいチームだった。ボイヤー・ムーア法の特徴は探索文字列の最後の文字から比較するという点である。この例では「ほのか」の「か」から調べていくのである。



まず「か」と被探索文字列中の3番目の文字「に」を比べる(1)。違うので次は「に」と「か」の1文字前の「の」,次にその前の「ほ」と比べる。どれも一致しないので3文字シフトする(2)。次に「か」と6番目の文字「の」を比べる。違うので1文字前の「の」と比較する。一致するので3文字とも一致するかもしれないと期待を込めて,今度は1文字だけシフトする(3)。「か」と「な」を調べて一致しないので「な」と「の」と「ほ」を調べていく。一致しないので,3文字シフトする(4)。今度は「か」と「か」が一致する。次にその1文字前の「の」と「り」を調べる。一致しない。ここで,ボイヤー・ムーア法がその力を発揮する。3文字目が一致していて,2文字目が一致しなければ,この3文字と一致する可能性はないので,バカーンと3文字シフトできるのである(5)。きりがないので途中省略するが,この例では10回目のシフトで「ほのか」と出会う。

 久しぶりにボイヤー・ムーア法を勉強しなおしてみて,『美しいなあ』と感じた。効率が良くスキがないアルゴリズムは素敵なのである。