传统的我们的检索是通过文章,逐个遍历找到对应关键词的位置。
而倒排索引,是通过分词策略,形成了词和文章的映射关系表,这种词典+映射表即为倒排索引。
有了倒排索引,就能实现o(1)时间复杂度的效率检索文章了,极大的提高了检索效率。
倒排索引的底层实现是基于:FST(Finite State Transducer)数据结构。
lucene从4+版本后开始大量使用的数据结构是FST。FST有两个优点:
1、 空间占用小。通过对词典中单词前缀和后缀的重复利用,压缩了存储空间;
2、 查询速度快。O(len(str))的查询时间复杂度。
标签:
笔试题
刷题
简历模板
AI算法
大数据
内推
内推: