查找附近的人: GeoHash算法

Author Avatar
AngelMsger 2月 25, 2018

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

GeoHash是什么

前段时间研究MongoDB, 发现MongoDB存在一种2d索引和一种2dsphere索引, 基于这两种索引可以对存储的数据进行进行一些Geo查询, 比如查找附近的餐馆, 地铁站等等, 很有意思也很方便. 之后就想知道背后的原理.

如果交给我这种过于相信机器计算能力的人, 就需要遍历所有的餐馆, 网吧和地铁站, 然后计算两点间的距离, 再将距离小于一定阈值的点罗列出来. 地铁站还好, 但是每个地方的餐馆, 网吧数量就很多了, 这种朴素算法的效率无法满足需求. 虽然我们可以进一步缩小范围, 毕竟我们已经知道了某一个要查找的点, 不过这种遍历所有点后一顿狂算的方式还是不怎么优雅.

说道快速查找与利用条件过滤, 不难联想到一个东西, 那就是索引. 我曾在[说说MySQL存储引擎, 索引及基本优化策略](../说说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编码是一个可逆的过程, 我们通过以上操作的逆操作可以得到某一编码所对应的经纬度范围.

GeoHash算法精度

根据维基百科的信息, 当编码长度为8时, 精度大约能够达到19米, 当编码长度达到9时就可以精确到2米了.

还有一个需要在实际实用中注意的点. 比如对应于某一区域内靠近边缘的点, 位于相邻区域内的某些目标肯能比本区域内的目标更加接近, 如果只在当前区域内查找则会得出一些不是非常理想的结果, 对于这钟情况, 我们通常会选择与当前区域相邻的其他8个区域参与计算.

参考资料

GeoHash核心原理解析

许可协议: CC BY-NC-SA 4.0
本文链接:https://blog.angelmsger.com/查找附近的人:GeoHash算法/