回到顶部 暗色模式

Geohash算法简介

1. Geohash算法介绍

Geohash-Wikipedia

        Geohash是一种用于公共领域的地理编码系统，其将地理位置编码为字母和数字的短字符串。Geohash允许任意精度的属性，可以通过增长或缩短字符串来改变精度。当两个区域的公共前缀越长，说明他们的联系更加紧密。但是反过来，具有短公共前缀或者没有公共前缀并不一定代表着联系很小。
        Geohash算法可以将一个二维的经纬度坐标转换成一个可以比较的字符串，也就是降维。使用三十二进制，全球被划分为 $32$ 个大块，再在每个大块内继续划分出 $32$个小块，因此对于越长的geohash字符串，其精度越大，代表的范围也就越小。通过Base32算法，geohash使用字母和数字表示值，如下所示：

数字 0 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进制 0 1 2 3 4 5 6 7 8 9 b c d e f g h j k m n p q r s t u v w x y z

        即使用了所有 $10$ 以内的数字，以及除 $a$, $i$, $l$ 和 $o$ 之外的所有小写字母。在计算的时候只需要在十进制和三十二进制之间转换即可，举例：

$$ \begin{aligned} (ezs42)_{32} &= e \times 32^4 + z \times 32^3 + s \times 32^2 + 4 \times 32^1 + 2 \times 32^0 \\ &= 13 \times 1048576 + 31 \times 32768 + 24 \times 1024 + 4 \times 32 + 2 \times 1 \\ &= 14672002. \\ \end{aligned} $$

        正如之前所说的，geohash算法将经纬度转换成一个字符串，自然也能由字符串转回经纬度。再以 $ezs42$ 为例，将其转换为二进制：

$$ \begin{aligned} &(e)_{32} = (01101)_2, \\ &(z)_{32} = (11111)_2, \\ &(s)_{32} = (11000)_2, \\ &(4)_{32} = (00100)_2, \\ &(2)_{32} = (00010)_2. \end{aligned} $$

        结果得到的二进制数字为：$(0110111111110000010000010)_2$ 。假设从左到右读，则奇数位代表纬度代码：$(101111001001)_2$，偶数位代表经度代码：$(0111110000000)_2$。
        接下来再通过二分法对经纬度代码进行分别处理。纬度的范围为 $-90 \sim 90$ ，我们将其划分为两块：$-90 \sim 0$ 和 $0 \sim 90$ 。查看纬度代码，第一位为 $1$，因此选择 $0 \sim 90$。如果为 $0$ 的话，就要选择左边的区间。即为 $0$ 选择左边，为 $1$ 选择右边。如果没有更多的位数，那么可以认为纬度为 $45$，这样误差范围就为 $\pm45$ 。但是在这里我们有更多的位数，因此可以继续下去。再对 $0 \sim 90$ 进行二分分为 $0 \sim 45$ 和 $45 \sim 90$ ，可以看到纬度代码第二位为 $0$ ，因此选择 $0 \sim 45$ 。如此往复，可以确认纬度值。再使用同样的方法，可以确认经度值，不过要注意经度的范围是 $-180 \sim 180$ 。
纬度确定：

位数 位值 最小值 中间值 最大值
0 1 -90.000 0.000 90.000
1 0 0.000 45.000 90.000
2 1 0.000 22.500 45.000
3 1 22.500 33.750 45.000
4 1 33.750 39.375 45.000
5 1 39.375 42.188 45.000
6 0 42.188 43.594 45.000
7 0 42.188 42.891 43.594
8 1 42.188 42.539 42.891
9 0 42.539 42.715 42.891
10 0 42.539 42.627 42.715
11 1 42.539 42.583 42.627

        可得纬度为 $42.583$ ，同理可得经度为 $-5.581$ ，经纬度误差范围都在 $\pm0.022$ 之间。根据经纬度与千米的比例表可得误差距离。

Geohash长度 纬度位数 经度位数 纬度误差 经度误差 千米误差
1 2 3 $\pm23$ $\pm23$ $\pm2500$
2 5 5 $\pm2.8$ $\pm5.6$ $\pm630$
3 7 8 $\pm0.70$ $\pm0.70$ $\pm78$
4 10 10 $\pm0.087$ $\pm0.18$ $\pm20$
5 12 13 $\pm0.022$ $\pm0.022$ $\pm2.4$
6 15 15 $\pm0.0027$ $\pm0.0055$ $\pm0.61$
7 17 18 $\pm0.00068$ $\pm0.00068$ $\pm0.076$
8 20 20 $\pm0.000085$ $\pm0.00017$ $\pm0.019$

        对于一个给定的经纬度，要想求得经纬度的二进制代码值，只需要将上述步骤倒过来即可。再以 $(42.583, -5.581)$ 为例。
纬度代码确定：

位数 最小值 中间值 最大值 位值
0 -90.000 0.000 90.000 1
1 0.000 45.000 90.000 0
2 0.000 22.500 45.000 1
3 22.500 33.750 45.000 1
4 33.750 39.375 45.000 1
5 39.375 42.188 45.000 1
6 42.188 43.594 45.000 0
7 42.188 42.891 43.594 0
8 42.188 42.539 42.891 1
9 42.539 42.715 42.891 0
10 42.539 42.627 42.715 0

        虽然通过geohash可以通过公共前缀来查找一些彼此相邻的点，但是在一些边缘情况无法通过这种方式进行查询。例如在本初子午线左右两端的geohash值并没有公共前缀，以及靠近南北极的区域的geohash值差异很大。因为geohash依赖经纬度得到数值，因此在这些经纬度变化迅速的区域，它们的geohash值的变化也很迅速。

2. Redis中使用geo数据类型

        继续以 $(42.583, -5.581)$ 为例，演示在Redis中操作geo数据类型。

geoadd location -5.581 42.583 gw01

        将 $(42.583, -5.581)$ 存入 $location$ 并命名为 $gw01$。$location$ 本质为 $zset$ 数据类型。再对其获取得

geopos location gw01

        计算其geohash值

geohash location gw01

        此外，通过

geodist
georadius
georadiusbymember

        这些指令可以计算范围内符合条件的坐标。

Geohash算法简介

回到顶部