Geohash的原理、算法和具体应用探究

Geohash 是一种地址编码，它能把二维的经纬度编码成一维的字符串。比如，北海公园的编码是wx4g0ec1。

Geohash 的原理、算法

下面以(39.92324, 116.3906)为例，介绍一下geohash的编码算法。

首先将纬度范围(-90, 90)平分成两个区间(-90, 0)、(0, 90)， 如果目标纬度位于前一个区间，则编码为0，否则编码为1。由于39.92324属于(0, 90)，所以取编码为1。然后再将(0, 90)分成 (0, 45), (45, 90)两个区间，而39.92324位于(0, 45)，所以编码为0。以此类推，直到精度符合要求为止，得到纬度编码为1011 1000 1100 0111 1001。

纬度范围 划分区间0 划分区间1 39.92324所属区间
(-90, 90) (-90, 0.0) (0.0, 90) 1
(0.0, 90) (0.0, 45.0) (45.0, 90) 0
(0.0, 45.0) (0.0, 22.5) (22.5, 45.0) 1
(22.5, 45.0) (22.5, 33.75) (33.75, 45.0) 1
(33.75, 45.0) (33.75, 39.375) (39.375, 45.0) 1
(39.375, 45.0) (39.375, 42.1875) (42.1875, 45.0) 0
(39.375, 42.1875) (39.375, 40.7812) (40.7812, 42.1875) 0
(39.375, 40.7812) (39.375, 40.0781) (40.0781, 40.7812) 0
(39.375, 40.0781) (39.375, 39.7265) (39.7265, 40.0781) 1
(39.7265, 40.0781) (39.7265, 39.9023) (39.9023, 40.0781) 1
(39.9023, 40.0781) (39.9023, 39.9902) (39.9902, 40.0781) 0
(39.9023, 39.9902) (39.9023, 39.9462) (39.9462, 39.9902) 0
(39.9023, 39.9462) (39.9023, 39.9243) (39.9243, 39.9462) 0
(39.9023, 39.9243) (39.9023, 39.9133) (39.9133, 39.9243) 1
(39.9133, 39.9243) (39.9133, 39.9188) (39.9188, 39.9243) 1
(39.9188, 39.9243) (39.9188, 39.9215) (39.9215, 39.9243) 1

经度也用同样的算法，对(-180, 180)依次细分，得到116.3906的编码为1101 0010 1100 0100 0100。

经度范围 划分区间0 划分区间1 116.3906所属区间
(-180, 180) (-180, 0.0) (0.0, 180) 1
(0.0, 180) (0.0, 90.0) (90.0, 180) 1
(90.0, 180) (90.0, 135.0) (135.0, 180) 0
(90.0, 135.0) (90.0, 112.5) (112.5, 135.0) 1
(112.5, 135.0) (112.5, 123.75) (123.75, 135.0) 0
(112.5, 123.75) (112.5, 118.125) (118.125, 123.75) 0
(112.5, 118.125) (112.5, 115.312) (115.312, 118.125) 1
(115.312, 118.125) (115.312, 116.718) (116.718, 118.125) 0
(115.312, 116.718) (115.312, 116.015) (116.015, 116.718) 1
(116.015, 116.718) (116.015, 116.367) (116.367, 116.718) 1
(116.367, 116.718) (116.367, 116.542) (116.542, 116.718) 0
(116.367, 116.542) (116.367, 116.455) (116.455, 116.542) 0
(116.367, 116.455) (116.367, 116.411) (116.411, 116.455) 0
(116.367, 116.411) (116.367, 116.389) (116.389, 116.411) 1
(116.389, 116.411) (116.389, 116.400) (116.400, 116.411) 0
(116.389, 116.400) (116.389, 116.394) (116.394, 116.400) 0

接下来将经度和纬度的编码合并，奇数位是纬度，偶数位是经度，得到编码 11100 11101 00100 01111 00000 01101 01011 00001。

最后，用0-9、b-z（去掉a, i, l, o）这32个字母进行base32编码，得到(39.92324, 116.3906)的编码为wx4g0ec1。

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

解码算法与编码算法相反，先进行base32解码，然后分离出经纬度，最后根据二进制编码对经纬度范围进行细分即可，这里不再赘述。 不过由于geohash表示的是区间，编码越长越精确，但不可能解码出完全一致的地址。

Geohash的应用：附近地址搜索

geohash的最大用途就是附近地址搜索了。不过，从geohash的编码算法中可以看出它的一个缺点：位于格子边界两侧的两点， 虽然十分接近，但编码会完全不同。实际应用中，可以同时搜索当前格子周围的8个格子，即可解决这个问题。

最后，我们来看看本文开头提出的两个问题：速度慢，缓存命中率低。使用geohash查询附近地点，用的是字符串前缀匹配：

代码如下:

SELECT * FROM place WHERE geohash LIKE 'wx4g0%';

而前缀匹配可以利用geohash列上的索引，因此查询速度不会太慢。另外，即使用户坐标发生微小的变化， 也能编码成相同的geohash，这就保证了每次执行相同的SQL语句，使得缓存命中率大大提高。

赞 (0)

