全文検索エンジン lucene(ルシーン) を使ってみた

カテゴリ
ブックマーク数
このエントリーを含むはてなブックマーク はてなブックマーク - 全文検索エンジン lucene(ルシーン) を使ってみた
このエントリーをはてなブックマークに追加


こんにちは 。 検索 関連 を 担当 して いる やましー です 。


今回は livedoor で提供しているサービスの中の「検索関連」について書きます。

このブログでも過去に何度か取り上げられていますが、livedoor では検索エンジンとして HyperEstraier、lucene、mysql + senna、Namazu、SUFARY などを利用しています。

その中で lucene の利用方法や機能拡張について説明します。


lucene とは


Apache Lucene は、Java で書かれた高性能で高機能な検索エンジンライブラリです。全文検索を(特にクロスプラットフォームで)必要とするほとんどのアプリケーションに適している技術です。
※ 公式サイトから抜粋


インデックスの作成


lucene は転置インデックス型の検索エンジンなので、ドキュメントを検索するには、まずインデックスの作成をします。
ドキュメントをインデクシングする流れは次のような感じです。

ドキュメント
 ↓
Analyzer
 ↓
Token
 ↓
インデックスの生成

まず、ドキュメントを Analyzer(Tokenizer) に通してテキストを Token(単語) に分解します。

私はライブドアが大好きです。
 ↓
私   は   ライブドア   が   大好き   です   。

lucene が標準で用意している Analyzer は日本語を処理するのに向いていない為、livedoor ではいくつかの Analyzer を開発しました。

・BygramAnalyzer-3.0
Bi-gramの誤字ではありません。なぜかそういう名前です。
文字コードの種別によって Uni-gram・Bi-gram を切り替えて Tokenize します。

・MeCabAnalyzer-1.0
MeCab の Java バインディングを利用して分かち書きをします。

・HyperAnalyzer-4.0
MeCabAnalyzer と BygramAnalyzer の中間的な位置付けです。
MeCab によって分かち書きされた単語を、その文字コードの種別によって、Uni-gram・Bi-gram・単語のまま を切り替えて Tokenize します。

・RangedValueAnalyzer-1.0
RangeQuery を使う場合、予め数値を固定長文字列に変換して格納し、クエリ文字列も固定長文字列である必要がある仕様が煩わしいので、Analyzer を通ったときに固定長文字列化することで、ドキュメントの追加・検索共に数値のまま処理できるようにしました。
※ AnalyzingQueryParser を使うことで RangeQuery に渡されたクエリ文字列も Analyzer を通すことができます。


最後に、分解された Token を元に転置インデックスを生成します。


検索


ドキュメントを検索する流れは次のような感じです。

クエリ文字列
 ↓
QueryParser
 ↓
Analyzer(Tokenizer)
 ↓
Query
 ↓
ドキュメントを検索・スコア計算
 ↓
Sort
 ↓
Hits

まず、クエリ文字列を QueryParser を通して解析された結果 Query になります。

text:(ライブドア AND 大好き)

上記の例では、text:というフィールドに ライブドア と 大好き という単語が含まれるドキュメントを検索します。

lucene のクエリ文字列については Query Parser Syntax に詳しく書かれています。

下記の2つのドキュメントで、
DocID: ドキュメント内容
----------------------------------------
1: 私はライブドアが大好きです。
2: 私はインターネットが大好きです。

転置インデックスが作成されているとして、
Token: DocID
----------------------------------------
私: 1,2
は: 1,2
ライブドア: 1
インターネット: 2
が: 1,2
大好き: 1,2
です: 1,2
。: 1,2

"ライブドア: 1" と "大好き: 1,2" を AND すると 1 のみがヒットします。
ここで単語の出現頻度などを元にスコア計算され、最後にソートされて結果となります。


プログラム例


インデックスの作成と検索の簡単なプログラム例を書きます。

・インデックスの作成

// Analyzer インスタンスを作成
Analyzer analyzer = new HyperAnalyzer();

// インデックスのオープン
String indexPath = "/path/to/your/index";
IndexWriter iw = new IndexWriter(indexPath, analyzer, true);

// ドキュメントの作成とインデックスへの追加
Document doc;

doc = new Document();
doc.add(new Field("name", "ライブドア一郎"), Field.Store.YES, Field.Index.YES);
doc.add(new Field("address", "東京都港区赤坂"), Field.Store.YES, Field.Index.YES);
doc.add(new Field("age", "25"), Field.Store.YES, Field.Index.UN_TOKENIZED);
iw.add(doc);

