全文检索的基本概念和原理

全文检索的基本概念和原理

 

最近拜读了觉先前辈的博客《Lucene3.0原理与代码分析》，深有感触，于是做下笔记，以加深自己的理解。

 

我们在生活中所接触到的数据可以分为两类：结构化数据和非结构化数据。

1.结构化数据：具有固定格式或有限长度，如数据库、元数据、行数据、存储于数据库中可以用二维表结构逻辑来表达实现的数据等。

2.非结构化数据：没有固定格式或不定长的数据，包括办公文档、文本、图片、邮件、图像和音频/视频等。

3.有些地方还会提到第三种：半结构化数据，介于完全结构化数据(如关系型数据库、面向对象数据库中数据)和完全无结构的数据(如声音、图像文件等)之间的数据，如XML、HTML等，可根据需要可按结构化数据来处理，也可抽取出纯文本按非结构化数据来处理。

 

结构化数据属于非结构化数据，是非结构化数据的特例。从数据模型而言：

1.结构化数据：二维表(关系型) 、先有结构、后有数据

2.半结构化数据：树、图、先有数据，后有结构

3.非结构化数据：无

 

非结构化数据又一种叫法叫全文数据。

 

按照数据的分类，搜索也分为两种：

1.对结构化数据的搜索：如对数据库的搜索，用SQL语句。再对元数据的搜索，如利用windows搜索文件名、文件类型、修改日期等。

2.对非结构化数据的搜索：如利用windows的搜索也可以搜索文件内容，Linux下的grep命令，再如用Google和百度可以搜索大量内容数据。

 

对非结构化数据也即对全文数据的搜索主要有两种方法：

1.顺序扫描法：比如要从一堆文档中，找出包含某个词组的所有文档，就是一个文档一个文档挨着看，并且对每一个文档是从头看到尾的，如果此文档包含该词组，则加入搜索的结果集中，接着看下一个文档，直到扫描完所有的文档为止。如利用windows的搜索功能搜索文件内容，其速度是相当的慢。如果你的硬盘容量是320G，而且里面满满的全是文本文件。Oh，my God！你要找包含某个词组的文件很有可能几个小时还找不完。Linux环境下的grep命令也是基于这样的搜索原理实现的。对于小数据量的环境，这种方法是非常直接、简单、易于实现的，而且效果也不是太差。但如果在海量数据环境下，这种方法是绝对不可取的。

对非结构化数据顺序扫描很慢，但对结构化数据的搜索相对较快。原因在于：结构化数据都是有一定结构的，我们可以采取一些技巧：比如一些搜索优化算法来加快搜索的速度。所以，到此，我们认识到问题的关键在于：我们应该想办法把非结构化的数据处理成结构化数据。

这种想法是自然而然的事情，却是构成了全文检索最基本的思路，即将非结构化数据中的一部分信息提取出来，重新组织，使其变得有一定的结构，然后设计出相应的高效的数据搜索算法和机制，从而达到搜索相对较快的目的。

而这部分从非结构化数据中提取出来的，然后重新组织，变得有结构的信息，在全文检索领域，我们称之为索引。

举个例子说明一下：我们都用过字典。如果没有拼音和部首检索表，要你在那么大一坨字典里找一个词组，那真不是一件容易的事。但如果按照拼音或部首进行查询，我们可以很快地定位并找到这个词组。拼音和部首的检索表对于字典而言就是所谓的索引。

这种先建立索引，再对索引进行搜索的过程就叫全文检索(Full-text Search)。

《Lucene in Action》中描述的全文检索的一般过程，非常精炼和简洁。

从上图中，可以看出，全文检索大体可分为两个过程：索引创建（Indexing）和索引搜索（Search）

1.索引创建：将现实世界中所有的结构化和非结构化数据提取信息，重新组织，使其结构化，创建索引的过程。

2.索引搜索：接收用户查询请求，搜索创建的索引，然后返回搜索的结果集的过程。

 

于是全文检索就存在三个非常重要的问题：

1.索引里面究竟存些什么？（Index）

2.如何创建索引？（Indexing）

3.如何对索引进行搜索？（Search）

 

一、索引里面究竟存的是什么？

首先，我们来分析一下为什么顺序扫描的速度会慢。

