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

FST
数据字典术语，通常从数据字典中查找指定单词的方式是对所有单词进行排序，使用二分查找。该方法的时间复杂度为Log(N) ，占用空间大小为O(N*len(term)) 。缺点是比较消耗内存，而且有完整的条款。当词条数达到千万级时，内存消耗非常大。
自 4 以来大量使用的数据结构是 FST（状态）。FST 有两个优点：
占用空间小，通过读词拆分复用和前缀后缀复用来压缩存储空间；查询速度快，查询时间复杂度只有O(len(term))
那么FST数据结构的原理是什么？我们先来看看什么是FSM(State) ，一个有限状态机，从“起始状态”到“终止状态” ，接受一个字符后，循环或者转移到下一个状态。
FST是一种特殊的FSM ，用来实现字典查找功能（也可以在NLP中转换）， FST可以用FST的形式来表示
示例：对“cat”、“deep”、“do”、“dog”和“dogs”五个词构造FST（注意：必须排序），结构如下：

文章插图
当值为对应的docId时，如cat/0 deep/1 do/2 dog/3 dogs/4 ， FST结构图如下：

文章插图
FST还有一个特点，就是在通用前缀的基础上，还会做一个通用的后缀，目的也是为了压缩存储空间。
红色弧线为NEXT- ，可通过绘图工具测试。
为了能够快速查找到docid ，使用了这个数据结构。具有以下特点：
元素排序，对应我们的倒链，按照docid从小到大排序；跳跃有固定的间隔，需要建立时指定。例如下图中的区间就是的级别；，这里指的是有多少层

文章插图
在哪里设置跳过指针？
? 设置更多的指针、更短的步数、更多的跳跃机会
? 更多指针比较和更多存储
? 设置更少的指针，更少的指针比较次数，但需要设置更长的步长? 更少的连续跳转
如果倒排列表的长度是L ，则将skip指针均匀地放置在每隔一步S 。
BKD树
也叫Block KD-tree ，根据FST的思想，如果查询条件很多，就需要根据FST找出每个条件的结果，进行联合操作。如果是数字类型，可能会有很多潜在的词条，查询销量会很低。为了支持高效的数值类或多维查询，引入了 BKD Tree 。在一个维度上，它是一个二叉搜索树。在二维中，如果要查询一个区间， logN的复杂度可以访问叶子节点对应的倒链。

文章插图
确定切分维度，其中维度的选择顺序为本维度方法中数据量最大的维度优先。一个直接的理解就是数据越分散，我们优先分割。分割点就是这个维度的中点。第 1 步和第 2 步是递归执行的。我们可以设置一个阈值。点数小于点数后，直到所有点都被分割后才会停止分割。

文章插图
过滤器
二进制处理，通过BKD-Tree找到的docID是无序的，所以要么先转换成有序的docID数组，要么构造，再与其他结果合并。
是一种预排序，只有在ES6.0之后才有。与查询时的排序不同，它是一种预排序，即数据预先按照一定的方式排序，是 Index 的一个设置，不能更改。