moshimore Knowledge

アプリ開発・紹介とメモ書き、日々の日記。

全文検索エンジンのサンプルを準備する

f:id:moshimore:20181127212033p:plain
実際に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の環境で2分くらいかかりました。

./wiser -x jawiki-latest-pages-articles.xml -m 1000 wikipedia_1000.db
[time] 2018/12/11 15:00:53.000001
count:1 title: Wikipedia:アップロードログ 20044月
count:2 title: Wikipedia:削除記録/過去ログ 200212月
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

以上、全文検索エンジンのサンプルを準備するでした。

*1:さくらのVPSでCentOSを使用しました。

*2:ソースコードのダウンロード先は書籍に記載されています。