エムスリーエンジニアリンググループ AI・機械学習チームの中村(@po3rin) です。 好きな言語はGo。仕事では主に検索周りを担当しています。
エムスリーでは検索エンジンとしてElasticsearchを利用しているのですが、Highlightingのフラグメント機能でとある問題が発生しました。その問題を解決する中でElasticsearch Highlighting の内部的な仕組みを理解することの重要性を改めて感じました。
今回はエムスリーで発生した問題の共有からはじめ、どのように解決したのかはもちろん、Elasticsearch Highlighting の内部的な仕組みも一部紹介します。ちなみに今回見ていくLucene のバージョンは 8.6.2 です。
「検索結果画面がすごく伸びてるんですが...」
ある日、別チームからとあるクエリで 「検索結果のスニペットが制限を超えて長くなっている 」という連絡がありました。Elasticsearchではハイライトした結果を フラグメント という単位に分割できるので、エムスリーではフラグメントのサイズを150文字に設定し、検索結果画面ではスニペットとしてフラグメントを表示する実装をしていました。
フラグメントのサイズはElasticsearchではfragment_sizeというパラメータで設定できます。その為、エムスリーではfragment_size: 150に設定していたのですが、150文字を大幅に超えるサイズのフラグメントがElasticsearchから返ってきていたのです。
最初はElasticsearchのバグを疑いましたが、調べていくうちに、ただ単にハイライトの機能をよく理解せずに使っていただけということに気づきました。
ElasticsearchレイヤーでみるHighlighter
私たちと同じ過ちを踏まないように、まずはElasticsearchレイヤーでのHighlighterを簡単に復習していきましょう。ElasticsearchのHighlighterには「Plain highlighter」「Unified highlighter」「Fast vector highlighter」の3種類あります。今回はその中でも弊社が利用していた & 実装が簡単なPlain highlighterに注目していきます。
Plain highlighter
Plain highlighterは単一フィールドに対して単純なクエリの一致をハイライトするのに最適なHighlighterです。Elasticsearchでは下記のようなリクエストでHighlightingが可能です。
GET /_search { "query": { "match": { "content": "kimchy" } }, "highlight": { "fields": { "body": { // どのタグで囲む？ "post_tags": [ "</strong>" ], "pre_tags": [ "<strong>" ] } }, "fragment_size": 150, // フラグメントサイズ "number_of_fragments": 1, // フラグメントの数 "type": "plain" // どのHighlighterを使うか }, }
Plain highlighterではゼロから小さなインメモリインデックスを作成し、元のクエリを再実行します。これはハイライトする必要があるすべてのフィールドとすべてのドキュメントに対して実行されます。その為、複雑なクエリや対象のフィールドが多い場合はパフォーマンスの為に別のHighlighterを使用する必要があります。
ちなみに Elasticsearch の Plain highlighterの実装はPlainHighlighter.javaにあります。コードは掲載しませんが、内部ではLuceneのAPIを利用していることがわかります。
LuceneレイヤーでみるHighlighter
Elasticsearch HighlightingのコアのアルゴリズムはLuceneで実装されています。LuceneとはElasticsearchの内部で利用されているオープンソースの検索エンジンライブラリです。あらかじめ蓄積した大量のデータから、指定したキーワードを探し出す機能を持ち、Javaのクラスライブラリとして提供されています。
それではLuceneのHighlighterの構成を見ていきましょう。Highlighterの構成要素は大きく3つあり、ScoreQuery、Formatter、Fragmenterです。
- ScoreQuery : 最適なフラグメントの為のスコアリング
- Formatter : どのタグで検索結果のテキストをハイライトするか
- Fragmenter: どのようにフラグメントに分割するかの責務を持つ
図にするとわかりやすいと思います。
Highlighterを初期化する場合、以下のようなコードになります。当然Elasticsearch内部でも同じようにLuceneのクラスを使ってハイライトが実装されています。この例で生成するHighlighterはElasticsearchでいう所のPlain highlighterにあたります。
// Formatter生成 Formatter formatter = new SimpleHTMLFormatter("<bold>", "</bold>"); // 検索に使ったクエリからQueryScorerを生成 QueryScorer scorer = new QueryScorer(query, "contents"); // FormatterとQueryScorerからHighlighterを生成 Highlighter highlighter = new Highlighter(formatter, scorer); // HighlighterにFragmenterを設定 Fragmenter fragmenter = new SimpleSpanFragmenter(scorer); highlighter.setTextFragmenter(fragmenter);
Highlighterを使って実際にハイライトさせる際にはTokenStreamも必要です。これは任意のAnalyzerが元のテキストから作るtoken列です。Analyzerによってはthisやisをstop wordsとして排除してくれます。ここからもAnalyzerがHighlighterの動作に影響を与えることが分かります。
あとはTokenStream とハイライトをつける対象のテキストを渡してあげるだけでテキストがハイライトされた文字列を取得できます。当然、結果はString[]としてフラグメントに分割されて返ってきます。
// Analyzerを使ってTokenStream生成 TokenStream stream = analyzer.tokenStream("contents", text); // TokenStream と 元のテキストからフラグメントを作る。第三引数は欲しいフラグメントの数 String[] frags = highlighter.getBestFragments(stream, text, 1);
弊社の「フラグメント長が指定制限を超える問題」は、LuceneのHighlighterの構造が頭に入っていれば、利用しているFragmenterに原因であることは概ね見当がつけられたはずですが、無知な私は最初かなり戸惑ってました。
1番シンプルなFragmenterの実装を覗く
Highlighterはどのようにフラグメントを分割しているのでしょうか。エムスリーではPlain highlighterを利用していたので、例としてPlain highlighterがどのようにフラグメント分割しているのか見ていきます。
Plain highlighterには設定できる Fragmenter がいくつか存在します。1番アルゴリズムがシンプルなSimple fragmenterでは、まず任意のAnlayzerで単語分割しそれらをループしていき、ループ内で単語のend_offsetがfragment_size × すでに作成されたフラグメントの数を超えるたびに新しいフラグメントを作成します。
実際にorg.apache.lucene.search.highlight.SimpleFragmenterのコードをみてみるとフラグメント判定のメソッドisNewFragmentが非常に単純なアルゴリズムであることがわかります。
public class SimpleFragmenter implements Fragmenter { // ... public boolean isNewFragment() { boolean isNewFrag = offsetAtt.endOffset() >= (fragmentSize * currentNumFrags); if (isNewFrag) { currentNumFrags++; } return isNewFrag; } // ... }
Simple Fragmenterはかなり単純なアルゴリズムである一方、ハイライトしたいフレーズがフラグメントで分割される可能性があります。
問題のSimpleSpanFragmenterを深掘る
これまでの説明で、今回問題になっていたフラグメントが制限を超えて長くなる問題を深掘る準備ができました。
エムスリーで使っていたHighlighterはPlain highlighterです。ElasticsearchのPlainHighlighter.java を覗くとその中でLuceneのSimpleSpanFragmenterクラスを利用しています。こいつが今回使われていたFragmenterです。
SimpleFragmenterと同じように isNewFragmentメソッドのコードを見てみましょう。
public class SimpleSpanFragmenter implements Fragmenter { // ... @Override public boolean isNewFragment() { position += posIncAtt.getPositionIncrement(); if (waitForPos <= position) { waitForPos = -1; } else if (waitForPos != -1) { return false; } WeightedSpanTerm wSpanTerm = queryScorer.getWeightedSpanTerm(termAtt.toString()); if (wSpanTerm != null) { List positionSpans = wSpanTerm.getPositionSpans(); for (PositionSpan positionSpan : positionSpans) { if (positionSpan.start == position) { waitForPos = positionSpan.end + 1; break; } } } boolean isNewFrag = offsetAtt.endOffset() >= (fragmentSize * currentNumFrags) && (textSize - offsetAtt.endOffset()) >= (fragmentSize >>> 1); if (isNewFrag) { currentNumFrags++; } return isNewFrag; } // ... }
長くて少しわかりづらいですが、SimpleFragmenterど同様なアルゴリズムをベースに、Spanクエリを使ったFragment判定が追加されているようです。
実験
SimpleSpanFragmenterをより深く理解するためにLucene本家のテストにPrintを挟んで何がおきているのかを手を動かしながら確認してみます。対象テストはtestSimpleSpanFragmenterです。LuceneのビルドインフラはGradleなので下記コマンドで対象の関数のみのテストが可能です。
./gradlew -p lucene/highlighter test --tests "*HighlighterTest.testSimpleSpanFragmenter"
しかし、テストだと標準出力がされないのでlucene/highlighter/build.gradleに下記を追加してあげます。
test {
testLogging {
events 'standard_out', 'standard_error'
}
}
これでテスト時にPrintデバッグできるようになりました。ここまでの仕込みはLuceneのコードリーディングで非常に有用です。
それではPrintを仕込んでテストを実行してみます。見たいのはSimpleFragmenterとの差異であるSpanの部分なのでそこにPrintを仕込んでみます。
public class SimpleSpanFragmenter implements Fragmenter { // ... // ... public boolean isNewFragment() { System.out.print("---------token----------"); System.out.print(termAtt.toString()); // ... if (wSpanTerm != null) { List positionSpans = wSpanTerm.getPositionSpans(); for (PositionSpan positionSpan : positionSpans) { System.out.print("start: " + positionSpan.start); System.out.print("end: " + positionSpan.end); // ... } } // ... }
またテスト関数testSimpleSpanFragmenterで検索クエリを確認しておきます。今回のテストケースではPhraseQueryが使われています。
public void testSimpleSpanFragmenter() throws Exception { // PhraseQuery を生成 Builder builder = new PhraseQuery.Builder(); builder.add(new Term(FIELD_NAME, "piece"), 0); builder.add(new Term(FIELD_NAME, "text"), 2); builder.add(new Term(FIELD_NAME, "very"), 5); builder.add(new Term(FIELD_NAME, "long"), 6); PhraseQuery phraseQuery = builder.build(); // ... }
また、テスト関数testSimpleSpanFragmenterにハイライトする対象のテキストを表示するようにしておきます。
これで実行してみると以下のような結果が得られます(一部抜粋)。
test: -------------------
Hello this is a piece of text that is very long and contains too much preamble and the meat is really here which says kennedy has been shot
-------------------------
---------token----------
piece
start: 4
end: 10
---------token----------
text
start: 4
end: 10
---------token----------
very
start: 4
end: 10
---------token----------
long
start: 4
end: 10
---------token----------
contains
---------token----------
too
---------token----------
// ...
この結果を図にして確かめてみましょう。
この図とコードから分かる通り、SpanQueryから取得したSpanの間は条件式からフラグメント分割判定をスキップします。Spanの間のterm以外は前に紹介したSimpleFragmenterと同じアルゴリズムでフラグメント分割をしています。これで元のクエリによってはfragment_sizeより大きなFragmentを許容してでもSpanが分割されないようになっているアルゴリズムがコードからも確認できました。
本問題の対応
今回の弊社の問題では非常に長いSpanが生成され、Elasticsearchで指定したfragment_sizeよりも非常に長いフラグメントを生成してしまっていたのが大きな問題でした。UIに影響が出ていた為、Hot fixとして、Elasticsearchのfragmenterオプションをsimpleに変更し、問題が発生しないことを確認しました。一方で今回の事件で弊社のハイライトを抜本的に見直す必要を感じた為、他のHighlighterへの移行を検討中です。
まとめ
ハイライトは検索一覧からユーザーの次のアクションに繋げるためにも是非利用したい機能ですが、その機能を使ってみて「動くから良い」で終わるのではなくハイライトを内部実装から理解して、適切なHighlighterを選んでいくことは重要です。皆さんも是非ハイライトの内部実装を深掘りしてみてください。
We're hiring !!!
エムスリーでは検索基盤の開発&改善を通して医療を前進させるエンジニアを募集しています！ 社内では最近、検索チームを中心に「Elasticsearch & Lucene コードリーディング会」が発足し、検索の仕組みに関する議論も活発です。
自分は2ヶ月前に入社したばかりなので、出来立てほやほやの転職エントリも是非読んでみて下さい。
「ちょっと話聞いてみたいかも」という人はこちらから！
参考文献
ドキュメント最強 www.elastic.co
Lucene読むなら絶対目を通したい記事 medium.com
