Geohashの原理、アルゴリズムと具体的な応用探究
Geohashは住所コードで、二次元の経緯度を一次元の文字列にエンコードすることができます。例えば、北海公園のコードはwx 4 g 0 c 1です。
Geohashの原理、アルゴリズム
以下は（39.9324，116.3906）を例にして、geohashの符号化アルゴリズムを紹介します。
まず緯度範囲(-90,90)を2つの区間(-90,0)、(0,90)に分け、目標緯度が前の区間にある場合は0として符号化します。そうでなければ1として符号化されます。39.9324は（0，90）に属しているので、符号化は1となる。その後、（0，90）を（0，45）、（45，90）の二つの区間に分け、39.2324は（0，45）に位置するので、0と符号化される。この類推により、精度が要求に適合するまでは、緯度符号化は1011,1100 0111 1001である。
緯度の範囲
区分区間0
区分区間1
39.924所属区間
(-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.023）
（39.923、40.0781）
1
（39.923、40.0781）
（39.903、39.902）
（39.902,40.0781）
0
（39.903、39.902）
（39.923、39.462）
（39.462,39.902）
0
（39.923、39.462）
（39.923、39.923）
（39.923,39.462）
0
（39.923、39.923）
（39.923、39.973）
（39.973、39.923）
1
（39.973、39.923）
（39.963,39.188）
（39.968,39.243）
1
（39.968,39.243）
（39.918、39.915）
（39.925、39.923）
1
経度も同じアルゴリズムで、（−180，180）を順次細分化し、116.3906の符号化を1101 0010 1100 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.32）
（115.32、118.125）
1
（115.32、118.125）
（115.32、116.78）
（116.78、118.125）
0
（115.32、116.78）
（115.32,116.015）
（116.015,116.78）
1
（116.015,116.78）
（116.015,116.367）
（116.367,116.78）
1
（116.367,116.78）
（116.367,116.42）
（116.522、116.78）
0
（116.367,116.42）
（116.367,116.455）
（116.455,116.42）
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 01111 00001 01101 01010111 0000 1を得る。
最後に、0-9、b-z（a、i、l、oを除く）の32文字でbase 32符号化を行い、（39.9324、116.3906）の符号化を得てwx 4 g 0 c 1とする。
十進数
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
base 32
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
base 32
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を使って近くの場所を調べます。文字列プレフィックスマッチングを使います。
Geohashの原理、アルゴリズム
以下は（39.9324，116.3906）を例にして、geohashの符号化アルゴリズムを紹介します。
まず緯度範囲(-90,90)を2つの区間(-90,0)、(0,90)に分け、目標緯度が前の区間にある場合は0として符号化します。そうでなければ1として符号化されます。39.9324は（0，90）に属しているので、符号化は1となる。その後、（0，90）を（0，45）、（45，90）の二つの区間に分け、39.2324は（0，45）に位置するので、0と符号化される。この類推により、精度が要求に適合するまでは、緯度符号化は1011,1100 0111 1001である。
緯度の範囲
区分区間0
区分区間1
39.924所属区間
(-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.023）
（39.923、40.0781）
1
（39.923、40.0781）
（39.903、39.902）
（39.902,40.0781）
0
（39.903、39.902）
（39.923、39.462）
（39.462,39.902）
0
（39.923、39.462）
（39.923、39.923）
（39.923,39.462）
0
（39.923、39.923）
（39.923、39.973）
（39.973、39.923）
1
（39.973、39.923）
（39.963,39.188）
（39.968,39.243）
1
（39.968,39.243）
（39.918、39.915）
（39.925、39.923）
1
経度も同じアルゴリズムで、（−180，180）を順次細分化し、116.3906の符号化を1101 0010 1100 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.32）
（115.32、118.125）
1
（115.32、118.125）
（115.32、116.78）
（116.78、118.125）
0
（115.32、116.78）
（115.32,116.015）
（116.015,116.78）
1
（116.015,116.78）
（116.015,116.367）
（116.367,116.78）
1
（116.367,116.78）
（116.367,116.42）
（116.522、116.78）
0
（116.367,116.42）
（116.367,116.455）
（116.455,116.42）
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 01111 00001 01101 01010111 0000 1を得る。
最後に、0-9、b-z（a、i、l、oを除く）の32文字でbase 32符号化を行い、（39.9324、116.3906）の符号化を得てwx 4 g 0 c 1とする。
十進数
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
base 32
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
base 32
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を使って近くの場所を調べます。文字列プレフィックスマッチングを使います。
SELECT * FROM place WHERE geohash LIKE 'wx4g0%';