周围的餐馆有哪些？GeoHash算法
来源：http://t.cn/EbMSD2A
geohash-feature
当今年代，每个人都有智能手机，出门在外，自然离不开使用手机地图了，查找附近的餐馆，附近的地铁站，非常方便，可是在这项技术背后又隐藏着什么算法呢？这篇博客将会讲述这个技术背后的GeoHash算法以及基本的实现。
首先既然算法名字叫做GeoHash了那么对单词比较敏感的人可能已经猜出来了，差不多就是对当前的位置生成一个Hash值，然后再比较相似吧，是的，大概就是这个样子。
GeoHash的原理就是讲一个地理位置的经纬度，转换成一个可以排序，可以比较的的Hash字符串。这个字符串。
GeoHash代表的不是一个精确地的标，而是一个区域，当Hash值越长的时候，这个hash代表的区域越小，就越精确，比如 wtw3eegq 这个Hash就是上海南京西路周围的的一块，但是 只有前6位 wtw3ee 的话这个Hash代表的区域面积就比 wtw3eegq要大，但是 wtw3eegq 是包扩在 wtw3ee 这个区域里面的，所以可以用这个特性来查找一个坐标周围的餐馆之类的地方。
GeoHash就是这样，他将地球首先分为四个象限，之后每一象限再平分为四个象限，就是这样无限细分下去，这样，地球就根据坐标分为了若干区域，每个区域都会根据算法来生成一个Hash值，Hash值越相似就代表两个区域的位置越近。
Screen Shot 2016-05-06 at 10.47.20 PM
ProximityChat
接下来将会讨论这个算法的具体细节：
- 计算纬度
比如我们需要计算 坐标 121.443469, 31.22246 的GeoHash值
首先将纬度范围(-90, 90)平分成两个区间(-90,0)、(0, 90)，如果目标纬度位于前一个区间，则编码为0，否则编码为1。
由于31.22246属于(0, 90)，所以取编码为1。
然后再将(0, 90)分成 (0, 45), (45, 90)两个区间，而31.22246位于(0, 45)，所以编码为0。
就和中学时代学过的二分法解方程一样简单，对吧~
以此类推，直到精度符合要求为止，得到编码为1010 1100 0110 0111 1100 ，下面的表只是计算了前8位，可以看出，二分次数越多，取得的值就越精确。
left | mid | right | bit |
|---|---|---|---|
-90 | 0 | 90 | 1 |
0 | 22.5 | 45 | 0 |
22.5 | 33.75 | 45 | 1 |
22.5 | 30 | 37.5 | 0 |
30 | 33.75 | 37.5 | 1 |
30 | 31.875 | 33.75 | 1 |
30 | 30.9375 | 31.875 | 0 |
30.9375 | 31.40625 | 31.875 | 0 |
接下来看经度
- 计算经度
首先将经度范围(-180, 180)平分成两个区间(-180,0)、(0, 180)，如果目标经度位于前一个区间，则编码为0，否则编码为1。
由于121.443469属于(0, 180)，所以取编码为1。
然后再将(0, 180)分成 (0, 90), (90, 180)两个区间，而121.443469位于(90, 180)，所以编码为1。
以此类推，直到精度符合要求为止，得到经度编码为1101 0110 0101 1100 0001 ，下面的表只是计算了前8位。
left | mid | right | bit |
|---|---|---|---|
-180 | 0 | 180 | 1 |
0 | 90 | 180 | 1 |
90 | 135 | 180 | 0 |
90 | 112.5 | 135 | 1 |
112.5 | 123.75 | 135 | 0 |
112.5 | 118.125 | 123.75 | 1 |
118.125 | 120.9375 | 123.75 | 1 |
120.9575 | 122.35375 | 123.75 | 0 |
- 经度纬度合并
接下来将经度和纬度的编码合并，奇数位是纬度，偶数位是经度
10101100011001111100 和 11010110010111000001 合并为： 1110011001111000001101101011010101010010
- Base32编码转换
得到合并后的编码之后，每5位一看，转换为十进制，之后按照Base32的编码表来转换为Base32编码
Decimal | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
Base32 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
Decimal | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
Base32 | 8 | 9 | b | c | d | e | f | g |
Decimal | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
Base32 | h | j | k | m | n | p | q | r |
Decimal | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
Base32 | s | t | u | v | w | x | y | z |
刚才合并的编码为：1110011001111000001101101011010101010010
将他分为11100、11001、11100、00011、01101、01101、01010、10010
十进制为：28, 25, 28, 3, 13, 13, 10, 18
根据编码表转换后的Base32编码值为 wtw3eebk
这个值：wtw3eebk 就是坐标121.443469, 31.22246 的GeoHash值
这样的话只要在坐标入库的时候程序顺便算出坐标的GeoHash值一并入库，就可以实现快速进行周边餐馆查找之类的功能了。
- 测试
为了看一下这个算法的可行性，我写了一个爬虫来访问高德地图来不断检索地址并且算出Geohash（文章最后会给出整个爬虫和算法的代码）
posi
我生成的GeoHash是8位的，通过匹配前6位：wtw3ef，来进行查找，匹配出了下面的餐馆
热辣壹号(淮海中路百盛店) 淮海中路918号百盛商场8层 121.459133,31.217455 wtw3efgy
伊秀寿司(淮海店) 淮海中路918号淮海百盛8层(久事复兴大厦) 121.459291,31.217210 wtw3efgv
丸龟制面(淮海百盛店) 淮海中路918号百盛购物中心B1楼13铺(近陕西南路) 121.459274,31.217533 wtw3efgz
查厘士港式餐厅(淮海中路黄金店) 淮海中路988黄金世界3层 121.458316,31.216696 wtw3efg4
九久日本料理(淮海店) 淮海中路939号巴黎春天百货5楼(地铁1号线陕西南路站) 121.459520,31.216730 wtw3efu4
通过地址可以看出来这几个餐馆都是位于淮海中路上的。
和高德地图检索周边出来的餐馆差不多：
Screen Shot 2016-05-06 at 11.42.00 PM
下面是GeoHash的精度表：
GeoHash长度 | Lat位数 | Lng位数 | Lat误差 | Lng误差 | km误差 |
|---|---|---|---|---|---|
1 | 2 | 3 | ±23 | ±23 | ±2500 |
2 | 5 | 5 | ± 2.8 | ±5.6 | ±630 |
3 | 7 | 8 | ± 0.70 | ± 0.7 | ±78 |
4 | 10 | 10 | ± 0.087 | ± 0.18 | ±20 |
5 | 12 | 13 | ± 0.022 | ± 0.022 | ±2.4 |
6 | 15 | 15 | ± 0.0027 | ± 0.0055 | ±0.61 |
7 | 17 | 18 | ±0.00068 | ±0.00068 | ±0.076 |
8 | 20 | 20 | ±0.000086 | ±0.000172 | ±0.01911 |
9 | 22 | 23 | ±0.000021 | ±0.000021 | ±0.00478 |
10 | 25 | 25 | ±0.00000268 | ±0.00000536 | ±0.0005971 |
11 | 27 | 28 | ±0.00000067 | ±0.00000067 | ±0.0001492 |
12 | 30 | 30 | ±0.00000008 | ±0.00000017 | ±0.0000186 |
Github链接
这个项目中有我写的爬虫，查询类和Geohash，Base32相关类
爬虫读取后存为txt，之后查询的时候读取txt作为临时数据库
nearbyfinder