2021SC@SDUSC
全文检索的过程全文检索主要分为创建索引、搜索索引这两件事。
因此，索引是其中很重要的东西，那么关于索引的问题因此而形成：
- 索引应该包括什么东西？
- 索引的建立方法。
- 如何搜索这些索引？
在解释这个问题之前，我先去了解了顺序扫描。
顺序扫描速度慢，我们文件在存储的时候是按照通过文件名查找底下的文字，即文章内容的字符串。
在查询时需要查询文章内容中匹配的字符串，然后得到文件名，这两个动作其实是相反的，所以速度比较慢。
所以我们需要用到索引，来保存从字符串到文件的映射。
由于从字符串到文件的映射是文件到字符串映射的反向过程，于是保存这种信息的索引称为反向索引。
接下来就正式解释索引里的内容，反向索引所保存的分为两个部分： 词典和倒排表。
词典存了文章内容中拆分成的词。而倒排表则是每个词被包含的文章，结构为链表：每个字符串都指向包此字符串的文档(document)链表，即为倒排表。
如果我们要搜索包含 a 和 b 的文件，则先取出包含字符串a 和b 的链表，然后进行链表的合并，就可以得出包含上面两个字符串的文件。
通过上面的描述，大家可能很容易想到创建索引的优势了：
创建索引只需要进行一次，不必像顺序扫描，每查找一次就要扫描一次，所以速度更高！
首先，把需要分词的文档首先传给分词组件，代码中为Tokenizer。
- 将文档分成一个一个单独的单词。
- 去除标点符号。
- 去除停词(没有意义的词)。
这样我们就将最开始的文档分成了一个个词元。
接下来，词元将会被语言处理组件处理(Linguistic Processor)，把类似意思的词转化为同一个词，使用户搜同义词或者类似的词可以被搜到。（因为他们都会被处理组件处理为同一个词，再进行搜索）
然后就可以将得到的词传给索引组件了（indexer）
索引组件做了以下事情：
- 将得到的词创建字典，记录了词和他们的对应文章名。
- 对词进行排序。
- 将相同的词合并。
其实经过上面的步骤，我们已经可以查找到需要的文件了，但是对于后续的处理同样是必要的，因为我们如何将搜索出的结果进行处理，来使他们达到按照你最想要的结果在最前面这样排序呢？
从用户的角度出发我们再来看一看：
搜索主要分为以下几步：
第一步：用户输入查询语句
查询语句同我们普通的语言一样，也是有一定语法的。
不同的查询语句有不同的语法，如 SQL 语句就有一定的语法。
查询语句的语法根据全文检索系统的实现而不同。最基本的有比如：AND, OR, NOT 等。
举个例子，用户输入语句：lucene AND learned NOT hadoop。
说明用户想找一个包含 lucene 和 learned 然而不包括 hadoop 的文档。
第二步：对查询语句进行词法分析，语法分析，及语言处理。
首先是词法分析：
如上述例子中，经过词法分析，得到单词有 lucene，learned，hadoop, 关键字有 AND, NOT。
如果在词法分析中发现不合法的关键字，则会出现错误。如 lucene AMD learned，其中由于AND 拼错，导致 AMD 作为一个普通的单词参与查询。
然后是语法分析：
语法分析主要是根据查询语句的语法规则来形成一棵语法树。
如果发现查询语句不满足语法规则，则会报错。如 lucene NOT AND learned，则会出错。
第三步：搜索索引得到符合语法树的文档。
此步骤有分几小步：
- 首先，在反向索引表中，分别找出包含 lucene，learn，hadoop 的文档链表。
- 其次，对包含 lucene，learn 的链表进行合并操作，得到既包含 lucene 又包含 learn 的文档链表。
- 然后，将此链表与 hadoop 的文档链表进行差操作，去除包含 hadoop 的文档，从而得到既包含 lucene 又包含 learn 而且不包含 hadoop 的文档链表。
此文档链表就是我们要找的文档。
第四步：根据得到的文档和查询语句的相关性，对结果进行排序。
虽然在上一步，我们得到了想要的文档，然而对于查询结果应该按照与查询语句的相关性进行排序，越相关者越靠前。
如何计算文档和查询语句的相关性呢？
不如我们把查询语句看作一片短小的文档，对文档与文档之间的相关性(relevance)进行打分(scoring)，分数高的相关性好，就应该排在前面。
那么又怎么对文档之间的关系进行打分呢？
这可不是一件容易的事情，首先我们看一看判断人之间的关系吧。
首先看一个人，往往有很多要素 首先，如性格，信仰，爱好，衣着，高矮，胖瘦等等。
其次对于人与人之间的关系，不同的要素重要性不同，性格，信仰，爱好可能重要些，衣着，高矮，胖瘦可能就不那么重要了，所以具有相同或相似性格，信仰，爱好的人比较容易成为好的朋友，然而衣着，高矮，胖瘦不同的人，也可以成为好的朋友。
因而判断人与人之间的关系，首先要找出哪些要素对人与人之间的关系最重要 首先要找出哪些要素对人与人之间的关系最重要。其次要判断两个人的这些要素之间的关系，比如一个人性格开朗，另一个人性格外向，一个人信仰佛教，另一个信仰上帝，一个人爱好打篮球，另一个爱好踢足球。我们发现，两个人在性格方面都很积极，信仰方面都很善良，爱好方面都爱运动，因而两个人关系应该会很好。
下面看一下如何判断文档之间的关系。
首先，一个文档有很多词组成，如 search, lucene, full-text, this, a, what 等。
其次对于文档之间的关系，不同的词重要性不同，比如对于本篇文档search, Lucene, full-text 就相对重要一些，this, a , what 可能相对不重要一些。所以如果两篇文档都包括search, Lucene，fulltext，这两篇文档的相关性好一些，然而就算一篇文档包括 this, a, what，另一篇文档不包括 this, a, what，也不能影响两篇文档的相关性。
因而判断文档之间的关系，首先找出哪些词(Term)对文档之间的关系最重要然后判断这些词(Term)之间的关系。找出词(Term)对文档的重要性的过程称为计算词的权重(Term weight)的过程。计算词的权重(term weight)有两个参数，第一个是词(Term)，第二个是文档(document)。词的权重(Term weight)表示此词(Term)在此文档中的重要程度，越重要的词(Term)有越大的权重(Term weight)，因而在计算文档之间的相关性中将发挥更大的作用。
判断词(Term)之间的关系从而得到文档相关性的过程应用一种叫做向量空间模型的算法(Vector Space Model)。
索引过程：
- 有一系列被索引文件
- 被索引文件经过语法分析和语言处理形成一系列词(Term)。
- 经过索引创建形成词典和反向索引表。
- 通过索引存储将索引写入硬盘。
搜索过程：
- 用户输入查询语句。
- 对查询语句经过语法分析和语言分析得到一系列词(Term)。
- 通过语法分析得到一个查询树。
- 通过索引存储将索引读入到内存。
- 利用查询树搜索索引，从而得到每个词(Term)的文档链表，对文档链表进行交，差，并得到结果文档。
- 将搜索到的结果文档对查询的相关性进行排序。
- 返回查询结果给用户。
