什么是搜索引擎？深入搜索引擎原理( 三 ) _搜索引擎原理

BM25算法的通式如下：
其中Q代表Query ， qi代表Q解析后的词素（对于中文，我们可以使用Query的分词作为词素分析，每个词都可以看成词素qi 。）； d 代表一个搜索结果文档； Wi 表示词素qi 的权重； R(qi, d)表示词素qi与文档d的相关度。
其中Wi通常用IDF表示， R用TF表示；综上所述， BM25算法的相关性得分公式可以概括为：
BM25 通过使用不同的词素分析方法、词素权重确定方法、词素-文档相关性确定方法，我们可以推导出不同的搜索相关性得分计算方法，为我们提供了更大的设计算法。灵活性。
部分4、空间索引
在评论和口碑中，经常会出现类似的场景，搜索“1公里内的食物” ，那么这1公里是如何实现的呢？
在数据库中，经纬度可以通过蛮力计算、矩形过滤、B-tree等方式进行索引，但是性能还是很慢（见为什么需要空间索引）。搜索中使用了一种非常巧妙的方法， Geo Hash 。

文章插图
如上图所示，表示根据北京几个地区生成的字符串有几个特点：
Geo Hash 是如何编码的？
地球上的任何位置都可以用纬度和经度来表示。纬度范围是[-90, 90] ，经度范围是[-180, 180] 。比如天安门的坐标是39.908,116.397 ，整体编码过程如下：
一、纬度39.908编码如下：
纬度分为两个区间，左边区间[-90 ， 0)用0表示，右边区间[0, 90]用1表示， 39.908是在右区间，所以第一个区间的一位码为1；将[0, 90]分成2个区间时，左边区间[0, 45)用0表示，右边区间[45, 90]用1表示， 39. 908是在左边的区间，所以第二个数字代码是0；同1、2的计算步骤， 3的后10位9.908码为“10111 00011”
二、经度116.397的编码如下：
经度分为两个区间，左边区间[-180 ， 0)用0表示，右边区间[0, 180]用1表示， 116.397是在右区间，所以第一个区间的一位码为1；将[0, 180]分为2个区间时，左边区间[0, 90)用0表示，右边区间[90, 180]用1表示， 116. 397是在正确的范围内，所以第二个位码为 1；同1、2的计算步骤， 11的最后6位码6.397为“11010 01011”
三、合并代码
把奇数的经度和偶数的纬度，把这2串代码组合起来，生成一个新串：“11100 11101 00100 01111”；通过编码，每5个二进制码为一个数字，根据表为“28 29 04 15” ，得到Geo Hash为：“WX4G”
即天安门广场的最后4位Geo Hash是“WX4G” 。如果需要更准确的经度，可以追溯对应的经纬度编码粒度。
附件：编码图

文章插图
Geo Hash 如何用于地理搜索？
比如搜索天安门200米以内的景点，下面是天安门附近的Geo code

文章插图
搜索过程如下：
首先确定天安门广场的Geo Hash为，（6位区号约为0.34平分公里，长宽约600米）， 6位区号代表600米，有半径300米>要求200M ，可以搜索所有编码为的景点，但由于天安门在边缘，不一定在中心。这需要将 8 个附近区域同时包含在搜索中。因此，在第三步一共搜索9个编码景点时，范围已经缩小到一个很小的区间，但是得到的景点的距离并不准确。距离计算过滤掉小于200米的景点得到最终结果。