词法分析停用词消除词干还原term选择索引构建.ppt

查询处理 也可根据一定策略在索引时就进行裁剪（静态索引裁剪） 基于词项的裁剪 一个词项对应的位置（文档）列表中，只保留得分较高的文档 TREC　TB　2006数据上实验显示，裁剪率50%时，检索结果质量没有显著下降（P＠10由0.503降为0.500，MAP由0.260降为0.238），查询的平均时间下降了37% 基于文档的裁剪 计算t在文档d中的分布与在文档集C中的分布之间的KL距离，将文档d中该距离较小的t删除掉 TREC　TB　2006数据上实验显示，裁剪率70%时，检索结果质量没有显著下降（P＠10由0.508降为0.503，MAP由0.260降为0.238），查询的平均时间下降了37% 裁剪后得到的结果与不裁剪时可能不一致，如何保证正确性？对基于词项的裁剪，是将文档得分小于某阈值的文档裁剪了，利用该阈值可算出文档对某查询得分的“上限”，对文档排序时利用该上限，如果排序结果不正确，可再用一个未裁剪的索引。 查询处理 预计算得分 在BM25等模型中，可将t在文档中的分值（而不是出现的次数，TF值较小，通常用2－3位二进制即可）直接存储在索引中，加快查询处理过程（主要是从磁盘中读索引的过程）。但分值的保存用浮点数需要24－32位。 可对评分进行离散化，然后再存储 查询处理 前面提到的通常是按文档及位置的编号对位置列表进行排序的 也可基于影响力对位置列表进行排序，但对前面的算法及复杂度影响很大。 小结 文档预处理 词法分析 停用词消除 (stop list) 词干还原(morphological stemming) Term选择 statistics (counting words) part-of-speech tagging compound splitting partial parsing: noun phrase extraction other: use of thesaurus, named entity recognition, ... 索引构建 Motivation Inverted index Steps 作业 练习使用分词系统 练习使用英语词干化工具 设计一个简单的索引系统和查询处理系统(每个词在文档中的分值用其词频表示) * incidence matrix 关联矩阵 * is AND and /s, /p, and /k ask for matches in the same sentence, same paragraph or within k words respectively. Double quotes give a phrase search (consecutive words); * How to build inverted index, 1M*1K terms document collection, There are 1G postings, can’t do it in memory. 讨论? * 刘奕群等《有哪些信誉好的足球投注网站引擎技术基础》 * 《信息检索-实现和评价有哪些信誉好的足球投注网站引擎》 * Multiple term entries in a single document are merged. Frequency information is added. The result is split into a Dictionary file and a Postings file. Why split? 基于排序的索引构建 Step1:从文件读入词条后，以（termID,position)对其记录，排序并写入磁盘（指定内存用完后）。 Step2: 将多个有序记录块通过多路合并操作进行合并 该方法每个位置都需要（termID,position)，其中各词项对应的词项编号需要一个词典，每个位置中包含词项编号也浪费了空间。 基于合并的索引 一开始建立一个常驻内在索引，一旦内存不足，就将常驻内存索引数据传输到磁盘，建立一个磁盘的倒排文档，并删除内存中的索引。重复执行起到索引构建完毕 对上面得到的倒排文档集进行合并成为最终索引。 索引的内容 模式依赖索引：支持面向文档检索的结构优化后的索引 文档编号索引 词频索引 位置索引 模式独立索引：没有优化的索引。允许在查询阶段才指定文档的定义(但需要额外的时间) Index size Stemming/case folding cut number of terms by ~40% number of pointers by 10-20% total space by ~30% Stop words Rule of 30: ~30 words account for ~30% of all term occurren