文本检索的索引技术.ppt

文本检索的索引技术 彭波 2003-11-1 提纲 l背景和概念 l文档分析 l索引创建 l索引查询 l相关资料 1。背景和概念索引作用 l索引? 提供从记录的特征快速查询到记录的数据结构(B树、散列表、 位图索引等） 数据库，文档数据库，SE/IR系统 l文本检索 记录文档doc，记录特征索引词(index terms) 数据库结构化，查询和事务型更 新 文档数据 库 非结构化，查询和事务型 更新 SE/IR系 统 非结构化，查询 1。背景和概念索引形式 l文本检索常见索引方式 Brute-force检索 grep 签名文件 signature file hash签名,false match 倒排文件 inverted file 高效，支持多种检索模型 l倒排索引 从index term快速查询到doc的索引结构 Doc正常表示为index term的集合，建立索引是把每 个index term表示为其出现的doc的集合，这个过程 称为inversion，即倒排。 1。背景和概念倒排 文档内容 Doc1.北京大学计算机系. Doc2.北京大学主页 Doc3计算机的发展 。 。 索引词索引项(posting list) 北京大学。 计算机。 。 原始文档 倒排索引 倒排 2。文档分析原则 l索引词的选择范围 人工索引质量高，但不适用大规模文档数据处理 自动索引 l部分索引title,abstract,keywords, etc（例如：北大图书馆的 WebCat系统） l全文索引文档中所有词都参与索引。(SE/IR普遍采用) l索引词的选择原则 Index term word l理想：表达文档内容的语义单位 l字、词、短语（词汇词） l中文分词 2。文档分析英文文本 lTokenize (Lexical grammar) 问题：“c+”，R is, are,was -be lStemmer (取词根） Stemmer -stem ; lSE为了支持精确查询，往往不使用后两种技术 A-ZA-Z+ return UPWORD; a-zA-Z0-9+ return WORD; A-ZA-Z+()?s)? return ACRONYM2; a-zA-Z0-9+a-zA-Z+ return CONTRACTION; A-Z.(A-Z.)+ return ACRONYM; 2。文档分析中文文本 l字符编码问题 字符集：GB2312,GBK,BIG5,HZ UNICODE 简、繁转换 （乾杯，乾坤） l分词问题 词？：语法词、词汇词 表达确定的意义（鱼）、非组合性（多媒体）、互译 检查（dioxide 二氧化物） 2。文档分析中文文本分词 l中文分词歧义 交集型：“部分居民生活水平”1 l分居、居民、民生、生活、 组合型：“老人家” l老人、老人家 l未登录词 专有名词（人名、地名、机构名、译名、术语等）、 新词 l对大规模中文信息处理，“词典规模是制约分词 精度的主要因素”2 2。文档分析中文文本混合索引 l基本分词词典 6万，选词较为严格 l统计识别的未登录词扩展词典 统计方法，精度不高 如果加入到基本分词词典中，带来大量组合型歧义问题，不能 正确处理。-混合索引 l混合索引 基本词典：“北京”“大学”，无“北京大学”；扩展词典：有“北京大 学” 文档中的“北京大学”，基本分词分为“北京”“大学”，扩展词 典基础上在分为“北京大学”，索引按“北京”“大学”，“/2北京大学” 这样三个单位建立。 3。倒排索引创建 l基本思想：排序 文档分析 文本数据 排序 词典倒排文件 term,ptr term,ptr Doc1,doc2 Doc1,doc2 先term,再docid 3。倒排索引创建算法优化 lTerm编码（词典组织） 每个term用整数编码，减小存储空间 英文前缀编码(liber,liberal,liberalist) 散列表(MPH,无冲突散列） l减少磁盘的随机访问次数（大内存环境） 在内存中排序，排序结果分批写入磁盘，最后合 并。 两趟算法，在内存中直接倒排，小倒排文件分批写入磁盘，最 后多路合并。 l数据压缩 3。倒排索引创建两趟算法 词典 词典 词典 主 词 典 倒排文件 倒排文件 倒排文件 主 倒 排 文 件 3。倒排索引创建两趟算法 lTwo-pass索引创建 1。Parsing ,提取index term，统计df和tf，通过hash表转换为 term id，生成词典文件(lexicon file)。 2。按统计得到的index term的tf,df属性,可以估计出对应posting list长度，预申请空间。再次parsing文档集，在内存中执行倒排 。结果保存到临时文件。 3。对多次生成的临时倒排文件，多路合并，压缩输出，得到最 终倒排文件。 l效率： Parsing（包括中文分词）为主要时间开销。空间开销在临时文 件(parsing结果，临时倒排文件)上，使用压缩。 3。倒排索引创建整数压缩 l整数压缩 的整数序列压缩存贮。 压缩的基本思想：高频使用较短的位表示，低频使 用较长的位表示（ Huffman编码 ）频率分布模式 与编码 有序整数序列，记录距离，改变频率分布模式，以提 高压缩比 l1,3,7,11,13,14 1,2,4,4,2,1 编码方案 l 系列、golomb系列、bytecode 4。索引查询 北京 词典 倒排文件 大学 北京大学 文档属性 4。索引查询 l布尔查询 北京 AND 大学 lVSM rank查询 相关度用文档相似度来计算 Similarity(Q,D)=COS(Q,D) 4。索引查询 lVSM rank查询 Document-level索引： 增加文档属性数据库：|D| l短语、临近查询 例如：“北京 网易” ，“北京大学” Word-level索引： l结构查询 例如：“北京大学 IN TITLE” 在loc数据中用位标识记录 .VS. 在word-level index基础上使用 text interval 4。索引查询效率问题 l索引压缩 减少磁盘io时间，增加cpu处理索引项的时间 折衷：使用Byte code， l索引的随机访问加入同步点 更多的IO次数，减少数据传输总量 折衷：控制block大小参数 l有待进一步工作 参考Justin Zobel,Ian Witten,Alistair moffat等人一系 列的paper 5。其它问题 l倒排索引更新 查询和更新效率 postinglist连续存储查询效率高，更新难 postinglist分块链表存储查询效率低，更新易 成批更