GeoHash算法解析马太航.doc

文档介绍：GeoHash算法解析
信息检索的过程,排序是非常重要的•一个环节,传统的一维数据排序,往往采用B树索引排序,它要求数据类型是nJ排序的,比如整型、字符串、浮点型数据;而对于二维的地理位置,B树索引便无能为力了,GeoHash便是为了解决二维地理位置排序而山现的一套算法技术。
1东ft多
十八譖a多
4EP WX4G0 WX4C
V:練’:
:R WX4G2 WX4O32
49tdi
•木確渴
郊区
城区
由于二维坐标不可排序,GeoHash解决此问题的思路是将二维数据转换为一维数据。 GeoHash将二维的经纬度转换转挽为字符串,每个字符串不是代表一个点,而是代表了一个矩形区域,这个矩形区域内的所有点都亨有共同的GeoHash位置信息。GeoHash位置有如下4个特点:字符串长度与位賈精度对应;字符串相近表示距离相近,这样有利于使用字符串匹配来进行附近信息查询;由于位置表示的是一个矩形区域,有利于隐私信息保护;点在位置所表示的矩形区域内移动,位置信息不变,这样有利于做数据的缓存。
GeoHash仅仅通过一个字符串來表示位置信息,GeoHash字符串的产生是通过确定的算法计算得來的。GeoHash有多种算法,算法根据空间曲线填充方式來确定。目前常用的几种空间曲线有3种:Peano曲线、Hilbert曲线、Z-order曲线。下而以Peano曲线来说明GeoHash 字符串的H•算方式,步骤可分为:二进制转换、组码、base32编码。
二进制转换:以GPS坐标(, )来计算。下面是经度的计算步骤:
1) 将纬度区间[-90,90】二分为[-90,0),[0,90](称为左右区间), 属于右区间[0,90],给标记为1;
2) 继续将区间[0,90]二分为[0,45),[45,901,,45), 给标记为0;
3) 递归上述过程,[a,b】。随着每次迭代区间[a,b]总在缩小,;给定的纬度x ()属于左区间,则记录0, 如果属于右区间则记录1,这样随着算法的进行会产生一个序列10111 00011,序列的长度跟给定的区间划分次数有关,划分次数依需求精度而定。经度的计算方式与维度类
似,产生序列1101001011。
组码:将维度和经度产生的序列依次交叉组合,偶数位放经度,奇数位放偶数,生成新
的二进制序列:11100 11101 0010001111。
base32编码:首先将11100 11101 00100 01111转成十进制,对应着28、29、4、15,十
进制对应的编码就是wx4go wx4g