2008.03.12 Wednesday
LuceneとSennaの比較：スコア計算
最近全文検索エンジンLudia（1.4.0）を触る機会を得た。LudiaはSennaのPostgreSQLバインディングである（念のため）。
Ludiaでのクエリーは、演算子@@を使ったSQLを投げればいいだけの簡単操作である。
たとえば次の例はauction_itemというテーブルのdescriptionカラムに「音楽」と「ビデオ」の両方の単語を含むレコードを「全文検索」で検索するSQLを発行している。ただし、結果をスコア順およびauction_id順でソートした結果の最初の1件のみを取得している：
なお、auction_itemのカラムdescriptionには全文検索インデックスfidxがあらかじめ作成されている。
ところでSennaについて前から気になっていることをこの結果を見てまた思い出した。それは検索結果のスコアのことだ。Sennaではどういう計算をしてスコアを算出しているのか前から気になっていたのだった。
上記のSQLで検索結果の全件を表示させてみると（SQLの最後の"limit 1"をはずす）、スコアは40がしばらく続き、ついで30がしばらく続き、25が続き、20が続き、・・・というような結果が得られる。この根拠はなんだろう。
ところでLuceneではスコアの計算式はSimilarityクラスのJavadocで紹介されている：
http://hudson.zones.apache.org/hudson/job/Lucene-trunk/javadoc/org/apache/lucene/search/Similarity.html
このような計算式をSennaのマニュアル上でもぜひ見たいところである。しかしGoogleでSennaのスコアの計算式を調べても出てこない。それどころかSennaのスコア算出の根拠を気にしているユーザがあまりいなさそうなのは私にとっては驚きだ。なぜなら検索結果の順番は、顧客からもっとも問い合わせの多い項目のひとつだからである。
Sennaはソースコードをオープンにしているので、ソースを丹念に調べればスコア算出の根拠も自分で調べられる、といわれれば確かにそのとおりだ。なので一応ソースを覗いてみる。ソースをダウンロードしてgrep scoreとすると、次のような行を見つけることができた：
他にもいくつかの行がヒットしていたのでここだけではないと思うが、とりあえず上の行だけ見るとなんらかの重み（？・・・"w"なので・・・）にtfを掛けてそれをスコアに足しこんでいるようである。idfはSennaでは考慮しないのか？と思いGoogleで"senna idf"で調べると今度はひっかかり、Sennaのマニュアルに次の説明を見つけることができた：
sen_sel_similar
stringをわかち書きした語のうち、idf値が大きなsimilarity_threshold個の語のいずれかを含むレコードを検索します。
どうやら設定によりidfが考慮されるようである。ということは、デフォルトの状態ではtfのみがスコア計算のパラメータとなるのだろうか。早速確かめてみよう。
Luidaで次のSQLを実行して検索対象文書となるレコードを作成する：
次に転置索引を作成する：
この状態で「aまたはb」（OR検索）を含む文書を全文検索してみよう。すると次のようになる：
予想通りtfのみが考慮された結果、aを最も多く含む文書がトップに表示され、その次にaをたくさん含む文書が2番目になり、最後にやっとbを含む文書が表示された。このデフォルトの動作はユーザを困惑させると思うのだが、どうだろう。
具体例にたとえるならば、「アップル または コンピュータ」というクエリを発行したユーザの気持ちとしては、アップルコンピュータのページが果物屋のページよりも先に表示されて欲しい、ということである。
ところがSennaのデフォルト設定では（いや、これはLudiaのデフォルト設定と言い換えたほうがいいかもしれない）、アップルが多数登場する果物屋のページが上位表示されてしまうのである。
Luceneではどうなるかというと、この例の場合はidfが大きな役割を果たし、bという単語の希少価値がスコアに大きく影響する。その結果、「a b」が最も上位に表示されるようになる。ついでtfの大きな「a a a a a a」となり最後に「a c a d a e」となる。つまりLuceneでは「アップル または コンピュータ」というクエリを発行したユーザは、「アップル」という単語が多数登場する果物屋のページに惑わされることなくアップルコンピュータのページに先にたどり着けるわけである。
これを実際に確かめるコードを次に示す：
実行結果は次のとおり、「a b」の文書が最も高いスコアを獲得する：
一部の顧客は検索結果の順位についてひどく敏感である。たとえばスポンサー企業から掲載料を受け取って検索結果としてその企業情報や商品などを表示するサービスを提供している顧客などだ。このようなときはその検索結果の順位についてきちんと根拠を説明できないといけない。場合によっては「10位に表示されてしまっている企業情報を1位に表示する」よう要望されることもある。そのためにはまず、現状のスコア値の根拠がなんなのかを知ることが絶対に必要になってくる。
こんなときに便利なのがLuceneのExplanationクラスである。前記の赤字部分のコメントアウトをはずして再度実行すると、次のようなスコア計算の根拠が表示される：
Lucene本にはtf、idf、lengthNorm(≒fieldNorm)、boostなどの解説がある。また、プログラムを実行できる環境をもっていない方は、弊社デモサイトの「スコア計算デモ」も参考になるだろう。
Ludiaでのクエリーは、演算子@@を使ったSQLを投げればいいだけの簡単操作である。
たとえば次の例はauction_itemというテーブルのdescriptionカラムに「音楽」と「ビデオ」の両方の単語を含むレコードを「全文検索」で検索するSQLを発行している。ただし、結果をスコア順およびauction_id順でソートした結果の最初の1件のみを取得している：
demo=> select auction_id,title,pgs2getscore(ctid,'fidx') from auction_item where
description @@ '*D+ 音楽 ビデオ' order by pgs2getscore desc,auction_id limit 1;
auction_id | title | pgs2getscore
------------+-----------------------------------------------------------+--------------
s62908788 | ★SONYソニーハードディスクオーディオレコーダーNAC-HD1新品 | 40
(1 row)
demo=>
なお、auction_itemのカラムdescriptionには全文検索インデックスfidxがあらかじめ作成されている。
ところでSennaについて前から気になっていることをこの結果を見てまた思い出した。それは検索結果のスコアのことだ。Sennaではどういう計算をしてスコアを算出しているのか前から気になっていたのだった。
上記のSQLで検索結果の全件を表示させてみると（SQLの最後の"limit 1"をはずす）、スコアは40がしばらく続き、ついで30がしばらく続き、25が続き、20が続き、・・・というような結果が得られる。この根拠はなんだろう。
ところでLuceneではスコアの計算式はSimilarityクラスのJavadocで紹介されている：
http://hudson.zones.apache.org/hudson/job/Lucene-trunk/javadoc/org/apache/lucene/search/Similarity.html
このような計算式をSennaのマニュアル上でもぜひ見たいところである。しかしGoogleでSennaのスコアの計算式を調べても出てこない。それどころかSennaのスコア算出の根拠を気にしているユーザがあまりいなさそうなのは私にとっては驚きだ。なぜなら検索結果の順番は、顧客からもっとも問い合わせの多い項目のひとつだからである。
Sennaはソースコードをオープンにしているので、ソースを丹念に調べればスコア算出の根拠も自分で調べられる、といわれれば確かにそのとおりだ。なので一応ソースを覗いてみる。ソースをダウンロードしてgrep scoreとすると、次のような行を見つけることができた：
:
./lib/query.c: *score += w * tf;
./lib/query.c: *score += w * tf;
./lib/query.c: *score += w * tf;
:
他にもいくつかの行がヒットしていたのでここだけではないと思うが、とりあえず上の行だけ見るとなんらかの重み（？・・・"w"なので・・・）にtfを掛けてそれをスコアに足しこんでいるようである。idfはSennaでは考慮しないのか？と思いGoogleで"senna idf"で調べると今度はひっかかり、Sennaのマニュアルに次の説明を見つけることができた：
sen_sel_similar
stringをわかち書きした語のうち、idf値が大きなsimilarity_threshold個の語のいずれかを含むレコードを検索します。
どうやら設定によりidfが考慮されるようである。ということは、デフォルトの状態ではtfのみがスコア計算のパラメータとなるのだろうか。早速確かめてみよう。
Luidaで次のSQLを実行して検索対象文書となるレコードを作成する：
demo=> create table test (col text);
CREATE TABLE
demo=> insert into test values ('a c a d a e');
INSERT 0 1
demo=> insert into test values ('a a a a a a');
INSERT 0 1
demo=> insert into test values ('a b');
INSERT 0 1
demo=>
次に転置索引を作成する：
demo=> create index tidx on test using fulltext(col);
CREATE INDEX
demo=>
この状態で「aまたはb」（OR検索）を含む文書を全文検索してみよう。すると次のようになる：
demo=> select col,pgs2getscore(ctid,'tidx') from test where col @@ '*DOR a b'
order by pgs2getscore desc;
col | pgs2getscore
-------------+--------------
a a a a a a | 30
a c a d a e | 15
a b | 10
(3 rows)
demo=>
予想通りtfのみが考慮された結果、aを最も多く含む文書がトップに表示され、その次にaをたくさん含む文書が2番目になり、最後にやっとbを含む文書が表示された。このデフォルトの動作はユーザを困惑させると思うのだが、どうだろう。
具体例にたとえるならば、「アップル または コンピュータ」というクエリを発行したユーザの気持ちとしては、アップルコンピュータのページが果物屋のページよりも先に表示されて欲しい、ということである。
ところがSennaのデフォルト設定では（いや、これはLudiaのデフォルト設定と言い換えたほうがいいかもしれない）、アップルが多数登場する果物屋のページが上位表示されてしまうのである。
Luceneではどうなるかというと、この例の場合はidfが大きな役割を果たし、bという単語の希少価値がスコアに大きく影響する。その結果、「a b」が最も上位に表示されるようになる。ついでtfの大きな「a a a a a a」となり最後に「a c a d a e」となる。つまりLuceneでは「アップル または コンピュータ」というクエリを発行したユーザは、「アップル」という単語が多数登場する果物屋のページに惑わされることなくアップルコンピュータのページに先にたどり着けるわけである。
これを実際に確かめるコードを次に示す：
public class TestScore {
static Directory dir;
static Analyzer analyzer = new WhitespaceAnalyzer();
public static void main(String[] args) throws IOException, ParseException {
dir = new RAMDirectory();
makeIndex();
searchIndex();
}
static void makeIndex() throws IOException {
IndexWriter writer = new IndexWriter( dir, analyzer );
writer.addDocument( getDocument( "a c a d a e" ) );
writer.addDocument( getDocument( "a a a a a a" ) );
writer.addDocument( getDocument( "a b" ) );
writer.close();
}
static Document getDocument( String value ){
Document doc = new Document();
doc.add( new Field( "f", value, Store.YES, Index.TOKENIZED ) );
return doc;
}
static void searchIndex() throws IOException, ParseException {
IndexSearcher searcher = new IndexSearcher( dir );
QueryParser qp = new QueryParser( "f", analyzer );
Query query = qp.parse( "a b" );
Hits hits = searcher.search( query );
for( int i = 0; i < hits.length(); i++ ){
Document doc = hits.doc( i );
float score = hits.score( i );
System.out.println( score + " : " + doc.get( "f" ) );
//Explanation explain = searcher.explain( query, hits.id( i ) );
//System.out.println( explain.toString() );
}
searcher.close();
}
}
実行結果は次のとおり、「a b」の文書が最も高いスコアを獲得する：
0.98479235 : a b
0.14789723 : a a a a a a
0.10457913 : a c a d a e
一部の顧客は検索結果の順位についてひどく敏感である。たとえばスポンサー企業から掲載料を受け取って検索結果としてその企業情報や商品などを表示するサービスを提供している顧客などだ。このようなときはその検索結果の順位についてきちんと根拠を説明できないといけない。場合によっては「10位に表示されてしまっている企業情報を1位に表示する」よう要望されることもある。そのためにはまず、現状のスコア値の根拠がなんなのかを知ることが絶対に必要になってくる。
こんなときに便利なのがLuceneのExplanationクラスである。前記の赤字部分のコメントアウトをはずして再度実行すると、次のようなスコア計算の根拠が表示される：
0.98479235 : a b
0.98479235 = (MATCH) sum of:
0.20126262 = (MATCH) weight(f:a in 2), product of:
0.4520737 = queryWeight(f:a), product of:
0.71231794 = idf(docFreq=3, numDocs=3)
0.63465154 = queryNorm
0.4451987 = (MATCH) fieldWeight(f:a in 2), product of:
1.0 = tf(termFreq(f:a)=1)
0.71231794 = idf(docFreq=3, numDocs=3)
0.625 = fieldNorm(field=f, doc=2)
0.78352976 = (MATCH) weight(f:b in 2), product of:
0.8919806 = queryWeight(f:b), product of:
1.4054651 = idf(docFreq=1, numDocs=3)
0.63465154 = queryNorm
0.8784157 = (MATCH) fieldWeight(f:b in 2), product of:
1.0 = tf(termFreq(f:b)=1)
1.4054651 = idf(docFreq=1, numDocs=3)
0.625 = fieldNorm(field=f, doc=2)
Lucene本にはtf、idf、lengthNorm(≒fieldNorm)、boostなどの解説がある。また、プログラムを実行できる環境をもっていない方は、弊社デモサイトの「スコア計算デモ」も参考になるだろう。
