文本检索的索引技术

《文本检索的索引技术》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、文本检索的索引技术彭波2003-11-1提纲背景和概念文档分析索引创建索引查询相关资料1。背景和概念－索引作用索引?提供从记录的特征快速查询到记录的数据结构(B树、散列表、位图索引等）数据库，文档数据库，SE/IR系统文本检索记录－》文档doc，记录特征－》索引词(indexterms)数据库结构化，查询和事务型更新文档数据库非结构化，查询和事务型更新SE/IR系统非结构化，查询1。背景和概念－索引形式文本检索常见索引方式Brute-force检索grep签名文件signaturefilehas

2、h签名,falsematch倒排文件invertedfile高效，支持多种检索模型倒排索引从indexterm快速查询到doc的索引结构Doc正常表示为indexterm的集合，建立索引是把每个indexterm表示为其出现的doc的集合，这个过程称为inversion，即倒排。1。背景和概念－倒排文档内容Doc1….北京大学计算机系….Doc2….北京大学主页…..Doc3…计算机的发展…。。。索引词索引项(postinglist)北京大学。。。计算机

3、3>。。。。。。。。。原始文档倒排索引倒排2。文档分析－原则索引词的选择范围人工索引－>质量高，但不适用大规模文档数据处理自动索引部分索引－>title,abstract,keywords,etc（例如：北大图书馆的WebCat系统）全文索引－>文档中所有词都参与索引。(SE/IR普遍采用)索引词的选择原则Indexterm≠word理想：表达文档内容的语义单位字、词、短语（词汇词）中文分词2。文档分析－英文文本Tokenize(Lexicalgrammar)问题：“c++”，R&B，U.S.，a.

4、out没有被识别问题：数字长度、词长度词规模Lemertization(曲折词形合并)He,him->he;is,are,was->beStemmer(取词根）Stemmer->stem;SE为了支持精确查询，往往不使用后两种技术[A-Z][A-Z]+returnUPWORD;[a-zA-Z0-9]+returnWORD;[A-Z][A-Z]+((')?[s])?returnACRONYM2;[a-zA-Z0-9]+'[a-zA-Z]+returnCONTRACTION;[A-Z].([A-

5、Z].)+returnACRONYM;2。文档分析－中文文本字符编码问题字符集：GB2312,GBK,BIG5,HZUNICODE简、繁转换（乾杯，乾坤）分词问题词？：语法词、词汇词表达确定的意义（鱼）、非组合性（多媒体）、互译检查（dioxide－二氧化物）2。文档分析－中文文本分词中文分词歧义交集型：“部分居民生活水平”[1]分居、居民、民生、生活、组合型：“老人家”老人、老人家未登录词专有名词（人名、地名、机构名、译名、术语等）、新词对大规模中文信息处理，“词典规模是制约分词精度的主要因素

6、”[2]2。文档分析－中文文本混合索引基本分词词典6万，选词较为严格统计识别的未登录词扩展词典统计方法，精度不高如果加入到基本分词词典中，带来大量组合型歧义问题，不能正确处理。->混合索引混合索引基本词典：“北京”“大学”，无“北京大学”；扩展词典：有“北京大学”文档中的“…北京大学…”，基本分词分为“北京”“大学”，扩展词典基础上在分为“北京大学”，索引按“北京”“大学”，“/2北京大学”这样三个单位建立。3。倒排索引创建基本思想：排序文档分析

7、oc>文本数据排序词典倒排文件term,ptrterm,ptrDoc1,doc2Doc1,doc2先term,再docid3。倒排索引创建－算法优化Term编码（词典组织）每个term用整数编码，减小存储空间英文－前缀编码(liber,liberal,liberalist…)散列表(MPH,无冲突散列）减少磁盘的随机访问次数－（大内存环境）在内存中排序，排序结果分批写入磁盘，最后合并。两趟算法，在内存中直接倒排，小倒排文件分批写入磁盘，最后多路合并。数

8、据压缩3。倒排索引创建－两趟算法词典词典词典主词典倒排文件倒排文件倒排文件主倒排文件①①①②③③③④④④3。倒排索引创建－两趟算法Two-pass索引创建1。Parsing,提取indexterm，统计df和tf，通过hash表转换为termid，生成词典文件(lexiconfile)。2。按统计得到的indexterm的tf,df属性,可以估计出对应postinglist长度，预申请空间。再次parsing文档集，在内存中执行倒排。结果保存到临时文件。3。对多次