関口宏司のLuceneブログ

OSS検索ライブラリのLuceneおよびそのサブプロジェクト(Solr/Tika/Mahoutなど)について
<< もうひとつの絞り込み検索(後編) | main | 第2回エンタープライズサーチカンファレンス >>
自分の家から一番近いレストランを探す(地理検索、地図検索)
最近、自分の中では「プアマンズ何々(貧乏人の何々)」というのが流行っている。

たとえば先週、Flex User Group(FxUG)の会合に初めて出席したときの話だ。Flexはここでのテーマと外れるので詳しい説明は省くが、RIA(Rich Internet Application)のアプリを開発するためのツールでAdobe(旧Macromedia)の製品である。

この集会の最後に「今後の参考のために」ということでアンケートが配られた。そのアンケートのある質問項目に「今後ユーザグループで取り上げてもらいたいテーマがあれば教えてください」というのがあったので、私はすかさず、このように書いた:

「Poor man's FDS(FDSを使わずに、Flex SDKだけでどこまでがんばれるか)」

FDSというのはFlex Data Servicesのことで、JMSのようなメッセージングサービスのサポートであったり、サーバのオブジェクトをクライアントで簡単に扱えるようになっていたり、という機能が含まれるのだが、Flexユーザの間ではその高機能さよりもライセンスの高価さで有名な製品なのであった。まったく気の毒なことである。

一方、Flex SDKというのは無償で使える開発者キットである。つまり、「SDKを使ってこのくらいがんばって書けばFDSの機能をこのくらい模倣できる」、そんなテーマをFxUGで取り上げて欲しいと書いたわけである。

なんとずうずうしい要求だろうか。しかし、安く上がるのに越したことはない。SDKでがんばることでどこまでFDSに迫れるのか、FDSが必要な場面はどういう要求仕様のときに限るのか、こういうことが明らかになると開発者としてはありがたい。しかし、Adobeとしてはたまったものではないだろう。FxUGの会場と参加者への飲み物を無料で提供しているというのに。。。




ところで、ライセンスフリー(無料)のLuceneを担いでいる私のところには「商用の全文検索エンジンは高価なのでLuceneでできませんか」という話が割とある。

先週の訪問先もその向きの話で、私はこういった案件に愛着を感じつつ「Poor man's XXX」と内心ひそかに呼んでいる(XXXにはある商用全文検索エンジンの名称が入る)。

さて、この訪問先での話はすでにXXXを使って動いているシステムをLuceneを使うようにXXXを置き換えられないか、というものであった。そこで、現在XXXの機能を使って実現しているいろいろな検索機能をLuceneでできるかどうかという検討を行った。

その中で面白いと思ったものが「GEOサーチ」というものだ。GEOはローマ字読みしてはいけない。「ジオサーチ」と読む。Geography(地理)のGEOで、「自分の家から一番近いレストランを探す」というような検索である。

この場合、すべての文書(レストラン検索で言うと1つの文書は1つのレストラン情報に相当)には位置情報(緯度経度情報)が属性としてつけられている。そして、その情報を使って「ある地点を中心とした縦横10km以内の中華料理店」や「ある地点から半径5km以内のすし屋」を探し、近い順にソートして表示するのである。

このような地理検索、地図検索はLuceneを使い慣れている方なら簡単だと思うかもしれない。X座標、Y座標でANDの範囲検索をすれば「ある地点を中心とした縦横10km以内の中華料理店」は得られるからだ。また、LIAには地理検索の結果を「自分の家から近い順にソートして表示する」サンプルプログラムが掲載されている。

しかし、「縦横」ではなく「半径」だったらどうだろう。「縦横」と「半径」の関係をわかりやすく図にすると次のようになる。

縦横と半径の関係

「縦横」の場合斜線の部分も含むが、半径の場合は斜線の部分に位置するレストランを検索結果に含めてはいけない。先週の訪問先では、「半径」で(も)検索したいという要望であった。

今回はこの「半径○km以内」を範囲検索する方法を検討してみる。

FunctionQueryの検討

