Description: 这篇博客简单介绍一下搜索引擎中的基础知识和原理。
由于在开发 github 上的 StackExchangeRecommenderSystem 时候会用到 lucene，
所以在这里先来复习一下搜索引擎中的基础知识和算法。
索引的基础知识
索引是在程序员的世界是常常被提起的名词，例如，在数据库中，在编程的时候为高级复杂的数据结构以及
对网页所创建索引，来提高程序的查询效率。
索引在日常生活中也很常见:字典目录中某个词语后面标识了出现该词的页码。
下面我们来一起学习一下，关于索引常见的词汇:
- 文档(Document): 索引所标定的’目标对象’: 是数据库索引，那么文档便是数据表中的某条记录;
如果是对网页创建的’倒排索引’(索引的一种类型)，那么文档便是网页的页面； 这个’目标对象’
还可以是某种具体的文件，例如 word，PDF文档 - 文档集合 (Document Collection): 就是上述’文档’构成的集合
- 文档编号(Document ID): 在搜索引擎内部为每个文档赋予的唯一标识，可以在文档集合中唯一标识一个文档
- 单词编号(Word ID): 用来唯一标识某个单词
- 倒排索引(Inverted Index): 普通的索引是为某个文档创建索引出在该文档中某个单词，
而倒排索引则是以单词为主题，通过单词来索引出出现该单词出现的文件； 倒排索引由两部分组成
{单词词典,和出现该单词的文档集合} - 单词词典(Lexicon): 搜索引擎通中的索引单位是单词，单词词典是在所有文档集合中出现过的单词所构成的集合；
而在单词词典中的每条索引项中记录的信息有{单词信息，单词所指向出现该单词的文章集合-倒排列表} - 倒排列表(PostingList): 倒排列表指的是，出现过某个单词的所有文档所构成的列表和该单词在该文档中出现的
位置信息； 倒排列表中的每条记录我们可以将其称作是倒排项(Posting). 倒排文件(Inverted File): 倒排文件是存储倒排索引的物理文件。我们都已经知道了倒排索引由两部分组成，
分别是，单词词典和倒排列表. 在此基础上，存放倒排列表的文件就叫做倒排文件。
倒排索引小例子
比如那今天的知乎日报新闻来举例
文章编号 文章标题 1 如何自己制定健身训练计划？ 2 女生怎么健身锻炼好身材？ 3 减肥对外貌的改变有多大？ 4 健身教练有哪些内幕？ 5 女生如何锻炼减肥既简单有健康？
单词 ID 单词 倒排列表 1. 自己 {1} 2. 女生 {2,5} 3. 减肥 {3,5} 4. 健身 {1,2} 5. 教练 {4} 6. 简单 {5} 7. 训练 {1} 8. 外貌 {3} 9. 改变 {3} 10. 哪些 {4} 11. 内幕 {5} 12. 锻造 {2,5} 13. 身材 {2} 14. 训练 {1} 15. 计划 {1}
当然，我们也为了让索引列表更细致的记录索引文件的信息来添加上某个词语出现的频率信息，TF 便是用来描述词语在某个文章中出现的次数的. 例如 ‘女生’ 这个词语在文章 2，5 均出现过，并且出现 1 次
便可以记成 女生 {2;1,5;1} 这样子。更加细致的记录方式是，将这个单词出现的位置也记录下来：
例如 ‘女生’这个单词在文章2,5中出现的位置分别是第 1 个位置，就写成如下的格式
女生 { (2;1;<1>),(5;1;<1>) }
单词词典 (Lexicon)
单词词典存放了在文档集合中出现过的所有单词的相关信息的同时也记录了该单词集合中的每个单词
所映射到的倒排列表在倒排文件中的位置信息。
可以试想一下，如果需要创建索引的文档集合十分的巨大，那么随之提出出来的单词词典中所存放的单词数量
也是十分庞大的。在数据结构课程中我们已经学习过，如果要快速的定位某个单词(键值)的话可以借助于
哈希链表或是树形词典这类的数据结构。
哈希加链表 - 单词词典
哈希加链表是处理哈希表冲突的一种解决方法，哈希表有随之配套的 hash 散列函数，会为每个输入的
key 键生成’唯一’标定该key 对应 value 的标识，但是如果 hash 散列函数选取的不当的话，便会造成
不同的 key 生成了重复的标识； 这就是所谓的’冲突’的发生，处理’冲突’有着不同的方法，
加链表就是在发生冲突的 key 的后面开辟一块空间存放后来的 key ; 待到查找的时候，通过 hash 散列函数
找到该 hash 生成数值指定的链表头，沿着链表继续寻找就可以了。
树形结构 - 单词词典
前缀树和后缀树都是可以做单词词典很好的数据结构
倒排列表
在前面我们提到过了，倒排列表中的基本构成单元倒排索引项中包含字段有:
{单词出现的文档的唯一编号,单词出现频率,<单词在文档中的位置1,位置2,位置3…>}
但是在实际的应用中为了尽量节省内存，通常会使用文档编号的差值来取代文章的唯一编号。
建立索引
建立索引有着不同的方法,同时索引也分为动态索引和静态索引，其中静态索引是生成索引之后在修改文档集合中的
文档之后，不能自动的更新之前索引文件 ； 而动态索引则是生成索引之后，修改文档集合中的文件内容之后
会随之自动的更新文档文件。
静态索引
两遍文档遍历法
两遍文档遍历法在创建索引的时候需要对文档集合执行两遍扫描，在创建索引的时候仅需要内存即可，整个过程无需磁盘参与。
- 首次扫描:
算出为该文档集合创建的索引所需的内存容量大小:搜集文档集合包含文档个数 N ，文档集合中不重复单词总数 M, 每个单词在多少个文档中出现 DF. 将所有单词的 DF 数值进行加和便是建立最终索引所需要的内存大小。 第二次扫描:
首次扫描已经确定了文档集合中的每个单词的 DF信息，在第二次扫描的时候，为每个单词的 DF 信息分配内存空间，并使用指针将单词集合与单词的 DF 信息将连接即可，也就是简历每个单词的倒排列表信息；
但是通过上面的陈述可知，在单词倒排列表中的倒排索引项仅仅包含单词 DF信息还是不够的；对文档 ID 或是文档 ID 偏移量的计算以及单词在文档中出现位移和出现次数等这些信息都可以在第二次扫描的时候来完成。
等到两遍扫描结束之后，将内存中创建的倒排列表和单词词典信息写入到磁盘中就完成了索引的创建了。对两遍文档遍历法的评估: 因为全程使用的是内存无需磁盘的参与，所以连通文档集合和生成的倒排列表等数据信息均需要存放到内存中，这需要内存足够大，或者是仅仅适用于创建文档集合规模较小的索引。同时，需要对文档进行两次扫描，比较耗时在速度上并不占优势。
排序法
排序法为文档集合创建索引是为了弥补两遍遍历法建立索引过程中，对内存消耗大这一缺点提出的。两边遍历索引生成方法使用内存的大小是不固定的，如果文档集合大内存开辟就会大一些，相反便会小一些。而排序法无论文档集合如何，其所需要的内存大小均是固定分配的。开辟的内存空间主要用来存放词典信息和索引的中间结果。
每当中间结果将内存吃空的时候，便会统一将内存中的中间数据写入到磁盘中。遵循上述倒排索引中所介绍的两部分的结构-单词词典,倒排列表(倒排列表的组成单元是倒排索引项)，在整个的排序法创建文件集合索引的过程中，单词词典始终是作为常驻内存的数据结构的。- 读取文档，对文档进行编号，每个文档为其创建唯一的标识 ID 号码
解析文档，每当在文档中遇到新单词，
{ 查看该单词在单词词典中是否有记录 1. 有记录，获取该单词在词典中的 ID 号码 2. 单词词典中没有记录该单词，为该单词创建全词典唯一的 ID 号码，然后将其收录到单词词典中 }在对当前文档完成了读取和解析之后，便能够为当前文档中出现的每个单词均创建包含着如下信息
(单词ID,文档ID,单词频率)
上述三元组便可以作为倒排索引列表中的索引项了，将该三元组索引项集合追加到用来存放中间处理结果的大小固定的内存缓冲区中。然后便可以开始处理下一个文档了。
- 在内存缓冲区被占满之前需要将缓冲区中的数据写入到磁盘临时文件中去，不过在写入之前需要对内存中的三元组序列执行排序操作； 首先按照单词 ID 进行非递减，然后按照文档 ID 进行非递减排序。由于内存中存放的中间结果并不一定全都是同一个文件生成的中间信息，所以会有单词ID 相同但是文档ID不同的情况，这种情况按照文档ID非递减的规则进行排序。PS: 在上述的全部过程中，单词词典是常驻内存的
- 每次执行向磁盘中写入中间缓存文件操作均是写入一个新的缓存文件，而不是在之前的缓存文件中执行追加。在对所文档集合中的每个文档均读取解析之后，剩下的工作便是合并临时写入磁盘的所有的中间文件了。由于写入磁盘之前在内存中执行了先按单词ID然后文章ID进行排序的操作，所以在合并的时候，只要首先将所有中间文件中单词ID相同的三元组合并为一个数组(由三元组元素构成的有序序列)，而所有的数组组合起来便是该文件的倒排列表了。接下来只要将倒排列表中的内容写入到文件中即可。而这个文件便是所谓的索引文件了。
- 对排序法的评估: 在排序法创建文档集合索引的过程中，单词词典作为常驻内存数据结构并不会被写入到磁盘的中间临时文件中且大小也随着解析文档个数的增多而变大，同时排序法中分配的内存大小是固定的，所以当单词词典大小变大之后，每次用来缓存三元组的个数也会随之减少，如果单词词典继续增大会无法缓存解析文件而生成的三元组，这样便会频繁的执行写入操作,从而导致程序整体性能的下降。
归并法
归并法是为了弥补排序法中，单词词典常驻内存耗空分配的固定内存这一缺陷而提出的。归并法的特点是在每次执行三元组数据信息写入的同时也会将单词词典信息写入到中间临时文件中。这样便可以保证为程序分配固定大小的内存会全部用于后续索引的创建。
- 归并法的执行过程和排序法大部分相同，不同之处之一是在写入中间缓存文件中是将 {单词词典，三元组集合} 写入到中间缓存文件中
之二是在文档集合中的全部文档完成解析之后，将所有生成的临时文件进行合并的时候，每个临时文件中存放的是最终倒排列表的一部分； 而最后的合并操作便是将所有的部分倒排列表合并成一个完成的倒排列表。
分布式索引
分布式索引和数据库中的’分片’ 技术有些类似，数据库的’分片’ 技术是通过将一张大数据库表中的信息按照表中的某个属性字段
中的不同值/或是范围分割成许多个来自于该大数据表的’子表’； 常用作’分片’的属性有地域和时间 ；
而分布式索引技术则是将文档集合按照文档或者是单词来对索引进行划分。
按照文档来划分索引
将大的文档集合划分成分布于不同机器上的文档子集，为每个文档自己创建各自的索引。
在执行查询的时候，会在每个机器上面执行查询，并把来自于每个子集的查询结果进行合并生成最终查询结果
按照单词来划分索引
在创建按照单词划分的倒排索引的时候，划分发生在合并中间缓存文件生成最终索引文件的时候。
每当将来自于所有中间缓存文件中的同一单词ID的三元组合并之后，将该三元组集合+单词发送到某台主机上面。
便完成了按照该单词对索引进行’分片’的操作。
在实际的应用场景中，按照文档来进行索引的划分这种方法比较常使用，而按照单词的划分仅仅在特定场合下使用。
因为按照单词来划分索引的可扩展性、均衡负载和容错性都不是很好。
查询处理
一次一个单词的查询处理
将用户查询语句执行清洗(我通常把去掉语句中无用符号和去掉停用词的操作叫做’清洗’…好记),
然后执行分词操作将语句分成多个词语组成集合，获取每个词语的倒排列表，然后计算每个词语与倒排列表中的
每一个文件的相似度，计算相似度之后，如果有文档重复的(两个不同词语倒排索引到同一个文档)，那么将重复的文档
得分进行累加；最后将得出得分最高的 K 个文档(通过优先队列进行存放)作为查询结果进行返回即可