搜索引擎技术介绍 王栋
搜索引擎技术介绍 王栋
Topics 概述 ■信息检索模型 ■信息检索系统的评价标准 ■Wveb搜索引擎的难点 ■Web搜索引擎体系结构 ■ Web crawler ■预处理 索引和查找 检索结果排序
Topics 概述 信息检索模型 信息检索系统的评价标准 Web搜索引擎的难点 Web搜索引擎体系结构 Web Crawler 预处理 索引和查找 检索结果排序
概述 搜索引擎属于信息检索( nformation retrieva,R)范畴 信息检索的基本任务 口如何找到并定位特定资源? 口这些资源可能来自 Web 数据库 ■文件系统 如果目标资源是Web,就称为Wveb搜索引擎 口 Google,百度, Yahoo!
概述 搜索引擎属于信息检索(Information Retrieval，IR)范畴 信息检索的基本任务 如何找到并定位特定资源？ 这些资源可能来自 Web 数据库 文件系统 …. 如果目标资源是Web，就称为Web搜索引擎 Google，百度，Yahoo！
Web User F system Get Users Present Query Search Gathe Results Data Index Search Document Index Index Figure 1.5 A typical application integration with Lucene
信息检索模型(1/3) ■信息检索模型(| R model)可形式化地表示为一个四元 组 其中D是一个文档集合,Q是一个查询集合,F是一个对文 档和查询建模的框架,R(q,d)是一个排序函数,它给查 询q和文档d之间的相关度赋予一个排序值,即相天度评 价 常见的信息检索模型有: 口布尔模型( Boolean mode) 口向量空间模型( Vector Space Model) 口概率模型( Probabilistic Model) 口推理网络模型( Inference Network Mode)
信息检索模型(1/3) 信息检索模型（IR model）可形式化地表示为一个四元 组： 其中 D是一个文档集合， Q是一个查询集合， F是一个对文 档和查询建模的框架，R(q, d) 是一个排序函数，它给查 询 q和文档 d之间的相关度赋予一个排序值，即相关度评 价。 常见的信息检索模型有： 布尔模型（Boolean Model ） 向量空间模型（Vector Space Model ） 概率模型（Probabilistic Model ） 推理网络模型（Inference Network Model ）
信息检索模型(12) 信息检索的一个核心问题是如何决定查询和文档之间的相 关度,節信息检索模型中的排序函数R(q,d)。 ■常用的相关度评价方法是向量空间模型( ector Space Model, vsm ■向量空间模型基于共有词汇假设( shared bag of words),即査询和文档都被认为是有所有关键词组成的 N维向量,相关度根据他们在向量空间中的夹角的 cosine 值表示,即 R(d, a)=cos(d, a)=d g / q 那么如何决定N维向量每一维的权重,即N维向量中每个 关键词的权重呢??
信息检索模型(1/2) 信息检索的一个核心问题是如何决定查询和文档之间的相 关度，即信息检索模型中的排序函数R(q,d) 。 常用的相关度评价方法是向量空间模型(Vector Space Model，VSM) 向量空间模型基于共有词汇假设（shared bag of words），即查询和文档都被认为是有所有关键词组成的 N维向量，相关度根据他们在向量空间中的夹角的cosine 值表示，即 R(d, q) = cos(d, q) = d·q / |d| ×|q| 那么如何决定 N维向量每一维的权重，即 N维向量中每个 关键词的权重呢？？
信息检索模型(2/2) 齪搋度閣对亨旻韁優棼躑猝續養熛亼比躞睥「謦, 就是说出 ,英语中的 the 基于这一原理,“逆文本频率指数”( nverse Document Frequency,|DF)通 常被用来计算关键词的权重。关键词t的IDF值可以被表示为: IDF(t)=log( N/df(t)) 其中N是所有文档总数,dft表示单词t的文档频率( Document Frequency), 即单词t在多少篇文档中出现。 IDF是一个单词在语言中的统计特性,所以少量新文档加入对它影响很小,可 以一次计算后作为单词的属性使用。 把TF(t,d)定义为单词t在文档d中的出现频率,那么文档d中关键词t的权重可 以表示为 Weight(t, d)=TF(t, d)*IDF(t 其中,DF(对单词t来说是一个全局权值,而TF(,d则是单词t在文档d中的 局部权值
信息检索模型(2/2) 根据信息论原理，信息单位出现的频率越大，携带的信息越小。这就是说出 现频度很高的词对于文档区分的作用很小，比如汉语中的 “ 的 ”，英语中的 “the”。 基于这一原理， “逆文本频率指数 ” （Inverse Document Frequency, IDF）通 常被用来计算关键词的权重。关键词 t 的IDF值可以被表示为： IDF(t) = log( N/ df(t) ) 其中 N是所有文档总数， df(t)表示单词 t的文档频率(Document Frequency)， 即单词 t在多少篇文档中出现。 IDF是一个单词在语言中的统计特性，所以少量新文档加入对它影响很小，可 以一次计算后作为单词的属性使用。 把TF(t, d)定义为单词 t在文档 d中的出现频率，那么文档 d中关键词 t的权重可 以表示为： Weight(t, d) = TF(t, d) * IDF(t) 其中，IDF(t)对单词 t来说是一个全局权值，而TF(t, d)则是单词 t在文档 d中的 局部权值
原理 根据TF*DF公式,文档集中包含某一词条 的文档越多,说明它区分文档类别属性的 能力越低,其权值越小; ■另一方面,某一文档中某一词条出现的频 率越高,说明它区分文档内容属性的能力 越强,其权值越大
原理 根据TF*IDF公式，文档集中包含某一词条 的文档越多，说明它区分文档类别属性的 能力越低，其权值越小； 另一方面，某一文档中某一词条出现的频 率越高，说明它区分文档内容属性的能力 越强，其权值越大
信息检索系统的评价标准 效率”几乎是任何计算机系统都需要考虑的问题,比如算 法的时空效率,对于信息检索系统,重要的效率指标通常 有: 口系统的查询响应时间( Response time) 口系统的查询吞吐量( Request throughput)。 效果”关注用户需求的满足程度,对于信息检索系统通常 有两个指标:查全率(Reca)和查准率( Precision)。 口查全率定义为检索结果集中的相关文档占整个文档全集中的相关 文档的百分比 口查准率定义为检索结果集中与用户査询相关的文档占整个检索结 果中所有文档的百分比。 口紊是箱笑看約1男相关是能在意素晕衡案 和查准率之间存在着相反的相互依赖关系,即查准率和査全率往 能两全其美,通常查准率高时,查全率低;查全率高时,查
信息检索系统的评价标准 “效率 ”几乎是任何计算机系统都需要考虑的问题，比如算 法的时空效率，对于信息检索系统，重要的效率指标通常 有： 系统的查询响应时间（Response time ） 系统的查询吞吐量（Request throughput）。 “效果 ”关注用户需求的满足程度，对于信息检索系统通常 有两个指标：查全率（Recall）和查准率（Precision）。 查全率定义为检索结果集中的相关文档占整个文档全集中的相关 文档的百分比 查准率定义为检索结果集中与用户查询相关的文档占整个检索结 果中所有文档的百分比。 查全率是衡量检索系统取回相关信息的能力，查准率是衡量检索 系统拒绝非相关信息的能力。实验证明，在信息检索中，查全率 和查准率之间存在着相反的相互依赖关系，即查准率和查全率往 往不能两全其美，通常查准率高时，查全率低；查全率高时，查 准率低
Web搜索引擎的难点 数据 口数据规模巨大且增长快 比如,Web上的网页量级是 billion,中国的Web页面就有几十亿 口Web的异构性 口多种多样 40000000 35000000 ■文本、图片、视频、音频等 30000000 口非结构化和半结构化数据 25000000 20000000 ■比如,文本数据和XML数据 0000000 用户 口如何表达查询需求? 口如何解释查询结果?
Web搜索引擎的难点 数据 数据规模巨大且增长快 比如，Web上的网页量级是billion，中国的web页面就有几十亿！ Web的异构性 多种多样 文本、图片、视频、音频等 非结构化和半结构化数据 比如，文本数据和XML数据 用户 如何表达查询需求？ 如何解释查询结果？ Internet growth 0 5000000 10000000 15000000 20000000 25000000 30000000 35000000 40000000 Sep-69 Sep-72 Sep-75 Sep-78 Sep-81 Sep-84 Sep-87 Sep-90 Sep-93 Sep-96 Sep-99 Hosts