【风控数据】 GPS空间索引算法之Geohash
前言
公司在对客户进行分析时, 常常会用到的数据就是 GPS 上报信息, 该数据是由
(longitude、latitude) 组成.
如果推算客户和门店的距离(推荐场景),
需要客户与多个门店进行距离计算(使用球面距离非欧式距离),
计算一定距离内的门店, 采用距离计算相对计算较大, 如何采用匹配的方式,
直接推算两者的距离差, GeoHash 应运而生.
GeoHash 算法
GeoHash 定义
来自于 Elasticsearch: 权威指南 的解释
Geohash是一种将经纬度坐标(lat/lon)编码成字符串的方式.这么做的初衷只是为了让地理位置在url上呈现的形式更加友好,但现在Geohash已经变成一种在数据库中有效索引地理坐标点和地理形状的方式.
GeoHash 视角
GeoHash 算法实际上将地球分割成无数个地理栅栏,
如下图所示:
相当于对于地球的无穷二等分, 从而得到其经纬度的二进制编码.
GeoHash 计算
- 获取经纬度的二进制编码
针对纬度为 39.912057 进行分层编码, 可以得到如下结果,
此时其编码为 101110001.
| 编码等级 | 全部范围 | 左区间(0) | 右区间(1) | 编码结果 |
|---|---|---|---|---|
| 1 | (-90, 90) | (-90, 0.0) | (0.0, 90) | 1 |
| 2 | (0.0, 90) | (0.0, 45.0) | (45.0, 90) | 0 |
| 3 | (0.0, 45.0) | (0.0, 22.5) | (22.5, 45.0) | 1 |
| 4 | (22.5, 45.0) | (22.5, 33.75) | (33.75, 45.0) | 1 |
| 5 | (33.75, 45.0) | (33.75, 39.375) | (39.375, 45.0) | 1 |
| 6 | (39.375, 45.0) | (39.375, 42.1875) | (42.1875, 45.0) | 0 |
| 7 | (39.375, 42.1875) | (39.375, 40.78125) | (40.78125, 42.1875) | 0 |
| 8 | (39.375, 40.78125) | (39.375, 40.078125) | (40.078125, 40.78125) | 0 |
| 9 | (39.375, 40.078125) | (39.375, 39.7265625) | (39.7265625, 40.078125) | 1 |
- 经纬度二进制编码合并
经度占偶数位, 纬度占奇数位, 注意: 0 也是偶数位
经度: 0000
纬度: 1111
合并后: 010101- 按照Base32进行编码
Base32 编码: 从 A-Z 与 2-7 共 32 个字符 Base32 编码优势: 可直接作为文件名, 并且避免易混字符(如排除0-1, 与 O 和 I 类似)
GeoHash 原理
为何采用经纬度二分后进行拼接的方式?
如图所示是GeoHash的编码路线, 其使用的是Peano空间填充曲线,
该曲线优点是将二维空间转换成一维曲线(事实上是分形维),对大部分而言,编码相似的距离也相近,但Peano空间填充曲线最大的缺点就是突变性,有些编码相邻但距离却相差很远,比如0111与1000,编码是相邻的,但距离相差很大.
如图所示,其中效果公认较好是 Hilbert空间填充曲线,相较于Peano曲线而言,Hilbert曲线没有较大的突变.
为什么GeoHash不选择Hilbert空间填充曲线呢?可能因为Peano曲线就是一种四叉树线性编码方式, 速度较快,实现简单.
GeoHash 优缺点
优点
GeoHash用一个字符串表示经度和纬度两个坐标.在数据存储时可以简化为只为一列做索引.GeoHash表示的并不是一个点,而是一个矩形区域.使用者可以发布地址编码,既能表明自己大致位置,又不至于暴露自己的精确坐标,有助于隐私保护.GeoHash编码的前缀可以表示更大的区域.
缺点
位于格子边界两侧的两点,虽然十分接近,但编码会完全不同.实际应用中,可以同时搜索当前格子周围的8个格子,即可解决这个问题.
GeoHash 精度
如下结果来自于维基百科: Geohash
| geohash length | lat bits | lng bits | lat error | lng error | km error |
|---|---|---|---|---|---|
| 1 | 2 | 3 | ±23 | ±23 | ±2500 |
| 2 | 5 | 5 | ±2.8 | ±5.6 | ±630 |
| 3 | 7 | 8 | ±0.70 | ±0.70 | ±78 |
| 4 | 10 | 10 | ±0.087 | ±0.18 | ±20 |
| 5 | 12 | 13 | ±0.022 | ±0.022 | ±2.4 |
| 6 | 15 | 15 | ±0.0027 | ±0.0055 | ±0.61 |
| 7 | 17 | 18 | ±0.00068 | ±0.00068 | ±0.076 |
| 8 | 20 | 20 | ±0.000085 | ±0.00017 | ±0.019 |
geohash length: 标准geohash算法中的字符长度km error: 代表的是 geohash 对应的矩形区域的对角线长度的二分之一, 随着 geohash 位数的增加误差在 4 倍左右和 8 倍左右交替减少.原因在于表格的经纬度位数变化相对不均匀, 如果同时增加一位, 大概成 2 倍减少.