実際にWikipediaのXMLダンプデータを検索する全文検索エンジンを構築していきます。
grepとの実行速度の比較は見物です。
前回のエントリーの続きになります。
内容が通じない場合があるので、先にこちらをご覧ください。
knowledge.moshimore.jp
全文検索エンジンwiserの概要
wiserの構成
作成する全文検索エンジンは、WikipediaのXMLダンプデータを対象にしたシステムになります。
以下のエントリーで説明した内容にWikipediaのXMLダンプデータを解釈する「XML解釈器」を追加しています。
knowledge.moshimore.jp
検索用の文書を用意する
WikipediaのXMLダンプデータは以下からダウンロードできます。
https://dumps.wikimedia.org/jawiki/
2018/12/11時点では、2.59GBのダウンロード容量がありました。
https://dumps.wikimedia.org/jawiki/latest/jawiki-latest-pages-articles.xml.bz2
wiserをセットアップする
wiserをビルドする
環境*1にも依りますが、以下のコマンドで、ビルド環境とライブラリをインストールしました。
yum install gcc sqlite sqlite-devel expat-devel bzip2
ダウンロードしておいたwiserのソースコード*2をmakeして実行ファイルを作成します。
make gcc -Wall -std=c99 -D_GNU_SOURCE -D_FILE_OFFSET_BITS=64 -O3 -g -I ./include -c wiser.c gcc -Wall -std=c99 -D_GNU_SOURCE -D_FILE_OFFSET_BITS=64 -O3 -g -I ./include -c token.c gcc -Wall -std=c99 -D_GNU_SOURCE -D_FILE_OFFSET_BITS=64 -O3 -g -I ./include -c search.c gcc -Wall -std=c99 -D_GNU_SOURCE -D_FILE_OFFSET_BITS=64 -O3 -g -I ./include -c postings.c gcc -Wall -std=c99 -D_GNU_SOURCE -D_FILE_OFFSET_BITS=64 -O3 -g -I ./include -c database.c gcc -Wall -std=c99 -D_GNU_SOURCE -D_FILE_OFFSET_BITS=64 -O3 -g -I ./include -o wiser wiser.o util.o token.o search.o postings.o database.o wikiload.o -l sqlite3 -l expat -l m
wiserを起動する
wiserを起動させると次のようなオプションが表示されます。
./wiser usage: ./wiser [options] db_file options: -c compress_method : compress method for postings list -x wikipedia_dump_xml : wikipedia dump xml path for indexing -q search_query : query for search -m max_index_count : max count for indexing document -t ii_buffer_update_threshold : inverted index buffer merge threshold -s : don't use tokens' positions for search
| オプション | 概要 |
|---|---|
| -c | 作成する転置インデックスの圧縮方法を指定します。 |
| -x | 取り込むWikipediaのダンプデータのパスを指定します。 |
| -q | 検索する場合の検索クエリ文字列を指定します。 |
| -m | ダンプデータから取り込む文書の最大数を指定します。 |
| -t | 転置インデックスを更新する際に用いるバッファサイズを指定します。 |
| -s | 検索時にトークンの位置情報を使わない検索を行います。すなわち、フレーズ検索を行いません。 |
Wikipediaデータを展開する
WikipediaのXMLダンプデータを解凍しておきます。
bunzip2 -k jawiki-latest-pages-articles.xml.bz2
wiserを動かす
転置インデックスを構築する
まずは、Wikipediaの1000件のデータで転置インデックスを構築してみました。
さくらのVPSで、CPU：2Core、メモリー：1G、SSD：30GBの環境で２分くらいかかりました。
./wiser -x jawiki-latest-pages-articles.xml -m 1000 wikipedia_1000.db [time] 2018/12/11 15:00:53.000001 count:1 title: Wikipedia:アップロードログ 2004年4月 count:2 title: Wikipedia:削除記録/過去ログ 2002年12月 count:3 title: アンパサンド count:4 title: Wikipedia:Sandbox count:5 title: 言語 （省略） count:998 title: 真鍋譲治 count:999 title: 真船一雄 count:1000 title: 望月峯太郎 [time] 2018/12/11 15:02:49.000000 (diff 115.878433) index flushed. [time] 2018/12/11 15:03:04.000005 (diff 15.509161) [time] 2018/12/11 15:03:06.000007 (diff 2.219826)
転置インデックスを用いて検索する
試しに「perl」を検索してみると、0.01秒で検索が行われ、即結果が表示されました。
./wiser -q 'perl' wikipedia_1000.db [time] 2018/12/11 15:07:17.000008 document_id: 731 title: Perl score: 450.554878 document_id: 879 title: バイオインフォマティクス score: 17.250695 Total 2 documents are found! [time] 2018/12/11 15:07:17.000008 (diff 0.015963)
10000件のデータでは、0.29秒で検索されました。
./wiser -q 'perl' wikipedia_10000.db [time] 2018/12/11 15:10:47.000005 document_id: 731 title: Perl score: 520.239913 document_id: 2666 title: アラン・チューリング score: 285.803711 document_id: 7574 title: 動物 score: 280.479821 document_id: 6924 title: 自然 score: 239.383272 document_id: 2560 title: バッファオーバーラン score: 223.366613 （省略） document_id: 5465 title: 書誌 score: 7.979265 document_id: 1673 title: カセットビジョン score: 7.435083 document_id: 5897 title: 自転 score: 3.097163 Total 39 documents are found! [time] 2018/12/11 15:10:47.000008 (diff 0.294207)
grepとwiserの実行速度を比較する
条件をそろえるために1000件のXMLファイルを作成します。
grep -m 1000 -n '</page>' jawiki-latest-pages-articles.xml | tail -n 1 | cut -d ":" -f 1 | xargs -I LINE head -n LINE jawiki-latest-pages-articles.xml > 1000.xml
10倍には届きませんでしたが、grepとwiserで、ずいぶんと差が出ることが分かりました。
もっと条件の良い環境だと、どんな結果になるのか気になるものです。
time grep 'parl' 1000.xml real 0m0.113s user 0m0.008s sys 0m0.032s
time ./wiser -q 'parl' wikipedia_1000.db real 0m0.016s user 0m0.006s sys 0m0.007s
書籍の内容は、以下のエントリーで紹介しています。
knowledge.moshimore.jp
以上、全文検索エンジンのサンプルを準備するでした。