其实是我们想要搜索的信息和非结构化数据中所存储的信息不一致造成的。非结构化数据中所存储的信息是每个文件包含哪些字符串，即从文件到字符串的映射。而我们想搜索的信息是哪些文件包含此字符串，即已知字符串，求相应的文件，即从字符串到文件的映射。两者恰恰是相反的，因此顺序扫描的速度会很慢。这样一来，如果索引中存储的是从字符串到文件的映射，则会大大提高搜索速度。

由于从字符串到文件的映射是文件到字符串映射的反向过程，于是保存这种信息的索引称之为反向索引。反向索引所保存的信息一般如下所示，假设文档集合里面有100篇文档，为了方便表示，我们为文档编号从1~100，得到下面的结构：

左边保存的一系列字符串，称之为字典。每个字符串都指向包含此字符串的文档（Document）链表，此文档链表称之为倒排表（Posting List）。有了索引，便使得保存的信息和要搜索的信息是一致的，大大加快了搜索的速度。

比如说，我们要搜索包含字符串“lucene”又包含字符串“solr”的文档，我们只需要以下几步：

1.取出包含字符串“lucene”的文档链表。

2.取出包含字符串“solr”的文档链表。

3.通过合并链表，找出既包含“lucene”又包含“solr”的文件。

看到这个地方，肯定会有人说：全文检索的确是加快了搜索的速度，但是却多了索引的过程，两者加起来不一定比顺序扫描快上多少。的确，加上索引过程，全文检索不一定比顺序扫描快，尤其是在数据量较小的情况下，而对于海量数据创建索引也是一个非常漫长的过程。然而两者还是有区别的，顺序扫描是每次都要扫描，而创建索引的过程仅仅需要一次即可，以后就一劳永逸了，每次搜索，创建索引过程都不必经过，直接去搜索创建好的索引即可。这就是全文搜索相对于顺序扫描的优势之一：一次索引，多次使用。

 

二、如何创建索引？

全文检索的索引创建过程一般会经过以下几个步骤：

（1）原始的文档数据集合（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.

 

（2）将原始文档进行分词

分词（Tokenize）的过程会做以下几件事情：

1.将文档分隔成一个一个单独的单词。

2.去除标点符号。

3.去除停词（Stop word）。

所谓停词（Stop word）就是一种语言中最普通的一些单词，由于没有特别的意义，因而大多数情况下不能成为搜索的关键词，因而创建索引时，这种词会被去除，而减少索引的大小。比如，英语中的停词“the”，“a”，“this”等。

对于每一种语言的分词组件（Tokenizer）都有一个停词集合。经过分词（Tokenize）后得到的结果称之为词元（Token）。在我们的例子中，所得到的词元为：

“Students”，“allowed”，“go”，“their”，“friends”，“allowed”，“drink”，“beer”，“My”，“friend”，“Jerry”，“went”，“school”，“see”，“his”，“students”，“found”，“them”，“drunk”，“allowed”。

 

（3）将得到的词元（Token）传给语言处理组件（Linguistic Processor）。

语言处理组件（linguistic processor）主要是对得到的词元（Token）做一些同语言相关的处理。对于英语，语言处理组件一般做以下几点：

1.将词元处理为小写（Lowercase）。

2.将词元处理为词根形式，如“cars”到“car”，这种操作称之为：stemming。

3.将词元处理为词根形式，如“drove”到“drive”，这种操作称之为：lemmatization。

stemming和lemmatization的异同：

1.相同之处：stemming和lemmatization都要使词汇成为词根形式。

2.两者的方式不同：

stemming采用的是“缩减”的方式，“cars”到“car”。

 lemmatization采用的是“转变”的方式，“drove”到“drive”。

3.两者算法的不同：

stemming主要是采取某种固定的算法来作这种缩减，如去除“s”，去除“ing”加“e”，将“action”变为“ate”，将“tional”变为“tion”。

lemmatization主要是采用保存某种字典的方式做这种转变。比如字典中有“diving”到“drive”，“drove”到“drive”，“am，is，are”到“be”的映射，做转变时，只要查字典就可以了。

stemming和lemmatization不是互斥关系，是有交集的，有的词元利用这两种方式都能达到相同的转换。

语言处理组件处理的结果称之为词（Term）。

在我们的例子中，经过语言处理，得到的词（Term）如下：

