Hatena::ブログ(Diary)

Imagine with 加藤和彦 このページをアンテナに追加 RSSフィード Twitter

2009-12-02(Wed)

簡単なWebサーチエンジンの作り方

筑波大学は3学期制で,12月1日から3学期が始まりました.3学期には私が担当している学類生(普通の大学の学部生)3年生向けの実験があります.約3ヶ月を掛けて,ほどほどの規模のプログラム作成を行います.私が作り,担当しているプログラム実験は「Webサーチエンジン」といいまして,テキストはこちらに公開しています.

この実験,結構,自信作なんです.Javaの基本的なプログラミングができることだけを仮定して,漏れのない全文検索を行うWebサーエンジンを作ります.Webデータ収集を自動的に行うクローラー付き.Googleのようなページランキング機能はありませんが,一応,サーチエンジンの基本機能を備えます.自慢は,このテキストが実質A4で印刷して2ページくらいであること.数学の小問を解いていくように,順番に小問を解いていくと,最後にはWebサーチエンジンができます.

ミソはサフィックス・アレイ(suffix array)というデータ構造を使っているところ.ディスク上に効率的に大規模suffix arrayを作るのは大変なのですが,メモリ中の文字列に対してならば,初心者でも簡単に作れます.

実験テキストではJavaで書くことを指定していますが,Java特有の機能は使用していません.Ruby, Python, Perl等のハイレベル言語を使えば,より簡潔,高速に書けます.

基本的なプログラミングができるようになって,中級レベルにチャレンジしたい方のよい練習問題ではと思います.