GeoHash 指南

做任何跟地理位置相关的服务,位置如何表示及存储是绝对绕不开的问题之一。位置的表示倒是可以用经纬度,但是索引和检索的时候,经纬度这种二维表示法就比较麻烦了,这时我们就可以利用 GeoHash 进行『降维攻击』来解决这个问题了。


更新记录

  • 2016.09.07: 初稿

场景

前几年 LBS 的特性像一股龙卷风一样席卷了整个 App 圈,任何应用都迫不及待地加入了基于地理位置的相关特性。这之中一个非常火的功能就是——查看附近的人/地点/事情,比方说查看附近的餐馆、景点、朋友等等。那么问题就来了,怎么判断是不是附近呢?怎么样定义这个『附近』呢?

就用『附近的人』这个功能来举例,假如我要找自己身边的人,最简单粗暴的办法就是把我跟所有人的距离算一次,然后选一个阈值,在这个阈值范围内的,认为是『附近』。但是问题来了,如果我们的数据库中有一亿人,那不是每次都要计算一亿次?我们得想个办法减少计算量。

因为知道自己的经纬度,所以可以知道自己在哪里,比方说深圳市南山区,那么我只需要计算同在南山区的人即可,考虑到我可能在边界上,那么多加周边的几个区进行计算即可。这样一来就可以过滤掉大部分的无用计算了。

这种方式有一个问题,就是需要很多额外的信息,比方说我得知道南山区,不同国家不同地区各种区域划分,而且有时候区域还会变化(比方说萝岗和南沙并入广州),这样就引入了许多不必要的复杂度。不过即使如此,这种利用特定区域划分来减少计算范围的方法,非常有借鉴意义,类似于搜素剪枝,也就是索引。

原理

因为要使用索引的思想,那么就需要确定拿来建立索引的字段,可是经纬度这种二维的数据很难通过一维索引来高效检索,于是我们可以利用 GeoHash 来进行转换。

不过在此之前,我们先来看看另一个概念 —— 字典树 Trie

在计算机科学中,trie,又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。

这里我们需要在意的就是一点,相同父节点数目越多的子节点,从词的角度上相似度越高。接下来的 GeoHash 算法就部分满足这种特性。

在介绍具体的算法之前,我们先从较高层级来理解 GeoHash:

  • GeoHash 可以把经纬度转换成一个字符串,把二维变成一维
  • 每个 GeoHash 出来的字符串表示的是一个矩形区域,虽然不够精确,但是一定程度上反而能够保护隐私。Hash 值越长,表示的区域越小
  • 越往左的编码表示的范围越大,可以利用这个特性来缩小或扩大检索范围

比方说,北京城区的 GeoHash 大概是这样的(本文部分图片来源这里,感谢作者制图):

可以看到,每个格子都有一个编号,具体编号的顺序也有具体的算法,比较常用的是 Peano 曲线、Hilbert 曲线和 Z-order 曲线。

至于选择哪种算法,在地理位置相关的应用中,主要考虑的是实现的难度和区域的突变特性。这里以 Peano 填充曲线来做例子,具体的编码方式是从左下角开始的,然后逐步进行递归细化。

Peano 曲线的主要问题是突变性,比方说从 0111 到 1000,虽然数值只变了 1,但是具体的区域就是一上一下两个极端(观察上面图片 Hilbert 曲线的变化幅度就小很多)。

算法

了解了基本概念,现在我们可以来看看到底怎么把经纬度转换成 GeoHash 字符串了。主要分三个步骤:

  1. 分别计算经纬度,转换成二进制字符串
  2. 合并字符串并分组
  3. 根据编码表转换为 Base32 字符串

这里就以广州的坐标为例(北纬 23.1291,东经 113.2644),看看如何转换为 GeoHash 字符串。这里多说一句,纬度的范围是 [-90, 90],经度的范围是 [-180, 180],其中负数代表南纬和西经。

先来处理纬度 23.1291,下面的表格中左值和右值分别代表区间的范围,中值用作二分法,这里如果落在左值和中值之间,则对应位为 0,反之为 1:

左值 中值 右值
-90 0 90 1
0 45 90 0
0 22.5 45 1
22.5 33.75 45 0
22.5 28.125 33.75 0
22.5 25.3125 28.125 0
22.5 23.90625 25.3125 0
22.5 23.203125 23.90625 0
22.5 22.8515625 23.203125 1
22.8515625 23.02734375 23.203125 1

然后再来算经度 113.2644,同样的道理:

左值 中值 右值
-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 0
112.5 115.3125 118.125 0
112.5 113.90625 115.3125 0
112.5 113.203125 113.90625 1
113.203125 113.5546875 113.90625 0

组合一下,纬度的编码是 10100 00011,经度的编码是 11010 00010。我们需要把这两个字符串组合起来,奇数位放经度,偶数位放纬度(这里要注意,网上很多文章这里没有写对),组合起来就是 11100 11000 00000 01101,也就是 28 24 0 13,对照 Base32 编码

Decimal Base 32 Decimal Base 32 Decimal Base 32 Decimal Base 32
0 0 1 1 2 2 3 3
4 4 5 5 6 6 7 7
8 8 9 9 10 b 11 c
12 d 13 e 14 f 15 g
16 h 17 j 18 k 19 m
20 n 21 p 22 q 23 r
24 s 25 t 26 u 27 v
28 w 29 x 30 y 31 z

可以得到广州的坐标(北纬 23.1291,东经 113.2644)经过 GeoHash 之后的前四位是 ws0e,我们在 GeoHash 的官方网站 检验一下:

可以看到前四位确实是 ws0e,我们手算的结果是正确的!不过因为计算精度的问题,这里只算了前四位,实际上是可以根据我们的需要来进行更多位数的计算的,网页中的编码长度是 9 位,精度基本达到 2 米的数量级(8 位的话则是 19 米,7 位是 76 米,6 位是 610 米)。如果是要做『附近』功能的话,至少要到 6 位的精度。

应用

了解了具体的 GeoHash 算法之后,我们可以来看看具体在实际应用中可能遇到的各种问题:

  • GeoHash 编码对应的是矩形区域,在边界处需要处理临近区域,但是具体区域的编码并不完全跟 hash 之后的字符串一致(参考前面 0111 和 1000的例子)。为此,我们需要使用周围八个区域的 GeoHash 编码,通过有限扩大搜索范围的方法来解决这个问题
  • 如果是用传统关系型数据库,可以直接利用 GeoHash 的前缀进行检索,比方说 select * from locations where geohash like 'ws03%'
  • 如果需要兼顾速度与精确度,那么同时保存经纬度和 GeoHash 即可,利用 GeoHash 来缩小范围,再利用经纬度进行精确计算
  • 计算周围 8 个矩形区域,利用原始的 GeoHash 字符串显然是不行的(考虑分别处于赤道两边且很相近的两个点)对于经度一个维度来说,无论切分几次,它的左邻和右邻都只会和它相差1。画一下就知道它是一棵有序的01满二叉树。根据当前矩形的经度串,很容易就获得了它的两个东西邻接经度串。同理,可以根据其纬度串获取南北邻接纬度串。连同当前矩形的经度串和纬度串,就能组合得到周边的8个矩形的二进制串了。Base32 编码后的到 geohash 值,即是所需要的8个索引了(此段来源
  • Base32 是一种简单的加密算法,详情请参考后文链接

总结

本文我们见到了解了 GeoHash 的相关概念和应用,具体的使用过程中还需要根据具体需求来进行调整(比方说不同的曲线填充算法),但是要保证具体实现的一致性。

参考资料

捧个钱场?