Groonga Advent Calendar 2016 12日目は、先月開催した新リリース自慢会で出てきた話題の1つを取り上げます。

Groongaの位置情報検索機能

Groongaは位置情報を使用した検索に対応しています。この機能は、ぐるなびの店舗検索のように「指定した地点の周囲にある地点のレコードを検索したい」という場面で使われます。

Groongaがどのように位置情報を保存して高速な検索を実現しているのかについては、以下の記事に図入りの詳しい解説がありますので、そちらも是非併せてご覧下さい。

groongaで高速な位置情報検索 - ククログ(2011-09-13)

様々な位置情報の表し方

Groongaは位置情報を緯度・経度の座標で表現します。しかし、位置にはそれ以外の表し方もあります。

地図上を一定の大きさの四角形で区切った「メッシュ」を単位とする表し方。
地図上を都道府県や市町村の境で区切った図形「シェイプ」を単位とする表し方。
「東京都豊島区南大塚3-29-9」のような住所表記。
京都での伝統的な「上ル」「下ル」のような交差点の曲がり方ベースでの住所表記。

ぐるなびの店舗検索のようなユースケースでは店舗の住所を緯度・経度へ変換してGroongaのデータベースに投入する必要がありますが、これは一般的な検索インデックス構築の際の「正規化（ノーマライズ）」にあたる操作と言えます。緯度・経度へ変換することさえできれば、Groongaはどんな位置情報でも容易に検索できると言えます。

Groongaで検索しにくいパターン

しかし、位置情報を使った検索には「地点ベースの検索」以外にも以下のようなパターンがあります。

ある地点の座標から、その地点が含まれるメッシュを特定する。
現在位置の座標から、都道府県・町名などを取得する（＝現在位置が含まれているシェイプを特定する）。

メッシュやシェイプは地点ではなく面積を持った範囲を表す物なので、地点をベースに検索するGroongaではうまく取り扱う事ができません。これはどういう事でしょうか。

ある特定の1つのメッシュやシェイプにその地点が含まれるかどうかの「当たり判定」は、メッシュと同じ大きさの矩形に地点が含まれるかどうかを検索すればできます。が、実際にはメッシュはたくさんあるので、メッシュの個数分だけ当たり判定を繰り返すのは効率が悪いです。これが、地点からそれが含まれるメッシュやシェイプを高速に見付けたいというニーズが生まれる理由です。

Groongaを使ってメッシュやシェイプとの当たり判定を効率よく行うためには、各メッシュ（シェイプ）の範囲内の地点をランダムにサンプリングして登録しておいたり、メッシュの四隅のように代表的な地点を登録しておいたりしてGroongaで「地点」として検索できるようにした上で、それらの点が確実に1つ以上含まれる大きさの円や矩形で検索し、ヒットした結果をさらに詳細に絞り込んでいく、というような工夫が必要になります。

住所表記の正規化

「上ル」「下ル」のような京都の伝統的な住所表記は碁盤の目状の町の作りに由来していますが、同じ地点を表すのに「この角を西に進んでから、次の角を北に進む」のと「この角を北に進んでから、次の角を西に進む」というような複数のルートがあり得ます。そのため、同じ住所なのに複数の表記が生まれることになります。

座標で検索する場合には問題ありませんが、住所表記で検索しようとすると表記に無数のパターンがあることが問題になります。なので、検索対象のデータも検索クエリも、「必ず先に北に進む」のようなルールに基づいて正規化しなくてはなりません。が、これを自動的に行うためには高度な判断が必要になってきます。

なお、Groongaには文字列の編集距離（文字列Aを何手改変すれば文字列Bに辿り着けるか、という形で2つの文字列の間の「似ている度合い」「異なっている度合い」を数値化した物）を使ったあいまい検索機能があります。京都の住所表記のような特異な例の正規化には利用できませんが、一般的な住所表記の多少の表記揺らぎはこれによっても吸収できるでしょう。

以上、Groonga Advent Calendar 2016 12日目としてGroongaの位置情報の取り扱いと地図情報の相性について述べました。引き続きGroonga Advent Calendarをお楽しみ下さい！