GeoHash算法

GeoHash

Geohash is a latitude/longitude geocode system invented by Gustavo Niemeyer when writing the web service at geohash.org, and put into the public domain. It is a hierarchical spatial data structure which subdivides space into buckets of grid shape.

简单说，GeoHash是一个将经纬度信息编码成一个string的算法。从而便于储存、查找。

GeoHash算法的步骤

GeoHash对经度纬度分别编码，原理是迭代做二分，进而逼近真实值。

我们以纬度举例。

由于地球纬度区间是[-90,90]，所以取区间中点pivot。如果某地点P的纬度大于pivot的值，则编码的第1位为1，反之为0。

然后缩小范围，迭代N次。得到最后的结果。

经度的范围是[-180, 180]。我们重复上面的过程，也可以得到经度编码。

最后我们把经度和纬度的编码进行交错组合，偶数位放经度，奇数位放纬度。得到最后的GeoHash编码。

例如，经纬度(57.64911,10.40744)可以使用base32编码为 u4pruydqqvj。

GeoHash算法的用途

由于GeoHash使用经纬度交错编码，所以我们使用某一个前辍，就可以划定一个经纬度范围。

GeoHash-grid

如果我们对GeoHash编码这一列进行索引加速，则可以在较快的时间内查找到某一个范围内的所有grid，进而获得POI等信息。

GeoHash的压缩思想

GeoHash的交错编码为区间查找提供了遍历。而对经纬度的逼近编码则提供了非常好的压缩特性。

易得，一个点位于pivot的左右/上下的机率是相同的。所以编码的每一位的信息量都是-logPr[s]=>1bit，达到了数据压缩的下限。

又由于二分逼近的良好性能，使得压缩/解压缩的速度可以达到极限。

不过在实际应用中，POI不可能完全平均分布，所以GeoHash的压缩只是一种接近最优解的方案。但是由于二分逼近法带来的可索引性，GeoHash绝对可以称的上是一个精妙完美的设计了。

应用 - 拉取目标周围的POI

我们在一些LBS应用中，经常需要拉取某一点周围的POI。

假设我们将POI存储为一个pvlist映射。并且获得了某点的GeoHash值。那么我们怎么取得周围的POI呢？

理想状态下，“附近的POI”都是在一个以某点为圆心的圆进行查找。但是由于GeoHash划分的范围是一个矩形，所以我们使用一个3×3的大矩形来替代圆形范围。

其中3×3矩形中最中间的矩形是我们确定的那个点。

然后，我们根据给出的半径r确定GeoHash的精确度。使得我们的3×3大矩形可以包含理想的圆形范围。

于是下一步的目标就是找到某点GeoHash的8个临近的GeoHash。

由上文我们可以得出，GeoHash的经纬度是分别编码的。以一个4×4的地图为例。

这是在纬度上的划分。

可以看出，连续的GeoHash Grid的纬度编码也是连续的。

经度同理。

所以我们只需要decode我们的GeoHash编码，将longitude和latitude编码分别进行-1/+1的操作就可以获得附近的POI的GeoHash码/前辍了。

总结

GeoHash的三个特性，可索引，压缩，便于存储。

还有，好久不写文了。