Geohash——「附近的人」背后的秘密

原创晨晓晨晓

前阵子趁着午休的空档捧读了小米十周年的《一往无前：雷军亲述小米热血10年》。书中写到小米的“米聊”遭遇腾讯的“微信”时，雷军说：如果微信一年之后杀入，米聊有50%的胜算；如果微信三个月内杀入，米聊100%必死。

两位卓越的程序员，讷言的创业者，金风玉露一相逢，便胜却人间无数。微信凭借短语音、摇一摇、QQ好友、附近的人等功能后来居上，无往不利。站在小米十周年的2020年回望十年前这场没有硝烟的战役，战略转移的小米成为最年轻的世界五百强，高歌猛进的微信更是成为最流行的国民应用。

本文要探讨的正是「附近的人」技术实现——Geohash。众所周知在极坐标系地球表面上位置的表达方式为经纬度，这种二维的表示意味着枚举所有距离达到用户数平方的量级。顾名思义，Geohash即地理位置的索引，核心思想是通过空间填充曲线将二维坐标转换成一维索引，以实现快速的临近搜索。

下图展示了北京9个区域的Geohash字符串，分别是WX4ER，WX4G2、WX4G3等等，每一个字符串代表了某一矩形区域。

Geohash编码中，字符串相似的表示距离相近（特殊情况后文阐述），这样可以利用字符串的前缀匹配来实现临近位置搜索。

首先，将极坐标系转化为笛卡尔坐标系，将平面分为若干大小相等的矩形。依次用连续的标识标记连续区域。通过此番降维后需要选择一种恰当的方式实现上下左右方向临近的区块标识符也尽可能的接近，称为空间填充曲线，常见的有Peano空间填充曲线（Z形）。

以经纬度值：（116.389550，39.928167）进行算法说明，对纬度39.928167进行逼近编码（地球纬度区间是[-90,90]，经度区间[-180,180]）

首先将纬度分为[-90,0)和[0,90]两个区间，分别称为左区间和右区间
判断39.928167归属于左区间或是右区间，此例位于右区间记为1
继续判断39.928167位于[0,45)或[45,90]，此例位于做区间记为0
递归上述过程，通过二分查找不断逼近精确的纬度

随着二分查找的次数增加，收获101110001100011的序列
同理，对经度116.389550进行编码。通过上述计算经度产生的编码为101110001100011
奇数位放纬度，偶数位放经度，两条序列交织组成以下序列

将组成的序列按照Base32进行编码（0-9，以及b-z去掉i,l,o等易混淆字符），得到编码wx4g0e

不同的编码长度表示不同的范围区间，字符串越长表示的范围越精确。

Geohash除了使用Base32编码方式外也有Base64编码的变体，我个人推测采取Base32编码原因之一是经度区间是纬度区间尺度的两倍。想象一下将地球表面沿穿过南北极点的截面切开，展开后两个外切正方形（近似）拼接后，长宽比为2:1，如此在第一轮编码时得以将地球表面分割为形状大小接近的矩形。如下：

如《人月神话》所说，“No Silver Bullets”。Geohash也存在局限性：

Peano曲线会发生突变（如示意图0111到1000），即序号连续的区域在位置上并不紧邻。可以通过处理边界条件或选用更好的空间填充曲线进行解决，如Hilbert曲线。
具有相同前缀的Geohash索引空间上紧邻，但区域边缘会出现前缀不同但位置上紧邻的情况。可以通过查询临近区域，并对临近区域再次计算的方式进行解决。

Geohash通过空间填充曲线进行降维，并通过Base32进行编码很巧妙的实现了高效临近位置搜索的方式。对于解决实际问题很有启发意义，也更加印证了算法和数据结构是开发人员的核心能力。

继续滑动看下一个