geohashは文字列で付近の低点検索を実現する
5367 ワード
転載:http://tech.idv2.com/2011/07/05/geohash-intro/
geohashは2次元の緯度を1次元の文字列に符号化できるアドレス符号化である.例えば、北海公園のコードはwx 4 g 0 ec 1です.
geohashには以下の特徴があります.
まず、geohashは経度と緯度の2つの座標を1つの文字列で表す.2つのカラムにインデックスを同時に適用できない場合(例えばMySQL 4以前のバージョン、Google App Engineのデータ層など)、geohashを利用して、1つのカラムにインデックスを適用するだけでよい場合があります.
次に,geohashは点ではなく矩形領域を表す.例えば、wx 4 g 0 ec 19が符号化され、矩形領域を表す.利用者はアドレスコードを公開することができ、北海公園の近くにいることを示すだけでなく、自分の正確な座標を暴露することもなく、プライバシー保護に役立つ.
第三に、符号化プレフィックスは、より大きな領域を表すことができる.例えばwx 4 g 0 ec 1であり、そのプレフィックスwx 4 g 0 eは、wx 4 g 0 ec 1を符号化することを含むより広い範囲を表す.このプロパティは、近くの場所の検索に使用できます.まず、ユーザの現在の座標に基づいてgeohash(例えばwx 4 g 0 ec 1)を計算し、そのプレフィックスを取ってクエリー(
SELECT * FROM place WHERE geohash LIKE 'wx4g0e%')を行い、近くのすべての場所をクエリーすることができる.geohashのアルゴリズム
以下、(39.9324,116.3906)を例に、geohashの符号化アルゴリズムについて説明する.まず緯度範囲(-90,90)を2つの区間(-90,0)、(0,90)に分け、目標緯度が前の区間にある場合は0、そうでない場合は1として符号化する.39.92324は(0,90)に属するため、符号化は1とする.その後、(0,90)を(0,45)、(45,90)の2つの区間に分け、39.9324は(0,45)に位置するので、0と符号化される.このようにして、精度が要求に合致するまで緯度符号化は1011 1000,10111,1001となる.
緯度範囲
区分区間0
区分区間1
39.92324所属区間
(-90, 90)
(-90, 0.0)
(0.0, 90)
1
(0.0, 90)
(0.0, 45.0)
(45.0, 90)
0
(0.0, 45.0)
(0.0, 22.5)
(22.5, 45.0)
1
(22.5, 45.0)
(22.5, 33.75)
(33.75, 45.0)
1
(33.75, 45.0)
(33.75, 39.375)
(39.375, 45.0)
1
(39.375, 45.0)
(39.375, 42.1875)
(42.1875, 45.0)
0
(39.375, 42.1875)
(39.375, 40.7812)
(40.7812, 42.1875)
0
(39.375, 40.7812)
(39.375, 40.0781)
(40.0781, 40.7812)
0
(39.375, 40.0781)
(39.375, 39.7265)
(39.7265, 40.0781)
1
(39.7265, 40.0781)
(39.7265, 39.9023)
(39.9023, 40.0781)
1
(39.9023, 40.0781)
(39.9023, 39.9902)
(39.9902, 40.0781)
0
(39.9023, 39.9902)
(39.9023, 39.9462)
(39.9462, 39.9902)
0
(39.9023, 39.9462)
(39.9023, 39.9243)
(39.9243, 39.9462)
0
(39.9023, 39.9243)
(39.9023, 39.9133)
(39.9133, 39.9243)
1
(39.9133, 39.9243)
(39.9133, 39.9188)
(39.9188, 39.9243)
1
(39.9188, 39.9243)
(39.9188, 39.9215)
(39.9215, 39.9243)
1
経度も同様のアルゴリズムで(−180,180)を順次細分化し,116.3906の符号化を1101 0010 1100 0100 0100とした.
経度範囲
区分区間0
区分区間1
116.3906所属区間
(-180, 180)
(-180, 0.0)
(0.0, 180)
1
(0.0, 180)
(0.0, 90.0)
(90.0, 180)
1
(90.0, 180)
(90.0, 135.0)
(135.0, 180)
0
(90.0, 135.0)
(90.0, 112.5)
(112.5, 135.0)
1
(112.5, 135.0)
(112.5, 123.75)
(123.75, 135.0)
0
(112.5, 123.75)
(112.5, 118.125)
(118.125, 123.75)
0
(112.5, 118.125)
(112.5, 115.312)
(115.312, 118.125)
1
(115.312, 118.125)
(115.312, 116.718)
(116.718, 118.125)
0
(115.312, 116.718)
(115.312, 116.015)
(116.015, 116.718)
1
(116.015, 116.718)
(116.015, 116.367)
(116.367, 116.718)
1
(116.367, 116.718)
(116.367, 116.542)
(116.542, 116.718)
0
(116.367, 116.542)
(116.367, 116.455)
(116.455, 116.542)
0
(116.367, 116.455)
(116.367, 116.411)
(116.411, 116.455)
0
(116.367, 116.411)
(116.367, 116.389)
(116.389, 116.411)
1
(116.389, 116.411)
(116.389, 116.400)
(116.400, 116.411)
0
(116.389, 116.400)
(116.389, 116.394)
(116.394, 116.400)
0
次に、経度と緯度の符号化を組み合わせ、奇数ビットが緯度であり、偶数ビットが経度であり、符号化11100 11101,001,01111,00000,01101,01011,00001を得る.
最後に、base 32を0−9、b−z(a,i,l,oを除く)の32文字で符号化し、(39.9324,116.3906)の符号化wx 4 g 0 ec 1を得た.
じっしん
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
復号アルゴリズムは符号化アルゴリズムとは逆にbase 32復号を先に行い,その後経緯度を分離し,最後にバイナリ符号化に基づいて経緯度範囲を細分化すればよいが,ここでは後述しない.しかしgeohashは区間を表すため,符号化が長ければ長いほど正確であるが,完全に一致したアドレスを復号することは不可能である.
geohashの応用:近隣アドレス検索
geohashの最大の用途は近くのアドレス検索です.しかし,geohashの符号化アルゴリズムから,格子境界の両側に位置する2点は,非常に近いが符号化が全く異なるという欠点が見られる.実際の応用では,現在の格子の周囲の8個の格子を同時に探索することができ,この問題を解決できる.
geohashのpythonライブラリを例にとると、関連するgeohash操作は次のようになります.
>>> import geohash
>>> geohash.encode(39.92324, 116.3906, 5) # ，5
'wx4g0'
>>> geohash.expand('wx4g0') # wx4g0 8
['wx4ep', 'wx4g1', 'wx4er', 'wx4g2', 'wx4g3', 'wx4dz', 'wx4fb', 'wx4fc', 'wx4g0']
SELECT * FROM place WHERE geohash LIKE 'wx4g0%';