実験課題「Webサーチエンジン」


担当教員
加藤 和彦 (Email: kato (atmark) cs.tsukuba.ac.jp)

TA(2018年度)
大羽史将(Email: ooba (at mark) osss.cs.tsukuba.ac.jp )

実験目的
Java言語を用いて比較的に大きなプログラムの作成を行う.suffix arrayと呼ばれるデータ構造を用いた全文検索用インデックスを作り,それを用いて,Webファイルに対する全文検索エンジンを作成する.また,発展課題として,Java以外のプログラミング言語での実現,あるいは,より進んだ検索機能の実現を行う.

関連科目
プログラミング入門,ソフトウェア構成論,システムプログラム,分散システム

課題
以下に述べられている実験課題は,課題を順に解答していくことにより,上記目的が自然に達成されるように構成されている.

課題1:Suffix Arrayを用いた検索エンジン
変数Tを長さnのテキスト(文字列)とする.テキストTの,a文字目からb文字目の部分文字列をT[a, b]と書く.テキストT全体はT[1, n]と書く.テキストTの最初のm文字を接頭辞(prefix),最後のm文字を接尾辞(suffix)と呼ぶ.テキストTのsuffixはs1=T[1, n], s2=T[2, n], ..., sn=T[n, n]のn個である.テキストTのn個のsuffixを辞書順に並べたとき,そのsuffixが元々何番目のsuffixだったかの番号(前述のsの番号)を配列にしたものをsuffix arrayと呼ぶ.

(例)T=”abcbccab”としたとき,Tのsuffixは
s1="abcbccab" 
s2= "bcbccab" 
s3=  "cbccab" 
s4=   "bccab" 
s5=    "ccab" 
s6=     "cab" 
s7=      "ab" 
s8=       "b"

s1, s2, ..., s8を辞書順にソートすると

s7="ab" 
s1="abcbccab" 
s8="b" 
s2="bcbccab" 
s4="bccab" 
s6="cab" 
s3="cbccab" 
s5="ccab"

sの添字をとることにより,Tのsuffix arrayは

[7, 1, 8, 2, 4, 6, 3, 5]

となる.

課題1-1
与えられた文字列のsuffix arrayを作成するプログラムを作成せよ.

課題1-2
与えられた文字列に対し,その部分文字列を入力し,部分文字列が 出現する全位置を列挙する検索プログラムを作成せよ.(ヒント: suffix array上の2分探索を行う)

課題1-3
指定された1個のHTMLテキストファイルをメモリ中に読み込んで1個の文字列とし,それに対する suffix arrayをメモリ中に作成し,ユーザから入力された文字列を検索して,入力文字列が出現する全位置を列挙するプログラムを作成せよ.

課題1-4
以下の手順で,複数ファイルに対して全文検索を行うプログラムを作成せよ.

(a) 指定された1個以上のm個のファイルをメモリ内で連結した長い文字列を作る.そのときにファイルの境界に,テキストファイル中には通常は現れない文字(例えばヌル文字 ’\0’ 等)を入れ,検索時に複数ファイルをまたいだ文字列にマッチしないようにしておく.

(b) (a)で作った長い文字列中の文字位置から元のファイル名を得られるようにするための表を作る.例えば,file1.html, file2.html, file3.htmlがそれぞれ100, 200, 300のファイルサイズをもつとき,[(“file1.html”, 100), (“file2.html”, 200), (“file3.html”, 300)]というような表を作る(効率的な方法,プログラムしやすい方法を各自工夫せよ).

課題1-3で作成したプログラムと,(a)および(b)で作ったプログラムを用いて,ユーザから入力された文字列を検索し,入力文字列が出現するファイル名とファイル内の位置(ファイルの先頭から数えた文字数)を全て列挙するプログラムを作成せよ.

課題2:Webサーチロボット(クローラ)を用いた検索システム

課題2-1(閉包概念の理解)あるファイルを起点として,そのファイルから参照することが可能なファイルの集合を,起点に指定したファイルの閉包(transitive closure)と呼ぶ.このとき,起点ファイルから直接的に参照するファイルだけでなく,参照するファイルが参照するファイル,その先の参照ファイル...というように,可能な参照をすべて辿る.(ただし,このドメイン外のサイトへ辿る必要はない)
http://www.osss.cs.tsukuba.ac.jp/kato/codeconv/CodeConvTOC.doc.html
をアクセスして,このURLを起点する閉包を求め,図示せよ.その際,参照する側のURLから参照される側のURLへ矢印を描くこと.

課題2-2(HTMLファイルの解析)指定されたURLに対し,そのファイル中からのファイル参照をすべて取りだして出力するプログラムを作成せよ.
ファイル参照とは,例えば<a href="file.html">の場合,”file.html”である。作成したプログラムを利用して,課題2-1中のURLをアクセスしたときの出力結果を求めよ.

URLで指定されたファイルをアクセスするのに,次のプログラムを参考としてよい:
http://www.osss.cs.tsukuba.ac.jp/kato/Page.java

( 余力のある人への課題:HTMLファイル内のコメントを読み飛ばす機能)

課題3(サーチエンジン)
課題1および2で作成したプログラムを組み合わせて,指定されたURLの閉包のHTMLファイル群の内容に対するsuffix arrayをメモリ中に作り,入力した文字列の検索を行い,入力文字列を含むURLを出力するプログラムを作成せよ.

課題4(発展課題)
次のいずれかを選択せよ。

(a) 課題3までのプログラミング実装を,Java言語以外のプログラミング言語を用いて行うこと。(例えば,C, C++, C#, Ruby, Python, Perl, Scala, Kotlin, Scheme等)ただし、課題3までの実装をJava 8の機能(ラムダ式,stream等)を使用しないで行った場合は,Java 8の機能を使用した実装をこの課題としてよい。

(b) and検索, or 検索,およびnot 検索の機能を追加せよ。また,検索単語の出現回数が多い順に出力結果をソートせよ。

(c) PageRankアルゴリズムを実装せよ。

レポート作成上の注意
こちら

© Kato