`
sungang_1120
  • 浏览: 322581 次
  • 性别: Icon_minigender_1
  • 来自: 成都
社区版块
存档分类

geohash 用字符串实现附近低点搜索(转载)

 
阅读更多

 

转载:http://tech.idv2.com/2011/07/05/geohash-intro/

 

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 划分区间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的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 Javascript的实现

    通过这种方式,每个正方形可以用一个字符串(即`GEOHASH`)来表示,这个字符串由一系列二进制位组成,对应着正方形在分形过程中的位置。 在JavaScript中,实现`GEOHASH`通常包括以下几个步骤: 1. **坐标到二进制...

    Java实现GeoHash算法

    GeoHash将经纬度坐标转换为字符串,使得地理位置可以被高效地索引和查询。这种算法利用了空间分割和编码策略,使得相邻的位置在编码后具有部分共享的字符串前缀,从而降低了空间搜索的复杂性。 GeoHash的基本原理是...

    nodejs geohash

    通过Geohash编码,可以快速查找附近的兴趣点、实现地图上的搜索过滤等功能,极大地优化了空间数据的存储和查询效率。 总之,"nodejs geohash"是Node.js开发中处理地理信息的一种有效工具,它利用Geohash算法将...

    geohash算法实现Java代码

    GeoHash算法是一种基于地理坐标的分布式空间索引技术,它通过将地球表面的经纬度坐标转化为可比较的字符串,使得我们可以高效地进行地理位置的搜索、范围查询以及邻居查找等操作。这种算法尤其适用于大数据和分布式...

    geohash:一个解决计算附近距离的php类库.zip

    总的来说,Geohash是解决计算附近距离和搜索附近商业点问题的强大工具,它通过将地理位置编码为字符串,实现了对空间位置的有效索引和快速查询,极大地简化了PHP开发者在地理位置应用处理上的工作。掌握并合理运用...

    python_geohash-0.8.5-cp312-cp312-win_amd64.whl.zip

    Geohash是一种将地理坐标(经度和纬度)编码成可搜索的字符串的方法,这使得在数据库中存储和检索地理位置变得高效。它通过分层的二进制编码系统,将地球表面划分为多个网格,每个网格都有一个唯一的字符串表示。这...

    GeoHash核心原理解析

    例如,在需要查询附近餐馆的位置信息时,可以使用GeoHash将用户的经纬度坐标转换为字符串,并进行前缀匹配查询。这样,相同或相近GeoHash值的餐馆信息可以存储在缓存中,以供快速访问。 GeoHash编码算法的步骤包括...

    python_geohash-0.8.5-cp36-cp36m-win_amd64.whl.zip

    - 范围查询:找出给定范围内的所有GeoHash,这对于实现地理位置附近的搜索非常有用。 - 邻居查询:找到与给定GeoHash相邻的其他GeoHash,这有助于处理边界情况和相邻区域的查找。 - 距离计算:根据GeoHash计算两个...

    geohash经纬度转换包linux

    其中,Geohash是一种广泛使用的地理位置编码技术,它基于二进制空间划分的算法,将经纬度坐标转化为字符串,方便数据库管理和空间索引。在Python编程语言中,存在许多第三方库用于实现Geohash的编码和解码。本压缩包...

    如何找到周围8个区域的GeoHash编码

    GeoHash编码是一种将地理坐标(经度和纬度)转换为字符串的方法,便于存储和查询地理位置数据。在Java中实现找到周围8个区域的GeoHash编码涉及到地理空间索引和定位算法的应用。以下是对这个主题的详细解释: Geo...

    python_geohash-0.8.5-cp310-cp310-win_amd64.whl.zip

    3. **邻近性查询**:通过计算两个Geohash字符串的差异,确定两个位置的接近程度,这在地理空间索引和搜索中非常有用。 4. **范围查询**:通过设置一个Geohash的边界,可以获取该区域内所有其他Geohash,这对于地图...

    python_geohash-0.8.5-cp37-cp37m-win_amd64.whl.zip

    3. **范围查询(Range Query)**:通过一个GeoHash字符串,可以查找附近的其他GeoHash,以实现地理位置的邻近性查询。这对于地理数据索引和搜索非常有用。 4. **边界计算(Boundary Calculation)**:可以计算出一...

    python_geohash-0.8.5-cp311-cp311-win_amd64.whl.zip

    2. **编码和解码**:GeoHash库提供了将经纬度坐标转换成GeoHash字符串的函数(如`geohash.encode`),以及将GeoHash字符串还原为经纬度的函数(如`geohash.decode`)。 3. **精度和长度**:GeoHash字符串的长度决定...

    python实现字符串模糊匹配

    Python 提供了多种字符串模糊匹配方法,可以使用编辑距离、FuzzyWuzzy 库等技术来实现字符串模糊匹配。在实际应用中,字符串模糊匹配技术可以广泛应用于搜索引擎、自然语言处理、信息检索等领域。

    geohash-1.3.0.jar

    1)GeoHash用一个字符串表示经度和纬度两个坐标,比如我现在所在位置的GeoHash值为 wx4sv61q; 2)GeoHash标识的并不是一个点,而是一个区域,比如 wx4sv61q 对应的就是一个矩形区域; 3)编码的前缀可以标识更大...

    encode_geohash.rar_geohash_geohash encode_matlab与geohash

    MATLAB程序“encode_geohash.m”很可能实现了上述步骤,提供了一个将经纬度坐标转换为GeoHash字符串的函数。用户可以输入经度和纬度值,程序会返回对应的GeoHash编码,便于后续的空间检索和数据分析。 在GIS应用中...

    C/OC_geohash

    例如,它可以用来快速查找附近的位置,通过比较两个Geohash字符串的相似程度来估计它们之间的距离,或者在数据库中通过Geohash进行范围查询,大大提高检索速度。 在压缩包文件“Geohash”中,很可能包含了C或OC的...

    输入字符串实现加减乘除四则运算(java)

    将近250行的算法 实现了通过字符串进行加减乘除四则运算 纯通过处理字符串和数组实现 希望能帮助大家: 例如:String input "33+26 77+70"; String result ""; try { result Account...

    Laravel开发-geohash

    本项目“Laravel开发-geohash”显然旨在为Laravel框架引入Geohash技术,这是一种将地理位置(经纬度)编码为短字符串的方法,便于存储、搜索和排序地理位置数据。 Geohash是一种空间数据索引技术,由David Uffinger...

    C语言实现字符串截取

    这两个函数都属于自定义实现,它们提供了灵活且实用的功能来帮助开发者轻松地从一个字符串中提取所需的子字符串。 ### 函数一:`subStringByIndex` #### 功能描述 `subStringByIndex` 函数通过指定起始索引(`...

Global site tag (gtag.js) - Google Analytics