第八章-搜索引擎技术.ppt
《第八章-搜索引擎技术.ppt》由会员分享,可在线阅读,更多相关《第八章-搜索引擎技术.ppt(380页珍藏版)》请在三一文库上搜索。
1、北京大学软件与微电子学院2009年度课程,1,第八章 搜索引擎技术,2010年11月,最后更新日期:2020-1-29,北京大学软件与微电子学院2009年度课程,2,主要内容,信息采集技术(Information gathering) 信息的组织和索引(Information organization&indexing) 相似度计算信息检索模型(IR models) 链接分析技术 查询分析技术 结果呈现技术 搜索引擎的评估技术(Evaluation),北京大学软件与微电子学院2009年度课程,3,主要内容,信息采集技术(Information gathering) 信息的组织和索引(Infor
2、mation organization&indexing) 相似度计算信息检索模型(IR models) 链接分析技术 查询分析技术 结果呈现技术 搜索引擎的评估技术(Evaluation),北京大学软件与微电子学院2009年度课程,4,信息的采集技术,北京大学软件与微电子学院2009年度课程,5,信息采集的概念,主要是指通过Web页面之间的链接关系从Web上自动获取页面信息,并且随着链接不断向所需要的Web页面扩展的过程,信息采集系统也常常称为Robot, Spider, Crawler等等 信息采集是搜索引擎获得数据来源的过程,地位相当重要 信息采集的目标:快速获得高质量的网页 信息采集是
3、一项十分繁杂和庞大的工程 不同的协议 不同的网络情况 时效性的要求 网页质量的要求 实际上是图的遍历过程 通过种子页面或站点(Seed),获取更多的链接,将它们作为下一步种子,循环 这个过程一般永远不会结束!,北京大学软件与微电子学院2009年度课程,6,WEB图结构,北京大学软件与微电子学院2009年度课程,7,WEB图中的一些概念,节点(Node):指每个网页,当图中每个连接的单位是网站时,每个网站看成一个Node。 入度(In degree):每个Node的入度指的是指向该Node的Node数目。 出度(Out degree):每个Node的出度指的是该Node指向的Node数目。,北京
4、大学软件与微电子学院2009年度课程,8,WEB的相关特性(1),Power Law(幂分布定律):WEB的很多属性满足f(x)=x-, 1,北京大学软件与微电子学院2009年度课程,9,WEB的相关特性(2),Small world(小世界)理论:整个WEB虽然庞大,但是任意两点之间的平均距离却不大。有人做过实验,计算出整个WEB的平均距离约为19。 人类社会的六度分离理论,人类社会至多通过6人可以实现两人的互通。,北京大学软件与微电子学院2009年度课程,10,WEB的相关特性(3),WEB的结构:蝴蝶结型(Bow-tie) SCC为连通部分 IN中网页指向SCC SCC指向OUT中网页
5、非连通部分(Tendrils),北京大学软件与微电子学院2009年度课程,11,信息采集的基本结构,北京大学软件与微电子学院2009年度课程,12,采集的遍历算法,宽度优先 vs. 深度优先 宽度优先:先采集完同一层的网页,再采集下一层网页 深度优先:先沿一条路径采到叶节点,再从同层其他路径进行采集 有研究表明:宽度优先的方法得到的网页集合的重要性更好 网站采集 vs. 全局URL采集 网站采集:一个网站一个网站采集 全局URL采集:将所有URL放入一个URL池,从中使用某种方法进行选择 网站采集在支持应用方面灵活性大一些,但是采集效率可能不如全局URL采集,通常的搜索引擎采用全局URL采集的
6、方法。,北京大学软件与微电子学院2009年度课程,13,采集网页的更新策略,定期重采:一段时间以后重新采集所有网页,全部采完以后替换原来的网页 增量采集:只按照某种策略采集那些可能新增、变化的网页,并删除那些已经不存在的网页 定期重采非常简单,但是浪费带宽,周期也长;增量采集可以节省带宽,网页更新周期相对较短,但是系统的复杂性增大。,北京大学软件与微电子学院2009年度课程,14,采集网页的速度保证措施,本地DNS解析 多机分布式并行 局域网联接多机进行采集并行 广域网分布式采集 单机多程序并行 多进程并行 多线程并行,北京大学软件与微电子学院2009年度课程,15,采集网页的质量保证措施,减
7、少重复页面的采集 URL重复的检测和排除 内容重复的检测和排除 保证重要页面的高优先级 入度高的网页相对重要 URL浅的网页相对重要 含有被别人广泛映像的内容的网页重要,北京大学软件与微电子学院2009年度课程,16,采集中的“礼貌”问题,遵守网站上发布的Robot.txt 采集限制协议 采集时尽量不要太过密集地采集某个网站,这种密集访问类似于DoS攻击,导致普通用户正常浏览网站产生困难。有些网站会严密控制这种密集访问行为。,北京大学软件与微电子学院2009年度课程,17,信息采集的研究趋势,高速、高质量信息采集 个性化信息采集 只采集符合用户的兴趣的数据 基于主题的信息采集 采集某个领域的数
8、据 信息采集及抽取 采集后提取结构化信息,北京大学软件与微电子学院2009年度课程,18,主要内容,信息采集技术(Information gathering) 信息的组织和索引(Information organization&indexing) 相似度计算信息检索模型(IR models) 链接分析技术 查询分析技术 结果呈现技术 搜索引擎的评估技术(Evaluation),北京大学软件与微电子学院2009年度课程,19,信息的组织和索引(Information organization&indexing),北京大学软件与微电子学院2009年度课程,20,提纲,字符串匹配 前向索引 倒排索引
9、,北京大学软件与微电子学院2009年度课程,21,课前思考题,Google号称80亿网页,Baidu也有10亿网页,数量可谓巨大,但是当我们输入一个查询时,返回时间往往不到1秒,为什么这么快?奥秘在哪里? 什么情况下使用字符串匹配? 什么情况下使用前向索引? 什么情况下使用倒排索引?倒排索引的生成过程如何?,北京大学软件与微电子学院2009年度课程,22,引言,检索面对的搜索基本问题:给定一个查询串,在文档集合里面搜索出现这些查询串的文档。 解决该问题的效率将影响检索的效率。,北京大学软件与微电子学院2009年度课程,23,提纲,字符串匹配 前向索引 倒排索引,北京大学软件与微电子学院2009
10、年度课程,24,基于字符串匹配的搜索,定义:给定一个子串q,在字符串d中查找q所有出现的位置(有时只要判断是否出现即可)。q的长度假设为m,d的长度假设为n。 搜索问题转化为对每个查询q,在文档集合中搜索出现查询q的文档。 当文档集合规模不大时,通过字符串定位可以实现检索。如小型网站的全文检索。 优点: 方法简单易行 很方便地支持文档更新(增加和删除) 缺点: 效率不高。,北京大学软件与微电子学院2009年度课程,25,Brute force方法,假设文档长度为n,子串长度为m,用子串逐一试探,一旦不能匹配则往后移动一位继续匹配,相当于一个窗口不断滑动。 例子: 查询:中国 文档:那一位同行来
11、自中国北京。 算法复杂度:(不考虑分词)最坏情况下时间复杂度O(mn),最好情况下O(n+m),北京大学软件与微电子学院2009年度课程,26,KMP方法,Knuth & Morris & Pratt发现,简称KMP方法。数据结构中的经典算法。 通过重用先前的匹配信息,减少滑动的次数,从而提高效率。 具体地:先预先求出模式串每个位置的next函数。匹配过程中一旦匹配失败则利用next函数滑动窗口进行匹配。 算法复杂度:最坏情况下仍然是O(mn),但是在一般情况下的实际执行时间是O(m+n)。特别适合于模式串和文本串之间存在许多“部分匹配”的情况。整个匹配过程中,指向文本串的指针不需要回溯。,北
12、京大学软件与微电子学院2009年度课程,27,其他方法及其他匹配方式,Aho-Corasick (AC) Boyer-Moore(BM) Shift-OR 多模式匹配 正则表达式匹配 模糊匹配、容错近似匹配,北京大学软件与微电子学院2009年度课程,28,提纲,字符串匹配 前向索引 倒排索引,北京大学软件与微电子学院2009年度课程,29,前向索引(1),直接对一篇篇文本扫描费时费力,能不能预先将文本处理一下进行匹配?答案是肯定的! 前向索引(Forward index) :将每篇文档表示成 DocID 及其文本内容组成的类向量模式。,北京大学软件与微电子学院2009年度课程,30,前向索引(
13、2),文档1:b d a b b c b a d c 文档2:a b c d a c d b d a b (注意:例子中为简化起见,用每个字母代表一个字符串索引单位),文档1,文档2,a,3,8,b,1,4,c,6,10,d,2,9,a,1,5,b,2,8,c,3,6,d,4,7,5,7,10,11,9,北京大学软件与微电子学院2009年度课程,31,前向索引(3),仍然是依次扫描每个文档,但是对于一个字符串的多次出现不需要一一扫描,而且对同一文档内的字符串查找可以采用二分查找的方式,加快匹配过程。也就是说通过预处理的方式加快对每篇文档的匹配速度。,北京大学软件与微电子学院2009年度课程,3
14、2,倒排索引(1),使用前向索引,仍然需要一篇篇扫描每个文档,如果文档数目较多,那么就非常费时费力。 能不能有一种方法能够直接从查询词定位到文档?答案是当然有了,这就是倒排索引(inverted index)。,北京大学软件与微电子学院2009年度课程,33,倒排索引(2),文档1:b d a b b c b a d c 文档2:a b c d a c d b d a b,文档ID号,偏移位置,dictionary,Posting list,北京大学软件与微电子学院2009年度课程,34,倒排索引(3),一本书中倒排索引的例子,北京大学软件与微电子学院2009年度课程,35,倒排索引(4),对
15、于单个查询词,搜索就是词典查找的过程,不需要扫描所有文档,只需要访问这个词对应的posting list,速度相当快。,北京大学软件与微电子学院2009年度课程,36,建立倒排索引的大致过程,索引源,预处理,分词,排序,写临时索引文件,合并临时索引文件,索引压缩,写索引文件,北京大学软件与微电子学院2009年度课程,37,中文分词(Chinese Word Segmentation),对于中文,分词的作用实际上是要找出一个个的索引单位 例子:李明天天都准时上班 索引单位 字:李 明 天 天 都 准 时 上 班 索引量太大,查全率百分百,但是查准率低,比如查“明天” 这句话也会出来 词:李明 天
16、天 都 准时 上班 索引量大大降低,查准率较高,查全率不是百分百,而且还会受分词错误的影响,比如上面可能会切分成:李 明天 天都 准时 上班 字词混合方式,北京大学软件与微电子学院2009年度课程,38,英文词根还原(Stemming),进行词根还原:stop/stops/stopping/stoppedstop 好处:减少词典量;坏处:按词形查不到,词根还原还可能出现错误 不进行词根还原: Stoppedsto+ppe+d 好处:支持词形查询;坏处:增加词典量,北京大学软件与微电子学院2009年度课程,39,停用词消除,停用词(stop words)是指那些出现频率高但是无重要意义,通常不会
17、作为查询词出现的词,如“的”、“地”、“得”、“都”、“是”等等 消除:通常是通过查表的方式去除,去除的好处-大大较少索引量,坏处-有些平时的停用词在某些上下文可能有意义 保留:索引空间很大,北京大学软件与微电子学院2009年度课程,40,排序,排序就是扫描每篇文档产生的(文档号,单词号,出现位置)三元组按照单词号重新排序,单词号相同的项再按照文档号排序,单词号和文档号都相同的再按照出现位置排序。 排序的过程正好是实现“倒排”的过程 排序以后的结果写入临时索引文件。,北京大学软件与微电子学院2009年度课程,41,排序举例(1),文档1 b d a b b c b a d c 文档2 a b
18、c d a c d b d a b,北京大学软件与微电子学院2009年度课程,42,排序举例(2),对文档1分析产生的三元组如下 b d a b b c b a d c (文档号,单词号,位置) (1,b,1) (1,d,2) (1,a,3) (1,b,4) (1,b,5) (1,c,6) (1,b,7) (1,a,8) (1,d,9) (1,c,10),北京大学软件与微电子学院2009年度课程,43,排序举例(3),对文档2分析产生的三元组如下 a b c d a c d b d a b (文档号,单词号,位置) (2,a,1) (2,b,2) (2,c,3) (2,d,4) (2,a,5)
19、 (2,c,6) (2,d,7) (2,b,8) (2,d,9) (2,a,10) (2,b,11),北京大学软件与微电子学院2009年度课程,44,排序举例(4),(1,b,1) (1,d,2) (1,a,3) (1,b,4) (1,b,5) (1,c,6) (1,b,7) (1,a,8) (1,d,9) (1,c,10),(2,a,1) (2,b,2) (2,c,3) (2,d,4) (2,a,5) (2,c,6) (2,d,7) (2,b,8) (2,d,9) (2,a,10) (2,b,11),(1,a,3) (1,a,8) (2,a,1) (2,a,5) (2,a,10) (1,b,
20、1) (1,b,4) (1,b,5) (1,b,7) (2,b,2),(2,b,8) (2,b,11) (1,c,6) (1,c,10) (2,c,6) (1,d,2) (1,d,9) (2,d,4) (2,d,7) (2,d,9),北京大学软件与微电子学院2009年度课程,45,写入临时索引文件,(1,a,3) (1,a,8) (2,a,1) (2,a,5) (2,a,10) (1,b,1) (1,b,4) (1,b,5) (1,b,7) (2,b,2),(2,b,8) (2,b,11) (1,c,6) (1,c,10) (2,c,6) (1,d,2) (1,d,9) (2,d,4) (2,
21、d,7) (2,d,9),北京大学软件与微电子学院2009年度课程,46,合并多个临时索引文件,一批文档(例如:50MB)产生一个索引文件 多批之间通过合并产生一个大的临时文件 如果不合并,可以建立通过文档进行分割的分布式索引 也可以合并以后,按照词典进行分割,文档1,2,m,文档m+1,m+2,2m,词1,2,n,词n+1,n+2,2n,北京大学软件与微电子学院2009年度课程,47,索引压缩,理论上,(全文)索引的大小和原始文件相当,因为每个词的每次出现都必须在posting list中记录。 需不需要压缩? 要压缩:索引大小通常和原始文本大小相当,不压缩可能会耗费大量存储开销 不压缩:硬
22、盘很便宜,数据量不是特别大,而且不需要解压缩的消耗,北京大学软件与微电子学院2009年度课程,48,倒排索引的更新,情况一:出现了新的词,则需要修改词典结构,在词典中增加词条。 情况二:出现了新的文档,则在相应的词条下增加posting list。 情况三:某些文档不复存在,则在相应的位置进行标记,等积累到一定时期进行一次性操作。,北京大学软件与微电子学院2009年度课程,49,词典的组织,顺序排序数组:采用字典序,查找采用二分法。空间消耗小,查找较快,但是插入删除麻烦。 二叉搜索树、B树、Trie树等。 Hash表:通过Hash函数直接把词映射到地址,空间消耗和Hash函数设计有关。较快,插
23、入删除容易。,北京大学软件与微电子学院2009年度课程,50,布尔查询的处理,And 关系:A and B,取出A、B的posting list进行交叉合并。 Or 关系:A or B,取出A、B的posting list进行叠加。 Not 关系:A And not B,取出A、B的posting list进行减操作。,北京大学软件与微电子学院2009年度课程,51,短语查询的处理,比如查AB,取出A、B的posting list,然后进行交叉合并,并且合并时要满足位置相邻的关系。,北京大学软件与微电子学院2009年度课程,52,小结,字符串匹配 前向索引 倒排索引,北京大学软件与微电子学院2
24、009年度课程,53,主要内容,信息采集技术(Information gathering) 信息的组织和索引(Information organization&indexing) 相似度计算信息检索模型(IR models) 链接分析技术 查询分析技术 结果呈现技术 搜索引擎的评估技术(Evaluation),北京大学软件与微电子学院2009年度课程,54,相似度计算-信息检索模型,北京大学软件与微电子学院2009年度课程,55,提纲,模型定义及分类 布尔模型 向量空间模型 概率模型 统计语言建模IR模型,北京大学软件与微电子学院2009年度课程,56,信息检索模型,信息检索模型是指如何对查询
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第八 搜索引擎 技术
链接地址:https://www.31doc.com/p-5030582.html