{管理信息化信息技术}第4章信息检索技术.ppt

下载

第四章 信息检索技术 11 内容提要  倒排文档检索  加权检索  全文检索 22 倒排文档检索 33 信息检索系统的体系结构 文本 数据库 数据库 管理 建索引 索引 提问处理 搜索 排序 排序后 的文档 用户 反馈 文本处理 用户界面 检出的文档 用户 需求 文本 提问 逻辑视图 倒排文档 44 建立索引的目的  对文档或文档集合建立索引，以加快检索速度对文档或文档集合建立索引，以加快检索速度  倒排文档（或倒排索引）是一种最常用的索引机制倒排文档（或倒排索引）是一种最常用的索引机制  倒排文档的索引对象是文档或文档集合中的单词等。倒排文档的索引对象是文档或文档集合中的单词等。 55 在关系数据库上建索引  这种想法也被应用于数据库技术中，即对数据库中需要这种想法也被应用于数据库技术中，即对数据库中需要 经常进行检索的域建立索引结构，进行快速的查询。经常进行检索的域建立索引结构，进行快速的查询。  索引结构索引结构: hashing, B+-tree: hashing, B+-tree  可以索引全部记录，在全部记录上进行搜索可以索引全部记录，在全部记录上进行搜索  精确地快速地查找精确地快速地查找 地址姓名 姓名索引 查询式: 姓名 = “张三” 张三 哈尔滨工业大学 张三 66 对文档进行索引  索引结构索引结构: : hashing, B+-trees, trieshashing, B+-trees, tries..  可以进行部分匹配可以进行部分匹配: ’%comput% ’: ’%comput% ’  可以进行短语搜索可以进行短语搜索::查找包含查找包含“computer “computer graphics”graphics”的文档的文档 文档索引 D1 D2 D3 computer D1, 23, 97, 104 D3, 43 graphics D2, 5 D3, 44 “computer”在D1中出现的位置 77 倒排文档组成  倒排文档一般由两部分组成：词汇表 （vocabulary）和记录表（posting list）  词汇表是文本或文本集合中所包含的所有不 同单词的集合。  对于词汇表中的每一个单词，其在文本中出 现的位置或者其出现的文本编号构成一个列 表，所有这些列表的集合就称为记录表 88 一般的倒排索引  索引文件可以用任何文件结构来实现索引文件可以用任何文件结构来实现  索引文件中的词项是文档集合中的词表索引文件中的词项是文档集合中的词表 architecture computer database retrieval ... D1, a1 D1, a2 D1, a3 索引项/ 词表 索引/ 索引文件/ 索引数据库 Postings 列表 Q = term1, term2, term3, ... 附加信息 例如：词位置，出现 次数 99 例子 11 22 33 44 55 66 77 88 99 1010 1111 1212 1313 1414 1515 1616 这这 是是 一本一本 关关于于 信息信息 检检索索 的的 教材教材 。。 介介绍绍 了了 检检索索 的的 基本基本 技技术术 。。 …… 技术 教材 检索 信息 … 15, … 8, … 6, 12, … 5, … … 词汇表 Posting list 文本 倒排文件 1010 以文本为记录表 记录表既可以存储文本中单词的编号位置，也可以指向 单词首字母的字符位置，还可以是其所在的文本编号，下图 是一个以文本为记录表的情况 1111 距离约束：需要位置信息为记录表  常常需要知道邻接条件，例如：常常需要知道邻接条件，例如： –– “database” “database” 后面紧跟着后面紧跟着“systems”“systems”  例如：短语搜索例如：短语搜索 “database systems” “database systems” –– “database”“database”和和““systems”systems”之间不能间隔超过之间不能间隔超过33个词个词 –– “database”“database”和和“architecture”“architecture”在同一个句子里在同一个句子里  需求扩展需求扩展:: –– 倒排索引中保存着关键词在文档中的位置，文档的组成单倒排索引中保存着关键词在文档中的位置，文档的组成单 元元((标题标题, , 小标题小标题, , 句子分割标记等句子分割标记等)) –– 检索算法和位置信息相关联，并需检查文档的组成单元检索算法和位置信息相关联，并需检查文档的组成单元 1212 以位置信息为记录表 –– 保存段落、句子和词的位置：保存段落、句子和词的位置： database file systems ... D345, 25 D348, 37 D350, 8 D123, 5 D128, 25 D345, 25  保存倒排表中的位置信息:  保存句子位置: 文档D350 第8句 database file systems ... D345, 2,3,5 D348, 37,5,9 D350, 8,12,1 D123, 5,4,3 D128, 25,1,12 D345, 2,3,6 文档D350 第8段，第12句 第1个词 1313 以权重信息为记录表  可保存出现频率，以便支持基于统计的检索可保存出现频率，以便支持基于统计的检索:: database file systems ... D345, 10 D348, 20 D350, 1 D123, 82 D128, 8 D345, 12 在D345中 “systems” 比 “database” 重要倍  Postings中的第二个单元可以是该term的权重 (例如, 可 以被归一化在0和1之间) ，或者是该term的出现频率 1414 同义词扩展词汇表  同义词对于提高召回率很有意义同义词对于提高召回率很有意义  同义词可以通过指针指向同一个同义词可以通过指针指向同一个postings list. ... database databases systems D345, 2,3,5 D348, 37,5,9 D350, 8,12,1 D123, 5,4,3 D128, 25,1,12 D345, 2,3,6 dataset 1515 建立索引的过程 1616 建立索引的过程  识别文档中的词识别文档中的词  删除停用词删除停用词(stop words)(stop words)  提取词干提取词干(stemming)(stemming)  用索引项的标号代替词干用索引项的标号代替词干(stems) (stems)  统计词干的数量统计词干的数量((tftf))  ((可选可选)) 对低频词项使用同义词词典对低频词项使用同义词词典(thesaurus)(thesaurus)  ((可选可选) ) 对高频词项构成短语对高频词项构成短语  计算所有单个词项、短语和语义类的权重计算所有单个词项、短语和语义类的权重 1717 英文词根还原(Stemming)  进行词根还原： stop/stops/stopping/stoppedက�stop – 好处：减少词典量；坏处：按词形查不到，好处：减少词典量；坏处：按词形查不到， 词根还原还可能出现错误词根还原还可能出现错误  不进行词根还原： – StoppedStoppedက�က�sto+ppe+dsto+ppe+d – 好处：支持词形查询；坏处：增加词典量好处：支持词形查询；坏处：增加词典量 1818 停用词消除  停用词(stop words)是指那些出现频率 高但是无重要意义，通常不会作为查询 词出现的词，如“的”、“地”、“得 ”、“都”、“是”等等 – 消除：通常是通过查表的方式去除，去除消除：通常是通过查表的方式去除，去除 的好处的好处--------大大较少索引量，坏处大大较少索引量，坏处--------有些平有些平 时的停用词在某些上下文可能有意义时的停用词在某些上下文可能有意义 – 保留：索引空间很大保留：索引空间很大 1919 建立索引的过程 – 举例  输入文本输入文本 –– The analysis of 25 indexing algorithms has not produced consistent retrieval The analysis of 25 indexing algorithms has not produced consistent retrieval performance. The best indexing technique for retrieving documents is not performance. The best indexing technique for retrieving documents is not knownknown  删除删除stopwordsstopwords –– analysis indexing algorithms produced consistent retrieval performance analysis indexing algorithms produced consistent retrieval performance best indexing technique retrieving documents knownbest indexing technique retrieving documents known  StemmingStemming –– analysis index algorithm produc consistent retriev perform best index analysis index algorithm produc consistent retriev perform best index technique retriev document knowntechnique retriev document known  转换为索引编号转换为索引编号 –– 123 345 110 2234 432 3565 2302 566 345 4321 3565 755 1128123 345 110 2234 432 3565 2302 566 345 4321 3565 755 1128  计算计算tftf –– 110 1 123 1 345 2 1 432 1 566 1 755 1 1128 1 2302 1 2344 110 1 123 1 345 2 1 432 1 566 1 755 1 1128 1 2302 1 2344 1 3565 2 4321 11 3565 2 4321 1  计算词项的权值计算词项的权值 ( (依赖于使用的模型依赖于使用的模型)) 2020 检索过程  给定给定queryquery  对对queryquery进行进行stemmingstemming，算法与对文档的处理相同，算法与对文档的处理相同  用索引编号代替用索引编号代替stemsstems  计算所有计算所有query termsquery terms的权重的权重  形成形成queryquery向量（对向量（对VSMVSM模型而言）模型而言）  计算计算queryquery向量和文档向量之间的相似度向量和文档向量之间的相似度  返回排序后的文档集合返回排序后的文档集合 2121 倒排索引上的布尔检索  一个布尔检索包含一个布尔检索包含nn个用布尔操作连接的词项个用布尔操作连接的词项 ，例如：，例如：““computer computer AND news AND NOT newsgroup”AND news AND NOT newsgroup” –– 可以用括号来调整逻辑运算次序可以用括号来调整逻辑运算次序  每个term从倒排索引中返回一个postings list  如果term不在任何文档中出现，则 postings list为空  检索结果根据逻辑关系相结合：  AND: 集合做交运算  OR: 集合做并运算  NOT: 集合做差运算 A B A and B 2222 倒排索引上的布尔检索  查询:中国 AND 文化 – 查找查找DictionaryDictionary，定位，定位中国中国;;  读取对应的读取对应的. – 查找查找DictionaryDictionary，定位，定位文化文化;;  读取对应的读取对应的. – ““MergeMerge” ” 合并合并(AND)(AND)两个两个postings:postings: 128 34 2 4 8 16 32 64 1 2 3 5 8 13 21 中国 文化 2323 34 1282 4 8 16 32 64 1 2 3 5 8 13 21 合并  ListsLists的合并算法的合并算法 34 2 4 8 16 32 64 1 2 3 5 8 13 21 中国 文化 2 8 If the list lengths are x and y, the merge takes O(x+y) operations. Crucial: postings sorted by docID. 2424 倒排索引上的布尔检索  标准的优化技术应用： – 从最短的从最短的posting listposting list开始做开始做““与与””操作，保操作，保 证中间结果越小越好证中间结果越小越好 – ““网络网络”” AND “AND “病毒病毒”” AND “AND “蠕虫蠕虫”” – 从哪个词项开始做交运算呢？从哪个词项开始做交运算呢？ 显然是：“病毒”和“蠕虫” 2525 倒排索引的优点  快速索引 (长query需要更多时间)  灵活性: 不同类型的信息都可以存储在 postings list中  如果存储了足够多的信息，则可以支持 复杂的检索操作 – 例如：如果记录了词在文档中的准确 位置，就可以支持短语检索，或模糊 检索 2626 倒排索引的缺点  很大的存储开销很大的存储开销 –– 50% - 150% - 300%50% - 150% - 300%  更新、插入和删除都需要很高的维护开销，更新、插入和删除都需要很高的维护开销， 倒排索引相对静态的环境倒排索引相对静态的环境((很少插入和更新很少插入和更新))中中 使用比较好使用比较好  处理开销随着布尔操作的增加而增长处理开销随着布尔操作的增加而增长  由于由于postingspostings越来越多越来越多((例如引入同义词例如引入同义词))，导，导 致索引检索的代价越来越大，需要对位置进致索引检索的代价越来越大，需要对位置进 行很多处理行很多处理((例如短语匹配例如短语匹配)) 2727 倒排文档中研究的问题  倒排文档的压缩  倒排文档的删除  倒排文档的插入 2828 索引压缩  理论上，(全文)索引的大小和原始文件 相当，因为每个词的每次出现都必须在 posting list中记录。  需不需要压缩？ – 要压缩：索引大小通常和原始文本大小相要压缩：索引大小通常和原始文本大小相 当，不压缩可能会耗费大量存储开销当，不压缩可能会耗费大量存储开销 – 不压缩：硬盘很便宜，数据量不是特别大，不压缩：硬盘很便宜，数据量不是特别大， 而且不需要解压缩的消耗而且不需要解压缩的消耗 2929 倒排索引的更新  情况一：出现了新的词，则需要修改词 典结构，在词典中增加词条。  情况二：出现了新的文档，则在相应的 词条下增加posting list。  情况三：某些文档不复存在，则在相应 的位置进行标记，等积累到一定时期进 行一次性操作。 3030 词汇表的组织  顺序排序数组：采用字典序，查找采用 二分法。空间消耗小，查找较快，但是 插入删除麻烦。  二叉搜索树、B树、Trie树等。  Hash表：通过Hash函数直接把词映射 到地址，空间消耗和Hash函数设计有关。 较快，插入删除容易。 3131 加权检索  加权检索根据每个词在检索要求中的重要程 度不同，分别给予一定的数值（权值）加以 区别，同时利用给出的检索命中界限值（阈 值，Threshold）限定检索结果的输出。  加权检索是布尔逻辑检索的一种扩充，把量 化思想引入定性检索中。  加权检索分为标引加权和检索加权两种类型。 3232 检索词赋权检索  对每一检索词给定一权值，代表其重要性。对每一检索词给定一权值，代表其重要性。 检索时，对存在的检索词的记录计算其权值检索时，对存在的检索词的记录计算其权值 总和。当权值总和大于阈值时，则认为命中。总和。当权值总和大于阈值时，则认为命中。  最简单、最容易实现的加权检索系统。最简单、最容易实现的加权检索系统。 3333  举例  一个企业管理者为了改进企业管理模式，接受新的管一个企业管理者为了改进企业管理模式，接受新的管 理理念，提高企业的竞争力，希望获取知识管理、竞理理念，提高企业的竞争力，希望获取知识管理、竞 争情报、企业文化方面的文献资料，用加权法列出的争情报、企业文化方面的文献资料，用加权法列出的 提问式如下：提问式如下： W = W = 知识管理（知识管理（44）竞争情报（）竞争情报（22）企业文化（）企业文化（11）） 表中“√”表示相应检索词与文献中主题词匹配，若设定阈值为4， 由上表可知，组合1至4为命中文献。 3434 检索词赋权检索的优缺点  检索词赋权检索的优点： – 明确了检索词在检索中的重要程度；明确了检索词在检索中的重要程度； – 通过提高或降低阈值来扩大和缩小检索输出的范围；通过提高或降低阈值来扩大和缩小检索输出的范围； – 检索结果按符合检索需求的重要程度顺序排列。检索结果按符合检索需求的重要程度顺序排列。  检索词赋权检索的缺点： – 加权法提问式表达不如逻辑式直观；加权法提问式表达不如逻辑式直观； – 权值的确定较为困难。权值的确定较为困难。 3535 加权标引  加权标引是指在对文献进行标引时，根 据每个标引词在文献中的重要程度不同， 为它们附上不同的权值，检索时通过对 检索词的标引权值相加来筛选命中记录。 3636 加权标引  在进行加权标引时，对反映文献主要内 容的标引词给予高权值，反映文献次要 内容的标引词给予较低的权值。  词频加权检索方法应建立在对全文数据 库和文摘数据库基础之上，否则词频加 权将失去意义。 3737 简单词频加权  简单词频加权检索：指检索时累计检索 词在记录中出现的次数来决定记录的权 值。  最大缺点就是不论文章长短、词频高低 都采用的是统一的词频标准。 3838 相对词频加权检索  将每将每一个检索词在本文中频率一个检索词在本文中频率和在和在整个数据整个数据 库中的频率库中的频率综合考虑，进行加权检索的方法。综合考虑，进行加权检索的方法。  文内频率文内频率==指定词在本文中的频次指定词在本文中的频次//该文本词该文本词 汇总频次汇总频次  文外频率文外频率==指定词在本文中的频次指定词在本文中的频次//该词在整该词在整 个数据库个数据库((所有文献所有文献))中总次数中总次数  文内频率解决了文内频率解决了短文章中词频过低短文章中词频过低的问题，的问题， 文外频率解决了文外频率解决了新词、专用词的低频新词、专用词的低频问题。问题。 3939 标引加权的检索过程  检索时给出检索词和检索阈值，对满足 检索阈值的检索结果按其权值之和从大 到小输出来筛选命中记录。  在实际的人工标引中尚未见有加权标引 的系统。  在计算机自动标引的系统中，可以方便 而有效的采用加权标引技术。 4040 标引加权检索阈值的设定  在检索中，阈值有两种设置方法： – 为每个检索词制定一个阈值，避免了次要为每个检索词制定一个阈值，避免了次要 内容被检出；内容被检出； – 给总的检索结果指定一个阈值，保证了命给总的检索结果指定一个阈值，保证了命 中文献的综合相关度。中文献的综合相关度。 4141 全文检索技术  全文检索，即检索的数据源、检索的对 象、检索匹配技术、检索结果都是全文 信息的检索。  全文检索有两种实现方式： – 对全文编索引；对全文编索引； – 不对全文进行任何加工处理，只是从前至不对全文进行任何加工处理，只是从前至 后的逐字匹配。后的逐字匹配。 4242 全文检索的技术指标 （（11）索引膨胀系数）索引膨胀系数  索引的膨胀系数是指针对全文所建的索引文索引的膨胀系数是指针对全文所建的索引文 件大小与全文文件大小之比。件大小与全文文件大小之比。  索引膨胀系数索引膨胀系数 = =索引文件的大小索引文件的大小//全文数据库全文数据库 的大小的大小  全文索引需要以最小的标引单位作为索引主全文索引需要以最小的标引单位作为索引主 键字，英语一般为单词，中文则为单汉字。键字，英语一般为单词，中文则为单汉字。 （（22）检索速度）检索速度 4343 全文检索的实现  全文检索的实现通常用检索词对全文产 生的词（字）索引文档的匹配。  西文的全文检索多数采用位置检索技术， 这样可以提高全文检索的查准率。  位置检索分为四种级别：记录级检索、 字段或段落级检索或自然句级检索、词 位置检索。 4444 词位置级检索 （1）词位置顺序相邻（W）  检索时要求（W）两边的词在原文中不 能有其他单词，并且次序不能颠倒。  例如：？select information （W） retrieval  可检得含有固定词组“information retrieval”的文献全文。 4545 词位置级检索 （（22）位置顺序隔词（）位置顺序隔词（nWnW））  表示由算符（表示由算符（nWnW）所连接的检索词之间最多）所连接的检索词之间最多 只能含有只能含有nn（（nn可以为可以为00）个单词，并且两词的）个单词，并且两词的 顺序不能颠倒。顺序不能颠倒。  例如：：例如：：? select computer ? select computer （（1W1W）） communication communication  其检索式表示含有下述词组的文献都可作为其检索式表示含有下述词组的文献都可作为 检索命中结果：检索命中结果：computer communicationcomputer communication；； computer and communicationcomputer and communication；；computer for computer for communicationcommunication。。 4646 词位置级检索 （3）词位置相邻（N）  若文献满足由算符（N）构成的检索式， 这些文献中必须包含算符（N）两侧的 词，并且它们是紧连的，但两词的顺序 可以颠倒。  例如 ：? select computer ? select computer （（NN）） television television  其检索结果是所有含有词组“computer “computer television”television”或或“television computer”“television computer”的文 献。 4747 词位置级检索 （（44）隔词运算（）隔词运算（nNnN））  在（在（nNnN）两侧的检索词间不能多于）两侧的检索词间不能多于nn个单词，个单词， 且两个检索词的次序可以任意。满足以上条且两个检索词的次序可以任意。满足以上条 件的文献可视为是隔词运算的检索结果。件的文献可视为是隔词运算的检索结果。  例如：？例如：？select econom?? select econom?? （（2N2N）） recovery recovery  凡含有下列词组文献可视为上式的检索结果：凡含有下列词组文献可视为上式的检索结果： economic recovery, recovery of the economic recovery, recovery of the economy, recovery from economiceconomy, recovery from economic。。 4848 字段级检索  比词位置检索的限制少。  子字段内词间“与”运算  字段内词间“与”运算  叙词字段词间“与”运算 4949 记录级检索  检索词出现在同一记录中的检索，目前 中文全文检索主要属于该级检索。记录 级全文检索等同于布尔逻辑检索中的“ 与”运算，其运算符为（C）。  例如：？select Internet （C） Navigate  该检索就相当于布尔逻辑运算式： Internet and Navigate 5050 反位置运算  反位置运算符为反位置运算符为NOTNOT，其作用为产生相反的，其作用为产生相反的 含义。不是一个独立运算符，通常得与其他含义。不是一个独立运算符，通常得与其他 运算符组合使用。运算符组合使用。  NOT WNOT W：要求该组合运算符右侧的检索词不：要求该组合运算符右侧的检索词不 能紧跟在左侧检索词之后；能紧跟在左侧检索词之后；  NOT NNOT N：要求该组合运算符两侧的检索词不：要求该组合运算符两侧的检索词不 能紧连；能紧连；  NOT SNOT S：要求该组合运算符两侧的检索词不：要求该组合运算符两侧的检索词不 能出现在同一子字段中；能出现在同一子字段中；  NOT FNOT F：要求该组合运算符两侧的检索词不：要求该组合运算符两侧的检索词不 能出现在同一字段中；能出现在同一字段中； 5151 全文检索效率的提高  用同义词词典来提高查全率  用排除词词典提高查准率 – 华人华人————中华人民共和国中华人民共和国 – 民法民法————人民法院人民法院 5252