前回は、位置情報を数値型やGeometry型でデータベースへ保存する方法について解説しました。今回は、文字列としてデータベースへ保存する方法について解説します。

Geohash

文字列として扱うといっても、緯度経度をそのまま“⁠35.0116, 135.768⁠”という文字列として扱うわけではありません。緯度経度を文字列として表現する方法はいくつかありますが、今回はGeohashを紹介します。

Geohashは、地図上の矩形エリアをあるルールにしたがって、文字列化するという手法です。Geohashの値が「短く」なると矩形エリアは「広く⁠」⁠、値が「長く」なると矩形エリアは「狭く」なります。またGeohashには、先頭文字列が一致するGeohashの矩形エリアは、その一致している文字列が示す矩形エリアに内包されている、という特徴があります。

百聞は一見に如かず、ということで、例を見てみましょう。以下のテーブルの、Geohashという列にあるのがGeohashの値で、矩形エリア列にあるのが、そのGeohashが指す矩形エリア（赤色部分）になります。

No	Geohash	矩形エリア
1	xn76u
2	xn76u4
3	xn76u4z
4	xn76u4zs
5	xn76u4zsz

Geohashの桁が1つ増えると、その矩形エリアが32分割されます。図示すると、以下のようになります。

緑色の矩形のGeohashは“⁠xn76ukb⁠”⁠ となり、その下の赤い矩形はそれぞれ、“⁠xn76ukb[BASE32String]⁠”(※2)という8桁のGeohashになります。

Goehashは、緯度経度のような点の情報ではありませんが、その桁数が10桁を超えると、矩形の一辺が1m以下になるので、緯度経度の代わりとして十分利用可能です。

Geohashのエンコード・デコード方法については、以下のブログが参考になります。

• ゆろよろ日記「GeoHashのdecodeのアルゴリズムの解説します & ScalaのGeoHashライブラリを作ってみました(仮)」

上記ブログでは、Geohashのデコード方法が紹介されていますが、エンコードはデコードの逆の手順で実現できます。Geohashは、すでに各言語でライブラリが提供されているので、自分で一から実装しなくても、手軽に利用できます。

Geohashのライブラリ

提供されているGeohashのライブラリの、代表的なものを以下にまとめてみました。

その他の言語のライブラリについては、http://en.wikipedia.org/wiki/GeohashのExternal Linkの項を参照してください。

例えば、perlのCPANモジュール Geo::Hashを利用して、Goehashをencode/decodeする方法は、以下のようになります。

my $geohash = Geo::Hash->new;
my $hash = $geohash->encode( $lat, $lon );

my $geohash = Geo::Hash->new;
my ($lat, $lon) = $geohash->encode( $hash );

Geohashが注目された理由

Geohashが注目されたのは、Google App EngineのDatastoreでの「検索のクエリで絞り込み条件が指定できるカラムは1つだけ」という仕様がきっかけと言われています。

この仕様のため、緯度、経度を別のカラムで管理してしまうと、「⁠ある矩形エリア内のスポットの検索」ができなくなってしまいます。そこで、位置情報をGeohashで管理することで、検索時に文字列の前方一致を行い、スポットの絞り込みを実現する方法が注目されたというわけです。

Geohashをスポット検索に利用する

それでは、実際にスポット検索に利用してみましょう。ここでは、以下のようなgeoテーブルに位置情報が格納されていると仮定します。

CREATE TABLE geo (
geo_id INT NOT NULL,
name VARCHAR(255) NOT NULL,
geo GEOMETRY NOT NULL,
geohash CHAR(12) NOT NULL,
PRIMARY KEY (geo_id),
SPATIAL KEY (geo)
)ENGINE=InnoDB;

検索の手順は、例えば以下のようになります。

1. 検索の中心となる緯度経度をGeohashに変換する
2. 求められたGeohashの先頭6桁(XXXXXX)をとって、以下のSQLで検索する

SELECT * FROM geo WHERE geohash like ‘XXXXXX%’;

具体的な値を入れてみましょう。

