逍遥游

地理编码 (Geohash)

什么是地理编码?

地理编码是一种地址编码,它能够将二维的经纬度转换成一维的字符串。

在具体讨论地理编码之前,我们先来看一下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。

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

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

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

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

附表:

十进制 base32
0 0
1 1
2 2
3 3
10 a
31 z

地理编码的特点

从上面的算法,我们容易看出geohash具有以下的特点:

  • GeoHash将二维的经纬度转换成字符串,降低了维度,便于存储与检索(只需建立一个索引)
  • 字符串越长,表示的范围越精确。
  • 字符串相似的程度表示距离远近,这样可以利用字符串的前缀匹配来查询附近

地理编码的应用

一项技术的提出最终是为了投入使用,那么地理编码的应用是什么?

随着LBS(基于位置服务)的火热,数据量越来越大,精度要求越来越高,处理速度要求越来越快,一个需要解决的问题是,如何才能快速精确地检索到某一点的周边信息?显然,原来基于经纬度的方法已经不适用,第一是范围比较的索引利用率并不高,第二是SQL语句极其不稳定(不同的当前位置会产生完全不同的SQL查询),很难缓存。因此我们需要寻找一种新的方式来实现这一目标。

于是,地理编码出现了。但是,为什么地理编码更快呢?

大家都知道对建立了索引的键进行查找会比没有建立索引的快很多,索引本质上是对索引字段进行排序,然后通过类似二分查找的方法进行快速查找,即它要求索引的字段是可排序的,一般而言,可排序的是一维字段,比如工资、年龄等等,但是对于空间上的一个点(二维,包括经度和纬度),如何排序呢?又如何索引呢?尽管有些数据库支持联合索引,但是可以想象,效率一定是比一维要低很多。如果能将二维转换为一维,那么情况会好很多。

另外,地理编码的一个特点是两个字符串拥有的相同前缀越多,表示这两个点距离越近。这样我们在查询时就可以使用“like ‘wasd%’” 来查询附近。

地理编码的不足之处与解决方案

前面我们可以看到,编码是将一块区域化分成四块。有没有可能出现这么一种情况:A与B处于同一块中,但是A处于这一块的边缘,而紧挨着的是另一块上的C点,但是从我们的算法得出的结果是,A 与B之间的距离要近一点,这实际上是不对的。

错误的根源来自于,我们将两个明明相距很近的两个点分到了不同的两块上。在大体上,地理编码可以表示点与点之间的距离远近,但是在碰到诸如边界的情况下,会出现不准确的问题。

解决的办法是,取得临近的几块区域,然后对于这些点,利用原来的经纬度来判断远近,这样基本可以消除误差。

geohash实现示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import ch.hsr.geohash.GeoHash;
import java.awt.Point;
import static java.lang.Math.pow;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
/**
*
* @author Newnius
*/
public class Test
{
public static void main(String[] args)
{
int n = 30;
double score;
GeoHash gh;
Map<String, Point> map;
map = new HashMap<String, Point>();
map.put("长春", new Point(125, 21));
map.put("吉林", new Point(126, 34));
map.put("舒兰", new Point(126, 58));
map.put("延吉", new Point(129, 31));
for (String key : map.keySet())
{
gh = GeoHash.withCharacterPrecision(map.get(key).getY(), map.get(key).getX(), 12);
System.out.println(gh);
}
}
}

需要用到的jar包:geohash-1.0.13.jar

geohash源代码下载:https://github.com/kungfoo/geohash-java


多说停止服务,disqus引导注册太过分,暂时不上评论系统了。有机会自己造轮子吧。邮箱:input@newnius.com