“student”，“allow”，“go”，“their”，“friend”，“allow”，“drink”，“beer”，“my”，“friend”，“jerry”，“go”，“school”，“see”，“his”，“student”，“find”，“them”，“drink”，“allow”。

也正是因为有语言处理的步骤，才能保证搜索drove，而drive也能被搜索出来。

 

（4）将得到的词（Term）传给索引组件（Indexer）

索引组件（Indexer）主要完成以下事情：

 

1.利用得到的词（Term）创建一个字典。

在我们的例子中，字典如下：

Term	Document ID
student	1
allow	1
go	1
their	1
friend	1
allow	1
drink	1
beer	1
my	2
friend	2
jerry	2
go	2
school	2
see	2
his	2
student	2
find	2
them	2
drink	2
allow	2

 

2.对字典按字母顺序进行排序。

Term	Document ID
allow	1
allow	1
allow	2
beer	1
drink	1
drink	2
find	2
friend	1
friend	2
go	1
go	2
his	2
jerry	2
my	2
school	2
see	2
student	1
student	2
their	1
them	2

 

3.合并相同的词（Term）成为文档倒排（Posting List）链表。

Document Frequency：文档频次，表示总共有多少文件包含此词（Term）。

Frequency：词频率，表示此文件中包含了几个此词（Term）。

所以对词（Term）“allow”来讲，总共有两篇文档包含此词，从而词后面的文档链表总共有两项，第一项表示包含“allow”的第一篇文档，即1号文档，此文档中，“allow”出现了2次，第二项表示包含“allow”的第二个文档，是2号文档，此文档中，“allow”出现了1次。

到此为此，索引已经创建完成了，我们可以通过它很快地找到我们想要的文档。

而在此过程中，我们惊喜地发现，搜索“dirve”，“driving”，“drove”，“driven”也能够被搜索到。因为在我们的索引中“dirve”，“driving”，“drove”，“driven”都将被处理为“dirve”，在搜索时，用户所输入的“driving”查询语句同样也会经过这里的1~3步，从而变为查询“drive”，从而可以搜索到想要的文档。

 

三、如何对索引进行搜索？

有了索引，剩下的问题就是如何对索引进行搜索了。到这里我们似乎可以宣布大功告成了。但事实果真如此吗？如果我们输入一下检索词，返回的只有1个或10多个文档，那么我们确实不需要再做些什么了。但如果找到的文档数量是1000个，甚至是以万、百万为数量级时，那究竟哪一个文档是你所需要的呢？

打开Google，比如你要在微软打份工作，于是你输入“Microsoft job”，你发现总共有22600000个结果返回。好大的数字啊，我的老天！突然发现找不到是一个问题，找到的东东太多同样也是一个问题啊。在如此众多的结果中，如何选择把最相关的结果放到最前面呢？

像Google做的是相当不错的，一下就找到了jobs at Microsoft。想像一下，如果前几个全部是“Microsoft does a good job at software industry…”那将是多么可怕的一件事情啊。

如何像Google一样，在成千上万的搜索结果集中，找到和查询语句最相关的呢？如何判断搜索出的文档和查询语句的相关性？下面我们就来探究探究其中的奥妙。

 

搜索过程主要分为以下几个步骤：

（1）用户输入查询语句

查询语句同我们普通语言一样，也是有一定语法的。不同的查询语句有不同的语法，如SQL语句就有一定的语法。查询语句的语法根据全文检索系统的实现而不同。最基本的有比如：AND、OR、NOT等。

举个例子，用户输入语句：lucene AND learned NOT hadoop。

说明用户想找一个包含lucene和learned，但却不包含hadoop的文档。

 

（2）对查询语句进行词法分析、语法分析及语言处理

由于查询语句有语法，因此要进行词法分析，语法分析及语言处理。

 

1.词法分析主要用来识别单词和关键字

如上述例子中，经过词法分析，得到单词有lucene，learned，hadoop，关键字有AND，NOT。如果在词法分析中发现不合法的关键字，则会出现错误。如果lucene AND learned，其中由于AND拼错，导致AND作为一个普通的单词参与查询。

 

2.语法分析主要是根据查询语句的语法规则来形成一棵语法树

