搜索
第10章发现与搜索引擎技术学习任务WEB搜索引擎工作原理物联网搜索引擎服务发现技术Clicktoaddtitleinhere123本章主要涉及：10.1搜索引擎技术概述•搜索引擎（searchengine）是指根据一定的策略、运用特定的计算机程序搜集互联网上的信息，在对信息进行组织和处理后，并将处理后的信息显示给用户，是为用户提供检索服务的系统。10.1.1搜索引擎的发展•1990年，加拿大麦吉尔大学（UniversityofMcGill）计算机学院的师生想到了开发一个可以用文件名查找文件的系统，开发出Archie。•当时，万维网（WorldWideWeb）还没有出现，人们通过FTP来共享交流资源。•Archie能定期搜集并分析FTP服务器上的文件名信息，提供查找分别在各个FTP主机中的文件。用户必须输入精确的文件名进行搜索，Archie告诉用户哪个FTP服务器能下载该文件。10.1.1搜索引擎的发展•虽然Archie搜集的信息资源不是网页（HTML文件），但和搜索引擎的基本工作方式是一样的：自动搜集信息资源、建立索引、提供检索服务。•所以，Archie被公认为现代搜索引擎的鼻祖。•由于Archie深受欢迎，受其启发，1993年又开发了一个Gopher搜索工具。10.1.2搜索引擎分类（1）全文索引•全文搜索引擎是名副其实的搜索引擎，国外代表有Google，国内则有著名的百度搜索。•它们从互联网提取各个网站的信息，建立起数据库，并能检索与用户查询条件相匹配的记录，按一定的排列顺序返回结果10.1.2搜索引擎分类根据搜索结果来源的不同，全文搜索引擎可分为两类:•一类拥有自己的检索程序（Indexer），俗称“爬虫”（Spider）程序或“机器人”（Robot）程序，能自建网页数据库，搜索结果直接从自身的数据库中调用，上面提到的Google和百度就属于此类；•另一类则是租用其他搜索引擎的数据库，并按自定的格式排列搜索结果，如Lycos搜索引擎。10.1.2搜索引擎分类（2）目录索引•目录索引虽然有搜索功能，但严格意义上不能称为真正的搜索引擎，只是按目录分类的网站链接列表而已。•用户完全可以按照分类目录找到所需要的信息，不依靠关键词（Keywords）进行查询。•目录索引中最具代表性的有Yahoo、新浪分类目录搜索。10.1.2搜索引擎分类（3）元搜索引擎•元搜索引擎（METASearchEngine）接受用户查询请求后，同时在多个搜索引擎上搜索，并将结果返回给用户。•著名的元搜索引擎有InfoSpace、Dogpile、Vivisimo等。10.2WEB搜索引擎工作原理web搜索引擎的原理通常为：•首先是用爬虫（Spider）进行全网搜索，自动抓取网页；•然后将抓取的网页进行索引，同时也会记录与检索有关的属性，中文搜索引擎中还需要首先对中文进行分词；•最后，接受用户查询请求，检索索引文件并按照各种参数进行复杂的计算，产生结果并返回给用户。10.2.1Web搜索引擎的组成搜索引擎一般由搜索器、索引器、检索器和用户接口四个部分组成：①搜索器：•其功能是在互联网中漫游，发现和搜集信息；②索引器：•其功能是理解搜索器所搜索到的信息，从中抽取出索引项，用于表示文档以及生成文档库的索引表；10.2.1Web搜索引擎的组成③检索器：•其功能是根据用户的查询在索引库中快速检索文档，进行相关度评价，对将要输出的结果排序，并能按用户的查询需求合理反馈信息；④用户接口：•其作用是接纳用户查询、显示查询结果、提供个性化查询项。10.2.1Web搜索引擎的组成搜索引擎组成10.2.2Web搜索引擎的工作模式①利用网络爬虫获取网络资源。•网络爬虫访问资源的过程，是对互联网上信息遍历的过程。•在实际的爬虫程序中，为了保证信息收集的全面性，及时性，还有多个爬虫程序的分工和合作问题，往往有复杂的控制机制。10.2.2Web搜索引擎的工作模式基本搜索器流程图10.2.2Web搜索引擎的工作模式②利用索引器从搜索器获取的资源中抽取信息，并建立利于检索的索引表：•当用网络爬虫获取资源后后，需要对这些进行加工过滤，去掉网控制代码及无用信息，提取出有用的信息，并把信息用一定的模型表示，使查询结果更为准确。•其中信息的表示模型一般有布尔模型，向量模型，概率模型和神经网络模型等。10.2.2Web搜索引擎的工作模式•Web上的信息一般表现为网页，对每个网页，须生成一个摘要，此摘要将显示在查询结果的页面中，告诉查询用户各网页的内容概要。•模型化的信息将存放在临时数据库中，由于web数据的数据量极为庞大，为了提高检索效率，须按照一定规则建立索引。•不同搜索引擎在建立索引时会考虑不同的选项，如是否建立全文索引，是否过滤无用词汇，是否使用meta信息等。10.2.2Web搜索引擎的工作模式索引的建立包括：■分析过程，处理文档中可能的错误；■文档索引，完成分析的文档被编码进存储桶，有些搜索引擎还会使用并行索引；■排序，将存储桶按照一定的规则排序，■生产全文存储桶。最终形成的索引一般按照倒排文件的格式存放。10.2.2Web搜索引擎的工作模式③检索及用户交互：•用户查询（query）理解，即最大可能贴近的理解用户通过查询串想要表达的查询目的，并将用户查询转换化为后台检索使用的信息模型；•根据用户查询的检索模型，在索引库中检索出结果集；•结果排序：通过特定的排序算法，对检索结果集进行排序。10.2.2Web搜索引擎的工作模式•现在用的的排序因素一般有查询相关度，google发明的pagerank计术，baidu的竞价技术等。•由于web数据的海量性和用户初始查询的模糊性，检索结果集一般很大，而用户一边不会有足够的耐性逐个查看所有的结果，所以怎样设计结果集的排序算法，把用户感兴趣的结果排在前面就十分重要。10.2.2Web搜索引擎的工作模式Web搜索引擎的工作模式10.2.3搜索引擎的技术设计与算法•搜索引擎的评价指标有响应时间、查全率、查准率和用户满意度等。•其中响应时间是从用户提交查询请求到搜索引擎给出查询结果的时间间隔，响应时间必须在用户可以接受的范围之内。•查全率是指查询结果集信息的完备性。•查准率是指查询结果集中符合用户要求的数目与结果总数之比。10.2.3搜索引擎的技术设计与算法•用户满意度是一个难以量化的概念，除了搜索引擎本身的服务质量外，它还和用户群体，网络环境有关系。•在搜索引擎可以控制的范围内，其核心是搜索结果的排序，即前文提到的如何把最合适的结果排到前面。10.2.3搜索引擎的技术设计与算法总的来说，Web搜索引擎的3个重要问题是：■响应时间：一般来说合理的响应时间在秒这个数量级■关键词搜索：得到合理的匹配结果■搜索结果排序：如何对海量的结果数据排序10.2.3搜索引擎的技术设计与算法•所以搜索引擎的体系结构得设计时需要考虑信息采集、索引技术和搜索服务三个模块的设计。1.信息采集Web搜索引擎的信息采集模块的主要功能是：•执行基于超文本传输协议（HypertextTransferProtocol,简称HTTP），从Web上收集页面信息，即Web机器人（爬虫）程序。10.2.3搜索引擎的技术设计与算法基于超文本传输协议的网络应答图10.2.3搜索引擎的技术设计与算法2.索引技术①网络爬虫程序的工作模式•网络爬虫程序根据HTTP协议，发送请求，并通过TCP连接接受服务器的应答。•由于Web搜索引擎需要抓取数以亿计的页面，所以建立快速分布式的网络爬虫程序才能满足搜索引擎对性能和服务的要求，其物理实现可能是一组终端。10.2.3搜索引擎的技术设计与算法爬虫程序物理设备架构图10.2.3搜索引擎的技术设计与算法②网络爬虫程序的基础结构•首先网络爬虫程序从URL链接库读取一个或多个URL作为初始输入并进行域名解析•然后根据域名解析结果（IP）访问Web服务器，建立TCP连接，发送请求，接受应答，储存接受数据，并分析提取链接信息（URL）放入URL连接库里。•爬虫程序递归执行该过程直到URL链接库为空。网络爬虫程序的基础结构如下图：10.2.3搜索引擎的技术设计与算法网络爬虫程序的基础结构10.2.3搜索引擎的技术设计与算法3.信息采集优化•信息采集优化需要考虑到：•网络连接优化策略、持久性连接和多进程并发设计等方面的问题。•同时由于网络爬虫程序会频繁调用域名系统，域名系统缓存可提高爬虫程序性能需要使用Web缓存技术.10.2.3搜索引擎的技术设计与算法相关域名系统的缓存策略：•■LRU（LeastRecentlyUsed）算法：将最近最少使用的内容替换出Cache缓存；•■LFU（LeaseFrequentlyUsed）算法：将访问次数最少的内容替换出Cache缓存；•■FIFO（First-In,First-Out）算法：在Cache缓存中执行数据的先进先出流程方法。10.2.3搜索引擎的技术设计与算法4.网页抓取算法①深度优先算法•在Web收集页面信息时，使用一个或一组预定义URL地址开始，然后根据页面内容中的超链接深度抓取页面，直到搜索结束（没有新的URL）。②广度优先算法•在Web收集页面信息时，使用一个或一组预定义URL地址开始，然后根据页面内容中的超链接广度抓取页面，抓取下一层的URL直到这一层的URL完全被抓取，直到搜索结束时返回。10.2.3搜索引擎的技术设计与算法③基于内容算法•根据关键字、主题文档的相似度和链接文本（Linkedtexts）估计链接值，并确定相应搜索策略的算法。•链接文本是包含对URL链接解释说明和内容摘要的文字信息。④基于HITS的算法•主要思想：在抓取Web页面时，采用Authority/Hub抓取策略。•Authority表示该页面被其他页面所引用的次数（页面入度值，in-degreevalue）。Hub表示其他页面引用该页面的次数（页面出度值，out-degreevalue）。10.2.3搜索引擎的技术设计与算法⑤PageRank（Google的专利技术）•Google的PageRank根据网站的外部链接和内部链接的数量和质量来衡量网站的价值。•PageRank背后的概念是，每个到页面的链接都是对该页面的一次投票，被链接的越多，就意味着被其他网站投票越多。10.2.3搜索引擎的技术设计与算法•这个就是所谓的“链接流行度”——衡量多少人愿意将他们的网站和你的网站挂钩。•PageRank这个概念引自学术中一篇论文的被引述的频度—即被别人引述的次数越多，一般判断这篇论文的权威性就越高。10.2.3搜索引擎的技术设计与算法•Google有一套自动化方法来计算这些投票。•Google的PageRank分值从0到10；PageRank为10表示最佳，但非常少见，类似里氏震级（Richterscale），PageRank级别也不是线性的，而是按照一种指数刻度。•这是一种奇特的数学术语，意思是PageRank4不是比PageRank3好一级—而可能会好6到7倍。因此，一个PageRank5的网页和PageRank8的网页之间的差距会比你可能认为的要大的多10.2.3搜索引擎的技术设计与算法PageRank的定义：•假设有T1…Tn个页面指向页面A（即引用）。•参数d是一个阻尼因子，其取值区间属于(0,1)，我们通常取值为0.85。•C(A)定义为指向页面A的其他页面的连接数，•页面A的PageRank或PR(A)值可以通过下面的公式得到：10.2.3搜索引擎的技术设计与算法5.索引技术①索引建立：预处理•当Web搜索引擎获得数据信息以后，首先需要对数据进行预处理，如将句子切分成有意义的词汇。由于中文的特殊性在切分句子时会产生二义性，如何合理的切分词汇是一个技术难题。•中文分词完全不同于英文分词，英文行文中，单词间以空格分隔；而中文只有字/句/段有明显分隔符，唯独词没有形式上的分隔符存在。10.2.3搜索引擎的技术设计与算法②索引建立：倒排文件模型③倒排文件（invertedfile），是指一个词汇集合W和一个文档集合D之间对应关系的数据结