鱼喃

听！布鲁布鲁，大鱼又在那叨叨了

地理编码 （Geohash）

Posted on Views: 99+

能快速找到邻居的编码方式

什么是地理编码？

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

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