はじめに
「検索エンジン自作入門」という書籍を買ったので、読み進めながら実践してみよう、という記事です。
個人の学習目的の記事ですので、ほぼ備忘録のような内容になっています。
そもそもは情報設計の学習のために「情報アーキテクチャ第4版」を読んだことが発端です。
情報を溜める仕組みがどのようにインデクシングを実施しているのかに興味を持ち、この際検索エンジンを作ってみるか、という発想に至りました。
とは言え正直、情報設計を理解する上で検索エンジンを作る必要はなかったですね。
まぁやっていく気持ちがあるし、折角なのでやってみましょう。
全文検索エンジンとは？
概要
ものすごくザックリ言うと、文書を検索する仕組みのことです。
おなじみGoogleをはじめとするWeb検索エンジンがその代表ですかね。
単に検索エンジンと言うと広義と狭義に分かれるようですが、今回は広義で用いられている全文検索エンジンが対象となります。
詳しいことは、ググるかWikipediaを参考に。
Wikipedia - 検索エンジン
全文検索エンジンの構成
※ 注：山田浩之、末永匡（著）「検索エンジン自作入門」（2014/9/25） p.14の図1-1を元に作成
上記の点線で示した部分が、いわゆる全文検索エンジンの主要な機能とのこと。
ほーん（ ＾ω＾）
まぁ、コンポーネントの名前から大体の察しはつきますね。
詳しく見ていくと、以下のような流れで動作する模様。
- インデックス構築機が文書からインデックスを作成
- 作成されたインデックスをインデックス管理機に格納
- 文書は文書管理機に格納
- インデックス検索機が検索アプリから検索クエリを受け付ける
- インデックス管理機から検索クエリにマッチするインデックスを取得する
- 取得したインデックスの情報から、文書管理機のデータを探し出す
- 検索アプリに返却
なるほどなるほど。
ここまで見た中で、気になるのは以下の2点。
- インデックスはどのような構造をしているのか？
- どうやってインデックスを作成しているのか？
もう少し詳細に追っていきます。
インデックスの構造
| keyword | page |
|---|---|
| qiita | P1,P2 |
| article | P1 |
上記のリストのようなものが、インデックスの構造だそうです。
ほーん（ ＾ω＾）
インデックスにも様々な種類があるようですが、ここで示したのは転置インデックスという種類のインデックスとのこと。
全文検索エンジンに使われるインデックスの仕組みの中では代表的な立ち位置みたいですね。
「このキーワードは○○ページ目にあるよ」と示しているだけなので、理解してしまえば単純です。
インデックスの作成方法
じゃあ転置インデックスをどうやって作っているのか、という話ですが、これも内訳を知ると非常にシンプルでした。
- 「どのページでどの単語が使われているのか」を洗い出し、リストを作る（ページ：行、単語：列）
- 行列を入れ替え、「どの単語がどのページで使われているのか」のリストを作る（単語：行、ページ：列）
- ページの列をまとめ、簡略化
要するに、
| qiita | article | |
|---|---|---|
| P1 | 1 | 1 |
| P2 | 1 | 0 |
↑これが
| keyword | page |
|---|---|
| qiita | P1,P2 |
| article | P1 |
↑こうなる、ということだそうです。
細かいことはさておき、ベースは理解。
参考書籍に全文検索エンジンのサンプルが用意されていたので、とりあえず動かしてみます。
セットアップ
環境構築
参考書籍で用いられている言語がC言語なので、一旦はC言語を動かす環境を作ります。
Cはまともに触ってきていませんが、何とかなるでしょう。
1. gccのインストール
gccは、Cのコンパイラです。
Macの場合はXcodeのCommand Line Toolsをインストールすれば一緒に入ってくるそうです。
既に入れていたので割愛。
2. Hello World
何はともあれ「Hello World」はやっておきましょう。
以下のファイルを作成。
#include <stdio.h>
int main(void){
printf("Hello World\n");
return 0;
}
で、gccでコンパイル。
$ gcc ./hello.c
$ ls
a.out hello.c
無事にコンパイルできました。
とりあえず動かしてみます。
$ ./a.out
Hello World
やりましたね。
これでもう、どうにかなる気がします。
全文検索エンジンのサンプルの用意
wiserというパッケージを利用します。
GitHubにも上がってました。
それをそのまま利用。
依存パッケージのインストール
$ brew install sqlite expat
expatはCのXML Parserみたいです。
データの用意
日本語版Wikipediaのデータを利用します。
↓から最新のXMLを落としましょう。
https://dumps.wikimedia.org/jawiki/
そして解凍。
bunzip2 -k jawiki-latest-pages-articles.xml.bz2
この解凍にくっそ時間かかりました。
ご注意を。
動作確認
$ ./wiser
usage: ./wiser [options] db_file
...
お、動きました。
まずはインデックスを作成してみます。
$ ./wiser -x jawiki-latest-pages-articles.xml -m 1000 wikipedia_1000.db
[time] 2019/01/10 01:39:41.000004
count:1 title: Wikipedia:アップロードログ 2004年4月
count:2 title: Wikipedia:削除記録/過去ログ 2002年12月
count:3 title: アンパサンド
count:4 title: Wikipedia:Sandbox
count:5 title: 言語
count:6 title: 日本語
count:7 title: 地理学
・・・
へぇー（小並感）
次は実際に検索してみましょう。
参考書籍に指示された通り、perlという文字列を検索。
./wiser -q 'perl' wikipedia_1000.db
[time] 2019/01/10 01:45:04.000004
document_id: 731 title: Perl score: 448.038067
document_id: 879 title: バイオインフォマティクス score: 17.152566
Total 2 documents are found!
[time] 2019/01/10 01:45:04.000004 (diff 0.007252)
すごい…（小並感）
自分で作ったわけではないですが、結構テンション上がります。
今回は一旦ここまでで。
次回の予定
転置インデックスを構築する機能を作ってみたいと思います。
ただこの項を書いているあたりで、wiserがノーライセンスであることが発覚。
ソースコードをそのまま記事で利用できない問題…。
自作しないと公開できないので、まずは元のソースコードの読解ですかね。