全⽂检索原理
在介绍全⽂检索前，先简单说下全⽂数据搜索的两种⽅式：
  　顺序扫描法(Serial Scanning)：所谓顺序扫描，⽐如要内容包含某⼀个字符串的⽂件，就是⼀个⽂档⼀个⽂档的看，对于每⼀个⽂档，从头看到尾，如果此⽂档包含此
字符串，则此⽂档为我们要的⽂件，接着看下⼀个⽂件，直到扫描完所有的⽂件。如利⽤windows的搜索也可以搜索⽂件内容，只是相当的慢。如果你有⼀个80G硬盘，如果
想在上⾯到⼀个内容包含某字符串的⽂件，不花他⼏个⼩时，怕是做不到。Linux下的grep命令也是这⼀种⽅式。⼤家可能觉得这种⽅法⽐较原始，但对于⼩数据量的⽂件，这
种⽅法还是最直接，最⽅便的。但是对于⼤量的⽂件，这种⽅法就很慢了。
  全⽂检索(Full-text Search) ：对全⽂数据中的⼀部分信息提取出来，重新组织，使其变得有⼀定结构，然后对此有⼀定结构的数据进⾏搜索，从⽽达到搜索相对较快的⽬
的。
这部分从⾮结构化数据中提取出的然后重新组织的信息，我们称之索引。
这种先建⽴索引，再对索引进⾏搜索的过程就叫全⽂检索(Full-text Search)。
下⾯这幅图描述了全⽂检索的⼀般过程:
全⽂检索⼤体分两个过程，索引创建(Indexing)和搜索索引(Search)。
索引创建：将现实世界中所有的结构化和⾮结构化数据提取信息，创建索引的过程。
搜索索引：就是得到⽤户的查询请求，搜索创建的索引，然后返回结果的过程。
于是全⽂检索就存在三个重要问题：
1. 索引结构？(Index)
2. 如何创建索引？(Indexing)
3. 如何对索引进⾏搜索？(Search)
下⾯我们顺序对每个问题进⾏研究。
1.索引⾥⾯究竟存些什么
索引⾥⾯究竟需要存些什么呢？
⾸先我们来看为什么顺序扫描的速度慢：
其实是由于我们想要搜索的信息和⾮结构化数据中所存储的信息不⼀致造成的。
⾮结构化数据中所存储的信息是每个⽂件包含哪些字符串，也即已知⽂件，欲求字符串相对容易，也即是从⽂件到字符串的映射。⽽我们想搜索的信息是哪些⽂件包含此字
符串，也即已知字符串，欲求⽂件，也即从字符串到⽂件的映射。两者恰恰相反。于是如果索引总能够保存从字符串到⽂件的映射，则会⼤⼤提⾼搜索速度。
由于从字符串到⽂件的映射是⽂件到字符串映射的反向过程，于是保存这种信息的索引称为反向索引。
反向索引的所保存的信息⼀般如下：
假设我的⽂档集合⾥⾯有100篇⽂档，为了⽅便表⽰，我们为⽂档编号从1到100，得到下⾯的结构：
左边保存的是⼀系列字符串，称为词典。
每个字符串都指向包含此字符串的⽂档(Document)链表，此⽂档链表称为倒排表(Posting List)。
有了索引，便使保存的信息和要搜索的信息⼀致，可以⼤⼤加快搜索的速度。
⽐如说，我们要寻既包含字符串“lucene”⼜包含字符串“solr”的⽂档，我们只需要以下⼏步：
1. 取出包含字符串“lucene”的⽂档链表。
2. 取出包含字符串“solr”的⽂档链表。
3. 通过合并链表，出既包含“lucene”⼜包含“solr”的⽂件。
看到这个地⽅，有⼈可能会说，全⽂检索的确加快了搜索的速度，但是多了索引的过程，两者加起来不⼀定⽐顺序扫描快多少。的确，加上索引的过程，全⽂检索不⼀定⽐
顺序扫描快，尤其是在数据量⼩的时候更是如此。⽽对⼀个很⼤量的数据创建索引也是⼀个很慢的过程。
然⽽两者还是有区别的，顺序扫描是每次都要扫描，⽽创建索引的过程仅仅需要⼀次，以后便是⼀劳永逸的了，每次搜索，创建索引的过程不必经过，仅仅搜索创建好的索
引就可以了。
这也是全⽂搜索相对于顺序扫描的优势之⼀：⼀次索引，多次使⽤。
2.如何创建索引
全⽂检索的索引创建过程⼀般有以下⼏步：
第⼀步：⼀些要索引的原⽂档(Document)
为了⽅便说明索引创建过程，这⾥特意⽤两个⽂件为例：
⽂件⼀：Students should be allowed to go out with their friends, but not allowed to drink beer.
⽂件⼆：My friend Jerry went to school to see his students but found them drunk which is not allowed.
第⼆步：将原⽂档传给分词组件(Tokenizer)
分词组件(Tokenizer)会做以下⼏件事情(此过程称为Tokenize)：
1. 将⽂档分成⼀个⼀个单独的单词。
2. 去除标点符号。
3. 去除停词(Stop word)。
所谓停词(Stop word)就是⼀种语⾔中最普通的⼀些单词，由于没有特别的意义，因⽽⼤多数情况下不能成为搜索的关键词，因⽽创建索引时，这种词会被去掉⽽减少索引的
⼤⼩。
英语中挺词(Stop word)如：“the”,“a”，“this”等。
对于每⼀种语⾔的分词组件(Tokenizer)，都有⼀个停词(stop word)集合。
经过分词(Tokenizer)后得到的结果称为词元(Token)。
在我们的例⼦中，便得到以下词元(Token)：
“Students”，“allowed”，“go”，“their”，“friends”，“allowed”，“drink”，“beer”，“My”，“friend”，“Jerry”，“went”，“school”，“see”，“his”，“students”，“found”，“them”，“drunk”，“allowed”。
第三步：将得到的词元(Token)传给语⾔处理组件(Linguistic Processor)
语⾔处理组件(linguistic processor)主要是对得到的词元(Token)做⼀些同语⾔相关的处理。
对于英语，语⾔处理组件(Linguistic Processor)⼀般做以下⼏点：
1. 变为⼩写(Lowercase)。
2. 将单词缩减为词根形式，如“cars”到“car”等。这种操作称为：stemming。
3. 将单词转变为词根形式，如“drove”到“drive”等。这种操作称为：lemmatization。
Stemming 和 lemmatization的异同：
相同之处：Stemming和lemmatization都要使词汇成为词根形式。
两者的⽅式不同：
Stemming采⽤的是“缩减”的⽅式：“cars”到“car”，“driving”到“drive”。
Lemmatization采⽤的是“转变”的⽅式：“drove”到“drove”，“driving”到“drive”。
两者的算法不同：
Stemming主要是采取某种固定的算法来做这种缩减，如去除“s”，去除“ing”加“e”，将“ational”变为“ate”，将“tional”变为“tion”。
Lemmatization主要是采⽤保存某种字典的⽅式做这种转变。⽐如字典中有“driving”到“drive”，“drove”到“drive”，“am, is, are”到“be”的映射，做转变时，只要查字典就可以了。
Stemming和lemmatization不是互斥关系，是有交集的，有的词利⽤这两种⽅式都能达到相同的转换。
语⾔处理组件(linguistic processor)的结果称为词(Term)。
在我们的例⼦中，经过语⾔处理，得到的词(Term)如下：
“student”，“allow”，“go”，“their”，“friend”，“allow”，“drink”，“beer”，“my”，“friend”，“jerry”，“go”，“school”，“see”，“his”，“student”，“find”，“them”，“drink”，“allow”。
也正是因为有语⾔处理的步骤，才能使搜索drove，⽽drive也能被搜索出来。
第四步：将得到的词(Term)传给索引组件(Indexer)
索引组件(Indexer)主要做以下⼏件事情：
1. 利⽤得到的词(Term)创建⼀个字典。
在我们的例⼦中字典如下：
2. 对字典按字母顺序进⾏排序。
3. 合并相同的词(Term)成为⽂档倒排(Posting List)链表。
在此表中，有⼏个定义：
Document Frequency 即⽂档频次，表⽰总共有多少⽂件包含此词(Term)。
Frequency 即词频率，表⽰此⽂件中包含了⼏个此词(Term)。
所以对词(Term) “allow”来讲，总共有两篇⽂档包含此词(Term)，从⽽词(Term)后⾯的⽂档链表总共有两项，第⼀项表⽰包含“allow”的第⼀篇⽂档，即1号⽂档，此⽂档中，“allow”出现了2次，第⼆项表⽰包含“allow”的第⼆个⽂档，是2号⽂档，此⽂档中，“allow”出现了1次。
到此为⽌，索引已经创建好了，我们可以通过它很快的到我们想要的⽂档。
⽽且在此过程中，我们惊喜地发现，搜索“drive”，“driving”，“drove”，“driven”也能够被搜到。因为在我们的索引中，“driving”，“drove”，“driven”都会经过语⾔处理⽽变
成“drive”，在搜索时，如果您输⼊“driving”，输⼊的查询语句同样经过我们这⾥的⼀到三步，从⽽变为查询“drive”，从⽽可以搜索到想要的⽂档。
3.如何索引搜索
到这⾥似乎我们可以宣布“我们到想要的⽂档了”。
然⽽事情并没有结束，到了仅仅是全⽂检索的⼀个⽅⾯。不是吗？如果仅仅只有⼀个或⼗个⽂档包含我们查询的字符串，我们的确到了。然⽽如果结果有⼀千个，甚⾄成千上万个呢？那个⼜是您最想要的⽂件呢？
搜索主要分为以下⼏步：
第⼀步：⽤户输⼊查询语句
查询语句同我们普通的语⾔⼀样，也是有⼀定语法的。不同的查询语句有不同的语法，如SQL语句就有⼀定的语法。查询语句的语法根据全⽂检索系统的实现⽽不同。最基本的有⽐如：AND, OR, NOT等。
举个例⼦，⽤户输⼊语句：lucene AND learned NOT hadoop。说明⽤户想⼀个包含lucene和learned然⽽不包括hadoop的⽂档。
第⼆步：对查询语句进⾏词法分析，语法分析，及语⾔处理
由于查询语句有语法，因⽽也要进⾏词法分析，语法分析及语⾔处理。
1. 词法分析主要⽤来识别单词和关键字。
如上述例⼦中，经过词法分析，得到单词有lucene，learned，hadoop, 关键字有AND, NOT。如果在词法分析中发现不合法的关键字，则会出现错误。如lucene AMD learned，其中由于AND拼错，导致AMD作为⼀个普通的单词参与查询。
2. 语法分析主要是根据查询语句的语法规则来形成⼀棵语法树。
如果发现查询语句不满⾜语法规则，则会报错。如lucene NOT AND learned，则会出错。如上述例⼦，lucene AND learned NOT hadoop形成的语法树如下：
3. 语⾔处理同索引过程中的语⾔处理⼏乎相同
如learned变成learn等。经过第⼆步，我们得到⼀棵经过语⾔处理的语法树：
第三步：搜索索引，得到符合语法树的⽂档
此步骤有分⼏⼩步：
1. ⾸先，在反向索引表中，分别出包含lucene，learn，hadoop的⽂档链表。
2. 其次，对包含lucene，learn的链表进⾏合并操作，得到既包含lucene⼜包含learn的⽂档链表。
3. 然后，将此链表与hadoop的⽂档链表进⾏差操作，去除包含hadoop的⽂档，从⽽得到既包含lucene⼜包含learn⽽且不包含hadoop的⽂档链表。
4. 此⽂档链表就是我们要的⽂档。
第四步：根据得到的⽂档和查询语句的相关性，对结果进⾏排序
虽然在上⼀步，我们得到了想要的⽂档，然⽽对于查询结果应该按照与查询语句的相关性进⾏排序，越相关者越靠前。
如何计算⽂档和查询语句的相关性呢？文档字符串是什么
不如我们把查询语句看作⼀⽚短⼩的⽂档，对⽂档与⽂档之间的相关性(relevance)进⾏打分(scoring)，分数⾼的相关性好，就应该排在前⾯。
⾸先，⼀个⽂档有很多词(Term)组成，如search, lucene, full-text, this, a, what等。
其次对于⽂档之间的关系，不同的Term重要性不同，⽐如对于本篇⽂档，search, Lucene, full-text就相对重要⼀些，this, a , what可能相对不重要⼀些。所以如果两篇⽂档都包含search, Lucene，fulltext，这两篇⽂档的相关性好⼀些，然⽽就算⼀篇⽂档包含this, a, what，另⼀篇⽂档不包含this, a, what，也不能影响两篇⽂档的相关性。
因⽽判断⽂档之间的关系，⾸先出哪些词(Term)对⽂档之间的关系最重要，如search, Lucene, fulltext。然后判断这些词(Term)之间的关系。
出词(Term)对⽂档的重要性的过程称为计算词的权重(Term weight)的过程。
计算词的权重(term weight)有两个参数，第⼀个是词(Term)，第⼆个是⽂档(Document)。
词的权重(Term weight)表⽰此词(Term)在此⽂档中的重要程度，越重要的词(Term)有越⼤的权重(Term weight)，因⽽在计算⽂档之间的相关性中将发挥更⼤的作⽤。
最后对上述索引创建和搜索过程所⼀个总结，如图：
1. 索引过程：
1) 有⼀系列被索引⽂件
2) 被索引⽂件经过语法分析和语⾔处理形成⼀系列词(Term)。
3) 经过索引创建形成词典和反向索引表。
4) 通过索引存储将索引写⼊硬盘。
2. 搜索过程：
a) ⽤户输⼊查询语句。
b) 对查询语句经过语法分析和语⾔分析得到⼀系列词(Term)。
c) 通过语法分析得到⼀个查询树。
d) 通过索引存储将索引读⼊到内存。
e) 利⽤查询树搜索索引，从⽽得到每个词(Term)的⽂档链表，对⽂档链表进⾏交，差，并得到结果⽂档。
f) 将搜索到的结果⽂档对查询的相关性进⾏排序。
g) 返回查询结果给⽤户。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。