搜索
第12章搜索引擎内容提要提供“普适性的数据分析与服务”的搜索引擎才能诠释出物联网“更深入的智能化”的内涵。本章将介绍搜索引擎的基本概念，体系结构和相关技术。•第11章介绍了海量信息存储技术和数据中心•物联网对海量数据存储的需求•三种网络存储体系结构•数据中心的基本概念以及典型的数据中心•如何降低数据中心的成本•本章重点介绍搜索引擎的基本概念，包括发展历程，体系结构（信息采集，索引技术，搜索服务），并针对一个类Google Web搜索引擎进行简要分析。内容回顾12.1 搜索引擎简介12.2 搜索引擎体系结构12.3 物联网搜索引擎搜索引擎有哪些？有哪三大模块组成？本章内容12.1搜索引擎简介Web搜索引擎一个能够在合理响应时间内，根据用户的查询关键词，返回一个包含相关信息的结果列表（hits list）服务的综合体。传统的Web搜索引擎是基于查询关键词的，对于相同的关键词，会得到相同的查询结果。常见Web搜索引擎搜索引擎的发展•搜索引擎的起源可追溯到1992年，由NCSA维护的“What’s NEW!”页面。•第一个原始搜索引擎W3Catalog（1993.9）•第一个Web机器人程序“World Wide Web Wanderer”（1993.6 MIT）•里程碑：WebCrawler（1994），Lycos（1994）商用•Google的建立：斯坦福博士生Larry Page 和Sergey Brin创立了Google•网络爬虫模块：主要功能是通过对Web页面的解析，根据Web页面之间的连接关系抓取这些页面，并储存页面信息交给索引模块处理。•索引模块：主要完成对于抓取的数据进行预处理建立关键字索引以便搜索模块输出。•搜索模块：对于用户的关键词，根据数据库的索引知识给出合理的搜索结果。Web搜索引擎的结构Web搜索引擎的工作模式搜集Web页面处理搜索结果接受搜索服务12.1 搜索引擎简介12.2 搜索引擎体系结构12.3 物联网搜索引擎搜索引擎具有怎样的体系结构和相关技术？本章内容Web搜索引擎的3个重要问题•响应时间：一般来说合理的响应时间在秒这个数量级•关键词搜索：得到合理的匹配结果•搜索结果排序：如何对海量的结果数据排序搜索引擎的体系结构信息采集索引技术搜索服务体系结构：信息采集搜索引擎体系结构信息采集索引技术搜索服务Web搜索引擎的信息采集模块主要功能：Web上收集页面信息，即Web机器人（爬虫）程序基于超文本传输协议（Hypertext Transfer Protocol, 简称HTTP）体系结构：信息采集搜索引擎体系结构信息采集索引技术搜索服务典型的基于超文本传输协议的网络应答网络爬虫程序的工作模式搜索引擎体系结构信息采集索引技术搜索服务网络爬虫程序根据HTTP协议，发送请求，并通过TCP连接接受服务器的应答。由于Web搜索引擎需要抓取数以亿计的页面，所以建立快速分布式的网络爬虫程序才能满足搜索引擎对性能和服务的要求，其物理实现可能是一组终端。网络爬虫程序的工作模式搜索引擎体系结构信息采集索引技术搜索服务爬虫程序物理设备架构图网络爬虫程序的基础结构搜索引擎体系结构信息采集索引技术搜索服务网络爬虫程序的基础结构搜索引擎体系结构信息采集索引技术搜索服务•首先网络爬虫程序从URL链接库读取一个或多个URL作为初始输入并进行域名解析•然后根据域名解析结果（IP）访问Web服务器，建立TCP连接，发送请求，接受应答，储存接受数据，并分析提取链接信息（URL）放入URL连接库里。•爬虫程序递归执行该过程直到URL链接库为空。信息采集优化搜索引擎体系结构信息采集索引技术搜索服务网络连接优化策略•持久性连接•多进程并发设计域名系统的缓存策略：由于网络爬虫程序会频繁调用域名系统，域名系统缓存可提高爬虫程序性能。•LRU（Least Recently Used）算法•LFU（Lease Frequently Used）算法•FIFO（First‐In, First‐Out）算法网页抓取算法搜索引擎体系结构信息采集索引技术搜索服务深度优先算法在Web收集页面信息时，使用一个或一组预定义URL地址开始，然后根据页面内容中的超链接深度抓取页面，直到搜索结束（没有新的URL）。广度优先算法在Web收集页面信息时，使用一个或一组预定义URL地址开始，然后根据页面内容中的超链接广度抓取页面，抓取下一层的URL直到这一层的URL完全被抓取，直到搜索结束时返回。网页抓取算法（续）搜索引擎体系结构信息采集索引技术搜索服务基于内容算法根据关键字、主题文档的相似度和链接文本（Linked texts）估计链接值，并确定相应搜索策略的算法。链接文本是包含对URL链接解释说明和内容摘要的文字信息。基于HITS的算法主要思想：在抓取Web页面时，采用Authority/Hub抓取策略。Authority表示该页面被其他页面所引用的次数（页面入度值，in‐degree value）。Hub表示其他页面引用该页面的次数（页面出度值，out‐degree value）。网页抓取算法（续2）搜索引擎体系结构信息采集索引技术搜索服务PageRank（Google的传奇技术）定义PageRank：我们假设有T1…Tn个页面指向页面A（即引用）。参数d是一个阻尼因子，其取值区间属于(0,1)，我们通常取值为0.85。C(A)定义为指向页面A的其他页面的连接数，页面A的PageRank或PR(A)值可以通过下面的公式得到：注意：PageRank值是Web页面的概率分布表示，所以所有Web页面的PageRank值的和是1。11()()()(1)(...)()()nnPRTPRTPRAddCTCT体系结构：索引技术搜索引擎体系结构信息采集索引技术搜索服务•Web爬虫抓取回来的页面信息，需要放入索引数据库里。•索引建立的好坏对于搜索引擎有很大的影响，优秀的索引能够显著的提高搜索引擎系统运行的效率及检索结果的品质。•文本分析技术是建立数据索引信息的支撑技术。索引建立：预处理搜索引擎体系结构信息采集索引技术搜索服务当Web搜索引擎获得数据信息以后，首先需要对数据进行预处理，如将句子切分成有意义的词汇。由于中文的特殊性在切分句子时会产生二义性，如何合理的切分词汇是一个技术难题。中文分词完全不同于英文分词，英文行文中，单词间以空格分隔；而中文只有字/句/段有明显分隔符，唯独词没有形式上的分隔符存在。索引建立：倒排文件模型搜索引擎体系结构信息采集索引技术搜索服务倒排文件（inverted file），是指一个词汇集合W和一个文档集合D之间对应关系的数据结构。建立倒排文件索引是建立索引数据库的核心工作。索引建立：倒排文件模型搜索引擎体系结构信息采集索引技术搜索服务索引模块架构体系结构：搜索服务搜索引擎体系结构信息采集索引技术搜索服务•搜索服务是Web搜索引擎工作流程的最后一步，根据用户提交的查询关键字展开搜索，将匹配结果返回给用户。•搜索服务的好坏直接影响Web搜索引擎的用户满意程度。搜索服务：结果显示搜索引擎体系结构信息采集索引技术搜索服务•接受用户的输入，提交用户搜索请求。•根据搜索结果列表合理的展示给用户。•在保护隐私的前提下，记录用户使用行为的详细信息，以便提高下次服务的满意度。搜索服务：网页快照搜索引擎体系结构信息采集索引技术搜索服务•Web上的数据每时每刻都在变化着，所以随时存在着检索到的页面信息已经不存在的可能。•Web搜索引擎为了提高服务质量，需要对搜索到的页面信息进行快照，以便在原来页面信息失效的情况下，保证用户能够通过快照功能查看页面。类Google Web搜索引擎的实例分析*类Google搜索引擎的架构•URL服务器•Web页面抓取器•存储服务器•URL解释器•排序器•Page Rank •搜索器类Google Web搜索引擎的实例分析*Google数据仓库的结构类Google Web搜索引擎的实例分析*查询评估流程1.解析查询（Query）2.把单词转化成wordID3.从每个单词的短桶文档列表开始查找4.扫描文档列表直到有一个文档匹配了所有的搜索词语5.计算这个文档对应的查询的评分6.如果到达短桶的文档列表结尾，从每个单词的全桶(full barrel)文档列表开始查找，跳到第4 步7.如果没有到达任何文档列表的结尾，跳到第4步8.根据评分对匹配的文档排序，然后返回评分最高的k个12.1 搜索引擎简介12.2 搜索引擎体系结构12.3 物联网搜索引擎物联网背景下的搜索引擎应具有哪些新特点？本章内容12.3物联网搜索引擎物联网时代搜索引擎的新思考•从智能物体角度思考搜索引擎与物体之间的关系，主动识别物体并提取有用信息。•从用户角度上的多模态信息利用，使查询结果更精确，更智能，更定制化。本章小结内容回顾本章介绍了搜索引擎的发展历程，重点讨论了搜索引擎的体系结构（信息采集，索引技术，搜索服务），并提出了物联网背景下搜索引擎的新思考。重点掌握•掌握Web搜索引擎的三大模块（网络爬虫模块，索引模块，搜索模块）的作用。•了解搜索引擎需要解决的三个问题（响应时间，关键词搜索，搜索结果排序）。本章小结重点掌握（续）•掌握搜索引擎信息采集的基本流程以及网络爬虫程序的基本结构和工作流程。•理解优化网络爬虫程序的途径。掌握常见的网页抓取算法的特点和流程。•了解索引技术预处理的困难，了解倒排文件模型。•举例说明Google Web搜索引擎的架构。Thank you!