如果发现查询语句不满足语法规则，则会报错。如lucene NOT AND learned，则会出错。如上述例子，lucene AND learned NOT hadoop形成的语法树如下：

3.语言处理同索引过程中的语言处理几乎相同

如learned 变成learn等。经过第二步，我们得到一棵经过语言处理的语法树。

（3）搜索索引，得到符合语法树的文档

此步骤分几个小步骤：

1.在反向索引表中，分别找出包含lucene，learn，hadoop的文档链表。

2.对包含lucene，learn的链表进行合并操作，得到既包含lucene又包含learn文档链表。

3.将此链表与hadoop的文档链表进行差操作，去除包含hadoop的文档，从而得到既包含lucene又包含learn而且不包含hadoop的文档链表。

4.此文档链表就是我们要找的文档。

 

（4）根据得到的文档和查询语句的，对结果进行排序

虽然我们已经得到了文档链表的结果集合，然而对于查询结果应该按照与查询语句的相关性进行排序，越相关者越靠前。那么，如何计算文档和查询语句的相关性呢？

不如我们把查询语句看作一片短小的文档，对文档与文档之间的（relevance）进行打分（scoring），分数高的相关性好，就应该排在前面。那么，又怎么对文档之间的关系进行打分呢？

这可不是一件容易的事情，首先我们来看一看判断人之间的关系吧。

首先，看一个人，往往有着很多因素，如性格、信仰、爱好、衣着、高矮、胖瘦等待。其次，对于人与人之间的关系，不同的要素重要性不同，性格、信仰、爱好可能重要些，衣着、高矮、胖瘦就不那么重要了，所以具有相同或相似性格、信仰、爱好的人更容易成为好朋友，然而衣着、高矮、胖瘦不同的人，同样可以成为好朋友。

因而，要判断人与人之间的关系，首先要找出哪些因素的影响因子比较重要，比如性格、信仰、爱好。其实要判断两个人的这些因素之间的关系，比如一个人性格开朗，另一个人性格外向，一个人信仰佛教，另一个人信仰上帝，一个人爱好篮球，另一个人爱好足球。我们可以发现，两个人在性格方面都很积极，信仰方面都很善良，爱好方面都爱运动，因而两个人关系应该会很好。

我们再来看一下公司之间的关系。对于一个公司而言，有很多人组成，如总经理，经理，首席技术官，普通员工，保安，门卫等。其次，对于公司与公司之间的关系，不同的人重要性不同，总经理，经理，首席技术官可能更重要一些，而保安，门卫就相对不那么重要。所以如果两个公司总经理，经理，首席技术官之间的关系比较好，那么这两个公司的关系也是比较好的。即便是一位普通员工与另一家公司的普通员工有血海深仇，怕也不会影响两个公司之间的关系。

因而在判断公司与公司关系的时候，首先要找出哪些人对公司与公司之间关系影响因子比较大，比如总经理，经理，首席技术官。其次要判断这些人之间的关系，比如两家公司的总经理曾经是同学，经理是老乡，首席技术官曾是创业的伙伴。我们发现，两家公司无论总经理，经理，首席技术官关系都很好，因而两家公司关系应该会很好。

在分析了上述两种关系之后，我们来看一下如何判断文档之间的关系。

首先，一个文档有很多词（Term）组成，如search，lucene，full-text，this，a，what等。

其次，对于文档之间的关系，不同的Term重要性不同，比如对于本篇文档，search，lucene，full-text就相对重要一些，this，a，what可能相对不重要一些。所以如果两篇文档都包含search，lucene，full-text，这两篇文档的相关性好一些，然而就算一篇文档包含this，a，what，另一篇文档不包含this，a，what，也不能影响两篇文档的相关性。

因而，判断文档之间的关系，首先找出哪些词（Term）对文档之间的关系最为重要，如search，lucene，full-text。然后判断这些词（Term）之间的关系。

找出词（Term）对文档的重要性的过程称之为计算词的权重（Term Weight）的过程。

计算词的权重有两个参数，第一个是词，第二个是文档。词的权重表示此词在此文档中的重要程度，越重要的词有越大的权重，因而在计算文档之间的中将发挥更大的作用。

判断词之间的关系从而得到文档相关性的过程应用一种叫做向量空间模型的算法（Vector Space Model）。

下面来分析一下这两个过程：

 