Lucene 2.0にもいまだ採用されていないが、JIRAにFunctionQueryというQueryクラスが提案されている。

http://issues.apache.org/jira/browse/LUCENE-446

このQueryはフィールドの値を計算してスコアに反映させることができるクラスであり、計算ロジックはValueSourceという抽象クラスをextendsしたクラスで実装し、それをFunctionQueryに与えるようになっている。このFunctionQueryを「半径○km以内」を範囲検索するQueryに使えないだろうか。

そこで試しに、ValueSourceをextendsしたDistanceFunctionクラスを実装してみる。



public class DistanceFunction extends ValueSource {

private ValueSource srcX;
private ValueSource srcY;
private int x;
private int y;
private int distance;

public DistanceFunction( ValueSource srcX, ValueSource srcY,
int x, int y, int distance ){
this.srcX = srcX;
this.srcY = srcY;
this.x = x;
this.y = y;
this.distance = distance;
}

:

public DocValues getValues(IndexReader reader) throws IOException {
final DocValues Xvals = srcX.getValues(reader);
final DocValues Yvals = srcY.getValues(reader);
return new DocValues() {
public float floatVal(int doc) {
return (float)doubleVal(doc);
}
public int intVal(int doc) {
return (int)doubleVal(doc);
}
public long longVal(int doc) {
return (long)doubleVal(doc);
}
public double doubleVal(int doc) {
double side2X = side2( Xvals.doubleVal(doc), x );
double side2Y = side2( Yvals.doubleVal(doc), y );
double val = (double)distance - Math.sqrt(side2X+side2Y);
return val < 0.0 ? 0.0 : val + 1.0;
}
public String strVal(int doc) {
return Double.toString(doubleVal(doc));
}
public String toString(int doc) {
return "omitted"; // 省略
}
private double side2( double src, int origin ){
return ( src - (double)origin ) * ( src - (double)origin );
}
};
}
:
}



上記のように、getValues()メソッドにて基準点(自分の家の座標)からのレストランの距離をスコアに反映するように実装する。

このクラスを次のようにFunctionQueryに渡して使うと、文書(=レストラン)のX座標とY座標の値から、ある地点からの距離をスコアに反映させることができる(基準点(5,5)から距離5以内のすし屋を検索している。以下同じ)。



protected void execQuery() throws IOException {
// IndexSearcherの取得
searcher = getIndexSearcher();
// 検索の実行
hits = searcher.search( getQuery( "すし", 5, 5, 5 ) );
}

private Query getQuery( String type, int x, int y, int distance ){
BooleanQuery bq = new BooleanQuery();
bq.add( new TermQuery( new Term( "type", type ) ),
BooleanClause.Occur.MUST );
ValueSource source = new DistanceFunction(
new IntFieldSource( "x" ), new IntFieldSource( "y" ),
x, y, distance );

bq.add( new FunctionQuery( source ), BooleanClause.Occur.MUST );
return bq;
}



しかし、(たとえスコアを0にしようとも)円の外の座標を持つ文書を「拒否」することはできない。そのため実行結果は次のようになり、座標(9,1)のすし屋も検索されてしまう。



すし (3,4) 1.0
すし (5,2) 0.8736577
すし (9,5) 0.70827353
すし (1,7) 0.6301897
すし (9,1) 0.3775051



したがって、ConstantScoreRangeQueryをBooleanQueryで組み合わせても図の正方形の部分以外を検索しないようにできるだけで、図の斜線の部分は検索結果に含まれてしまい、FunctionQueryでは「半径○km以内」の範囲検索は実現できないことがわかった。

DistanceQueryの実装を検討

次に、FunctionQueryでの失敗の教訓を生かし、Queryのrewrite()をオーバーライドするDistanceQueryなるものを作成することを検討してみる。

このQueryには基準(レストラン検索で言えば、自分の家が基準)となる座標と半径を与える。そして、rewrite()にて可能性のある座標の文書をすべてインデックスから拾うための別のプリミティブなQueryに置き換えるよう展開する。スコアは置き換えられたQueryにて計算されるため、「自分の家から近い順に結果を得る」ためには別途Sortを使用する必要がある。

