GeoHash 算法

计算「附近的人」,当数据量并发量很小的时候,我们可以直接在数据库中拿到所有点的经纬度信息,然后利用勾股定理依次计算两点间距离,排序。但是当你的数据库里有几百万个点的时候,为了提高系统性能,我们可以先以一个点为中心画一个圆,然后计算这个圆中的所有点的距离。但是MySQL的性能毕竟有限,如果并发量也上来呢?恐怕现在还没有那个系统有这么强悍的计算量,因此GeoHash应运而生。

简单来说,GeoHash可以理解为另一种地址编码方式,它将二维空间的经纬度数据编码成一个字符串,字符串的二进制码值越接近,也说明两个点的实际距离约接近(存在一定的误差)。

注意:GeoHash值表示的是一个矩形区域,hash值越长,矩形的范围越小。例如wx4g0ec1,编码wx4g0e表示的范围就比wx4g0ec1更大。所以GeoHash可以用来快速圈定给定坐标的附近坐标。

此外(题外话)使用GeoHash来表示位置信息,也有助于隐私保护。在线根据GeoHash转换经纬度:http://geohash.org/{GeoHash}

算法实现

将经纬度转换为二进制

比如(39.923201, 116.390705)这个点,纬度的范围是(-90,90),其中间值为0。对于纬度39.923201,在区间(0,90)中,因此得到一个1;(0,90)区间的中间值为45度,纬度39.923201小于45,因此得到一个0,依次计算下去,即可得到纬度的二进制表示,如下表:

geohash_4

最后得到纬度的二进制表示为:10111000110001111001

同理可以得到经度116.390705的二进制表示为:11010010110001000100

合并经度、纬度的二进制

将经度、纬度二进制按照奇偶位合并。

1
11100 11101 00100 01111 00000 01101 01011 00001

按照Base32进行编码

将上一步合并后的二进制数转换为十进制,然后生成对应的Base32码(0-9,a-z 去掉 a,i,l,o 四个字母)。同理,将编码转换成经纬度的解码算法与之相反,具体不再赘述。

geohash_base32

上述合并后的二进制编码后的结果为:

1
wx4g0ec1

由此可见编码越长,表示的范围越小,位置也越精确。
下表摘自维基百科

geohash_precision

可以看出,当geohash base32编码长度为8时,精度在19米左右,而当编码长度为9时,精度在2米左右,编码长度需要根据数据情况进行选择。

算法原理

为什么经纬度两串编码是交叉组合成一串编码的?

这就要从GeoHash算法编码原理的起源说起了,简称“二刀法”:将空间划分为四块,编码的顺序分别是左下角00,左上角01,右下脚10,右上角11,也就是类似于Z的曲线,当我们递归的将各个块分解成更小的子块时,编码的顺序是自相似的,每一个子块也形成Z曲线,这种类型的曲线被称为Peano空间填充曲线

geohash_1
geohash_2

但是Peano空间填充曲线最大的缺点就是突变性,有些编码相邻但距离却相差很远,比如0111与1000,编码是相邻的,但距离相差很大。

除Peano空间填充曲线外,还有很多空间填充曲线,如图所示,其中效果公认较好是Hilbert空间填充曲线,相较于Peano曲线而言,Hilbert曲线没有较大的突变。为什么GeoHash不选择Hilbert空间填充曲线呢?可能是Peano曲线思路以及计算上比较简单吧,事实上,Peano曲线就是一种四叉树线性编码方式。
geohash_3

使用问题

Geo 的数据使用单独的 Redis 实例部署,不使用集群环境。因为单个key的数据量有可能很大,不利于集群的迁移。为了降低单个zset集合的大小,可以将数据按国家拆分、按省拆分、按市拆分。(每个省市拆分的时候,记得对边缘点进行一些冗余存储)。

矩形边缘点问题

将其相邻的8个区域的点也都加进来,一起算距离。然后排序。

曲线突变问题

Peano空间填充曲线,这种曲线会产生突变,造成了编码虽然相似但距离可能相差很大的问题,因此在查询附近餐馆时候,首先筛选GeoHash编码相似的POI点,然后再进行实际距离计算。

参考资料:

本文标题:GeoHash 算法

文章作者:NibNait  

发布时间:2019年07月07日 - 12:07

最后更新:2019年07月16日 - 02:07

原始链接:https://tianbin.org/learning/GeoHash/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%