文本检索的索引技术幻灯片.ppt
文本检索的索引技术文本检索的索引技术第1页，共22页，编辑于2022年，星期六提纲提纲l背景和概念l文档分析l索引创建l索引查询l相关资料第2页，共22页，编辑于2022年，星期六1。背景和概念索引作用。背景和概念索引作用l索引?提供从记录的特征快速查询到记录的数据结构(B树、散列表、位图索引等）数据库，文档数据库，SE/IR系统l文本检索记录文档doc，记录特征索引词(indexterms)数据库结构化，查询和事务型更新文档数据库非结构化，查询和事务型更新SE/IR系统非结构化，查询第3页，共22页，编辑于2022年，星期六1。背景和概念索引形式。背景和概念索引形式l文本检索常见索引方式Brute-force检索grep签名文件signaturefilehash签名,falsematch倒排文件invertedfile高效，支持多种检索模型l倒排索引从indexterm快速查询到doc的索引结构Doc正常表示为indexterm的集合，建立索引是把每个indexterm表示为其出现的doc的集合，这个过程称为inversion，即倒排。第4页，共22页，编辑于2022年，星期六1。背景和概念倒排。背景和概念倒排文档内容Doc1.北京大学计算机系.Doc2.北京大学主页.Doc3计算机的发展。索引词索引项(posting list)北京大学。计算机。原始文档倒排索引倒排第5页，共22页，编辑于2022年，星期六2。文档分析原则。文档分析原则l索引词的选择范围人工索引质量高，但不适用大规模文档数据处理自动索引l部分索引title,abstract,keywords,etc（例如：北大图书馆的WebCat系统）l全文索引文档中所有词都参与索引。(SE/IR普遍采用)l索引词的选择原则Indextermwordl理想：表达文档内容的语义单位l字、词、短语（词汇词）l中文分词第6页，共22页，编辑于2022年，星期六2。文档分析英文文本。文档分析英文文本lTokenize(Lexicalgrammar)问题：“c+”，R&B，U.S.，a.out没有被识别问题：数字长度、词长度词规模lLemertization(曲折词形合并)He,him-he;is,are,was-belStemmer(取词根）Stemmer-stem;lSE为了支持精确查询，往往不使用后两种技术A-ZA-Z+returnUPWORD;a-zA-Z0-9+returnWORD;A-ZA-Z+()?s)?returnACRONYM2;a-zA-Z0-9+a-zA-Z+returnCONTRACTION;A-Z.(A-Z.)+returnACRONYM;第7页，共22页，编辑于2022年，星期六2。文档分析中文文本。文档分析中文文本l字符编码问题字符集：GB2312,GBK,BIG5,HZUNICODE简、繁转换（乾杯，乾坤）l分词问题词？：语法词、词汇词表达确定的意义（鱼）、非组合性（多媒体）、互译检查（dioxide二氧化物）第8页，共22页，编辑于2022年，星期六2。文档分析中文文本分词。文档分析中文文本分词l中文分词歧义交集型：“部分居民生活水平”1l分居、居民、民生、生活、组合型：“老人家”l老人、老人家l未登录词专有名词（人名、地名、机构名、译名、术语等）、新词l对大规模中文信息处理，“词典规模是制约分词精度的主要因素”2第9页，共22页，编辑于2022年，星期六2。文档分析中文文本混合索引。文档分析中文文本混合索引l基本分词词典6万，选词较为严格l统计识别的未登录词扩展词典统计方法，精度不高如果加入到基本分词词典中，带来大量组合型歧义问题，不能正确处理。-混合索引l混合索引基本词典：“北京”“大学”，无“北京大学”；扩展词典：有“北京大学”文档中的“北京大学”，基本分词分为“北京”“大学”，扩展词典基础上在分为“北京大学”，索引按“北京”“大学”，“/2北京大学”这样三个单位建立。第10页，共22页，编辑于2022年，星期六3。倒排索引创建。倒排索引创建l基本思想：排序文档分析文本数据排序词典倒排文件term,ptrterm,ptrDoc1,doc2Doc1,doc2先term,再docid第11页，共22页，编辑于2022年，星期六3。倒排索引创建算法优化。倒排索引创建算法优化lTerm编码（词典组织）每个term用整数编码，减小存储空间英文前缀编码(liber,liberal,liberalist)散列表(MPH,无冲突散列）l减少磁盘的随机访问次数（大内存环境）在内存中排序，排序结果分批写入磁盘，最后合并。两趟算法，在内存中直接倒排，小倒排文件分批写入磁盘，最后多路合并。l数据压缩第12页，共22页，编辑于2022年，星期六3。倒排索引创建两趟算法。倒排索引创建两趟算法词典词典词典主词典倒排文件倒排文件倒排文件主 倒排 文件 第13页，共22页，编辑于2022年，星期六3。倒排索引创建两趟算法。倒排索引创建两趟算法lTwo-pass索引创建1。Parsing,提取indexterm，统计df和tf，通过hash表转换为termid，生成词典文件(lexiconfile)。2。按统计得到的indexterm的tf,df属性,可以估计出对应postinglist长度，预申请空间。再次parsing文档集，在内存中执行倒排。结果保存到临时文件。3。对多次生成的临时倒排文件，多路合并，压缩输出，得到最终倒排文件。l效率：Parsing（包括中文分词）为主要时间开销。空间开销在临时文件(parsing结果，临时倒排文件)上，使用压缩。第14页，共22页，编辑于2022年，星期六3。倒排索引创建整数压缩。倒排索引创建整数压缩l整数压缩的整数序列压缩存贮。压缩的基本思想：高频使用较短的位表示，低频使用较长的位表示（Huffman编码）频率分布模式与编码有序整数序列，记录距离，改变频率分布模式，以提高压缩比l1,3,7,11,13,141,2,4,4,2,1编码方案l系列、golomb系列、bytecode第15页，共22页，编辑于2022年，星期六4。索引查询。索引查询北京词典倒排文件大学 北京大学 文档属性第16页，共22页，编辑于2022年，星期六4。索引查询。索引查询l布尔查询北京AND大学lVSMrank查询相关度用文档相似度来计算Similarity(Q,D)=COS(Q,D)第17页，共22页，编辑于2022年，星期六4。索引查询。索引查询lVSMrank查询Document-level索引：增加文档属性数据库：|D|l短语、临近查询例如：“北京网易”，“北京大学”Word-level索引：docid,F(d,t),l结构查询例如：“北京大学INTITLE”在loc数据中用位标识记录.VS.在word-levelindex基础上使用textinterval第18页，共22页，编辑于2022年，星期六4。索引查询效率问题。索引查询效率问题l索引压缩减少磁盘io时间，增加cpu处理索引项的时间折衷：使用Bytecode，l索引的随机访问加入同步点更多的IO次数，减少数据传输总量折衷：控制block大小参数l有待进一步工作参考JustinZobel,IanWitten,Alistairmoffat等人一系列的paper第19页，共22页，编辑于2022年，星期六5。其它问题。其它问题l倒排索引更新查询和更新效率postinglist连续存储查询效率高，更新难postinglist分块链表存储查询效率低，更新易成批更新，删除使用结果过滤。l分布式结构按文档划分.vs.按索引词划分按文档划分，各个节点间在查询过程中相互无需数据通信，扩展性好。第20页，共22页，编辑于2022年，星期六5。相关资料。相关资料lhttp:/www.stanford.edu/class/cs276a/lhttp:/www.cs.mu.oz.au/mg/第21页，共22页，编辑于2022年，星期六谢谢谢谢!第22页，共22页，编辑于2022年，星期六
