深入搜索引擎原理( 三 ) _搜索引擎

其中 Wi 通常使用 IDF 来表达，R 使用 TF 来表达；综上，BM25算法的相关性得分公式可总结为：

文章插图

BM25 通过使用不同的语素分析方法、语素权重判定方法，以及语素与文档的相关性判定方法，我们可以衍生出不同的搜索相关性得分计算方法，这就为我们设计算法提供了较大的灵活性。
Part 4、空间索引在点评口碑上，经常有类似的场景，搜索 “1公里以内的美食”，那么这个1公里怎么实现呢？
在数据库中可以通过暴力计算、矩形过滤、以及B树对经度和维度建索引，但这性能仍然很慢(可参考为什么需要空间索引 ) 。搜索里用了一个很巧妙的方法，Geo Hash 。

文章插图

如上图，表示根据 GeoHash 对北京几个区域生成的字符串，有几个特点：

一个字符串，代表一个矩形区域
字符串越长，表示的范围越精确 (长度为8时精度在19米左右，而当编码长度为9时精度在2米左右)
字符串相似的，表示距离相近（这就可以利用字符串的前缀匹配来查询附近的POI信息)

Geo Hash 如何编码？地球上任何一个位置都可以用经纬度表示，纬度的区间是 [-90, 90]，经度的区间 [-180, 180] 。比如天安门的坐标是 39.908,116.397，整体编码过程如下：
一、对纬度 39.908 的编码如下：

将纬度划分2个区间，左区间 [-90, 0) 用 0 表示，右区间 [0, 90] 用 1 表示，39.908 处在右区间，故第一位编码是 1；
在将 [0, 90] 划分2个区间，左区间 [0, 45) 用 0 表示，右区间 [45, 90] 用 1 表示，39.908处在左区间，故第二位编码是 0；
同1、2的计算步骤，39.908 的最后10位编码是 “10111 00011”

二、对经度 116.397 的编码如下：

将经度划分2个区间，左区间 [-180, 0) 用 0 表示，右区间 [0, 180] 用 1 表示，116.397处在右区间，故第一位编码是 1；
在将 [0, 180] 划分2个区间，左区间 [0, 90) 用 0 表示，右区间 [90, 180] 用 1 表示，116.397处在右区间，故第二位编码是 1；
同1、2的计算步骤，116.397 的最后6位编码是 “11010 01011”

三、合并组码

将奇数位放经度，偶数位放纬度，把2串编码组合生成新串：“11100 11101 00100 01111”；
通过 Base32 编码，每5个二进制编码一个数，“28 29 04 15”
根据 Base32 表，得到 Geo Hash 为：“WX4G”

即最后天安门的4位 Geo Hash 为 “WX4G”，如果需要经度更准确，在对应的经纬度编码粒度再往下追溯即可。
附：Base32 编码图

文章插图

Geo Hash 如何用于地理搜索？
举个例子，搜索天安门附近 200 米的景点，如下是天安门附近的Geo编码

文章插图

搜索过程如下：

首先确定天安门的Geo Hash为 WX4G0B，（6位区域码约 0.34平分千米，约为长宽600米区域)
而6位编码表示 600 米，半径 300 米 > 要求的 200 米，搜索所有编码为 WX4G0B 的景点即可
但是由于天安门处于 WX4G0B 的边缘位置，并不一定处在正中心。这就需要将 WX4G0B 附近的8个区域同时纳入搜索，故搜索 WX4G0B、WX4G09、WX4G0C 一共9个编码的景点
第3步已经将范围缩小到很小的一个区间，但是得到的景点距离并不是准确的，需要在通过距离计算过滤出小于 200 米的景点，得到最终结果。

由上面步骤可以看出，Geo Hash 将原本大量的距离计算，变成一个字符串检索缩小范围后，再进行小范围的距离计算，及快速又准确的进行距离搜索。
Geo Hash 依据的数学原理

文章插图

如图所示，我们将二进制编码的结果填写到空间中，当将空间划分为四块时候，编码的顺序分别是左下角00，左上角01，右下脚10，右上角11，也就是类似于Z的曲线。当我们递归的将各个块分解成更小的子块时，编码的顺序是自相似的（分形），每一个子快也形成Z曲线，这种类型的曲线被称为Peano空间填充曲线。
这种类型的空间填充曲线的优点是将二维空间转换成一维曲线（事实上是分形维），对大部分而言，编码相似的距离也相近，但Peano空间填充曲线最大的缺点就是突变性，有些编码相邻但距离却相差很远，比如0111与1000，编码是相邻的，但距离相差很大。