しかしそもそも無数に可能性のある座標(グラフの網の目が細かくなれば円に含まれる座標は増えていく)を拾って別のQueryにどのように展開すればいいのだろう。BooleanQueryはTooManyClauses例外が投げられてしまうのでもちろん使えない。

・・・まったく思いつかないので、この方法は机上の検討だけでボツにした。

RadiusFilterの実装を検討

次に、図のようなRadiusFilterというFilterの実装を検討してみる。

RadiusFilter

このFilterは円形をしており、ボツになったDistanceQueryと同じように円の中心座標と半径を与える。そして、Filterを通過した文書をBitSetで返すようにする。

RadiusFilterはFilterを通過した文書をBitSetで返すためにFilterのbits()メソッドをオーバーライドしなければならない。そのようなbits()メソッドは実装可能だろうか。

一般のFilterでは、bits()の引数で渡されたIndexReaderを使ってTermEnumを取得し、そのうちのTermが条件を満たしていればBitSetをセットする、というように実装される。このとき、調べる属性は一種類であるのが通常である。TermEnumは属性ごとにソートされているので、TermEnumを順番に調べていく方法はbits()を実装するのに効率がよい。

しかし今回のテーマでは、調べる属性はX座標とY座標というように2つにまたがってしまっている。そのため、TermEnumをX座標(またはY座標)で絞ってもY座標(またはX座標)を取得するためにDocumentを読まなければならなくなってしまい、効率が悪い。

しかし、もし座標を1つの属性でまとめて持てば、この方法でも可能である。たとえば、(5,9)という座標は1つの属性で"0509"というように持たせるのである。日本列島のように南北に長いところで地理検索を行うのであれば、YX(緯度経度)の順番でまとめて持てば効率がよいだろう。

この方針でできそうのなで実際にプログラムを書いてみる。すると、RadiusFilterは次のようになる。



public class RadiusFilter extends Filter {

private String lowerTerm;
private String upperTerm;
private double x;
private double y;
private double distance;

public RadiusFilter( int x, int y, int distance ){
this.x = (double)x;
this.y = (double)y;
this.distance = (double)distance;
lowerTerm = getFormattedInt( x - distance ) +
getFormattedInt( y - distance );
upperTerm = getFormattedInt( x + distance ) +
getFormattedInt( y + distance );
}

private String getFormattedInt( int v ){
Format format = new DecimalFormat( "00" );
return format.format( v );
}

public BitSet bits(IndexReader reader) throws IOException {
BitSet bits = new BitSet( reader.maxDoc() );
TermEnum enumerator = reader.terms( new Term( "xy", lowerTerm ) );
try{
if( enumerator.term() == null )
return bits;
TermDocs termDocs = reader.termDocs();
try {
do {
Term term = enumerator.term();
if( term != null && term.field().equals( "xy" ) ){
if( term.text().compareTo( lowerTerm ) >= 0 ){
int compare = upperTerm.compareTo( term.text() );
if( compare < 0 )
break;
if( checkDistance( term ) ){
termDocs.seek( term );
while( termDocs.next() )
bits.set( termDocs.doc() );
}
}
}
else
break;
} while( enumerator.next() );
}
finally{
termDocs.close();
}
}
finally{
enumerator.close();
}
return bits;
}

private boolean checkDistance( Term term ){
String xy = term.text();
double dx = Double.parseDouble( xy.substring( 0, 2 ) );
double dy = Double.parseDouble( xy.substring( 2 ) );
double side2X = side2( dx, x );
double side2Y = side2( dy, y );
boolean b = Math.sqrt( side2X + side2Y ) <= distance;
//System.out.println( "checking " + xy + " : " + b );
return b;
}
private double side2( double dist, double origin ){
return ( dist - origin ) * ( dist - origin );
}
:
}



そして、このFilterを使ったプログラムは次のようになる。



protected void execQuery() throws IOException {
// IndexSearcherの取得
searcher = getIndexSearcher();
Filter filter = new RadiusFilter( 5, 5, 5 );
hits = searcher.search( getQuery( "すし" ), filter );
}

