创建博客 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

周森

做好手中的每一件事&注重细节

 
 
 

日志

 
 

全文检索原理  

2006-11-20 09:45:01|  分类: 技术 |  标签: |举报 |字号 订阅

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


一、索引项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/ 一些公用的数据结构

 

参考文献:
1.车东,《在应用中加入全文检索功能 — 基于Java的全文索引引擎Lucene简介》,http://www.chedong.com/tech/lucene.html
2、刘挺 《搜索引擎技术》 哈工大信息检索研究室

 

  评论这张
 
阅读(3114)| 评论(3)
|      
推荐 转载

历史上的今天

最近读者

热度

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2014