プログラマなら読むべき「世界でもっとも強力な９のアルゴリズム」

世界でもっとも強力な9のアルゴリズム

これは実にわかりやすくて興味深いアルゴリズムを紹介する本だ。僕が駆け出しプログラマだった頃アルゴリズムを知ることは大事なことだと僕に言って聞かせた。

とはいえ僕はわかりづらい本ばかりを読んでいたのでその苦行には全然耐えられなかった記憶がある。30代にもなってさすがにアルゴリズムってなんぞやとは言えないし、もうちょっと勉強しなおしたいと思っていたところでこの本を見つけた。

とてもおもしろくて特別な知識がなくてもわかるように書かれてある。それこそが本書の売りであるわけだ。

イントラダクションから結論を書いているのが良い。

そもそも、アルゴリズムとはいったい何なのか。もっとも簡単な答えを言えば、アルゴリズムとは、問題を解決するために必要な手順を正確に規定したレシピである。 

 いいねズバリその通り。

個々のステップは、絶対的に正確でなければならず、人間の直観や推測を必要としてはならない。

 これも的確な文章だ。

第2章にはwebと検索についてのアルゴリズムを持ってきている。このテーマは読者の気を引くのに十分なキャッチーさがある。

検索には、マッチングとランキングの2段階がある。第1（マッチング）段階終了後は、マッチした数千から数百万ものページが残される。第2（ランキング）段階では、これらが関連性の高さ順にソートされる。

じつにわかりやすいweb検索の偉大なアルゴリズムは2つの段階に絞られている。

　ウェブ検索エンジンのインデックスは、本の索引と同じような仕組みになっている。本の「ページ」は、ワールドワイドウェブではウェブページに置き換わり、検索エンジンはウェブ上のすべてのウェブページに別々のページ番号を割り当てる（確かにページはたくさんある。最新の数字では数十億と言われる。しかし、コンピュータは、大きな数を扱うのがとても得意だ）。 

例えば僕のブログは1ページ目、はてブのTOPページは2ページ目というような感じでインデックスを割り合てている。

　ウェブ検索エンジンのインデックスは、本の索引と同じような仕組みになっている。本の「ページ」は、ワールドワイドウェブではウェブページに置き換わり、検索エンジンはウェブ上のすべてのウェブページに別々のページ番号を割り当てる（確かにページはたくさんある。最新の数字では数十億と言われる。しかし、コンピュータは、大きな数を扱うのがとても得意だ）。

コンピュータは、まずあらゆるページに含まれるすべての単語をまとめたリストを作り、次にそのリストをアルファベット順に並べ替えてインデックスを構築する。その結果を「ワードリスト」と呼ぶことにしよう。この場合は、「a、cat、dog、mat、on、sat、stood、the、while」である。その次に、コンピュータはページをざっと見て単語を1つずつ探していく。

(省略)

検索エンジンは、数百億ものウェブページから正しい結果を返さなければならないことを忘れてはならない。

この問題に対する答えこそ、現代の検索エンジンを実現させた最初の本当にすばらしいアイデアである。それは、インデックスにただページ「番号」を保存するだけではなく、ページ内の「位置」も保存するというアイデアだ。ここでいう位置は、特に難しいものではない。単にページのなかで単語がどこにあるかを示していればよい。)

---- (省略) ----

インデックスに単語のページ内の位置情報を組み込むと、大量のウェブページを読み込まなくても、インデックスの数行を見るだけでフレーズ検索のヒットを見つけることができる。この単純な位置情報トリックこそ、現代の検索エンジンを動かすための鍵の1つなのである。

 このように、簡単な説明と問題点を指摘し、さらにその問題を解決するアルゴリズムを結論から説明していくという風に本書は進む。

僕が興味深く読んだのは第5章の誤り訂正符号。これは自動的にデータの誤りを見つけて訂正する方法。

第6章パターン認識。これは今ほっとな画像解析などに必要なアルゴリズム。

第7章データ圧縮。言わずと知れたzip圧縮などの理論だ。

この3つの章はわかりやすいし「なるほどなあ」と手を打つ理論で、難しいことはないのだ。

第8章のデータベースはプログラマに馴染みが深いものだが、素人だととっつきにくいかもしれない。第9章のデジタル署名と第10章の決定不可能性はぶっちゃけ読みにくい。さらっと読んだ感じだと何言っているのかわからない。だからこそ最後の方に持ってきたのかもしれない。

だがいずれにせよアルゴリズムを面白く理解できるという点について異論はない。

アルゴリズムって意味不明なんだよなぁと思っているプログラマは読んで見るべき一冊だ。