private Query getQuery( String type ){
return new TermQuery( new Term( "type", type ) );
}



実行結果は次のようになり、この方法はうまくいくことがわかる(ただし、「自分の家から近い順にソート」をするために、実際にはSortの機能をさらに組み合わせることになる。以下の実行結果はSortを使っていないのでソートされていない)。



すし (5,2) 1.0
すし (3,4) 1.0
すし (9,5) 1.0
すし (1,7) 1.0



DistanceHitCollectorの実装を検討

最後に、HitCollectorを拡張したDistanceHitCollectorを実装することを検討してみる。

HitCollectorを引数に取るsearch()メソッドでは、Queryの結果セットの文書すべてに対してHitCollectorのcollect()メソッドが呼ばれるため、「半径○km以内」の文書を確実に取得できることはプログラムを書くまでもなくわかる。しかも好きなようにソートも可能である(したがって、HitCollectorを引数に取るsearch()メソッドにはSortを引数に取るバージョンがない)。

DistanceHitCollectorのプログラムは次のようになる。



public class DistanceHitCollector extends HitCollector {

private List cache;
private IndexReader reader;
private double x;
private double y;
private double distance;
private int calledCount;

public DistanceHitCollector( IndexReader reader, int x, int y, int distance ){
cache = new ArrayList();
this.reader = reader;
this.x = (double)x;
this.y = (double)y;
this.distance = (double)distance;
calledCount = 0;
}

public void collect(int id, float score) {
calledCount++;
try{
Document doc = reader.document( id );
double d = calcDistance( doc );
if( d > distance )
return;
cache.add( new DocDistance( doc, d ) );
}
catch( IOException ignored ){}
}

private double calcDistance( Document doc ){
double side2X = side2( getX( doc ), x );
double side2Y = side2( getY( doc ), y );
return Math.sqrt( side2X + side2Y );
}

private double getX( Document doc ){
return Double.parseDouble( doc.get( "x" ) );
}

private double getY( Document doc ){
return Double.parseDouble( doc.get( "y" ) );
}

private double side2( double dist, double origin ){
return ( dist - origin ) * ( dist - origin );
}

public List getSortedDocDistanceList(){
Collections.sort( cache, new DistanceComparator() );
return cache;
}

public int getCalledCount(){ return calledCount; }

public static class DocDistance {
private Document document;
private double distance;
public DocDistance( Document document, double distance ){
this.document = document;
this.distance = distance;
}
public Document getDocument(){ return document; }
public double getDistance(){ return distance; }
}

static class DistanceComparator implements Comparator {
public int compare( DocDistance arg0, DocDistance arg1 ) {
if( arg0.getDistance() > arg1.getDistance() )
return 1;
else
return -1;
}
}
}



ただし、DistanceHitCollectorのcollect()メソッドが呼ばれる回数を最小限に抑えるために、使う場合は次のように
ConstantScoreRangeQueryと組み合わせる必要がある。これにより、DistanceHitCollectorは(最初の図の)斜線の部分だけを
はじくようになる。



protected void execQuery() throws IOException {
// IndexSearcherの取得
searcher = getIndexSearcher();
dhc = getDistanceHitCollector( searcher );
searcher.search( getQuery( "すし", 5, 5, 5 ), dhc );
}

private Query getQuery( String type, int x, int y, int distance ){
BooleanQuery query = new BooleanQuery();
Query tq = new TermQuery( new Term( "type", type ) );
query.add( tq, BooleanClause.Occur.MUST );
query.add( new ConstantScoreRangeQuery( "x", "00", "10", true, true ),
BooleanClause.Occur.MUST );
query.add( new ConstantScoreRangeQuery( "y", "00", "10", true, true ),
BooleanClause.Occur.MUST );
return query;
}

// 検索結果の表示
protected void printResults() throws IOException {
List hits =
dhc.getSortedDocDistanceList();
for( DistanceHitCollector.DocDistance docDistance : hits ){
Document doc = docDistance.getDocument();
double distance = docDistance.getDistance();
System.out.println( doc.get( "title" ) + "¥t" + distance );
}
searcher.close();
}

