Geohash的原理、算法和具体应用探究
作者:junjie 发布时间:2023-10-06 07:59:44
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语句,使得缓存命中率大大提高。
猜你喜欢
- 相关介绍Python是一种跨平台的计算机程序设计语言。是一个高层次的结合了解释性、编译性、互动性和面向对象的脚本语言。最初被设计用于编写自动
- 每天急匆匆赶地铁上班的时候总会一不小心就会忘记打卡,尤其是软件打卡,那有没有什么办法可以解决忘打卡的问题呢?今天给大家推荐一下一款神器,利用
- 二进制转字符串入口参数:字节流函数返回:字符串Code By:Madpolice利用 ADODB.Stream 对象,速度比原来
- 图片的上传上传图片使用了表单提交, 下面是html部分, enctype="multipart/form-data"表示
- *注意:本文的内容涉及到修改NTFS磁盘权限和设置安全策略,请务必在确认您了解操作可能的后果之后再动手进行任何的修改。文中提及的权限都是在原
- 很早以前就有很多关于用CSS制作的相册,今天突然想看又找不到,反正也无聊,自己做了一下,结果做一下发现自己温习了一些东西。还行,
- 本文实例为大家分享了JavaScript实现多层颜色选项卡嵌套的具体代码,供大家参考,具体内容如下这是学JavaScript时候的一个作业,
- if语句用来表示某种可能的情况,并如何处理该情况。if语句可以用来表示一种可能性、两种可能性或者多种可能性。1 一种可能性单个的if语句表示
- 问题缘由:负责公司的开发平台研发工作,考虑的知识产权的保护工作,必须要考虑java的加密技术和js脚本的加密技术。在目前java加密很容易破
- Event事件用来控制线程的执行出现e.wait(),就会把这个线程设置为False,就不能执行这个任务;只要有一个线程出现e.set(),
- 昨天用ucweb看到了goos发的一篇帖子:谁说Float菜单不可以水平居中,进去看了看,觉得方法有点繁琐了,用到了负边距,position
- 调用sklearn的model_selection时,发现sklearn中没有model_selection的模块。经过检查,发现anaco
- 最近写了一个VUE的web app项目,需要实现某个部位吸顶的效果。即,页面往上滑动,刚好到达该部位时,该部分,固定在顶部显示。1、监听滚动
- 本文实例为大家分享了python实现五子棋游戏的具体代码,供大家参考,具体内容如下# -*- coding:utf-8 -*-# @Time
- 直接代码data_arr = []data = iter_files(dir,speakers)for k,v in data.items(
- vue中为何方法要写在methods里面1.methods是什么?首先先来段代码,我们在template中设定一个按钮,在点击按钮的时候打印
- 本文实例讲述了微信小程序学习笔记之文件上传、下载操作。分享给大家供大家参考,具体如下:前面介绍了微信小程序登录API与获取用户信息操作。这里
- 调用百度API获取经纬度信息。import requestsimport jsonaddress = input('请输入地点:
- Base64是一种用64个字符来表示任意二进制数据的方法。用记事本打开exe、jpg、pdf这些文件时,我们都会看到一大堆乱码,因为二进制文
- asp编程手工定义参数的方法: Dim con As ADODB.Connection