文章图片
文章图片
文章图片
文章图片
那么 ， 大家有没有想过 ， 这个查找功能是如何实现的吗？作为受过高等教育的人 ， 大家肯定立即就想到了可以通过经纬度进行计算 。 具体算法类似于这样：
地球近似于一个球体 ， 地球赤道周长约40075.04公里 ， 半径约为6371公里 ， 因此 ， 可以很容易地用立体几何的方法求出其距离 ， 例如说最常见的大圆距离（Great-Circle Distance） 。
公式如下：
其中 ，R为地球半径 ， Aj、Aw分别表示A点的经度、纬度；Bj、Bw分别表示B点的经度、纬度 。 这样 ， 通过简单的立体几何方法就可以很容易地求出其距离 。
如果有人对于地理信息学比较了解的话 ， 还会知道半正矢公式（Haversine公式） ， 因为大圆距离公式用到了大量的余弦函数 ， 因此在两点距离过短的时候 ， 会导致比较大的舍入误差 。 而半正矢公式则因为采用了正弦函数的方法 ， 因此即使距离过小 ， 也可以保留足够的有效数字 。 半正矢公式的形式如下所示：
其中
这里面的R为地球半径 ， 可取平均值 6371km；φ1 φ2 表示两点的纬度；Δλ 表示两点经度的差值 。
有了这些算法 ， 那么理论上来查找附近的人就可以很方便地实现了 。 但是为什么要说从理论上讲呢？因为在工程实践中 ， 这样查找的计算量太大了 。 对于几个经纬度的数据而言还可以 ， 但是对于大规模数据查询而言 ， 没有实际可操作性 。 就比如想在一个一百万条数据的数据库里查找附近5公里之内的餐馆有哪些 ， 那么要对一百万条数据做各种三角函数操作 ， 这显然是不现实的事情 ， 更别说在互联网上应用的数据体量远大于百万条 。 而且这样的数据也很难对其查询效率进行优化 。
那么 ， 要怎么解决这个问题呢？这就是我们今天要介绍的神奇算法 ， Geohash算法了 。 通过Geohash算法 ， 我们可以把两个坐标的距离计算简化为两个字符串的比较 ， 从而可以最大限度的应用速度更快的字符串相关函数 ， 并且对其进行排序或索引 。
下面我们就来看看Geohash算法具体是怎么做到这一点的 。
Geohash的本质就是将用到的整个地图区域进行矩形分割 ， 然后在各个矩形之中再次进行矩形分割 ， 而每一次分割中所在的区域用一个字符代表 ， 这样一次次分割之后 ， 就可以最大可能的逼近实际坐标所在地 。 而这个坐标也就可以用一串字符来代替了 。 常用的Geohash算法中 ， 每个字符用5个比特来标识 ， 这样就会有32个不同的组合（0-31） ， 于是我们就可以将这个地图区域划分为32个区域 。 这样划分之后 ， 第一个字母划分的区域就如下图所示：
然后我们再对各个区域继续进行划分 ， 就会得到类似于wx4eqzrx ， 这样的一个字符串了 。
而这时 ， 我们就可以方便地使用类似于
Select * from world where geohash like 'wx4eqw%';
这样的sql语句查询到附近想要查询的东西了 。 是不是很方便呢？通过这种方式 ， 我们就把复杂的三角函数计算 ， 转化成了计算化处理效率非常高的字符串操作了 。
那么 ， 想必大家一定要问了 ， 坐标转化成的字符串是怎么生成的呢？其实也很简单 。
我们以纬度39.928167为例 。
a. 首先我们以区间[-9090
进行二分为[-900)[090
， 称为左右区间 ， 可以确定39.928167属于右区间[090
， 标记为1
b. 接着将区间[090
进行二分为 [045)[4590
， 可以确定39.928167属于左区间 [045) ， 标记为0
c. 递归上述过程39.928167总是属于某个区间[ab
。 随着每次迭代区间[ab
总在缩小 ， 并越来越逼近39.928167 ， 划分次数越多 ， 距离就越精确 ， 字符串也就会越长 ， 如下图所示：
推荐阅读
- 地球的自转能力究竟有多强？
- 4.6亿年前生物多样性为何盛极而衰
- 处在怎样的一个维度，可以把时间、空间自由掌控着
- 散射辐射变送器的功能与安装
- 直径超200万光年！中国天眼最新发现的宇宙结构，在2.9亿光年外
- 百科全书-地理篇-气候类型 简介
- 历史探秘：5亿年前的“皮鞋”印之谜，外星人的足迹？
- 地球各个角度受到的太阳辐射电磁波不同
- 金字塔究竟是做什么的？