GeoHashで範囲検索を行う

2019-12-10

前回の問題点

前回は2点間の距離を求めるアルゴリズムをいくつか紹介しました。 どのアルゴリズムでもデータが大量にあると全データとの距離計算が必要となり、現実的ではありません。 対策として考えられるのはなんらかの方法で大体で良いので一定距離以内のデータを取得し、そこから距離計算でソートするという方法でしょう。

ぱっと思いつくデータの高速検索と言えばHashです。理想的に作れば O(1) となるはずです。 Hashは特定のアルゴリズムで1意な値(ハッシュ値)に変換する技術ですが、通常元データが近い値でも全く異なるハッシュ値を生成します。 理想的に言えば、近いデータであれば近いハッシュ値を生成するハッシュ関数があれば良さそうです。 ただそれだけでは不十分で、距離でもフィルタ出来る事が必要です。

もちろんハッシュ以外の方法でも良いのですが、似たような仕組みが必要です。

非常に実現は難しそうですが、このようなアルゴリズムが既に存在しておりその内の 1 つが GeoHash です。

GeoHash

GeoHash (ジオハッシュ) はパブリックドメインになっているのが良い点です。 実装もさほど難しくはなく、また各言語でライブラリが実装されている事も珍しくありません。

サンプルとして東京大学を選びます。緯度が35.716701、経度が139.759556です。 (全国大学データより)

この位置情報を GeoHash 化すると xn77hq1bcewh という文字列になります。 GeoHash は xn77hq1bcewh -> xn77hq1bcew -> xn77hq1bce …と右桁から短くするすることにより範囲が広くなるという特徴があります これを地図上で表現するとこのようになります

サンプル画像

GeoHashのアルゴリズム

Wikipedia にもありますが、デコードの方法からの解説となっておりエンコードの説明が無いため、エンコードの解説を行います

2分探索の経路をbit化する

緯度で計算を行います。

-90 〜 90 の間で2分探索を行います。 大きい場合は 1 、小さい場合は 0 とします。

つまり、 35.716701 は -90 〜 0 か 0 〜 90 のどちらの範囲に入るかというと 0 〜 90 ですので 1 が得られます。 次は 0 〜 90 の間ですので 0 〜 45 と 45 〜 90 の間ですので 0 〜 45 になります。つまり 0 となります。 これを必要な精度になるまで繰り返します

bit min 緯度 max
1 -90 35.716701 90
0 0.0 35.716701 90
1 0.0 35.716701 45.0
1 22.5 35.716701 45.0
0 33.75 35.716701 45.0
0 33.75 35.716701 39.375
1 33.75 35.716701 36.5625
0 35.15625 35.716701 36.5625
1 35.15625 35.716701 35.859375
1 35.5078125 35.716701 35.859375
0 35.68359375 35.716701 35.859375
0 35.68359375 35.716701 35.771484375
1 35.68359375 35.716701 35.7275390625
1 35.70556640625 35.716701 35.7275390625
0 35.716552734375 35.716701 35.7275390625
0 35.716552734375 35.716701 35.7220458984375
0 35.716552734375 35.716701 35.71929931640625
0 35.716552734375 35.716701 35.717926025390625
0 35.716552734375 35.716701 35.71723937988281
0 35.716552734375 35.716701 35.716896057128906
1 35.716552734375 35.716701 35.71672439575195
1 35.71663856506348 35.716701 35.71672439575195
0 35.716681480407715 35.716701 35.71672439575195
1 35.716681480407715 35.716701 35.716702938079834
1 35.716692209243774 35.716701 35.716702938079834
1 35.716697573661804 35.716701 35.716702938079834
0 35.71670025587082 35.716701 35.716702938079834
1 35.71670025587082 35.716701 35.71670159697533

得られた bit を並べると 1011001011001100000011011101 になります。

経度の場合は -180 〜 180 の間で計算を開始します。 同じく計算すると 11100011011000100111001101100 が得られます。

得られたbit列を交互に並べる

得られたbit列を交互に並べます。順番は経度、緯度の順番です

経度: 11100011011000100111001101100

緯度: 1011001011001100000011011101

これを交互に並べるこのようになります。

111011010000111001111000010110000010101001011011011110010

