geoHash的问题这篇博客(https://www.jianshu.com/p/7332dcb978b2)里已经写得非常完善了, 本文从数学方面来解释一下它的一些缺陷。明白GeoHash原理的话可以直接看最后一段
一、皮亚诺曲线的数学论证
以下内容节选自知乎:
皮亚诺曲线很有名气,它是一个“填满单位正方形的曲线”,不过它也让人迷惑,一个坑是它其实有过好几个定义,而即使是维基百科,上面的介绍也是错的;另一个坑是,它是按照曲线族的极限定义的,而极限与曲线族中的任意一条曲线,性质未必相同。
比如维基说:“1890年,意大利数学家[朱塞佩·皮亚诺]发明能填满一个正方形的曲线,叫做皮亚诺曲线“——嗯,到这里,是对的,让我们把这个称为定义一。
维基继续说:”其构造方法如下:取一个正方形并且把它分出九个相等的小正方形,然后从左下角的正方形开始至右上角的正方形结束,依次把小正方形的中心用线段连接起来;下一步把每个小正方形分成九个相等的正方形,然后上述方式把其中中心连接起来……将这种操作手续无限进行下去,最终得到的极限情况的曲线就被称作皮亚诺曲线。”图如下:
——嗯,这个说法也成立,让我们称这个为定义二。
两个都成立阿,那不挺好吗?问题就在于,这两个定义是不等价的——皮亚诺当年的构造方法,跟定义二里的构造方法,是不一样的。
——————分割线——————
OK,让我们从头说起。严谨一点,称“填满一个正方形的曲线,叫做皮亚诺曲线“这种最广义的说法,为定义零。皮亚诺的方法为定义一,上面整整齐齐的构造方法,为定义二。
皮亚诺当初首要目的,是为了填满正方形,他并不在乎如上图那样整整齐齐。与皮亚诺最类似的构造方法,在张筑生老师《数学分析新讲》第三册里有介绍,是索恩伯格(Isaac Jacob Schoenberg)1938年提出的:
image image image image整个过程比较罗嗦,其实想法也很简单,就是把小数拆开,一分为二——比如有小数0.12345678,按奇偶拆成0.1357和0.2468——这样单位区间上0到1的一个小数,就拆成了两个,让它们是纵横坐标,就指定了一个点,这样就填满正方形了。用数学语言说,我们要在单位区间[0,1]上定义两个函数phi和psai,使得对任意x属于[0,1],phi(x),psai(x)也属于[0,1]。x从跑到1,(phi(x), psai(x))从(phi(0), psai(0))跑到(phi(1), psai(1)),把点连起来,就是曲线,然后想办法找到合适的phi和psai,让这个曲线能走遍正方形的所有点,就大功告成。
一分为二最简单的就是如上面例子所示按奇数和偶数位拆开——小数0.12345678,拆成小数对(0.1357, 0.2468).
这里让我们再进一步,用二进制表示,那么十进小数0.5,换成二进制就是0.1,写成0.100000....,可以拆成二进制的小数对(0.10000, 0.00000),换成十进制就是(0.5,0)。
到这里似乎还好,问题在于,这样拆,是不连续的,即,phi和psai不连续!不连续的话,x从跑到1,(phi(x), psai(x))跑的点连不起来,就不是曲线。
验证一下:十进小数0.49999999....,换成二进制就是0.0111111.......,可以拆成二进制的小数对(0.011111...., 0.11111.....),这就是(0.1, 1.0),换成十进制就是(0.5,1)。这样,x从0.49999...跳到0.5,(phi(x), psai(x))从(0.5,1)跳到了(0.5,0),步子太大,断了。
怎么办?上面Schoenberg的构造方法就是来解决这个问题的,简而言之,他引入了三进制,多了一个缓冲区间,这样就把两边连起来了。
Schoenberg function,是这个样子的:
image上面张老师的书里的图19-10是基本函数w,Schoenberg fucntion是w的一个无穷级数,即函数序列的极限。
可以证明,Schoenberg function处处连续,处处不可导。
Schoenberg function是phi,phi(3x)是psai(x),形成的曲线是这样的:
image可以看到,跟上面维基的定义二里的乖宝宝相比,这样形成的皮亚诺曲线(定义一),是狂野的多了。
但不管好不好看,可以看到,任何一个单位正方形内的点,都能合并成一个单位区间的数,换句话说,这样定义的皮亚诺曲线,确实是一个满射,它填满了整个正方形。
——————分割线——————
好,现在让我们讨论定义二的曲线。这个曲线明显舒服的多,它的简化版本是希尔伯特曲线(Hilbert Curve)
image这个定义很直观,唯一要说明的是一个坑:这样的曲线,似乎每一个条线段端点,至少有一个坐标是有理数,那这样的曲线能否经过两个坐标都是无理数的点呢?比如(1/pi, 1/pi)。
甚至有人证明了它”不可能遍历正方形“:按照皮亚诺曲线的定义,它应该无法遍历平面啊? | 死理性派小组 | 果壳网 科技有意思。
这就回到了开头说的:曲线族的极限与曲线族中的任意一条曲线,性质未必相同。
例如有这样的曲线族fk(x) =1/k,很显然任意一条曲线都有f_k(x)>0,但这个曲线族的极限很显然是f(x)=0。
可以证明,定义二所述的皮亚诺曲线,作为曲线族的极限,是经过正方形内的每一个点的,它也是满射。
——————分割线——————
关于皮亚诺曲线的维度和面积,”等待飞翔“的回答里已经阐述,不再赘述。
——————分割线——————
geoHash问题
Geohash 一个点附近的地方(但不绝对) hash 字符串总是有公共前缀,并且公共前缀的长度越长,这两个点距离越近。
由于这个特性,Geohash 就常常被用来作为唯一标识符。用在数据库里面可用 Geohash 来表示一个点。Geohash 这个公共前缀的特性就可以用来快速的进行邻近点的搜索。越接近的点通常和目标点的 Geohash 字符串公共前缀越长(但是这不一定,也有特殊情况,下面举例会说明)
Geohash 也有几种编码形式,常见的有2种,base 32 和 base 36。
Decimal | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Base 32 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | b | c | d | e | f | g |
Decimal | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Base 32 | h | j | k | m | n | p | q | r | s | t | u | v | w | x | y | z |
base 36 的版本对大小写敏感,用了36个字符,“23456789bBCdDFgGhHjJKlLMnNPqQrRtTVWX”。
Decimal | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Base 36 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | b | B | C | d | D | F | g | G | h | H | j |
Decimal | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Base 36 | J | K | I | L | M | n | N | P | q | Q | r | R | t | T | V | W | X |
Geohash 实际应用举例
接下来的举例以 base-32 为例。举个例子。
假设需要查询距离美罗城最近的餐馆,该如何查询?
第一步我们需要把地图网格化,利用 geohash。通过查表,我们选取字符串长度为6的矩形来网格化这张地图。
经过查询,美罗城的经纬度是[31.1932993, 121.43960190000007]。
先处理纬度。地球的纬度区间是[-90,90]。把这个区间分为2部分,即[-90,0),[0,90]。31.1932993位于(0,90]区间,即右区间,标记为1。然后继续把(0,90]区间二分,分为[0,45),[45,90],31.1932993位于[0,45)区间,即左区间,标记为0。一直划分下去。
左区间 | 中值 | 右区间 | 二进制结果 |
---|---|---|---|
-90 | 0 | 90 | 1 |
0 | 45 | 90 | 0 |
0 | 22.5 | 45 | 1 |
22.5 | 33.75 | 45 | 0 |
22.5 | 28.125 | 33.75 | 1 |
28.125 | 30.9375 | 33.75 | 1 |
30.9375 | 32.34375 | 33.75 | 0 |
30.9375 | 31.640625 | 32.34375 | 0 |
30.9375 | 31.2890625 | 31.640625 | 0 |
30.9375 | 31.1132812 | 31.2890625 | 1 |
31.1132812 | 31.2011718 | 31.2890625 | 0 |
31.1132812 | 31.1572265 | 31.2011718 | 1 |
31.1572265 | 31.1791992 | 31.2011718 | 1 |
31.1791992 | 31.1901855 | 31.2011718 | 1 |
31.1901855 | 31.1956786 | 31.2011718 | 0 |
再处理经度,一样的处理方式。地球经度区间是[-180,180]
左区间 | 中值 | 右区间 | 二进制结果 |
---|---|---|---|
-180 | 0 | 180 | 1 |
0 | 90 | 180 | 1 |
90 | 135 | 180 | 0 |
90 | 112.5 | 135 | 1 |
112.5 | 123.75 | 135 | 0 |
112.5 | 118.125 | 123.75 | 1 |
118.125 | 120.9375 | 123.75 | 1 |
120.9375 | 122.34375 | 123.75 | 0 |
120.9375 | 121.640625 | 122.34375 | 0 |
120.9375 | 121.289062 | 121.640625 | 1 |
121.289062 | 121.464844 | 121.640625 | 0 |
121.289062 | 121.376953 | 121.464844 | 1 |
121.376953 | 121.420898 | 121.464844 | 1 |
121.420898 | 121.442871 | 121.464844 | 0 |
121.420898 | 121.431885 | 121.442871 | 1 |
纬度产生的二进制是101011000101110,经度产生的二进制是110101100101101,按照“偶数位放经度,奇数位放纬度”的规则,重新组合经度和纬度的二进制串,生成新的:111001100111100000110011110110,最后一步就是把这个最终的字符串转换成字符,对应需要查找 base-32 的表。11100 11001 11100 00011 00111 10110转换成十进制是 28 25 28 3 7 22,查表编码得到最终结果,wtw37q。
我们还可以把这个网格周围8个各自都计算出来。
image.png从地图上可以看出,这邻近的9个格子,前缀都完全一致。都是wtw37。
如果我们把字符串再增加一位,会有什么样的结果呢?Geohash 增加到7位。
image.png
当Geohash 增加到7位的时候,网格更小了,美罗城的 Geohash 变成了 wtw37qt。
看到这里,读者应该已经清楚了 Geohash 的算法原理了。咱们把6位和7位都组合到一张图上面来看。
可以看到中间大格子的 Geohash 的值是 wtw37q,那么它里面的所有小格子前缀都是 wtw37q。可以想象,当 Geohash 字符串长度为5的时候,Geohash 肯定就为 wtw37 了。
接下来解释之前说的 Geohash 和 Z 阶曲线的关系。回顾最后一步合并经纬度字符串的规则,“偶数位放经度,奇数位放纬度”。读者一定有点好奇,这个规则哪里来的?凭空瞎想的?其实并不是,这个规则就是 Z 阶曲线。看下图:
image.png几个问题
GeoHash的缺点
我们发现在前面的皮亚诺曲线推倒的过程中, 把小数拆开, 一分为二的过程其实和GeoHash中将经纬度合二为一是个相反过程。 以base-32 为例, 我们假设有一个地理位置二进制为(11111, 111111)和另一个(100000,000000)显然他们离的很远, 我们把它变为GeoHash值, 则一个为11111111111, 一个为100000000000,转换为十进制后为001zz 和 00200: 在数值上这两个点相差很小, 但是实际距离相差很大。 这里对应的数学现象就是前边提到的, 单纯的奇偶交叉排列二进制下是不连续的, 我们可以把精度设的越来越高, 但是终究它的极限是跳跃的。 再看上图我们发现凡是涉及到进位操作的时候都有可能会有跳跃。
所以我们可以看出GeoHash在使用过程中不能简单通过GeoHash值是否近似来判断是否离的很近, 而应一次获取圆心附近的九个方框(通过前缀是否相同判定, 由于进位的情况会改变前缀所以会把这种跳跃点忽略), 拿到所有点位后, 通过求欧氏距离来算定远近。
如何找到附近的区块
我们很容易联想到如果一个点在格林尼治天文台附近, 那么单纯通过前缀他会忽略掉离自己很近的目标。 事实上所有处于二分位置的线附近都会有一样的问题, 即明明离的很近, 但是前缀完全不同。 事实上查找附近区块是有规律的
image.png
通过这个图我们可以看出来, base32会把空间分为32块, 每一个小空间的空间排序也是一样的, 这样通过简单的排序规则, 我们就可以找到附近的8个区块的前缀, 然后一次获取9个区块, 再进行欧氏距离计算。
网友评论