相关推荐

  • Geohash的原理、算法和具体应用探究

    Geohash 是一种地址编码,它能把二维的经纬度编码成一维的字符串.比如,北海公园的编码是wx4g0ec1. Geohash 的原理.算法 下面以(39.92324, 116.3906)为例,介绍一下geohash的编码算法. 首先将纬度范围(-90, 90)平分成两个区间(-90, 0).(0, 90), 如果目标纬度位于前一个区间,则编码为0,否则编码为1.由于39.92324属于(0, 90),所以取编码为1.然后再将(0, 90)分成 (0, 45), (45, 90)两个区间,而39

  • Vue.use的原理和设计源码探究

    目录 前言 基本使用 源码解析 控制反转 前言 这段时间打算回顾一下Vue的全局方法,脑海里第一个跳出来的方法就是Vue.use,之所以会首先想到它,我觉得和我平时看的面试题相关~~~ Vue.use的原理是面试中常问的点,因为相对于其他全局方法,Vue.use源代码逻辑清晰,如果了解它,也就代表这个人是看过Vue源码的!!! 基本使用 在Vue官网中是这样说明的:通过全局方法 Vue.use(plugin) 使用插件 首先要知道什么是插件,插件通常用来为 Vue 添加全局功能(过滤器.指令.组

  • Redis高效检索地理位置的原理解析

    Redis高效检索地理位置的原理解析

    Redis GEO 用做存储地理位置信息,并对存储的信息进行操作.通过geo相关的命令,可以很容易在redis中存储和使用经纬度坐标信息.Redis中提供的Geo命令有如下几个: geoadd:添加经纬度坐标和对应地理位置名称. geopos:获取地理位置的经纬度坐标. geodist:计算两个地理位置的距离. georadius:根据用户给定的经纬度坐标来获取指定范围内的地理位置集合. georadiusbymember:根据储存在位置集合里面的某个地点获取指定范围内的地理位置集合. geoh

  • python实现八大排序算法（1）

    python实现八大排序算法（1）

    排序 排序是计算机内经常进行的一种操作,其目的是将一组"无序"的记录序列调整为"有序"的记录序列.分内部排序和外部排序.若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序.反之,若参加排序的记录数量很大,整个序列的排序过程不可能完全在内存中完成,需要访问外存,则称此类排序问题为外部排序.内部排序的过程是一个逐步扩大记录的有序序列长度的过程. 看图使理解更清晰深刻: 假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序

  • Java面试题冲刺第二十三天--算法(2)

    Java面试题冲刺第二十三天--算法(2)

    目录 面试题1:你说一下常用的排序算法都有哪些? 追问1:谈一谈你对快排的理解吧 追问2:说一下快排的算法原理 追问3:来吧!给我手敲一个快排 面试题2:来!再给我手撸一个Spring 追问1:哦,咳咳-说一下构成递归的前提条件有啥? 追问2:递归都有哪些优缺点? 追问3:给我手写一个简单的递归算法的实现吧 面试题3: 10亿个数中找出最大的100000个数(top K问题) 总结 面试题1:你说一下常用的排序算法都有哪些? 追问1:谈一谈你对快排的理解吧 快速排序,顾名思义就是一种以效率快为特

  • 解决ASP.NET Core中使用漏桶算法限流的问题

    解决ASP.NET Core中使用漏桶算法限流的问题

    目录 算法原理 算法实现 进程内即内存漏桶算法 基于Redis的漏桶算法 应用算法 1.安装Nuget包 2.使用中间件 漏桶算法是限流的四大主流算法之一,其应用场景各种资料中介绍的不多,一般都是说应用在网络流量控制中.这里举两个例子: 1.目前家庭上网都会限制一个固定的带宽,比如100M.200M等,一栋楼有很多的用户,那么运营商怎么保证某些用户没有使用过多的带宽,从而影响到别人呢?这时就可以使用漏桶算法,限制每个用户访问网络的最大带宽,当然实际会比这复杂很多. 2.有一个祖传接口,当时写的时

  • Java实现图片比对算法

    采用直方图原理算法比对图片的细微差别效果比较好,以下两张区别很小的图片识别效果如下: 识别结果: 主要代码如下: import javax.imageio.*; import java.awt.image.*; import java.awt.*; import java.io.*;   public class PhotoDigest {     public static void main(String[] args) throws Exception {         float pe

  • python数据挖掘Apriori算法实现关联分析

    python数据挖掘Apriori算法实现关联分析

    目录 摘要: 关联分析 Apriori原理 算法实现 挖掘关联规则 利用Apriori算法解决实际问题 发现毒蘑菇的相似特征 总结: 摘要: 主要是讲解一些数据挖掘中频繁模式挖掘的Apriori算法原理应用实践 当我们买东西的时候,我们会发现物品展示方式是不同,购物以后优惠券以及用户忠诚度也是不同的,但是这些来源都是大量数据的分析,为了从顾客身上获得尽可能多的利润,所以需要用各种技术来达到目的. 通过查看哪些商品一起购物可以帮助商店了解客户的购买行为.这种从大规模数据集中寻找物品间的隐含关系被称

  • rsa详解及例题及python算法

    rsa详解及例题及python算法

    目录 rsa 详解及例题及python 算法原理 算法描述 案例手稿 实现python 运算 m=71 -> c=15 c=15 -> m=71 正常的rsa c->m m->c 安全性 运算速度 rsa 详解及例题及python 算法原理 RSA公开密钥密码体制的原理是:根据数论,寻求两个大素数比较简单,而将它们的乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥 算法描述 任意选取两个不同的大素数p和q计算乘积 n=pq n 的欧拉函数 φ(n): φ(n)=(p-1)

  • 浅析Java中的SPI原理

    在面向对象的程序设计中,模块之间交互采用接口编程,通常情况下调用方不需要知道被调用方的内部实现细节,因为一旦涉及到了具体实现,如果需要换一种实现就需要修改代码,这违反了程序设计的"开闭原则".所以我们一般有两种选择:一种是使用API(Application Programming Interface),另一种是SPI(Service Provider Interface),API通常被应用程序开发人员使用,而SPI通常被框架扩展人员使用. 在进入下面学习之前,我们先来再加深一下API和

随机推荐