既然涉及的是旅游搜索,那就不能少了空间搜索的内容。现在移动设备之广泛想必不必多说。根据eMarketer的新数据,2015年全球智能手机用户将达到19.1亿,2016年该指数将增长12.6%达到21.6亿。智能手机都会带有GPS模块,现在一个APP不获取下用户位置都觉得是吃亏,不过这也用户隐私的侵犯也很严重,尤其是在Android生态圈中,不过现在各大手机厂商的系统都对这一块做了一些限制。

空间搜索,又名Spatial Search,基于空间搜索技术,可以做到:

  1. 对Point(经纬度)和其他的几何图形建索引
  2. 距离计算:根据给定点计算它到其他点的距离。
  3. 限定框过滤器:查找某些特定区域内所有匹配项(文档)。
  4. 排序:根据到固定点的距离对搜索结果进行排序。
  5. 相关度改进:使用距离作为记录中的增强因素,同时允许其他因素发挥作用。
  6. 查询解析:在给出位置的地址或其他一些用户规定时,创建可用于根据索引数据进行搜索的编码表示。

空间搜索原理

在Solr中,空间搜索主要基于GeoHash和Cartesian Tiers 2个概念来实现。下面先来讲解一下这两个算法,虽然这两种算法可以很容易在网上找到资料,但是我在这里对其进行总结,并根据之前自己的知识和相似的技术、算法思想进行对比。后面将会是和Solr相关的如何进行配置和查询,虽然这些算法的实现比较复杂,好在Solr已经帮我们做好了,通过配置就可以使用。当然这里最需要感谢的美团的技术团队,这么无私的把这些技术分享出来,我基本上是靠美团的这篇文章来完成了这个模块的工作。

GeoHash算法

GeoHash即Geology和Hash的组合,使用hash算法的方法对地理信息进行编码,要想充分了解GeoHash,我们先来了解Hash。

各种Hash及其核心思想

Hash(散列)算法,是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要,使得数据量变小,将数据的格式固定下来。该函数将数据打乱混合,重新创建一个叫做散列值(hash values,hash codes,hash sums,或hashes)的指纹。

计算机中有关Hash的应用有很多的,例如java的HashMap、Hash Table、数据加密、数据完整性、错误校正等方面都有应用。它的基本思想上面的Wikipedia已经定义的比较好了,我来分享下我的见解,hash就是把数据按照某种规则进行重组再表示,这个再表示比原始的数据量要小,其实是有损的转换,因此不能从再表示中还原数据。另外由于再表示的取值空间比较小,会有不同的原始数据经过Hash之后得到相同的再表示,这也就意味着冲突,好的转换规则能最低限度的降低冲突概率。

和GeoHash比较相近的应用是Hash Table,它通过关键码值(Key value)来访问数据,把key通过一个hash函数生成Hashcode,这个Hashcode对应一个位置,而其value就放在这个位置,相当于是key和value所在位置的一个映射。我们知道线性的数据结构能够通过index(下标)来快速获取数据(非线性需要遍历才能找到),我们可以直接把下标当做key,这样的<key,value>也可以快速找到,但希望的是key可以是任何字符,那么经过hash函数的转换,Hash Table应运而生。

Hash Table是为了解决查询速度的问题,GeoHash当然也是为了解决这个问题,它主要解决的是地理位置的查找,不过其复杂程度比Hash Table高一些,不过也算比较容易理解。

GeoHash初识

其实GeoHash就是将二维的经纬度转换成字符串,并且这些字符串有个特征是同一个地区的前缀N位是相同的,如果两点的GeoHash字符串前缀相同的位数越多表示这两点越接近,因此将距离的计算转换成字符串相同位数的比较,虽然是其基本原理如此常见,但运算量的减小确是非常巨大的。

为了能让大家对我上面说的概念有个更直观的了解,于是我很恬不知耻地借用别人的图片来给大家看,也是蛮拼(lan)的。 上图可以看到每一个字符串代表了一个矩形区域(为啥是矩形不是方形?下面再说),只要是这个区域内的所有点经过GeoHash算法之后前5位一定是相同的。这就有个好处,那就是缓存啊,把数据按照区域缓存起来加快访问速度和减小负载,真是机智。

上面的图是啥意思呢?字符串越长,表示的范围越精确。5位的编码能表示10平方千米范围的矩形区域,而6位编码能表示更精细的区域(约0.34平方千米),也就是说在大格子里面画小个子,也从正面说明了前缀相同的位数越多表示这两点越接近。

GeoHash算法步骤

我们都知道地球的纬度为-90~90,经度为-180~180,我就用美团这篇文章的数据来讲吧。例如纬度为39.92324,经度为116.3906(这货真懒)

二分编码

  1. 对区间[-90,90]进行二分为[-90,0),[0,90],称为左右区间,可以确定39.92324属于右区间[0,90],给标记为1;
  2. 接着将区间[0,90]进行二分为 [0,45),[45,90],可以确定39.92324属于左区间 [0,45),给标记为0;
  3. 递归上述过程,39.92324总是属于某个区间[a,b],随着每次迭代区间[a,b]总在缩小,并越来越逼近39.928167;
  4. 如果给定的纬度(39.92324)属于左区间,则记录0,如果属于右区间则记录1,这样随着算法的进行会产生一个序列1011 1000 1100 0111 1001,序列的长度跟给定的区间划分次数有关。
  5. 同理,地球经度区间是[-180,180],对经度116.3906进行编码的过程也类似的二分编码,过程如下:

组码&Base32编码

通过上述计算(图中只显示16次二分,共20次),纬度产生的编码为1011 1000 1100 0111 1001,经度产生的编码为1101 0010 1100 0100 0100。偶数位放经度,奇数位放纬度。因为经纬度都分别二分了20次,现在要组合成一个二十位数,这个数从左往右(纬度表示为lat,经度表示为lng)

|40|39|38|37|36|…| |