doc = new Document();
doc.add(new Field("name", "ライブドア二郎"), Field.Store.YES, Field.Index.YES);
doc.add(new Field("address", "東京都港区赤坂"), Field.Store.YES, Field.Index.YES);
doc.add(new Field("age", "23"), Field.Store.YES, Field.Index.UN_TOKENIZED);
iw.add(doc);

doc = new Document();
doc.add(new Field("name", "ライブドア花子"), Field.Store.YES, Field.Index.YES);
doc.add(new Field("address", "群馬県伊勢崎市今井町"), Field.Store.YES, Field.Index.YES);
doc.add(new Field("age", "21"), Field.Store.YES, Field.Index.UN_TOKENIZED);
iw.add(doc);

// インデックスのクローズ
iw.close();


・インデックスの検索

// インデックスのオープン
String indexPath = "/path/to/your/index";
IndexSearcher is = new IndexSearcher(indexPath);

// Analyzer インスタンスを作成
Analyzer analyzer = new HyperAnalyzer();

// QueryParser によるクエリ文字列の解析
String queryString = "name:ライブドア AND address:東京";
QueryParser qp = new QueryParser("name", analyzer);
Query query = qp.parse(queryString);

// ソート関連
SortField sortField = new SortField("age", SortField.Int);
Sort sort = new Sort(sortField);

// 検索
Hits hits = is.search(query, sort);

// Hits の表示
System.out.println(hits.length() + "件ヒット");
for (int i = 0; i < hits.length(); i++)
{
Document doc = hits.doc(i);
System.out.println(
(i + 1) + ": " +
doc.get("name") + "," +
doc.get("address") + "," +
doc.get("age"));
}

上記の実行結果:
1: ライブドア二郎,東京都港区赤坂,23
2: ライブドア一郎,東京都港区赤坂,25

このような感じで lucene を使うことで簡単に全文検索のプログラムを書くことができます。


Orchestra(オーケストラ)


lucene は非常に高速で、単体でも数百万件のドキュメントを大抵1秒以内に検索することができます。しかしドキュメント数が数千万件規模になるとレスポンスタイムが問題になってきます。
そこで lucene を複数のノードに分散する「Orchestra」という仕組みを開発しました。
クラスやインターフェイスをそのままの分散型にしても良かったのですが、IndexWriter や IndexSearcher のオープン・クローズという煩わしい作業を意識せずにドキュメントの追加・削除・検索を行えるようにしました。

Orchestra


あるサービスでは、ノード1つに約3,300,000件で15ノードを連結して約50,000,000件のドキュメントを格納しています。それでも大抵数百ミリ秒以内に検索することができます。


奏(Kanade)


lucene、Orchestra は Java で書かれているので、フロント側の perl から直接利用できません。そこで、ドキュメントの追加・削除・検索を http 経由で行う「奏(Kanade)」という仕組みを開発しました。

奏(Kanade)


Kanade Queue に http 経由で add/delete/commit のコマンドを追加すると、バックグラウンドで稼働している Kanade Indexing Service により順次 Orchestra へ処理されます。
Kanade Search に http 経由で検索クエリを渡すと xml/json/csv の形式で結果を返します。


QueryParser の機能拡張


lucene の標準の QueryParser は良くできていて、一般的なウェブ検索などのクエリで必要なパターンの多くをサポートしています。AND、OR、NOT、フレーズなど。

しかし複雑な検索パターンを必要とする場合には lucene の Query クラスを継承して独自の Query クラスを作成することになります。そのようにしてできた Query クラスを QueryParser は認識できません。

しかしせっかく QueryParser という便利なものがあるので、例えば独自に作成した Query クラスを下記のようなクエリ文字列で使えたら・・・と思います。

category:書店 AND &geo_in_circle( lat => 'lat_field', long => 'long_field', center => 'E139.44.40.6N35.40.7.4', distance => '5')

上記の例では lat_field と long_field に緯度経度が格納されているドキュメントを前提に、center の値に近い順に、5キロメートル以内にある書店を検索する、というような感じです。

QueryParse は 拡張BNF という文法で書かれており、JavaCC でコンパイルすることで Java のソースコードが生成されます。lex や Flex といったレキシカル・アナライザのようなものです。


次回


中途半端な終わりかたになってしまうかと思いますが、だいぶ長くなってしまったので QueryParser の機能拡張やレキシカル・アナライザについては、また次回ということで。
レスポンス
コメント(0)
トラックバック(0)

このエントリーをはてなブックマークに追加