想开发一个附近的人功能？你不得不知的Geohash算法

​随着移动互联网的发展，很多基于地理位置信息的服务也越来越流行。比如说我们平常经常使用的查找附近的人，或者是附近的餐馆，共享单车等等。,那么，大家有没有想过，这个查找功能是如何实现的吗？作为受过高等教育的人，大家肯定立即就想到了可以通过经纬度进行计算。具体算法类似于这样：,地球近似于一个球体，地球赤道周长约40075.04公里，半径约为6371公里，因此，可以很容易地用立体几何的方法求出其距离，例如说最常见的大圆距离（Great-Circle Distance）。,公式如下：,,其中， R为地球半径，Aj、Aw分别表示A点的经度、纬度；Bj、Bw分别表示B点的经度、纬度。这样，通过简单的立体几何方法就可以很容易地求出其距离。,,如果有人对于地理信息学比较了解的话，还会知道半正矢公式（Haversine公式），因为大圆距离公式用到了大量的余弦函数，因此在两点距离过短的时候，会导致比较大的舍入误差。而半正矢公式则因为采用了正弦函数的方法，因此即使距离过小，也可以保留足够的有效数字。半正矢公式的形式如下所示：,,其中,,这里面的R为地球半径，可取平均值 6371km；φ1, φ2 表示两点的纬度；Δλ 表示两点经度的差值。,有了这些算法，那么理论上来查找附近的人就可以很方便地实现了。但是为什么要说从理论上讲呢？因为在工程实践中，这样查找的计算量太大了。对于几个经纬度的数据而言还可以，但是对于大规模数据查询而言，没有实际可操作性。就比如想在一个一百万条数据的数据库里查找附近5公里之内的餐馆有哪些，那么要对一百万条数据做各种三角函数操作，这显然是不现实的事情，更别说在互联网上应用的数据体量远大于百万条。而且这样的数据也很难对其查询效率进行优化。,那么，要怎么解决这个问题呢？这就是我们今天要介绍的神奇算法，Geohash算法了。通过Geohash算法，我们可以把两个坐标的距离计算简化为两个字符串的比较，从而可以最大限度的应用速度更快的字符串相关函数，并且对其进行排序或索引。,下面我们就来看看Geohash算法具体是怎么做到这一点的。,Geohash的本质就是将用到的整个地图区域进行矩形分割，然后在各个矩形之中再次进行矩形分割，而每一次分割中所在的区域用一个字符代表，这样一次次分割之后，就可以最大可能的逼近实际坐标所在地。而这个坐标也就可以用一串字符来代替了。常用的Geohash算法中，每个字符用5个比特来标识，这样就会有32个不同的组合（0-31），于是我们就可以将这个地图区域划分为32个区域。这样划分之后，第一个字母划分的区域就如下图所示：,,然后我们再对各个区域继续进行划分，就会得到类似于wx4eqzrx，这样的一个字符串了。,,而这时，我们就可以方便地使用类似于：,这样的sql语句查询到附近想要查询的东西了。是不是很方便呢？通过这种方式，我们就把复杂的三角函数计算，转化成了计算化处理效率非常高的字符串操作了。,那么，想必大家一定要问了，坐标转化成的字符串是怎么生成的呢？其实也很简单。,我们以纬度39.928167为例。,a. 首先我们以区间[-90,90]进行二分为[-90,0),[0,90]，称为左右区间，可以确定39.928167属于右区间[0,90]，标记为1,b. 接着将区间[0,90]进行二分为 [0,45),[45,90]，可以确定39.928167属于左区间 [0,45)，标记为0,c. 递归上述过程39.928167总是属于某个区间[a,b]。随着每次迭代区间[a,b]总在缩小，并越来越逼近39.928167，划分次数越多，距离就越精确，字符串也就会越长，如下图所示：,,这样我们就得到了纬度的二进制表示，同样我们也可以对经度进行二进制表示。然后，我们把经度放到偶数位，纬度放到奇数位，把两个二进制串合并到一起，最后将得到的二进制串编码每5位进行base32编码，最终就得到了我们想要的，对于每个小方格进行表示的Geohash字符串序列。,但是这样做了之后，很多人会发现一个问题，那就是每个Geohash字符串事实上都是代表一个小方格的，那么就会产生边界跨越的问题。就像下图中的红点，和上面的绿点并不在一个方格里，因此如果我们光查询红点所在的格子的话，就会查询不到明明离它很近的上面的绿点，反而可以查询到更远一点的下面的绿点。,,那么怎么解决这个问题呢？其实也很简单，就是在查询的时候，把周围的8个格子也考虑进来一起查询就行了。那么具体是怎么做的呢？我们可以看到，周围的8个格子，本质上就是经度纬度的格子二进制数与中间的格子差1，所以我们只需要对红点的经纬度二进制数，进行加减1的操作就可以获取到附近格子的字符串了。而这样做本质上就是损失了一个格子的精度。而在经纬度位数足够的情况下，这个误差是可以忽略不计的。通过计数我们可以得出：,在纬度相等的情况下，经度每隔0.00001度，距离相差约1米；在经度相等的情况下，纬度每隔0.00001度，距离相差约1.1米；而在geohash的位数是9位数的时候，大概为附近2米；8位的话，大约为附近19米。对于大部分人来讲，可以说是一个可以接受的误差了哦。​