当前位置：首页 > news >正文

2023-02-04 Elasticsearch 倒排索引的理解 Trie前缀树原理

news 来源：原创 2024/4/27 18:57:27

1 搜索引擎引出倒排表的原理

全文搜索引擎自然语言处理(NLP) 、爬虫、网页处理、大数据处理如谷歌、百度、搜狗、必应等等
垂直搜索引擎有明确搜索目的的搜索行为如各大电商网站、OA、站内搜索、视频网站等
要求：查询快（高效的压缩算法快速的编码和解码速度）查询准（BM25 、TF-IDF）检索结果丰富（召回率）

面向海量数据，如何达到“搜索引擎”级别的查询效率?

索引 1-帮助快速检索 2-以数据结构为载体 3-以文件的形式落地

我们以mysql数据库为例
在这里插入图片描述
MySQL索引能解决大数据检索的问题吗?

1、索引往往字段很长，如果使用B+trees，树可能很深，I0很可怕
2、索引可能会失效
3、精准度差

在这里插入图片描述
全文检索：索引系统通过扫描文章中的每一个词，对其创建索引，指明在文章中出现的次数和位置，当用户查询时，索引系统过就会根据事先创建的索引进行查找，并将查找的结果反馈给用户的检索方式。
在这里插入图片描述
倒排索引的核心原理：

2 倒排索引的数据结构

在这里插入图片描述

3 FOR压缩算法

在这里插入图片描述
拆分的规则 - 这个折中值是怎么确定的呢？

4 RBM 压缩算法

在这里插入图片描述

5 Trie前缀树原理

当我们利用搜索引擎时，只需输入部分字符，就可以得到我们想要的关键字。这种向部分键入的字符串建议可能的单词的功能便是自动补齐功能，广泛用于搜索引擎、IDE 等。那这种功能是怎样实现的呢？本文介绍的前缀树便是一种很好的解决方案。

前缀树，又称字典树。它是一棵 N 叉树。前缀树一般用于存储、查找字符串。

前缀树的每个节点代表一个字符，通常用一个属性 isEnd 来标注字符串的末尾，从根节点到 isEnd 为 true 的节点的路径便是一个字符串。

前缀树的一个重要的特性是，结点所有的后代都与该结点相关的字符串有着共同的前缀，这是前缀树名称的由来。

下面这个例子，存储了 apply、apple、apart、bee 和 bed 和app 6个单词的前缀树。
在这里插入图片描述
FSM(Finite State Machines)有限状态机：表示有限个状态(State)集合以及这些状态之间转移和动作的数学模型。其中一个状态被标记为开始状态，0个或更多的状态被标记为final状态。

有限个状态；同一时间只能处于同一个状态；不同状态可以互相转换；状态是无序的

FSA：有限状态接收机
确定性：在任何给定状态下，对于任何输入，最多只能遍历一个transition
非循环：不可能重复遍历同一个状态
Final唯一性：当且仅当有限状态机在输入序列的末尾处于"最终""状态时，才"接受"特定的输入序列

在这里插入图片描述

举例：ms msc 都不存在。
在这里插入图片描述
思考：wl 是否存在？但是词项字典不存在wl。

FST：有限状态转换机
FST最重要的功能是可以实现Key到Value的映射，相当于HashMap<Key,Value>。FST的查询速度比HashMap要慢一点，但FST的内存消耗要比HashMap少很多。FST在Lucene中被大量使用，例如：倒排索引的存储，同义词词典的存储，搜索关键字建议等。

查询快;极致压缩空间占用;
特性:
确定性：在任何给定状态下，对于任何输入，最多只能遍历一个transtion
非循环：不可能重复遍历同一个状态
transducer：转化器有相关的值(payload)，final节点会输出一个值
比起前面的前缀树以及FSA，在存储的时候多了一个value值。

在这里插入图片描述

fst 构建