全文检索原理

全文检索是指计算机索引程序通过扫描文章中的每一个词,对每一个词建立一个索引,指明该词在文章中出现的次数和位置,当用户查询时,检索程序就根据事先建立的索引进行查找,并将查找的结果反馈给用户的检索方式。这个过程类似于通过字典中的检索字表查字的过程。

一、索引项term

1、索引项
英文:空格分隔的单词

中文:字,迭代二元项,中文分词

2、索引项处理
提取词干:对于英文,一般是取词干,对于中文,一般是取同义词,目的是减少索引项的数目,提高检索速度,提高查全率

中文分词:尤其对于歧义词需要处理,对于提高准确率有益

词性标注:对于某些词不做索引,比如叹词、连词、助词、标点等

停止词表:英文:the, a, and, 中文:的,了,和,

二、全文检索评价标准
精确度: Precision = 正确返回结果/所有返回结果

查全率: Recall = 正确返回结果/所有正确结果

(Precision高,Recall不一定高;反之依然)

索引膨胀率

查询速度

索引建立速度

三、全文检索基本模型

1、倒排索引
建立索引的步骤

识别文档中的词

删除停用词

提取词干

用索引项的编号代替词干

统计词干的数量

计算权重

索引结构

hash ,b±tree

检索过程
分析给定query

对分析后的query进行词干提取,算法与对文档的处理 相同

用索引项编号代替词干

对找到的索引项内的文档纪录进行逻辑处理和排序

返回排序后的文档集合

倒排索引的优点
快速索引(长query需要更多时间,线形增加)

灵活性: 不同类型的信息都可以存储在postings list中

如果存储了足够多的信息,则可以支持复杂的检索操作

例如:如果记录了词在文档中的准确位置,就可以支持短语检索,或模糊检索

倒排索引的缺点

很大的存储开销 50% -150% -300%

更新、插入和删除都需要很高的维护开销,倒排索引相对静态的环境(很少插入和更新)中使用比较好

处理开销随着布尔操作的增加而增长

2、签名文件
优点

Signature文件小而可控

由于文件组织简单,因此维护费用小(更新和删除)

Signatures容易生成,插入费用低

重叠编码适合多属性检索

Signature文件在倒排文件和全文扫描之间做了空间和时间的平衡

适合中等大小的数据库和查询频率较低的系统

容易进行并行处理

缺点
和倒排文件相比,搜索速度慢

去除False drops需要昂贵的开销 因为所有被匹配的signature必须通过模式匹配来确认

在signature中,很难对频率和权值信息进行编码

其它query函数,例如分离条件、同义词、通配符, 邻近(proximity)操作都很难使用

3、Pat数组
Pat数组模型将文本看成一组字符串的有序叠合,用户输入的检索字符串就不会被分解成单个字符的集合,而是直接检索字符串.

四、lucene介绍
Lucene是apache软件基金会[4] jakarta项目组的一个子项目,是一个开放源代码[5]的全文检索引擎工具包,即它不是一个完整的全文检索引擎,而是一个全文检索引擎的架构,提供了完整的查询引擎和索引引擎,部分文本分析引擎(英文与德文两种西方语言)。

Lucene的目的是为软件开发人员提供一个简单易用的工具包,以方便的在目标系统中实现全文检索的功能,或者是以此为基础建立起完整的全文检索引擎。

Lucene作为一个全文检索引擎,其具有如下突出的优点:
(1)索引文件格式独立于应用平台。Lucene定义了一套以8位字节为基础的索引文件格式,使得兼容系统或者不同平台的应用能够共享建立的索引文件。

(2)在传统全文检索引擎的倒排索引的基础上,实现了分块索引,能够针对新的文件建立小文件索引,提升索引速度。然后通过与原有索引的合并,达到优化的目的。

(3)优秀的面向对象的系统架构,使得对于Lucene扩展的学习难度降低,方便扩充新功能。

(4)设计了独立于语言和文件格式的文本分析接口,索引器通过接受Token流完成索引文件的创立,用户扩展新的语言和文件格式,只需要实现文本分析的接口。

(5)已经默认实现了一套强大的查询引擎,用户无需自己编写代码即使系统可获得强大的查询能力,Lucene的查询实现中默认实现了布尔操作、模糊查询(Fuzzy Search[11])、分组查询等等。

lucene的组成结构:对于外部应用来说索引模块(index)和检索模块(search)是主要的外部应用入口
org.apache.Lucene.search/ 搜索入口

org.apache.Lucene.index/ 索引入口

org.apache.Lucene.analysis/ 语言分析器

org.apache.Lucene.queryParser/ 查询分析器

org.apache.Lucene.document/ 存储结构

org.apache.Lucene.store/ 底层IO/存储结构

org.apache.Lucene.util/ 一些公用的数据结构