搜索引擎关键技术

搜索引擎关键技术陈超2014年11月9日目录1、hadoop简介2、搜索引擎简介3、搜索引擎关键技术搜索引擎爬虫搜索引擎索引搜索引擎检索排序4、学习资源5、动动手认识搜索，从Google开始Google云存储与云计算架构服务器集群Google文件系统（GFS）PercolatorPregelMegaStore应用层搜索广告地图gmailGoogle+……..MapReduceBigTableChubbyGoogle三驾马车Hadoop简介hadoop之父-DougCuttinglucene搜索插件库分布式处理软件框架GoogleGFSGoogleMapReduce2000nutch可爬可搜2005为解决存储和计算问题HDFSMapReduce两个核心Hadoop谁在用？facebook、淘宝、360、京东……Hadoop开源架构与Google系统对应关系图HadoopHDFS（Google文件系统（GFS））Hbase（BigTable）MapReduce应用层NutchLucenepig服务器集群HiveZookeeper（Chubby）……目录1、hadoop简介2、搜索引擎简介3、搜索引擎关键技术搜索引擎爬虫搜索引擎索引搜索引擎检索排序4、学习资源5、动动手•全国科学技术名词审定委员会——“万维网环境中的信息检索系统，包括目录服务和关键字检索两种服务方式”。•百度百科——“搜索引擎指根据一定的策略、运用特定的计算机程序从互联网上搜集信息，在对信息进行组织和处理后，为用户提供检索服务，将用户检索相关的信息展示给用户的系统”。•维基百科——“搜索引擎指自动从因特网搜集信息，经过一定整理以后，提供给用户进行查询的系统。”•综上可见，搜索引擎是一种从互联网上采集数据，并将其进行存储、加工和重新组织后，向用户提供查询和结果展示的信息检索系统。什么是搜索引擎搜索引擎分类全文搜索引擎垂直搜索引擎元搜索引擎门户搜索引擎目录索引•早期：分类目录（人工整理）代表：Yahoo、hao123•第一代：文本检索（采用经典信息检索模型）代表：AltaVista、Excite•第二代：链接分析（利用网页间的链接关系）代表：Google、Baidu等等•第三代：用户为中心（以理解用户为核心）代表：目前大部分搜索引擎搜索引擎发展历史•更全——索引网页数量。•更快——贯穿于搜索引擎的大多数技术方向。•更准——内容排序技术，链接分析技术，用户行为研究。“更全”与“更快”可以使其不落后于同类产品。“更准”则构建其核心竞争能力。搜索引擎3个目标搜索引擎整体架构网络爬虫网页去重反作弊倒排索引链接关系云存储与云计算平台网页排序Cache系统查询分析内容相似性链接分析目录1、hadoop简介2、搜索引擎简介3、搜索引擎关键技术搜索引擎爬虫爬虫基础爬虫关键技术搜索引擎索引搜索引擎检索排序4、学习资源5、动动手•爬虫将海量网页数据传送到本地并形成网页的镜像备份，是搜索引擎系统关键的、基础的构件。什么是爬虫抽取URL8已抓取URL队列待抓取URL队列种子URL971读取URL23互联网下载网页库网页下载网页DNS解析654•批量型爬虫（BatchCrawler）有较明确的抓取范围和目标（抓取一定量的网页、抓取消耗时间等），达到目标则停止抓取。•增量型爬虫（IncrementalCrawler）持续不断抓取，并能对抓取的网页做到周期性更新。通用商业搜索引擎爬虫基本属于此类。•垂直型爬虫（FocusedCrawler）只抓取特定主题内容或特定行业的网页，难点：人工之别网页内容是否属于指定行业或者主题。垂直搜索网站一般需要此类爬虫。爬虫类型•优秀爬虫特性高性能•指爬虫抓取速度，以爬虫每秒钟下载的网页数量作为性能指标。可扩展性•很容易增加抓取服务器和爬虫数量。健壮性•能及时有效处理各种异常情况（如：网页编码不规范、宕机等）友好性•（1）保护网站的部分私密性——爬虫禁抓协议、网页禁抓标记•（2）减少被抓取网站的网络负载——在不影响爬虫性能的情况下，减少对单一站点短期内的高频访问•评价标准网页抓取覆盖率、抓取网页时新性、抓取网页重要性优秀爬虫特性及爬虫质量评价标准目录1、hadoop简介2、搜索引擎简介3、搜索引擎关键技术搜索引擎爬虫爬虫基础爬虫关键技术搜索引擎索引搜索引擎检索排序4、学习资源5、动动手•爬虫系统有4个至关重要的组成部分，它们基本决定了爬虫系统的质量和性能。抓取策略网页更新策略（增加下载网页的时效性）暗网抓取（增加网页覆盖率）分布式爬虫（决定爬虫性能）爬虫系统关键技术•抓取策略主要目的：决定待抓取URL队列的排序。不同的抓取策略，就是利用不同的方法来确定待抓取URL队列中的URL优先顺序。•宽度优先遍历策略（BreathFirst）——非常简单直观且历史悠久的遍历方法。基本思想：将新下载网页直接追加到待抓取URL队列末尾。（1）抓取策略网页1网页4网页3网页2网页9网页8网页7网页6网页5123456待抓取URL队列（2）网页更新策略历史参考策略原理：过去频繁更新的网页，将来也会频繁更新。方法：利用泊松过程对网页变化建模，预测何时内容会发生变化。用户体验策略原理：以用户体验为中心，在不影响用户体验的前提下，利用网页内容变化所带来的搜索质量变化（结果排名）确定更新时间。方法：保存网页多个历史版本，根据过去每次内容变化对搜索质量的影响，得出一个平均值，以此作为判断的依据。聚类抽样策略（效果好）原理：不依赖历史信息。根据网页一些属性预测其更新周期，具有相似属性的网页，更新周期也类似。归类后，同一类别网页具有相同更新频率。方法：将对某个类别种的采样网页的更新周日作为该类别的其他网页更新周期。网页更新策略动态性随着新的页面的出现，本地页面内容要被更改或者删除一致性对已经抓取的网页，爬虫要负责保持其与互联网页面内容的同步。WhyHow•暗网——目前搜索引擎爬虫按照常规方式很难抓取到的互联网页面。如：以数据库方式存储内容的网页。（3）暗网抓取（DeepWebCrawling）暗网爬虫目的：将暗网数据从数据库中挖掘出来，并加入到搜索引擎的索引，增加信息覆盖程度。两种策略：（1）Google采用“深度搜索”技术，进行主动抓取，通过查询模板尽可能得到多的记录。（2）百度—“阿拉丁计划”，一个开放的平台，与网站合作，由网站直接提交数据的形式。如：搜索“火车票”得到（4）分布式爬虫分布式爬虫数据中心数据中心抓取服务器抓取服务器抓取服务器抓取服务器爬虫程序爬虫程序爬虫程序爬虫程序爬虫程序爬虫程序爬虫程序爬虫程序URL服务器互联网URL集合抓取服务器抓取服务器抓取服务器互联网URL集合抓取服务器抓取服务器抓取服务器HashURL集合URL集合URL集合主从式爬虫对等式爬虫（哈希取模）对等式爬虫（一致性爬虫）爬虫中的云计算技术网页存储与备份——分布式存储技术网页URL去重——数据管理技术服务器管理——云计算平台管理技术节点故障时的迁移服务——分布式资源管理技术目录1、hadoop简介2、搜索引擎简介3、搜索引擎关键技术搜索引擎爬虫搜索引擎索引索引基础索引构建索引更新查询处理搜索引擎检索排序4、学习资源5、动动手中文分词•分词技术，是自然语言处理技术的关键和基础技术之一。常见的分词技术有：最大匹配法：正向最大匹配法、逆向最大匹配法、双向最大匹配法等。最大概率法分词：一个待切分的汉字串可能有多种切分结果，将概率最大的切分作为其切分的结果。•在搜索引擎中，分词技术也是一个必备的技术。出现在两个阶段：构建索引阶段：对原始文本进行预处理用户查询阶段：对用户输入的查询语句进行分词处理。•例句：长春市长春节致辞词典：长春、长春市、市长、春节、致辞正向：长春市/长春/节/致辞逆向：长春/市长/春节/致辞倒排索引实例内部公开InternalUseOnly▲单词ID单词文档频率倒排列表（DocID）1谷歌5(1;1;1),(2;1;1),(3;2;1;6),(4;1;1),(5;1;1)2地图5(1;1;2),(2;1;2),(3;1;2),(4;1;2),(5;1;2)3之父4(1;1;3),(2;1;3),(4;1;3),(5;1;3)4跳槽2(1;1;4),(4;1;4)5Facebook5(1;1;5),(2;1;5),(3;1;8),(4;1;5),(5;1;8)6加盟3(2;1;4),(3;1;7),(5;1;5)7创始人1(3;1;3)8拉斯2(3;1;4),(5;1;4)9离开1(3;1;5)10与1(4;1;6)11Wave1(4;1;7)12项目1(4;1;8)13取消1(4;1;9)14有关1(4;1;10)15社交1(5;1;6)16网站1(5;1;7)内部公开InternalUseOnly▲文档编号文档内容1谷歌地图之父跳槽Facebook2谷歌地图之父加盟Facebook3谷歌地图创始人拉斯离开谷歌加盟Facebook4谷歌地图之父跳槽Facebook与Wave项目取消有关5谷歌地图之父拉斯加盟社交网站Facebook倒排索引——示意图内部公开InternalUseOnly▲磁盘倒排文件倒排列表……………………内存词典单词1单词2单词3单词5单词4•词典用来维护文档集合中出现过的所有的单词，并通过倒排列表记载某个单词在文档中出现的频率、位置等信息。在支持搜索时，根据用户的查询词，在词典里查询，就能够获得相应的倒排列表，并以此作为后续排序的基础。单词词典•倒排列表用来记录有哪些文档包含了某个单词，一般在文档集合里会有很多文档包含某个单词，每个文档会记录文档编号（DocID），单词在这个文档中出现的次数（TF）及单词在文档中哪些位置出现过等信息，这样与一个文档相关的信息被称为倒排索引项（Posting），包含这个单词的一系列倒排索引项形成列表结构，这就是某个单词对应的倒排列表。倒排列表单词DocID,TF,pos1,pos2,…………DocID,TF,pos1,pos2,…倒排索引项倒排索引项倒排索引项倒排列表词典项单词187196199单词18793编号差值为了更好地对数据进行压缩在实际的搜索引擎系统中，并不存储倒排索引项中的实际文档编号，而是代之以文档编号差值（D-Gap）目录1、hadoop简介2、搜索引擎简介3、搜索引擎关键技术搜索引擎爬虫搜索引擎索引索引基础索引构建索引更新查询处理搜索引擎检索排序4、学习资源5、动动手•第一遍文档扫描时，搜索引擎系统完成一些全局信息的统计，比如文档的数量M，每个文档的单词数量N，不同单词的数量P，每个单词的文档频率DF等等，进而估算索引大致需要多少内存。根据估算值，预先申请一块连续的内存来存储倒排索引。•第二遍文档扫描的主要工作就是填补每个单词的倒排列表，即对于每个单词，获得其所在文档的ID以及其在该文档出现的频率TF，如此不断填充第一遍扫描时所分配的内存空间。经过两遍文档扫描后，可将词典及倒排列表信息由内存写入到磁盘。•两遍文档倒排法的索引构建过程完全在内存中进行，要求内存一定要足够大，要能够存储所有文档的倒排索引。（1）两遍文档遍历法•排序倒排法（Sort-basedInversion）在内存中始终分配一个固定的空间，用于存放词典信息和索引中间结果，当分配的内存被消耗光的时候，把中间结果写入磁盘，同时清空中间结果占据的空间，为下一轮存放索引中间结果做存储区准备，它可以对任意规模的文档集合建立索引。（2）排序法文档ID赋值→单词ID赋值→更新词典→统计词频→构建三元组→三元组排序→写中间结果文件→合并中间结果文件。•归并倒排法（Merge-basedInversion）对排序法的改进，即当内存定额被耗光时，将所有内存内容，包括词典等也一并写入磁盘，此前的内存被清空，如此后续在建立