全文检索原理及实现方式
全⽂检索原理及实现⽅式
⼀、总论
根据 定义：
"Apache Lucene(TM) is a high-performance, full-featured text search engine library written entirely in Java. It is a technology suitable for nearly any application that requires full-text search, especially cross-platform."
Lucene 是⼀个⾼效的，基于Java 的全⽂检索库。
所以在了解Lucene之前要费⼀番⼯夫了解⼀下全⽂检索。
那么什么叫做全⽂检索呢？这要从我们⽣活中的数据说起。
我们⽣活中的数据总体分为两种：结构化数据 和⾮结构化数据 。
结构化数据： 指具有固定格式或有限长度的数据，如数据库，元数据等。
⾮结构化数据： 指不定长或⽆固定格式的数据，如邮件，word⽂档等。
当然有的地⽅还会提到第三种，半结构化数据，如XML，HTML等，当根据需要可按结构化数据来处理，也可抽取出纯⽂本按⾮结构化数据来处理。
⾮结构化数据⼜⼀种叫法叫全⽂数据。
按照数据的分类，搜索也分为两种：
对结构化数据的搜索 ：如对数据库的搜索，⽤SQL语句。再如对元数据的搜索，如利⽤windows搜索对⽂件名，类型，修改时间进⾏搜索等。
对⾮结构化数据的搜索 ：如利⽤windows的搜索也可以搜索⽂件内容，Linux下的grep命令，再如⽤Google和百度可以搜索⼤量内容数据。
对⾮结构化数据也即对全⽂数据的搜索主要有两种⽅法：
⼀种是顺序扫描法 (Serial Scanning)： 所谓顺序扫描，⽐如要内容包含某⼀个字符串的⽂件，就是⼀个⽂档⼀个⽂档的看，对于每⼀个⽂档，从头看到尾，如果此⽂档包含此字符串，则此⽂档为我们要的⽂件，接着看下⼀个⽂件，直到扫描完所有的⽂件。如利⽤windows 的搜索也可以搜索⽂件内容，只是相当的慢。如果你有⼀个80G硬盘，如果想在上⾯到⼀个内容包含某字符串的⽂件，不花他⼏个⼩时，怕是做不到。Linux下的grep命令也是这⼀种⽅式。⼤家可能觉得这种⽅法⽐较原始，但
对于⼩数据量的⽂件，这种⽅法还是最直接，最⽅便的。但是对于⼤量的⽂件，这种⽅法就很慢了。
有⼈可能会说，对⾮结构化数据顺序扫描很慢，对结构化数据的搜索却相对较快（由于结构化数据有⼀定的结构可以采取⼀定的搜索算法加快速度），那么把我们的⾮结构化数据想办法弄得有⼀定结构不就⾏了吗？
这种想法很天然，却构成了全⽂检索的基本思路，也即将⾮结构化数据中的⼀部分信息提取出来，重新组织，使其变得有⼀定结构，然后对此有⼀定结构的数据进⾏搜索，从⽽达到搜索相对较快的⽬的。
这部分从⾮结构化数据中提取出的然后重新组织的信息，我们称之索引 。
这种说法⽐较抽象，举⼏个例⼦就很容易明⽩，⽐如字典，字典的拼⾳表和部⾸检字表就相当于字典的索引，对每⼀个字的解释是⾮结构化的，如果字典没有⾳节表和部⾸检字表，在茫茫辞海中⼀个字只能顺序扫描。然⽽字的某些信息可以提取出来进⾏结构化处理，⽐如读⾳，就⽐较结构化，分声母和韵母，分别只有⼏种可以⼀⼀列举，于是将读⾳拿出来按⼀定的顺序排列，每⼀项读⾳都指向此字的详细解释的页数。我们搜索时按结构化的拼⾳搜到读⾳，然后按其指向的页数，便可到我们的⾮结构化数据——也即对字的解释。
这种先建⽴索引，再对索引进⾏搜索的过程就叫全⽂检索(Full-text Search) 。
下⾯这幅图来⾃《Lucene in action》，但却不仅仅描述了Lucene的检索过程，⽽是描述了全⽂检索的⼀般过程。
[图]全⽂检索的⼀般过程
全⽂检索⼤体分两个过程，索引创建 (Indexing) 和搜索索引 (Search) 。
索引创建：将现实世界中所有的结构化和⾮结构化数据提取信息，创建索引的过程。
搜索索引：就是得到⽤户的查询请求，搜索创建的索引，然后返回结果的过程。
于是全⽂检索就存在三个重要问题：
1. 索引⾥⾯究竟存些什么？(Index)
2. 如何创建索引？(Indexing)
3. 如何对索引进⾏搜索？(Search)
下⾯我们顺序对每个个问题进⾏研究。
⼆、索引⾥⾯究竟存些什么
索引⾥⾯究竟需要存些什么呢？
⾸先我们来看为什么顺序扫描的速度慢：
其实是由于我们想要搜索的信息和⾮结构化数据中所存储的信息不⼀致造成的。
⾮结构化数据中所存储的信息是每个⽂件包含哪些字符串，也即已知⽂件，欲求字符串相对容易，也即是从⽂件到字符串的映射。⽽我们想搜索的信息是哪些⽂件包含此字符串，也即已知字符串，欲求⽂件，也即从字符串到⽂件的映射。两者恰恰相反。于是如果索引总能够保存从字符串到⽂件的映射，则会⼤⼤提⾼搜索速度。
由于从字符串到⽂件的映射是⽂件到字符串映射的反向过程，于是保存这种信息的索引称为反向索引 。
反向索引的所保存的信息⼀般如下：
假设我的⽂档集合⾥⾯有100篇⽂档，为了⽅便表⽰，我们为⽂档编号从1到100，得到下⾯的结构
[图]字典及倒排表结构
左边保存的是⼀系列字符串，称为词典 。
每个字符串都指向包含此字符串的⽂档(Document)链表，此⽂档链表称为倒排表 (Posting List)。
有了索引，便使保存的信息和要搜索的信息⼀致，可以⼤⼤加快搜索的速度。
⽐如说，我们要寻既包含字符串“lucene”⼜包含字符串“solr”的⽂档，我们只需要以下⼏步：
1. 取出包含字符串“lucene”的⽂档链表。
2. 取出包含字符串“solr”的⽂档链表。
3. 通过合并链表，出既包含“lucene”⼜包含“solr”的⽂件。
[图]倒排表合并过程
看到这个地⽅，有⼈可能会说，全⽂检索的确加快了搜索的速度，但是多了索引的过程，两者加起来不⼀定⽐顺序扫描快多少。的确，加上索引的过程，全⽂检索不⼀定⽐顺序扫描快，尤其是在数据量⼩的时候更是如此。⽽对⼀个很⼤量的数据创建索引也是⼀个很慢的过程。然⽽两者还是有区别的，顺序扫描是每次都要扫描，⽽创建索引的过程仅仅需要⼀次，以后便是⼀劳永逸的了，每次搜索，创建索引的过程不必经过，仅仅搜索创建好的索引就可以了。
这也是全⽂搜索相对于顺序扫描的优势之⼀：⼀次索引，多次使⽤。
三、如何创建索引
全⽂检索的索引创建过程⼀般有以下⼏步：
第⼀步：⼀些要索引的原⽂档(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”，“Jerr y”，“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”，“g o”，“school”，“see”，“his”，“student”，“find”，“them”，“drink”，“allow”。
也正是因为有语⾔处理的步骤，才能使搜索drove，⽽drive也能被搜索出来。
第四步：将得到的词(Term)传给索引组件(Indexer)。
索引组件(Indexer)主要做以下⼏件事情：
存的部首1. 利⽤得到的词(Term)创建⼀个字典。
在我们的例⼦中字典如下：
Term Document ID
student1
allow1
go1
their1
friend1
allow1
drink1
beer1
my2
friend2
jerry2
go2
school2
see2
his2
student2
find2
them2
drink2
allow2
2. 对字典按字母顺序进⾏排序。
Term Document ID
allow1
allow1
allow2
beer1
drink1
drink2
find2
friend1
friend2
go1
go2
his2
jerry2
my2
school2
see2
student1
student2
their1
them2
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”，从⽽可以搜索到想要的⽂档。
三、如何对索引进⾏搜索？
到这⾥似乎我们可以宣布“我们到想要的⽂档了”。
然⽽事情并没有结束，到了仅仅是全⽂检索的⼀个⽅⾯。不是吗？如果仅仅只有⼀个或⼗个⽂档包含我们查询的字符串，我们的确到了。然⽽如果结果有⼀千个，甚⾄成千上万个呢？那个⼜是您最想要的⽂件呢？
打开Google吧，⽐如说您想在微软份⼯作，于是您输⼊“Microsoft job”，您却发现总共有22600000个结果返回。好⼤的数字呀，突然发现不到是⼀个问题，到的太多也是⼀个问题。在如此多的结果中，如何将最相关的放在最前⾯呢？
[图]Google的搜索实例
当然Google做的很不错，您⼀下就到了jobs at Microsoft。想象⼀下，如果前⼏个全部是“Microsoft does a good job at software industry…”将是多么可怕的事情呀。
如何像Google⼀样，在成千上万的搜索结果中，到和查询语句最相关的呢？
如何判断搜索出的⽂档和查询语句的相关性呢？
这要回到我们第三个问题：如何对索引进⾏搜索？
搜索主要分为以下⼏步：
第⼀步：⽤户输⼊查询语句。
查询语句同我们普通的语⾔⼀样，也是有⼀定语法的。
不同的查询语句有不同的语法，如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等。
经过第⼆步，我们得到⼀棵经过语⾔处理的语法树。
[图]经过语⾔处理的语法树
第三步：搜索索引，得到符合语法树的⽂档。
此步骤有分⼏⼩步：
⾸先，在反向索引表中，分别出包含lucene，learn，hadoop的⽂档链表。
其次，对包含lucene，learn的链表进⾏合并操作，得到既包含lucene⼜包含learn的⽂档链表。
然后，将此链表与hadoop的⽂档链表进⾏差操作，去除包含hadoop的⽂档，从⽽得到既包含lucene⼜包含learn⽽且不包含hadoop的⽂档链表。
此⽂档链表就是我们要的⽂档。
第四步：根据得到的⽂档和查询语句的相关性，对结果进⾏排序。
虽然在上⼀步，我们得到了想要的⽂档，然⽽对于查询结果应该按照与查询语句的相关性进⾏排序，越相关者越靠前。
如何计算⽂档和查询语句的相关性呢？
不如我们把查询语句看作⼀⽚短⼩的⽂档，对⽂档与⽂档之间的相关性(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)，因⽽在计算⽂档之间的相关性中将发挥更⼤的作⽤。
判断词(Term) 之间的关系从⽽得到⽂档相关性的过程应⽤⼀种叫做向量空间模型的算法(Vector Space Model) 。
下⾯仔细分析⼀下这两个过程：
1. 计算权重(Term weight)的过程。
影响⼀个词(Term)在⼀篇⽂档中的重要性主要有两个因素：
Term Frequency (tf)：即此Term在此⽂档中出现了多少次。tf 越⼤说明越重要。
Document Frequency (df)：即有多少⽂档包含次Term。df 越⼤说明越不重要。

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