検索の中心となる緯度経度は(35.65351281779606 , 139.75139379501343)とすると、Geohashは xn76u4ebg2xb になります。この値の先頭6桁である xn76u4 の矩形エリアが検索範囲になります。

これを図にすると以下のようになります。ピンが立っているところが、検索の中心点、赤いエリアが検索対象のエリアです。この赤いエリア内に存在するスポットが、近くのスポットとして検索されます。

一見、これでうまく行くように思えます。ここで、検索の中心点を変更してみましょう。

今度は、検索の中心となる緯度経度を (35.65527379152256 , 139.7567367553711)としてみます。このGeohashは、xn76u4zepbzb となり、先頭6桁をとると xn76u4 となるため、検索エリアは先程の中心点と同じになります。中心点と検索エリアの関係を図示すると以下のようになります。

先ほどと異なり、今度は検索の中心点としたいピンが、検索対象エリアの端にマッピングされてしまっています。これだと検索の範囲が偏ってしまい、以下の図のように、図の右上にある検索の中心点に近いスポットが検索されないことになります。

この問題に対応するために、検索対象のGeohashの周り8方向のGeohashを計算して、検索エリアをその8つのエリアを含めた範囲に拡張します。図にすると、以下のようになります。

検索範囲は広くなってしまいましたが、検索の中心点に近いスポットも、ちゃんと検索対象になりました。

検索するときのSQLは、以下のようなOR検索になります。便宜的にGeohashの最後の一桁を1から8までの数値にしていますが、実際はライブラリの関数などを利用して、中心となるGeohashの周り8方向のGeohashの値を計算しましょう。

SELECT * FROM geo
   WHERE
       geohash like ‘XXXXXXX%’ OR geohash like ‘XXXXXX1%’ OR geohash like ‘XXXXXX2%’
OR geohash like ‘XXXXXX3%’ OR geohash like ‘XXXXXX4%’ OR geohash like ‘XXXXXX5%’
OR geohash like ‘XXXXXX6%’ OR geohash like ‘XXXXXX7%’ OR geohash like ‘XXXXXX8%’;

ORのlike検索が、パフォーマンス的に気になる場合は、桁数を絞った検索用のgeohashのカラムを設けて、IN句で検索するという方法もあります。ただし、この場合は、検索対象のGeohashの桁数を柔軟に増減させるという方法は取れません。

SELECT * FROM geo
   WHERE
       geohash_for_search IN
      (‘XXXXXXX’ , ‘XXXXXX1’ , ‘XXXXXX2’ ,  ‘XXXXXX3’ , ‘XXXXXX4’ , ‘XXXXXX5’
, ‘XXXXXX6’ , ‘XXXXXX7’ , ‘XXXXXX8’);

Geohashまとめ

Geohashを使うときに、気をつけたいことをまとめます。

• Geohashの値が「短く」なると、指す矩形エリアは「広く⁠」⁠、値が「長く」なると、エリアは「狭く」なる
• Geohashの先頭からの文字列が一致する矩形エリアは、一致する文字列が指す矩形エリアに内包される
• Geohashを使ってスポットを検索するときは、9マスのGeohashを利用する

いつ、どの型を使うべきか

連載2回にわたり、数値型、平面空間型、文字列型とそれぞれのデータの保存方法を紹介してきました。それぞれのメリット、デメリット、どういうケースで使うと良いかをまとめると、以下のようになります。

はてなココでの事例

はてなココでは、データベース上にGeometry型のカラムと、文字列型のカラムを併存させるハイブリットな形を取っています。今自分がいる場所を中心として、近くのスポットをざっくりと検索したいときは、Geohashの検索を利用し、Google Map上にスポットをマッピングするときは、Geometry型のカラムを緯度経度の矩形エリアを指定して検索しています。

両方のカラムを保持するのは冗長ではありますが、位置情報サービスとして今後の機能拡張に柔軟に対応できるように、今の形にしています。

次回予告

第6回は、文字列として位置情報をデータベースに保存する方法を解説しました。次回は、連載の最終回「Googla App Engineを使って簡単な位置情報サービスを作ってみる」です。これまでの内容をおさらいしながら、実際に緯度経度を投稿するサービスを作ってみます。