なぜGeohashが必要なのか
地図上で検索してピンを立てる機能を作るのに必要
Geohash超概要
Geo: 地理情報（緯度経度）
Hash: 文字列に変換
つまり、緯度経度を文字列に変換したもの
検索システムの愚直な実装
愚直に検索システムを実装することを考える。
このような構成のテーブルを想定する。
地図の表示地点に近い店舗をSQLで検索する。
- 地図表示地点の緯度経度は map_center_lat, map_center_lng とする
- 表示領域は -Δlat ~ Δlat, -Δlng ~ Δlng とする
SELECT * FROM RESTAURANT
WHERE
map_center_lat > (lat - delta_lat) -- 緯度絞り込み1
AND map_center_lat < (lat + delta_lat) -- 緯度絞り込み2
AND map_center_lng > (lng - delta_lng) -- 経度絞り込み1
AND map_center_lng < (lng + delta_lng) -- 緯度絞り込み2
-- 今回は地理情報処理の話なので店舗の検索は省略
課題
- 条件式が4つ必要
- 範囲を絞り込むΔlat, Δlngが感覚的にわかりにくい
Geohashを使って検索システムを実装する
このような構成のテーブルを想定する。
地図の表示地点に近い店舗をSQLで検索する。
- 地図表示地点の緯度経度をエンコードしたものを map_geohash とする
SELECT * RESTAURANT
WHERE geohash = map_geohash
これだけで地図に表示されている座標のGeohashと同じ、つまり近い場所にあるものを検索することができる。
Geohashの桁数を落として検索すれば検索範囲を広げることができる。
実装して動かしてみる。
Geohash 計算方法
1. 緯度経度を二進数に変換
緯度は -90 ~ 90 のレンジがあるので、このレンジを二分探索する。
-90 ~ 90 の中間は0, ターゲットの値が右にあるので1桁目は 1 -- ①
0 ~ 90 の中間は45, ターゲットの値が左にあるので2桁目は 0 -- ②
必要な桁数まで繰り返す
つまり、桁が増えるごとに精度が倍々になる。
経度も同様の方法で算出する。
2. 二進数の緯度経度をミックス
二進数緯度と二進数経度をミックスして一つにする。
緯度は奇数ビット、経度は偶数ビット
3. Base32 でエンコーディング
2でミックスした二進数を5ビットずつに区切ってBase32でエンコーディングする
011100001011010
↓
01110 / 00010 / 11010
↓
OC2
ref: RFC3548 https://datatracker.ietf.org/doc/html/rfc3548
Geohash のエレガントさ
- 「ある座標に近いものを検索する」という複雑な問題を「同じ文字列を検索する」という単純な問題に置き換えることができる
- 検索文字列を短くすれば広範囲、長くすれば狭い範囲の検索ができる
- 感覚的にわかりやすい
- Geohashにインデックスを貼ることで検索の高速化ができる
- 緯度経度表現より桁数が短くなる
- 東京都庁
- 35.6896068,139.6891424
- xn7749ke
ちなみに、GoogleではPlus codeというジオエンコーディングが用いられており、これはGeohashと似たような性質を持つ。
