北京大学：《数据结构与算法》课程教学资源（实习讲义）搜索引擎技术介绍

■概述 搜索引擎技术介绍 ■信息检索模型 ■信息检索系统的评价标准 ■Web搜索引擎的难点 Wveb搜索引擎体系结构 m Web Crawler 王栋 ■预处理 ■索引和查找 ■检索结果排序 唾 概述 ■搜索引擎属于信息检索( Information retrieva,IR)范畴 ■信息检索的基本任务 口如何找到并定位特定资源? 文件系统 ■如果目标资源 就称为Web搜索引擎 Frea as a hp 信息检索模型(1/3) 信息检索模型(1/2) ■信息检索模型( IR model)可形式化地表示为一个四元 漫检畬息鰲饞虧厚潆。文杓之间的相 D, Q, F, R(q, d) 向量空间模型基于共有词汇假设( shared bag of 词组成的 ■常见的信息检索模型有 口布尔模型( Boolean Model) R(d, q)=cos(d, q)=d- q /ld xlql 口 决定N维向量每一维的权重,即N维向量中每个 率模型( Probabilistic Model 词的权重呢?? 推理网络模型( Inference Network model)

1 搜索引擎技术介绍 王栋 Topics „ 概述 „ 信息检索模型 „ 信息检索系统的评价标准 „ Web搜索引擎的难点 „ Web搜索引擎体系结构 „ Web Crawler „ 预处理 „ 索引和查找 „ 检索结果排序 概述 „ 搜索引擎属于信息检索(Information Retrieval，IR)范畴 „ 信息检索的基本任务 … 如何找到并定位特定资源？ … 这些资源可能来自 „ Web „ 数据库 „ 文件系统 „ …. „ 如果目标资源是Web，就称为Web搜索引擎 … Google，百度，Yahoo！ 信息检索模型(1/3) „ 信息检索模型（IR model）可形式化地表示为一个四元 组： < D, Q, F, R(q, d) > „ 其中D是一个文档集合，Q是一个查询集合，F是一个对文 档和查询建模的框架，R(q, d) 是一个排序函数，它给查 询q和文档 d之间的相关度赋予一个排序值，即相关度评 价。 „ 常见的信息检索模型有： … 布尔模型（Boolean Model） … 向量空间模型（Vector Space Model） … 概率模型（Probabilistic Model） … 推理网络模型（Inference Network Model） 信息检索模型(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) 原理 髋優殺鷂碼x獰旻醫棼躊徨霰大迁勰睥薛醫醫∵·出 ■根据TF+DF公式,文档集中包含某一词条 薇案x键高额键向mDFe可以鞍为:m 的文档越多,说明它区分文档类别属性的 能力越低,其权值越小 率多少是中:出表示单词的文规 Document Frequency? 语言中的统计特性,所以少量新文档加入对它影响很小,可 ■另一方面,某一文档中某一词条出现的频 d中的出现频率,那么文档d中关键词t的权重可 率越高,说明它区分文档内容属性的能力 ght(t, d)=TF(L d)*IDF(t) 越强,其权值越大 來说是一个全屙权值,而TF(d则是单词在文档d中的 唾 信息检索系统的评价标准 Wveb搜索引擎的难点 要考虑的问题,比如算 系统,重要的效率指标通常 ■数据 口数据规模巨大且增长快 比如,Web上的网页量级是b画on,中国的wb页面就有几十亿! 系统的查询吞吐量( Request throughput) Web的异构性 ■“效果关注用户需求的满足程度,对于信息检索系统通常 口多种多样 口盒券 为检索结果集中的相关文档占整个文档全集中的相关 口非结构化和半结构化数据 口彙薷窑爻檎棼琵中与用户查通相关的文档古整个检索结 比如,文本数据和XML数据 ■用户 口素纔是背霜奖畜1另相关是确在意难秦举签空率 如何表达查询需求 如何解释查询结果? Wveb搜索引擎体系结构

2 信息检索模型(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*IDF公式，文档集中包含某一词条 的文档越多，说明它区分文档类别属性的 能力越低，其权值越小； „ 另一方面，某一文档中某一词条出现的频 率越高，说明它区分文档内容属性的能力 越强，其权值越大。 信息检索系统的评价标准 „ “效率”几乎是任何计算机系统都需要考虑的问题，比如算 法的时空效率，对于信息检索系统，重要的效率指标通常 有： … 系统的查询响应时间（Response time） … 系统的查询吞吐量（Request throughput）。 „ “效果”关注用户需求的满足程度，对于信息检索系统通常 有两个指标：查全率（Recall）和查准率（Precision）。 … 查全率定义为检索结果集中的相关文档占整个文档全集中的相关 文档的百分比 … 查准率定义为检索结果集中与用户查询相关的文档占整个检索结 果中所有文档的百分比。 … 查全率是衡量检索系统取回相关信息的能力，查准率是衡量检索 系统拒绝非相关信息的能力。实验证明，在信息检索中，查全率 和查准率之间存在着相反的相互依赖关系，即查准率和查全率往 往不能两全其美，通常查准率高时，查全率低；查全率高时，查 准率低。 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 Web搜索引擎体系结构 Query Engine Central Index indexer Webpages crawlers Query Ranked List of URLs

网络爬虫 veb是一个有向图 a Google's mission: Organize the world <href information and make it universally <href accessible and useful ■第一步要解决信息的获取问题 ■网络爬虫( Web crawler)是搜索引擎的 重要组成部分,它负责把网上的数据抓取 <href (craw)下来供搜索引擎使用。 网页为节点 网页中的 Hyper Link为有向边 唾 系统框图 High-performance Crawler need A high level view of a web crawler Scalable Parallel. distributed ■Fast o Bottleneck? Network utilization n Document D DoS. robotbxt D Traps, errors, crash recovery Read/write ■ Continuous 口 Batch or incrementa 大规模爬取器 图唾 大规模爬取器:性能和可靠性问题 ■避免让DNS查询成为瓶颈 ■同时并发抓取多个网页(例如一台机器200个并发) Http 口这是充分利用网络带宽的基础 normalizer 多进程、多线程 口用一个数据结构,显式将一个抓取过程的状态表达出来 MisPageKnown? 口检查结束标志 ■URL提取中的问题 口消除重复,减少冗余的抓取(不那么容易,同义URL问 口避免“ spider traps",陷入少量网站中 pool cf URLS

3 网络爬虫 „ Google's mission: Organize the world's information and make it universally accessible and useful. „ 第一步要解决信息的获取问题 „ 网络爬虫（ Web Crawler）是搜索引擎的 重要组成部分，它负责把网上的数据抓取 （Crawl）下来供搜索引擎使用。 Web是一个有向图 <href …> <href …> <href …> <href …> <href …> <href …> <href …> 网页为节点 网页中的HyperLink为有向边 系统框图 High-performance Crawler need… „ Scalable … Parallel , distributed „ Fast … Bottleneck? Network utilization „ Polite … DoS, robot.txt „ Robust … Traps, errors, crash recovery „ Continuous … Batch or incremental 大规模爬取器的一种结构图 大规模爬取器：性能和可靠性问题 „ 避免让DNS查询成为瓶颈 „ 同时并发抓取多个网页（例如一台机器200个并发） … 这是充分利用网络带宽的基础 „ 多进程、多线程 „ 利用异步sockets（Soumen的观点） … 用一个数据结构，显式将一个抓取过程的状态表达出来 … 检查结束标志 „ URL提取中的问题 … 消除重复，减少冗余的抓取（不那么容易，同义URL问 题） … 避免“spider traps”，陷入少量网站中

ssue:消除已经访问过的URL 检查某个URL是否已经被抓过了 口在将一个新的URL放到工作池之前 Diving in the crawlers 口要很快,不要在这里形成性能瓶颈(检查将要访问磁盘) Take TsE for ex 口符合条件(即未被访问过)的URLs放到 crawler的任务中 ■优化方法 陈志杰 口可以通过计算并对比(规格化后的)URL的MD5来实现 口利用访问的时空局部性- cache 口高效率的查找表数据结构 a Bloom filter 口空间效率很高,用于判断某元素是否属于某集合 唾 预处理 中文分词简介(1/3 ■对于抓下来的HTML文档,需要解析HTML 胬意忠柰在姗李曾鼙亂黩数钒分或曾暫知的菌达 ■扫描并提取词串 下面的中文断句,来自百度广告宣传片 知我 口 Stemming:提取词根 题我知练不知道 另外中文的具体含义 在具体的前后语言环境中去分析,比 去掉停用词( Stop Words) 口在慈善拍卖会上,世界冠军们夺冠时的「乒乓球拍尝完了」 口"的,“地”,等 口字符串匹配(正序、逆序、最少切分、最大切分等) 机构名、人名等 。王解(同法句法等方式处用) 奮窥趨过染日護毙墅漭翬里 第二种的算 中文分词简介(23) 中文分词简介(23) ■正向最大匹配法MM)从左向右匹配词典 n-gram方法 ■逆向最大匹配法(RMM)从右向左匹配词典 口把单字( unigram)或相邻的两个字( bigram)或更多 口例子 看作一个索引项 口例子:全文索引完成 口 unigram(1-gram):全,文,索,引,完,成 ■全切分 口 bigram(2gram):全文,文索,索引,引完,完成 口利用统计方法训练得到一个概率模型 口3gram:全文索,文索引,索引完,引完成 口根据词典生成各种可能的切分情况 ■简单,P3实习大家可以考虑 bigram分词。 模型计算各种切分的可能性,可能性最大的

4 Issue：消除已经访问过的URL „ 检查某个URL是否已经被抓过了 … 在将一个新的URL放到工作池之前 … 要很快，不要在这里形成性能瓶颈（检查将要访问磁盘） … 符合条件（即未被访问过）的URLs放到crawler的任务中 „ 优化方法 … 可以通过计算并对比（规格化后的）URL的MD5来实现 … 利用访问的时空局部性--Cache … 高效率的查找表数据结构 „ 用B-树管理 „ Bloom filter … 空间效率很高，用于判断某元素是否属于某集合 Diving in the crawlers Take TSE for ex. 陈志杰 预处理 „ 对于抓下来的HTML文档，需要解析HTML … Word，PDF….. „ 扫描并提取词串 „ 英文 … Stemming：提取词根 „ 中文 … Segmenting：分词 „ 去掉停用词（Stop Words） … “the”， “a”，etc … “的”， “地”，等 „ 词性标注 „ 命名实体识别 … 日期、数字、机构名、人名等。 中文分词简介(1/3) „ 因为中文本身存在着很大的歧义性，同样一句话，不同的断句，表达 的意思就不一样。这对于计算机去做机器分析，就带来了巨大的困 难。 „ 下面的中文断句，来自百度广告宣传片: … 我知道你不知道我知道你不知道我知道你不知道 我知道，你不知道。我知道，你不知道我知道，你不知道 我知道你，不知道我。知道你不知道我，知道你不知道 我，知道你不知道我知道。你，不知道我知道你不知道 „ 另外中文的具体含义，还必须放在具体的前后语言环境中去分析。比 如： … 在慈善拍卖会上，世界冠军们夺冠时的「乒乓球 拍卖 完 了」 „ 中文分词，在具体的算法实现上分为三种： … 字符串匹配(正序、逆序、最少切分、最大切分等) … 基于理解（词法，句法等方式处理） … 基于统计 „ 在中文搜索引擎中，目前基本上是这三种算法混合使用。第二种的算 法实现起来过于复杂，所以以第一种和第三种算法为主。 中文分词简介(2/3) „ 正向最大匹配法(MM)从左向右匹配词典 „ 逆向最大匹配法(RMM)从右向左匹配词典 … 例子 „ 输入:企业要真正具有用工的自主权 „ MM:企业/要/真正/具有/用工/的/自主/权 „ RMM:企业/要/真正/具有/用工/的/自/主权 „ 全切分 … 利用统计方法训练得到一个概率模型 „ 比如，P(人民|中国) = 0.6 … 根据词典生成各种可能的切分情况 „ 如何枚举？怎么保存结果？ … 利用概率模型计算各种切分的可能性，可能性最大的 就是最终结果 中文分词简介(2/3) „ n-gram方法 … 把单字（unigram）或相邻的两个字（bigram）或更多 看作一个索引项 … 例子：全文索引完成 … unigram（1-gram）：全，文，索，引，完，成 … bigram（2-gram）：全文,文索，索引，引完，完成 … 3-gram：全文索，文索引，索引完，引完成 „ 简单，P3实习大家可以考虑bigram分词

索引和查找 ■两种查找方式 口顺序查找 口基于索引的查找 ■显然,第一种方式适合对规模小,变化快 的数据集查找;第二种方式适合于大规模 的静态数据集。 ■现代的数据库系统在查找过程中结合了两 种方式 唾 常见的索引方式 倒排索引实现 ■后缀数组,倒排索引和 Signature files ■倒排索引( inverted index)组成 ■由于词表的规模不会很大,所以在查询时 口词表( Dictionary, lexic 词表通常是常驻内存的 如果文档集很大,那么词的出现位置列表 ( word positions)也可能很大。如果内存 D o(log n) lookups to find a list 不够大可放在外存中 ■把出现位置列表放在内存中可大大提高查 询速度 word positions 示例— scene索引结构 Block addressing =二分查找=> 种缩小出现位置列表的方法:把文档分 成若干个块,在出现位置列表中只记录词 出现在哪一块中,而不记录具体位置。再 ple applet aqua…fo 从这一个块中进行顺序查找。这种方式称 为 Block addressing fr docids for apple docids for applet ■例如 prx proxs for apple proxs for applet Block 3 This is a text I A text has many I words. Words are I made from letters

5 索引和查找 „ 两种查找方式 …顺序查找 …基于索引的查找 „ 显然，第一种方式适合对规模小，变化快 的数据集查找；第二种方式适合于大规模 的静态数据集。 „ 现代的数据库系统在查找过程中结合了两 种方式。 常见的索引方式 „ 后缀数组，倒排索引和Signature files „ 倒排索引(inverted index) 组成 … 词表（Dictionary，lexicon） „ Hash table … O(1) lookup … complex to expand „ B-tree … O(log n) lookups to find a list … easy to expand „ …. … Postings „ document ids „ word positions 倒排索引实现 „ 由于词表的规模不会很大，所以在查询时 词表通常是常驻内存的。 „ 如果文档集很大，那么词的出现位置列表 （word positions）也可能很大。如果内存 不够大可放在外存中。 „ 把出现位置列表放在内存中可大大提高查 询速度。 示例——lucene索引结构 apple foo bar … apple applet aqua … foo … .tii(in memory) .tis … docIds for apple docIds for applet … … prox’s for apple prox’s for applet … .frq .prx <=二分查找=> 顺序查找=> Block addressing „ 一种缩小出现位置列表的方法：把文档分 成若干个块，在出现位置列表中只记录词 出现在哪一块中，而不记录具体位置。再 从这一个块中进行顺序查找。这种方式称 为Block addressing。 „ 例如： Block 1 Block 2 Block 3 Block 4 This is a text. | A text has many | words. Words are | made from letters