（1）计算权重（Term Weight）的过程

影响一个词在一篇文档中的重要性主要有两个因素：

1.Term Frequency（tf）：即此Term在此文档中出现了多少次。tf越大说明越重要。

2.Document Frequency（df）：即有多少文档包含此Term。df越大说明越不重要。

其实，这两条规则可以这样理解：正如我们程序员所学的技术一样，这项技术掌握越深越好（掌握越深说明花的时间越多，tf越大），找工作时越有竞争力。然而对于所有程序员来说，这项技术懂的人越少越好（懂的人少，则df小），找工作越有竞争力。人的价值在于其不可替代性就是这个道理。

词在文档中出现的次数越多，说明此词对该文档越重要，如“搜索”这个词，在本文档中出现的次数很多，说明本文档主要在讲关于“搜索”方面的内容。然而一篇英文文档中，this出现的次数更多，就说明越重要吗？不是的，这是由第二个因素进行调整。第二个因素说明，有越多的文档包含此词，则说明此词太普通，不足以区分这些文档，因而重要性越低。

明白了这个道理之后，我们来看看公式：

这仅仅只是term weight计算公式的简单典型实现。实现全文检索系统的人会有自己的实现，Lucene就与此稍有不同。

 

（2）判断Term之间的关系从而得到文档相关性的过程，也即向量空间模型的算法（VSM）

我们把文档看作一系列Term，每一个Term都有一个权重，不同的Term根据自己在文档中的权重来影响文档相关性的打分计算。于是我们把所有此文档中的Term的权重看作一个向量。

Document = {term1, term2, …… ,term N}

Document Vector = {weight1, weight2, …… ,weight N}

同样的，我们可以把查询语句看作一个简单的文档，也用向量表示。

Query = {term1, term 2, …… , term N}

Query Vector = {weight1, weight2, …… , weight N}

我们把所有搜索出的文档查询向量放到一个N维空间中，每个Term都是一维的。

 

在此，我们成功地把文档相关性的计算问题，转化为了求两个向量之间夹角的问题，夹角越小，相关性越大。

有人会问，查询语句一般很短，包含的Term很少，因而查询向量维数很小，而文档很长，包含Term很多，文档向量维数很大。你的图中两者维数怎么都是N呢？

在这里，既然要放到相同的向量空间，自然维数是相同的，不同时，取二者的并集，如果不包含某个Term，则将该Term的权重设置为0即可。打分公式如下：

举个例子，查询语句有11个Term，共有三篇文档搜索出来，其各自权重如下表所示：

	t1	t2	t3	t4	t5	t6	t7	t8	t9	t10	t11
D1	0	0	.477	0	.477	.176	0	0	0	.176	0
D2	0	.176	0	.477	0	0	0	0	.954	0	.176
D3	0	.176	0	0	0	.176	0	0	0	.176	.176
Q	0	0	0	0	0	.176	0	0	.477	0	.176

于是计算，三篇文档同查询语句的相关性打分分别为：

 

于是文档二的相关性最高，先返回，其次是文档三，最后是文档一。到此为止，我们可以找到我们最想要的文档了，这仅仅是信息检索技术中的基本理论。然而，当我们看过Lucene之后，我们会发现，Lucene是对这种基本理论的一种基本的实践。所以在以后分析Lucene文章中，会常常看到以上理论在Lucene中的应用。

在进入Lucene之前，对上述索引创建和搜索过程做一个总结，此图参照http://www.lucene.com.cn/about.htm中文章《开放源代码的全文检索引擎Lucene》。

 

（1）索引过程：

1.有一系列被索引文件

2.被索引文件经过词法分析和语言处理形成一系列Term

3.经过索引创建形成词典和反向索引表

4.通过索引存储将索引写入硬盘

 

（2）搜索过程：

1.用户输入查询语句

2.对查询语句经过词法分析和语言处理得到一系列的Term

3.通过语法分析得到一个查询树

4.通过索引存储将索引读入到内存

5.利用查询树搜索索引，从而得到每个Term的文档链表，对文档链表进行交、差，并提到结果文档

6.将搜索结果集进行相关性排序

7.返回查询结果给用户

 

参考博文：先觉《Lucene3.0原理与代码分析》http://www.cnblogs.com/forfuture1978/archive/2010/02/22/1671487.html