查找附近的人:GeoHash算法

Author Avatar
Vista Chyi 2月 25, 2018

GeoHash是一种快速查找附近单位的算法。

GeoHash是什么

前段时间研究MongoDB,发现MongoDB存在一种2d索引和一种2dsphere索引,基于这两种索引可以对一些存储的数据进行进行一些Geo查询,比如查找附近的餐馆,地铁站等等,很有意思也很方便。之后就想知道背后的原理,如果交给我这种倾向于相信机器计算能力的人,怕是要遍历所有的餐馆,网吧和地铁站,然后计算两点间的距离,再将距离小于一定阈值的点罗列出来。仔细想想这恐怕受不了,地铁站还好,但是每个地方不知道有多少餐馆,网吧啊,这算的效率实在太低了。虽然我们可以进一步缩小范围,毕竟我们已经知道了某一个要查找的点,不过这种遍历所有点然后一顿狂算的方式还是不怎么优雅。
说道快速查找与利用条件过滤,不难联想到一个东西,那就是索引。我曾在说说MySQL存储引擎,索引及基本优化策略利用相似哈希判断文本近似程度中提到,对于长而杂乱的字符串或结构复杂数据,我们可以通过某种编码方式,将其对应为易于索引的短串,就可以比较方便的进行比对和查找。地理位置信息与此类似,经纬度座标数据也具有上述特点,我们要想办法为他建立索引,使地理位置相近的点索引值也不会相差太多,方便我们快速某一个点查找附近的其他点。GeoHash正是这样一种算法。

GeoHash的实现原理

首先要说明的是,本文是我阅读了GeoHash核心原理解析后的总结,原文写的很好,也很直观,推荐阅读。本文接下来的部分也基本是原文的复述。
GeoHash算法的基本思想是将某一个区域映射为一个字符串,这个字符串有一些特点。比如对于区域的划分,可大可小,大区域可再分为小区域。对于有这样类似父子关系的区域,小区域与大区域应当有相同的前缀,而小区域对应的串应当大区域对应的串的基础上更长一些,多出的一些用以描述小区域相对于大区域的位置。也就是说,我们把所有要考虑的地方看成一个最大的区域,然后开始划分,在划分的结果中再划分,并不断映射为字符串,字符串越长,地理位置越精确。
所以我们始终是在以区域讨论问题,而不是某个具体的座标点。不过其实很多应用并不需要精确的位置信息,而且这样做有以下两方面的好处:

  1. 利于保护用户隐私,该区域内所有用户得到的索引值是相同的。
  2. 易于缓存,以区域作为缓存对象是更加高效的,同一区域内的请求可以共享结果,我们不能总是期待用户站在同一个精确点上发出请求。

我们根据索引后的字符串前缀来匹配POI(Point of Interest, 感兴趣的点,比如前文所述查找附近的餐馆和地铁站)信息,通过前缀长度不同控制粒度(范围),而相邻区域拥有相同的前缀,因为他们同属与同一个更大的区域。这样的查找是十分高效的。

举例

我们来讨论点更实际的。
我们知道地球的经度范围为[-180, 180),纬度范围为[-90, 90]。现在我们实用二分法,对经度和纬度进行划分,如果经纬度在划分后的左半区域,则写为0,右半区域则写为1。比如对于给定的经纬度(116.389550, 39.928167),我们得到如下序列:(1101001011,1011100011)。然后我们将两个二进制串合并,奇数放纬度,偶数放经度,则得到新串11100111010010001111。之后对此串进行Base32编码,就得到了最后的编码wx4g。Base32编码是一个可逆的过程,我们通过以上操作的逆操作可以得到某一编码所对应的经纬度范围。

根据维基百科的信息,当编码长度为8时,精度大约能够达到19米,当编码长度达到9时就可以精确到2米了。
还有一个需要在实际实用中注意的点。比如对应于某一区域内靠近边缘的点,位于相邻区域内的某些目标肯能比本区域内的目标更加接近,如果只在当前区域内查找则会得出一些不是非常理想的结果,对于这钟情况,我们通常会选择与当前区域相邻的其他8个区域参与计算。

参考资料

GeoHash核心原理解析

许可协议:署名-非商业性使用-相同方式共享
本文链接:https://blog.angelmsger.com/查找附近的人:GeoHash算法/