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 构建
此时，再输入wl试试？尽管节点3是final节点,但是由于值对不上，所以不会搜索成功的。