private DistanceHitCollector getDistanceHitCollector( IndexSearcher searcher ){
return new DistanceHitCollector( searcher.getIndexReader(), 5, 5, 5 );
}



実行結果(上記printResults()による検索結果の表示)は次のようになり、指定した距離(5)を超えるすし屋は含まれず、「自分の家(5,5)から近い順」にソートされていることがわかる。



すし (3,4) 2.23606797749979
すし (5,2) 3.0
すし (9,5) 4.0
すし (1,7) 4.47213595499958



まとめ

以上検討の結果、「半径○km以内」の文書を(他の検索条件とともに)検索するには、次の2つの方法で実現できることがわかった。

1.RadiusFilterを実装
2.DistanceHitCollectorを実装

1.の方法はFilterであるため、CachingWrapperFilterを使ってRadiusFilterを再利用できる場面であれば2.よりも有利であろう。しかし、無数のインターネットのWebサイト訪問者に同じ座標を中心とする「半径5km以内のレストラン」の情報を繰り返し提供する場面は考えにくいのでFilterのメリットは働かないのではないか。

2.の方法は距離を計算するために、collect()メソッド内でDocumentを読まなければならない点が1.と比べて不利である。ただし、距離の計算が一度で済み(1.ではFilterとSortで2回必要)、ソートまでできてしまう点と、Documentを読んでいるのでキャッシュできる点が魅力的である。検索結果の表示のことまで考えれば、円の中に含まれるレストランが数十軒のオーダーなら2.の方が速いかもしれない。

実際にどちらの方法を取るかは、案件ごとに計測するのが望ましい。考慮するパラメータには、次のようなものがあげられる。


  • インデックス内の総文書数

  • 円に含まれる平均の文書数

  • Filterが再利用できるアプリケーションかどうか


| 関口宏司 | Lucene自由自在 | 00:40 | comments(0) | trackbacks(3) |









http://lucene.jugem.jp/trackback/92
[MySQL][Senna][全文検索]MySQLのSpatial Data TypesとSenna全文検索の併用
MySQLのSpatial Extensions http://dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html を使って、 以下のブログで実現していることをMySQL + Sennaで実現できるのかな? http://lucene.jugem.jp/?eid=92
| グニャラくんのグニャグニャ備忘録@はてな | 2006/09/11 12:47 PM |
Lucene
BooleanQuery が TooManyClausesException を投げてきた・・・ なんだとー・・・! で、調べました。関口宏氏の Lucene ブログのエントリ: 「自分の家から一番近...
| aki note | 2006/12/15 12:14 AM |
CustomScoreQuery
LuceneのAPIでCustomScoreQueryなる便利なものがありました。 いつもお世話になっている関口さんのブログで以前 自分の家から一番近いレストランを探す(地理検索、地図検索) という記事が...
| mono-blog | 2008/01/31 12:02 PM |
+ Solrによるブログ内検索
+ PROFILE
      1
2345678
9101112131415
16171819202122
23242526272829
30      
<< September 2018 >>
+ LINKS
検索エンジン製品 - 比較のポイント
商用検索エンジンを購入した企業担当者は読まないでください。ショックを受けますから・・・
>>製品比較 10のポイント
+ Lucene&Solrデモ
+ ThinkIT記事
+ RECOMMEND
Apache Solr入門 ―オープンソース全文検索エンジン
Apache Solr入門 ―オープンソース全文検索エンジン (JUGEMレビュー »)
関口 宏司,三部 靖夫,武田 光平,中野 猛,大谷 純
+ RECOMMEND
Lucene in Action
Lucene in Action (JUGEMレビュー »)
Erik Hatcher,Otis Gospodnetic,Mike McCandless
FastVectorHighlighterについて解説記事を寄稿しました。
+ RECOMMEND
+ SELECTED ENTRIES
+ RECENT COMMENTS
+ RECENT TRACKBACK
+ CATEGORIES
+ ARCHIVES
+ MOBILE
qrcode
+ SPONSORED LINKS