Sloppy Phrase Search の slop とは

2017-06-04

Solr

Solr というか Lucene には Sloppy Phrase Search (Proximity Search) という機能があります。
"foo bar" で検索すると "foo bar" というフレーズの存在するドキュメントしかヒットしませんが、"foo bar"~n だと foo と bar の間に n 単語存在していてもヒットします。この n の値が slop と呼ばれるものです。例えば n = 1 であれば "foo bar"~1 で "foo baz bar" というフレーズの存在する文書もヒットします。

% # "foo baz bar" を追加
% curl -d '[{"id":1, "name_t":"foo baz bar"}]' 'http://localhost:8983/solr/test/update?commit=true'
% # "foo bar" だとヒットしない
% curl 'http://localhost:8983/solr/test/select?indent=on&q=name_t:%22foo%20bar%22&wt=json'
{
  "responseHeader":{
    "status":0,
    "QTime":1,
    "params":{
      "q":"name_t:\"foo bar\"",
      "indent":"on",
      "wt":"json"}},
  "response":{"numFound":0,"start":0,"docs":[]
  }}
% # "foo bar"~1 だとヒットする
% curl 'http://localhost:8983/solr/test/select?indent=on&q=name_t:%22foo%20bar%22~1&wt=json'
{
  "responseHeader":{
    "status":0,
    "QTime":0,
    "params":{
      "q":"name_t:\"foo bar\"~1",
      "indent":"on",
      "wt":"json"}},
  "response":{"numFound":1,"start":0,"docs":[
      {
        "id":"1",
        "name_t":"foo baz bar",
        "_version_":1569196527200501760}]
  }}

つまり、ドキュメントに存在するフレーズと検索クエリのフレーズの “距離” をどれだけ許容するかが slop と言えます。
文字列間の距離といえば編集距離なので、Lucene の Sloppy Phrase Search における距離も単語を文字に見立てた編集距離かと思いきや、独自の距離なので注意が必要です。

そんなわけで、Sloppy Phrase Search における距離の定義や slop がどのように使われているかを調べてまとめてみました。対象の Solr のバージョンは 6.5.1 です。

Sloppy Phrase Search における距離

距離の計算は SloppyPhraseScoreer#phraseFreq で行っています。よって、ここで算出されている距離 (matchLength) が Lucene の Sloppy Phrase Search における距離の定義と言えます。
例として、"a b c b a" というドキュメントに対して、"a b c"~4 というクエリを投げることを考えます。ドキュメントの各単語の位置やクエリの各単語のオフセットは次のようになります。

position	0	1	2	3	4
document	a	b	c	b	a

offset	0	1	2
query	a	b	c

クエリの各単語がマッチしたドキュメントの全ての位置に対して、document position - query offset を求めます。これが PhrasePositions#position です。

term	query offset	phrase positions
a	0	0, 4
b	1	0, 2
c	2	0

これらの情報から、各位置の組み合わせに対して max phrase position - min phrase position を計算し、それを距離とします。次の表の sloppy phrase 中のドットは任意の term を意味しています。

a pos	b pos	distance	sloppy phrase	levenshtein distance
0	0	0	a b c	0
4	0	4	b c . a	3
0	2	2	a . c b	2
4	2	4	c b a	2

とりあえずレーベンシュタイン距離ではないことがわかると思います。

全ての組み合わせの距離を求めると上記のようになりますが、実際は効率化のため一部の組み合わせしか考慮されません。
現状では "a b c", "b c . a", "c b a" のみが考慮されます。

Sloppy Phrase Search における頻度

Sloppy Phrase Search では、term frequency の代わりに phrase frequency というものを使っています。それを計算しているのが SloppyPhraseScoreer#phraseFreq です。
デフォルトの BM25Similarity であれば、距離 (matchLength を使って) を使って次のように計算しています。[ ] は Iverson bracket で、距離が slop 以下であれば 1、そうでなければ 0 になります。

\[\rm{freq} = \sum_{sp \in \rm{Sloppy\ Phrases}}\frac{1}{\rm{dist}(sp) + 1} \Big[\rm{dist}(sp) \le \rm{slop}\Big]\]

freq が 0 の場合、そのドキュメントはクエリにマッチしなかったことになります。
また、距離が大きい sloppy phrase ほど頻度が小さくなることがわかります。

まとめ

slop はドキュメントに存在するフレーズと検索クエリのフレーズの “距離” をどれだけ許容するかを表す
Sloppy Phrase Search において、距離とは独自の距離であり、一般的な編集距離とは異なる
Sloppy Phrase Search では term frequency の代わりに phrase frequency が使われ、距離が大きい sloppy phrase ほどその値は低くなる