GeoHashの原理と、原理に立ち戻った故の喜び

GeoHash、いいですよね。

地図で検索したいけど座標が緯度経度の二変数で表されるせいで範囲検索難しいぜ！を、一つの文字列として表す事で、範囲検索できるぜ！に変えてくれるアレです。  

今回はそんなgeoHashの基礎原理とちょっと面白い応用について書いていきまっす！！

geoHashってなんだぜ？ な方は [[特徴](#特徴)] から
geoHash、あーアレか。 な方は [[原理](#原理)]から
はいはい二進数二進数。 な方は [[喜び](#喜び)]を読んでいただけたらなと思います。

# 特徴
まず実例をみてみます。

|xn76utyn|
|:---:|
|<img width="300" alt="スクリーンショット 2019-12-05 21.19.32.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/266081/31e9f674-aa72-883d-e768-20307e96ef4e.png">|

こんな感じで、 **数字とアルファベットの組み合わせ(`xn76utyn`)が、ある一定の範囲を示します** 。

文字列であらわすことで、DBにて文字列検索をするだけで範囲検索が可能になります。

英数字の**桁数が範囲の細かさを表しており**、末尾の桁を一つなくすと**32倍**になります。
実際に、末尾の文字を1、2こ消したものは下のようになります。

|xn76uty|xn76ut|
|:---:|:---:|
|<img width="300" style="float-left" alt="スクリーンショット 2019-12-05 21.19.53.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/266081/b7aab64c-2b38-87dc-4bbe-965627b180b8.png">|<img width="300" style="float" alt="スクリーンショット 2019-12-05 21.20.16.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/266081/5c84c028-22c2-38cd-b78d-2a017b21d1dd.png">|

**隣接したものは似た値になることが多い**ですが、**全然異なることも**多々あります。
`xn76utyn`の右隣は`xn76utyp`だけど、例えば兵庫県のある地域においては以下のように全然違うgeoHashが隣接しています。

|兵庫県のどこか{ lat:34.82072648783, lng:134.99983199531 }|
|:---:|
|<img width="564" alt="スクリーンショット 2019-12-05 21.33.48.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/266081/871c8651-7dbb-8b6c-95c1-2e0f4d8c4a57.png">|

`英数字で表す`,`一桁けすと32倍の範囲になる`,`近い場所は似た値になる`
この三つがgeoHashの主な特徴です。
なぜこのような特徴になるのか、geoHashの原理を知り、考えていきたいと思います。


# 原理
一言で言うと、`世界地図を緯度経度で2分割していき、北（東)を1,南(西)0を当てた二進数を32進数化したもの`です。

実際に一桁のgeoHash`x`を得るまでの流れをみていきます

<img width="311" alt="スクリーンショット 2019-12-06 21.52.19.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/266081/2da10b9d-52f9-e099-3982-d9f3b8780bef.png">

世界地図を経度と緯度を順に分割していって、真ん中より値が大きいか小さいかで1 or 0 を当てていきます。
下の画像みたいな流れを行います。


<img width="600" alt="スクリーンショット 2019-12-06 22.28.24.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/266081/0f6e6678-ab1b-c857-94ff-2c6e8f79db1b.png">

得られた`11101`を二進数として、10進数に直してから、下の表を元に文字に変換します。
(変換の際に少し違う表を利用しているサイトもあります。以下の表はwikiったものです。base32です。)

| こんな | 感じ | に | 変換 |
|:--|:--|:--|:--|
| 0=>0 | 8=>8 | 16=>h | 24=>s |
| 1=>1 | 9=>9 | 17=>j | 25=>t |
| 2=>2 | 10=>b | 18=>k | 26=>u |
| 3=>3 | 11=>c | 19=>m | 27=>v |
| 4=>4 | 12=>d | 20=>n | 28=>w |
| 5=>5 | 13=>e | 21=>p | 29=>x |
| 6=>6 | 14=>f | 22=>q | 30=>y |
| 7=>7 | 15=>g | 23=>r | 31=>z |

`11101(2)` => `29` => `x` と得ることができました。

このように、アルファベット(英数字)一文字は2分割を五回行なった結果であるので、
geoHashの`一文字増えるごとに2^5=32分割される`という特徴が自然と導かれます。

`隣接した値が近くなる`理由も、分割によって出現した二つの領域は末尾の`0,1`だけが異なることで説明され、
`隣接した値が全然違う`ことになる理由も、分割していくはじめの方の段階で`1,0`が分かれてしまったら、得られる32進数も大きく変わるはずということで説明できます。

以上がgeoHashの原理です。
原理を知ったことで次から書く、`喜び`を得ることができます！
# 喜び

便宜上、geoHashの元となった二進数をgeoBinaryと呼ぶことにします。(かっこいい名前あったら教えてください)

### 精度
geoHashは一桁追加するだけで`1/32`の面積に絞りこんじゃってました。
`日本`全体で検索して、少し絞って`東日本`を検索しようとしたら、一気に`東京・埼玉`まで絞りこんじゃったみたいな感じです。嫌ですね。
でもgeoBinaryなら`1/2`の絞り込みだから、`東日本`の検索ができます。

ﾍｲｼｬ周りをgeoBinaryとgeoHashで表し、比較してみました。

```
geoHash: `xn76utyn`と1文字消去
geoBinary: `1110110100001110011011010110011111010100`から1~5文字消去
```

|geoHash|geoBinary|
|:---:|:---:|
|<img width="275" alt="スクリーンショット 2019-12-06 0.33.27.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/266081/acc12f7b-2b78-19bb-b68e-bb0fe5d1cfab.png">|<img width="270" alt="スクリーンショット 2019-12-06 0.27.49.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/266081/1ebbd767-ef7a-b806-3fb8-dd5e881ebe4e.png">|

大分精度が向上していることが明らかですね。


### 隣接
隣接した領域を調べることも。geoBinaryだったら簡単にできます。

geoBinaryは経度緯度を交互に分割する、即ち`経度は奇数桁`、`緯度は偶数桁`に対応することになります。

あるgeoBainary`001011`があったとして、経度`011`、緯度`001`に分けられる。
右(東)側に行けば行くほど経度に関するbit列は大きく、上(北)に行けば行くほど緯度に関するbit列は大きくなるはず。
帰納的に考えると、経度`011`の一つ右は1を足して`100`、一つ左は1を引いて`010`
つまり、下のような隣接した範囲が簡単に計算できます。

<img width="473" alt="スクリーンショット 2019-12-06 0.01.33.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/266081/10c10578-4a87-24c9-068b-b0e77a6d6245.png">

これによって、ある領域の近傍に存在する領域を容易に求めることができます。

### 検索

#### ・伸縮
検索方法も面白いことができます。

DBへの保存の際に、各桁をそれぞれのカラムに保存する設計にすると、次のコードのように、ある桁を飛ばした検索ができるようになります。

```js
geoBinary: {
  digit_1: 0,
  digit_2: 1,
  digit_3: 0,
  digit_4: 0,
  ......
}

where('digit_1 = 0').where('digit_2 = 1').where('digit_4 = 0')
```

whereを飛ばした桁においては分割を無視しているという事を意味し、下図のように`奇数or偶数桁`の末尾を何個か飛ばして検索する事で、geoHashでは実現できなかった、細長い領域の検索を一つのクエリで行えます。(※活用法は不明)
(省略しますが、飛ばす桁を変える事でブラインド模様や市松模様でも検索できます。(※活用法は不明))


```js
1: [1,1,1,0,1,1,0,1,0,0,0,0,1,1,1,0,0,1,1,0,1,1,0,1,0,1,1,0,0,1,1,1,1,1,0,1,0,1,0,0]
2: [1,1,1,0,1,1,0,1,0,0,0,0,1,1,1,0,0,1,1,0,1,1,0,1,0,1,1,0,0,1,1,1,1,1,0,1,0,1,0, ]
3: [1,1,1,0,1,1,0,1,0,0,0,0,1,1,1,0,0,1,1,0,1,1,0,1,0,1,1,0,0,1,1,1,1,1,0,1,0, ,0, ]
4: [1,1,1,0,1,1,0,1,0,0,0,0,1,1,1,0,0,1,1,0,1,1,0,1,0,1,1,0,0,1,1,1,1,1,0, ,0, ,0, ]
5: [1,1,1,0,1,1,0,1,0,0,0,0,1,1,1,0,0,1,1,0,1,1,0,1,0,1,1,0,0,1,1,1,1, ,0, ,0, ,0, ]
```

|1|2|3|4|5|
|:---:|:---:|:---:|:---:|:---:|
<img width="400" alt="スクリーンショット 2019-12-06 20.34.49.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/266081/f2c170b5-32db-8d1f-e6e0-2a8c1fdf1c92.png">|<img width="400" alt="スクリーンショット 2019-12-06 20.35.22.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/266081/eba43327-db4e-3c03-1908-82ea568b52be.png">|<img width="400" alt="スクリーンショット 2019-12-06 20.36.32.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/266081/884dbd8d-f9ab-edce-5244-1bfb8e46711a.png">|<img width="400" alt="スクリーンショット 2019-12-06 20.36.50.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/266081/92ebf971-f3a0-f763-16da-4bc8cc48d52d.png">|<img width="400" alt="スクリーンショット 2019-12-06 20.37.50.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/266081/6d777f4f-788a-4c95-55a0-9bce5903c593.png">

#### ・結合

できるだけ少ないクエリで検索を行えるよう計算することも比較的容易です。
まず、表示している範囲内を一定の精度のgeoBinaryで埋めてみたものを考えます。

<img width="300" alt="スクリーンショット 2019-12-06 20.55.44.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/266081/5cd3809c-83f4-73a6-8554-7601147c6708.png">

この範囲全てを検索するには、`13 * 8 = 114`個のor検索が必要になりますが、一部DB(firestoreなど)では、一回に行える`or検索`の数が10個以下などに制限されているため、非常に検索の効率が悪い。

ここで隣り合うgeoBinaryを結合を試みます。
`[ソート => 連続した二つのgeoBainaryが、最後の桁以外一緒だった場合、最後の桁を消して一つにまとめる]`と言う手順を繰り返せば、無駄に細かい領域に分けずに済みます。

例えば、[`1110100, 1110101`, `1110110, 1110111`]の四つの範囲があったとして、
[`111010, 111011`]=>[`11101`]と、一つの範囲にまとめることができます。

実際に先ほどの分割領域を結合していったものは下のようになります。
(※下図は繰り返しの中の1手順の中で結合が10回以下しか行われなかった場合は繰り返しを止めています。)

<img width="300" alt="スクリーンショット 2019-12-06 20.56.58.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/266081/d64a7408-0d07-de7a-ce9c-3122627120d6.png">

検索すべき対象領域が少なくなりました。
(利用するDBによって、利点か否かが変わってくると思いますが、例えば僕が使っているfirestoreでは、12回の検索が必要だったものが、3回で完了できるようになっており、大きなコスト削減ができています。)

### 変換
geoBinaryはただのbit列なので、geoHashだけでなく他の形式への変換が非常に容易です。
例えば[whats3words](https://www.watch.impress.co.jp/docs/news/1154515.html)のような位置情報を単語で示すといったサービスも、単語リストとgeoBinaryを一定の桁をまとめて数値化したものとを結びつけることで容易に実装できます。

## 終わりに

最後の方は書きたい事を書きなぐってしまいました。。。
もし、geoHashを使って他にこういう面白いこともできるよ！みたいなことあったらぜひ教えてください！

駄文、乱文、乱文、乱文失礼しました。　ありがとうございました。 :bow:


##　参考
https://qiita.com/yabooun/items/da59e47d61ddff141f0c
http://saibara.sakura.ne.jp/map/convgeo.cgi