このbit列を5つ毎に分割します

["11101", "10100", "00111", "00111", "10000", "10110", "00001", "01010", "01011", "01101", "11100", "10"]

最後が5桁に足りないので0で埋めます

["11101", "10100", "00111", "00111", "10000", "10110", "00001", "01010", "01011", "01101", "11100", "10000"]

Base32 にエンコードする

得られた5桁の2進数を10進数化します

[29, 20, 7, 7, 16, 22, 1, 10, 11, 13, 28, 16]

これを以下のtableに従って変換すると xn77hq1bcewh が得られます

数値 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Base32 0 1 2 3 4 5 6 7 8 9 b c d e f g


数値 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Base32 h j k m n p q r s t u v w x y z

これが理解できればデコードは逆に行えば良いですし、 Wikipedia の記事も理解しやすいはずです。

GeoHashの実装

エンコード部分を Ruby で実装したのがこちらです。

class GeoHash
  def initialize(latitude, longitude)
    @latitude = latitude
    @longitude = longitude
  end

  def encode
    lat_string = convert_byte_string(@latitude, -90, 90, range(@latitude))
    lon_string = convert_byte_string(@longitude, -180, 180, range(@longitude))

    calc_hash(lat_string, lon_string)
  end

  private
  def range(val)
    range = 10 ** (val.to_s.split('.')[-1].size * -1)
    range = [range, 10 ** -6 ].max
  end

  def convert_byte_string(val, min, max, range)
    mid = (min + max).to_f / 2

    bit = val > mid ? 1 : 0

    if bit == 0
      max = mid
    else
      min = mid
    end

    if (min - max).abs <= range
      bit.to_s
    else
      ret = convert_byte_string(val, min, max, range)
      bit.to_s + ret.to_s
    end
  end

  def base32_table
    {
      0=>'0', 1=>'1', 2=>'2', 3=>'3', 4=>'4', 5=>'5', 6=>'6', 7=>'7', 8=>'8', 9=>'9', 10=>'b',
      11=>'c', 12=>'d', 13=>'e', 14=>'f', 15=>'g', 16=>'h', 17=>'j', 18=>'k', 19=>'m', 20=>'n',
      21=>'p', 22=>'q', 23=>'r', 24=>'s', 25=>'t', 26=>'u', 27=>'v', 28=>'w', 29=>'x', 30=>'y', 31=>'z',
    }
  end

  def calc_hash(latitude, longitude)
    bytes = longitude.chars.zip(latitude.chars).flatten.join
    bytes = bytes.chars.each_slice(5).map(&:join)
    bytes[-1] = "#{bytes[-1]}00000"[0, 5]

    values = bytes.map{|v|Integer("0b#{v}")}

    return values.map{|v|base32_table[v]}.join
  end
end

geohash = GeoHash.new(35.716701,139.759556)
puts geohash.encode # => u4pruydqqvh

桁数と範囲

すでに紹介した通りGeoHashは桁数と範囲が比例して狭くなります 範囲はこのようになります

桁数 南北の距離 東西の距離
1 4989600.00m 4050000.00m
2 623700.00m 1012500.00m
3 155925.00m 126562.50m
4 19490.62m 31640.62m
5 4872.66m 3955.08m
6 609.08m 988.77m
7 152.27m 123.60m
8 19.03m 30.90m
9 4.76m 3.86m
10 0.59m 0.97m

4桁で都道府県ほど、5桁で市区町村ほどの範囲となりますのでこの辺りが良く使う桁数となるでしょう

ライブラリ

Ruby であればこの辺りが有名なようです

Pythonでは python-geohash が有名なようですね

たださほど難しくもなく一度作ればそれで終わりですので、ライブラリによっては更新も無いものも多いでしょう。 自前で作成しても良いかもしれません。

まとめ

GeoHashは便利ですが問題点もあります

  • bit数が5となっており、精度によって縦長、横長となる
  • そもそも長方形なので特定の点からの一定距離でデータが欲しい場合に外れるデータが出てくる
  • 精度による範囲の細かいコントロールが難しく、サービスによっては細かな検索には不向き

次回は同様の範囲検索が可能なアルゴリズムを紹介します