geohash:用字符串实现附近地点搜索 - idv2

标签: geohash 字符串 近地点 | 发表时间:2011-07-23 19:40 | 作者:(author unknown) 猪头小队长
出处:http://tech.idv2.com/

上回说到了用经纬度范围实现附近地点搜索。 一些小型应用中这样做没问题,但在大型应用中它有个显著的缺点:速度慢。慢的原因有两个, 第一是范围比较的索引利用率并不高,第二是SQL语句极其不稳定(不同的当前位置会产生完全不同的SQL查询),很难缓存。

可以考虑使用geohash算法。

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

geohash-intro-01.png

geohash有以下几个特点:

首先,geohash用一个字符串表示经度和纬度两个坐标。某些情况下无法在两列上同时应用索引 (例如MySQL 4之前的版本,Google App Engine的数据层等),利用geohash,只需在一列上应用索引即可。

其次,geohash表示的并不是一个点,而是一个矩形区域。比如编码wx4g0ec19,它表示的是一个矩形区域。 使用者可以发布地址编码,既能表明自己位于北海公园附近,又不至于暴露自己的精确坐标,有助于隐私保护。

第三,编码的前缀可以表示更大的区域。例如wx4g0ec1,它的前缀wx4g0e表示包含编码wx4g0ec1在内的更大范围。 这个特性可以用于附近地点搜索。首先根据用户当前坐标计算geohash(例如wx4g0ec1)然后取其前缀进行查询 (SELECT * FROM place WHERE geohash LIKE 'wx4g0e%'),即可查询附近的所有地点。

geohash-intro-02.png

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划分区间139.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划分区间1116.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。

十进制0123456789101112131415
base320123456789bcdefg
十进制16171819202122232425262728293031
base32hjkmnpqrstuvwxyz

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

geohash的应用:附近地址搜索

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

以geohash的python库为例,相关的geohash操作如下:

>>> import geohash
>>> geohash.encode(39.92324, 116.3906, 5)  # 编码,5表示编码长度
'wx4g0'
>>> geohash.expand('wx4g0')                # 求wx4g0格子及周围8个格子的编码
['wx4ep', 'wx4g1', 'wx4er', 'wx4g2', 'wx4g3', 'wx4dz', 'wx4fb', 'wx4fc', 'wx4g0']

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

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

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

相关 [geohash 字符串 近地点] 推荐:

geohash:用字符串实现附近地点搜索 - idv2

- 猪头小队长 - tech.idv2.com
上回说到了用经纬度范围实现附近地点搜索. 一些小型应用中这样做没问题,但在大型应用中它有个显著的缺点:速度慢. 慢的原因有两个, 第一是范围比较的索引利用率并不高,第二是SQL语句极其不稳定(不同的当前位置会产生完全不同的SQL查询),很难缓存. 可以考虑使用geohash算法. geohash是一种地址编码,它能把二维的经纬度编码成一维的字符串.

geohash:用字符串实现附近地点搜索

- LiuWeifeng - idv2
上回说到了用经纬度范围实现附近地点搜索. 一些小型应用中这样做没问题,但在大型应用中它有个显著的缺点:速度慢. 慢的原因有两个, 第一是范围比较的索引利用率并不高,第二是SQL语句极其不稳定(不同的当前位置会产生完全不同的SQL查询),很难缓存. 可以考虑使用geohash算法. geohash是一种地址编码,它能把二维的经纬度编码成一维的字符串.

Geohash学习笔记

- - 标点符
Geohash是一种地址编码,它能把二维的经纬度编码成一维的字符串. 比如,北海公园的编码是wx4g0ec1. Geohash有以下几个特点:. Geohash用一个字符串表示经度和纬度两个坐标. 在数据存储时可以简化为只为一列做索引. Geohash表示的并不是一个点,而是一个矩形区域. 使用者可以发布地址编码,既能表明自己大致位置,又不至于暴露自己的精确坐标,有助于隐私保护.

[转]GeoHash原理分析

- - tenfyguo的技术专栏
机机是个好动又好学的孩子,平日里就喜欢拿着手机地图点点按按来查询一些好玩的东西. 某一天机机到北海公园游玩,肚肚饿了,于是乎打开手机地图,搜索北海公园附近的餐馆,并选了其中一家用餐. 饭饱之后机机开始反思了,地图后台如何根据自己所在位置查询来查询附近餐馆的呢. 苦思冥想了半天,机机想出了个方法:计算所在位置P与北京所有餐馆的距离,然后返回距离<=1000米的餐馆.

字符串匹配那些事(一)

- jiessie - 搜索技术博客-淘宝
本系列文章主要介绍几种常用的字符串比较算法,包括但不限于蛮力匹配算法,KMP算法,BM算法,Horspool算法,Sunday算法,fastsearch算法,KR算法等等. 本文主要介绍KMP算法和BM算法,它们分别是前缀匹配和后缀匹配的经典算法. 所谓前缀匹配是指:模式串和母串的比较从左到右,模式串的移动也是从左到右;所谓后缀匹配是指:模式串和母串的的比较从右到左,模式串的移动从左到右.

字符串匹配的Boyer-Moore算法

- - 阮一峰的网络日志
上一篇文章,我介绍了 KMP算法. 但是,它并不是效率最高的算法,实际采用并不多. 各种文本编辑器的"查找"功能(Ctrl+F),大多采用 Boyer-Moore算法. Boyer-Moore算法不仅效率高,而且构思巧妙,容易理解. 1977年,德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了这种算法.

JavaScript中的字符串操作

- - CSDN博客推荐文章
JavaScript中的字符串操作.    字符串在JavaScript中几乎无处不在,在你处理用户的输入数据的时候,在读取或设置DOM对象的属性时,在操作cookie时,当然还有更多.... JavaScript的核心部分提供了一组属性和方法用于通用的字符串操作,如分割字符串,改变字符串的大小写,操作子字符串等.

字符串匹配的KMP算法

- - 博客园_知识库
   字符串匹配是计算机的基本任务之一.   举例来说,有一个字符串"BBC ABCDAB ABCDABCDABDE",我想知道,里面是否包含另一个字符串"ABCDABD".   许多算法可以完成这个任务, Knuth-Morris-Pratt算法(简称KMP)是最常用的之一. 它以三个发明者命名,起头的那个K就是著名科学家Donald Knuth.

我们不需要字符串类型

- - 博客 - 伯乐在线
字符串是应该作为内置类型还是仅仅作为字符数组的一个别名呢. 考虑到实现细节的可选性,我并不认为需要对字符串进行类型特化. 在C++看来,字符串和“vector”容器基本上是一样的,除了某些特殊操作,例如:大小写转换,需要依赖容器元素“char”类型(而不是作用于容器本身). 字符串除了是一系列的字符组成,没有什么特别的.