前回は2点間の距離を求めるアルゴリズムをいくつか紹介しました。 どのアルゴリズムでもデータが大量にあると全データとの距離計算が必要となり、現実的ではありません。 対策として考えられるのはなんらかの方法で大体で良いので一定距離以内のデータを取得し、そこから距離計算でソートするという方法でしょう。
ぱっと思いつくデータの高速検索と言えばHashです。理想的に作れば O(1) となるはずです。 Hashは特定のアルゴリズムで1意な値(ハッシュ値)に変換する技術ですが、通常元データが近い値でも全く異なるハッシュ値を生成します。 理想的に言えば、近いデータであれば近いハッシュ値を生成するハッシュ関数があれば良さそうです。 ただそれだけでは不十分で、距離でもフィルタ出来る事が必要です。
もちろんハッシュ以外の方法でも良いのですが、似たような仕組みが必要です。
非常に実現は難しそうですが、このようなアルゴリズムが既に存在しておりその内の 1 つが GeoHash です。
GeoHash (ジオハッシュ) はパブリックドメインになっているのが良い点です。 実装もさほど難しくはなく、また各言語でライブラリが実装されている事も珍しくありません。
サンプルとして東京大学を選びます。緯度が35.716701、経度が139.759556です。 (全国大学データより)
この位置情報を GeoHash 化すると xn77hq1bcewh という文字列になります。 GeoHash は xn77hq1bcewh -> xn77hq1bcew -> xn77hq1bce …と右桁から短くするすることにより範囲が広くなるという特徴があります これを地図上で表現するとこのようになります
Wikipedia にもありますが、デコードの方法からの解説となっておりエンコードの説明が無いため、エンコードの解説を行います
緯度で計算を行います。
-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列を交互に並べます。順番は経度、緯度の順番です
経度: 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"]
得られた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 の記事も理解しやすいはずです。
エンコード部分を 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は便利ですが問題点もあります
次回は同様の範囲検索が可能なアルゴリズムを紹介します