読者です 読者をやめる 読者になる 読者になる

stop-the-world

takuya-a のブログ

「Elasticsearch での類似文書検索と More Like This Query API 詳解」というタイトルで発表しました

 Elasticsearch 勉強会 in 大阪・京都で発表しました。

 最近、興味をもって調べていた More Like This Query API について、改めてソースコードリーディングしながら整理した内容になっています。

 この発表で使ったスライドを Speaker Deck にアップしました。大阪と京都で同内容の発表でしたが、スライドの体裁をよくして見やすくした、京都での発表スライドをアップしています。

Elasticsearch での類似文書検索と More Like This Query API 詳解 // Speaker Deck

 関西では初の開催ということで、何を発表するか、かなり悩みました。

 先月の Hatena Engineer Seminar #5 では、どちらかというと事例についての発表だったので、もうちょっと汎用的に使える知識を、とはいえ、入門的な話は johtani さんがしてくださるので、より発展的な内容を、ということで類似文書検索に着地しました。

 ただ、両日ともに全文検索より Kibana 等の分析系のほうに興味がある方が多かったようで、参加者の興味を外していた感が否めませんでしたが。。(あとで Twitter を見返してみると、何人かの方には刺さっていたようでした)

類似文書検索とそのアプリケーションについて

 類似文書検索は、 Web 検索のみならず、社内文書の検索や、特許検索など、多くの検索アプリケーションで有用な技術です。

 ブログの関連エントリー機能などでも使われている技術だと思いますが、類似文書を関連エントリーとしてよいかどうかは、一考の余地があります。要するに、文章が似ているからといって、そのエントリーがブログの読者にとって有益かどうかはまた別問題、ということです。

 これについては、 id:skozawa さんが以前に発表した以下のスライドが参考になるかと思います(はてなブックマーク関連エントリー機能で、実際に Elasticsearch を使って実現されている技術について解説されています)。

優先度つきキューによる Top-K retrieval

 スライドの中で、優先度つきキュー (PriorityQueue) を使ってスコア上位 K 個の語(ターム)を求めるアルゴリズムが出てきました。発表では時間がなくて話せなかったので、ここで補足しておきます。

 Top-K を求めるアルゴリズムは、全文検索エンジンにとって最もコアであり、性能が求められる部分です。なぜなら、全文検索というのは、「与えられたクエリでの文書のスコアを計算し、スコア上位 K 件の文書を返す」という処理に他ならないからです。Lucene レベルでも、でかい転置インデックスから文書の Top-K を計算しており、そこにサイズ制限のある優先度つきキューが使われています。優先度つきキューを使用する際には、スコアを優先度とみなし、優先度の高い文書(= スコアの高い文書)を取り出します。

 Elasticsearch の More Like This Query API でも、膨大な数の語(ターム)の Top-K を計算するために、このアルゴリズムが使われています(こちらは文書ではなく、各タームのスコアを計算してスコア上位のタームを求めていることに注意)。

 優先度つきキューは、(プリミティブな)配列を使って実装できるため、定数オーダーの操作も高速ですが、これを使って Top-K を求めると、普通にソートするのと比べると、計算量のオーダーも下がるため、ソート対象が大きい場合には劇的な効果があります。

バイナリヒープを用いた制限のある優先度つきキューの実装

 優先度付きキュー (Priority Queue) はヒープ 、とくにバイナリヒープで実装されることが多いようです。ここで、ヒープとしては Min-Heap (最小値をもつ要素が先頭になるヒープ)を使うところがポイントです。

 サイズ制限のある優先度付きキューの実装は、普通に Max-Heap を使って実装すると、

  1. delete-min: ヒープから優先度の低いノードを削除 (O(N))
  2. insert: ノードを追加 (O(1))

ですが、 Min-Heap を使うと、

  1. extract-min: ヒープから優先度の低いノードを削除 (O(log N))
  2. insert: ノードを追加 (O(1))

となります。もう少し補足します。

 ルートノードは優先度が最も低いことが保証されているため、これは削除してよいということになります。上述の通り、先頭の要素の削除は O(log N) で可能です。単純に Max-Heap を使って、先頭以外の要素の削除をした場合には O(N) ですから、相当に高速化できました。

 最後に、サイズが k の配列を用意し、そこにバイナリヒープから順番に取り出した要素を、逆順に詰めていきます。詰め終わった配列を見ると、 Top-k の要素がソートされた状態で得られることになります。

(なお、ここでの優先度つきキューは、最初に要素の追加をすべて済ませ、最後にまとめて優先度の高い要素を取り出す、というタイプのものです。ジョブキューのような、追加の途中で削除があるような用途には使えません)

 バイナリヒープを配列で実装する方法については、以下の PDF が参考になります。

 Lucene での優先度つきキューの実装については、以下のソースを参照してください。

あとがき

 大阪では、ヤフー大阪支社の方々にお世話になりました。勉強会のあとの懇親会も楽しかったです。ありがとうございました。

 また、両日ともに elastic 社の方々には大変お世話になりました。また、 Elasticsearch: The Definitive Guide を献本いただいたり、 elastic ロゴ入りのビーチボールや sugru などの elastic な販促グッズもいただきました。

 京都での開催については、発表者全員のスライドが揃いましたら、開催報告エントリーを上げようと思います。