网络智能搜索引擎概要课件.ppt

第10章 网络智能搜索引擎,主要内容10.1 网络智能搜索引擎概述10.2 网络智能搜索引擎的结构原理10.3 网络智能搜索机理10.4 网络智能搜索策略10.5 网络智能搜索引擎的关键技术10.6 网络智能搜索引擎实例分析,10.1 网络智能搜索引擎概述,(一) 搜索引擎发展简况搜索引擎:是指通过网络搜索软件或网站登陆等方式，以一定的策略在互联网上搜集和发现信息，并将Web上大量网站的页面收集到本地，经过加工处理和组织，从而能够对用户提出的各种查询做出响应，提供用户所需的信息。,1993年底，NASA，Repository-Based Software Engineering (RBSE) spider第一个索引Html文件正文的搜索引擎，第一个使用关键词串匹配的引擎；,1994年7月，Michael Mauldin，Lycos第一个现代意义上的搜索引擎；,1994年，David Filo和杨致远，Yahoo成功地使网络信息搜索的概念深入人心，揭开了搜索引擎大发展的序幕。,（二）搜索引擎的智能行为分析 1、影响搜索引擎性能的最关键因素：,（1）信息的采集。搜索过程应在一定条件下选择最优路径沿着具有相关主题的链接进行搜索，这要求搜索引擎能够识别相应的网站和网页信息资源，是一种智能性的体现。,（2）信息的加工处理与组织。当采用合适的算法和策略从网络信息资源中获取到原始超文本信息后，还需要从中抽取出有价值的信息内容进行索引存储，构建信息数据库。,（3）信息检索。信息检索查询为用户提供直接服务，它根据用户的信息需求，完成对数据库的查找过程，并以一定的方式向用户提供查询结果。信息检索是搜索引擎最终的价值体现，是影响搜索引擎性能的关键环节。,2、搜索引擎的智能性分析：,（1）检索技术的智能化, 机灵的网络蜘蛛,智能搜索引擎的设计网络蜘蛛能遍历整个因持网，自动完成在线信息的索引，还能通过启发式学习采取最有效的搜索策略，选择最佳时机获取从Internet上自动收集、整理过的信息。同时，它能够对网页内容的相关性及该网页所包含的链接质量等做出判断，质量较差或内容不大相关的网页将不被选取，从而保证信息来源的质量，提高检索效果。, 语义检索及自然语言理解技术,语义检索是一种建立在文献概念相关关系基础上的检索。通过抽取能够描述文献内容的概念（如用文中的关键词或与之相应的主题词）建立一种语义索引，而用户在系统的辅助下选用合适的词语表示自己的信息需求，然后在两者之间执行概念匹配，匹配在语义上相同、相近、相包含的词语，从而实现信息的深度检索,借助自然语言理解技术，智能搜索引擎能够实现基于知识（或概念）层面的检索，并且对知识有一定的理解与处理能力，能够实现分词技术、同义词技术、概念搜索、短语识别以及机器翻译技术等。因而智能搜索引擎具有信息服务的智能化、人性化特征，允许用户采用自然语言进行信息检索，并能为用户提供更方便、更确切的搜索服务。, 检索对象形式的多样性,智能搜索引擎具有跨平台工作和处理多种混合文档结构的能力，能处理HTML(HyperText Markup Language，超文本标志语言)、SGML(Standard for General Markup Language，通用标志语言标准)、XML(eXtended Marked Language，扩展标志语言)文档以及其他类型的文档，如Word、WPS等。另外，智能搜索引擎还支持多语言检索，允许用户用中文输入查询英文或其他语言的信息。, 人工/机编混合型目录,它呈两种形式：人工进行质量控制的机编目录和运用智能技术检索的手编目录。这种混合型目录能够弥补机编目录和手编目录的缺憾，提高了网页索引覆盖率。,（2）检索结果处理的智能化, 保存和利用用户的使用记录，分析检索结果的相关度,例如访问量排序和基于超链接的排序。搜索引擎记录其所搜索到的Web页面的被点击次数（即访问量），从而判断该Web页面被访问的频率。这是一种由公众集体确认网站重要性的方法，具有一定的客观性与公众性。而基于超链接的排序则是利用Web页面之间的引用关系，综合考虑Web页面被引用次数以及所引用页面的相关度来判断本页面的重要性。, 检索结果的转换过滤,根据一定条件对检索结果进行优化过滤的过程，如信息格式的支持与转换。采用信息过滤技术可减少重复信息和垃圾信息，应用聚类技术对检索结果进行联机聚类等，从而“精简”检索结果。, 检索结果的知识提取,搜索程序具有机械性及其对网络用户的透明性，而网络用户缺乏搜索程序所规定的概念和语词符号，这就使得用户的检索具有一定的模糊性，进而降低检索结果的满意度。因此，智能搜索引擎通过对用户需求进行分析研究，跟踪用户的兴趣爱好，建立用户模型库，利用用户知识对检索结果进行一定程度上的知识提取，完成检索结果的集成。,（3）检索服务的智能化,在检索服务方面，检索质量的提高依赖于对网络用户信息需求的分析与挖掘，最基本的在于确定提问词中隐含的“意义范围”，即词语在不同领域的含义。只有理解查询词的含义范围，理论上将检索范围缩小到一个适当的相关范围，检索才能精确。同时，试图理解用户的意图，并相应地将检索结果分类编排，便于用户的选择利用。智能搜索引擎的智能化包括：个性化服务、主动性、智能辅助、人机接口智能化。,10.2 网络智能搜索引擎的结构原理 10.2.1 智能搜索引擎总体框架模型及功能,智能搜索引擎模型采用扩展式的客户端/服务器结构，包括表示层、应用层和数据层三层应用服务（模型如图10-1所示）,（1）表示层,表示层主要的功能是给用户提供一个友好的人机界面，管理和实现用户和系统的交互，将用户提交的检索请求传递给应用层和数据层所在的服务器，同时负责接收服务器端的检索结果，并显示给用户。,（2）应用层,应用层是实现智能搜索的主要应用逻辑，由智能搜索模块与用户模型库两部分组成。其智能搜索模块能实现对用户搜索的“代理”，“理解”用户的提问，主动获取满足用户需求的信息并推荐给用户。用户模型库能与智能搜索模块进行交互，是其功能实现的依据和保障。, 智能搜索模块,智能搜索模块的结构如下图所示，由各种Agent及共享知识库、本体库、信息库构成。,用户Agent,用户Agent能对用户输入的检索提问进行解析、细化，形成初步检索式；能接收用户对检索结果的反馈；通过检测用户与系统交互过程中用户的检索行为，分析用户行为的意图，获取用户感兴趣的相关信息及其感兴趣的程度；将检索结果提交给用户。用户Agent拥有知识，了解用户的需求和爱好，能够辅助用户智能地完成某个任务（浏览或检索），并具有学习和适应能力。同时它受用户的控制，用户可以观察它的活动状态，可以临时性地暂停或恢复其活动，甚至将它永久性地撤销。,学习Agent,处理Agent,学习Agent负责对用户Agent收集的用户信息进行分析和处理，实现用户模型的建立及其动态维护。,处理Agent包括4个方面的功能，一是对检索提问进行预处理，在共享知识库中查找相关或相似信息，或借助本体知识对检索提问进行规范化处理；二是对搜索Agent在远端搜索到的信息进行处理并存入本地信息库；三是对搜索到的结果按用户需求进行分析、过滤，并将有用信息选择、推荐给用户；四是定期根据用户的偏好对本地信息库进行整理、分类。,检索Agent,搜索Agent,控制Agent,检索Agent负责执行本地信息库的检索，完成本地信息库的知识检索服务。,搜索Agent负责执行远程搜索，获取符合检索提问的相关信息，同时对用户感兴趣的站点进行监测，以便通知用户所监测站点的最新更新内容。,控制Agent的主要工作是对各个Agent的执行顺序和交互行为进行控制和协调。,本体库,本地信息库,本体库存储领域集、关键字集以及本体的相关知识等。,本地信息库主要存储搜索Agent从远端带回的并经过处理了的信息。对于检索提问，若在本地即能搜索到所需信息，则能大大提高搜索效率。, 用户模型库,用户模型库包括用户知识模型和领域知识模型。领域知识模型主要包含有关领域的知识，可以帮助实现处理Agent对用户检索提问的预处理；同时领域知识模型可以存储相关领域的成功搜索案例。用户知识模型中的信息则是有关系统用户的信息，如用户的知识背景、兴趣爱好等个性描述信息。搜索引擎通过和用户进行交互操作，对用户的信息进行收集、学习等方式，建立用户的用户知识模型和领域知识模型，并及时发现用户信息的变化以更新用户知识模型，适应用户需求的动态变化。,（3）数据层,数据层主要由信息搜集与处理模块构成（结构如图10-3所示）。该模块的工作原理是：通过网络爬虫或网络机器人、网站提交等方式收集网页建立原始网页数据库，然后利用领域知识库和兴趣库对原始网页数据库通过信息抽取与组织模块形成各个类型的网页索引数据库。其中信息抽取与组织模块主要负责分析、提取原始网页数据库中存储页面的相关信息，依据一定的相关度算法及数据挖掘与聚类技术，建立各个类型的网页索引数据库。数据层能够实现对Internet上的信息的“先”处理，即将数据“归类”，以简化搜索Agent的搜索过程，并利用兴趣库及领域知识库，结合用户的兴趣，以便实现主动推送服务及专题信息的搜索。,10.2.2 智能搜索引擎系统的工作流程,（1）用户提交检索请求：用户Agent接收用户提交的检索请求，对其进行细化，然后把初步处理后的结果交给学习Agent。,（2）用户模型库的建立或更新：若该用户是初次检索，则学习Agent通过分析、学习其检索行为建立用户模型库；若用户不是初次检索，则学习Agent根据学习到的内容对用户模型库进行更新。,（3）规范化检索提问：处理Agent接收到检索提问后，参照用户模型库中的类似成功检索案例，以形成全面有效的检索提问进行检索；若用户模型库中无类似成功检索案例，则依据本体库中知识对检索提问进行规范化处理，找出出现该关键字的各个领域及在该领域下的关键字的含义。然后处理Agent将处理后的检索提问返回到用户Agent，由用户根据自己需求选择或确认处理后的检索提问，并再次依序往下传递检索提问。当然，用户可以设定无需将处理结果返回，而由系统全权代理。,（4）检索信息：处理Agent先将检索提问传递给检索Agent，进行本地信息库的就近搜索，若找到相关信息则直接将结果返回处理Agent，比如需求相同的不同用户提出相同检索任务，则后来用户的检索提问可以“照搬”先前用户的检索结果，即在本地信息库进行搜索，从而提高检索效率。若检索Agent在本地信息库没有检索到相关信息，或者搜索到的信息的相关性低于指定阈值（阈值可由用户或系统设定），则处理Agent将检索提问传递给搜索Agent，搜索Agent到远端进行搜索。最后搜索Agent将检索结果返回到处理Agent。,（5）检索结果的处理：根据用户的个性化需求，处理Agent对返回的检索结果进行分析、过滤，并将结果推荐给用户。若检索结果来自远端搜索，则处理Agent还要将检索结果存入本地信息库。,（6）用户反馈信息的学习：应用层将检索结果提交给用户后，学习Agent对用户Agent收集的用户的相关反馈信息进行学习，以存储相关结果，如成功搜索案例，并依据用户的反馈信息进行自学习，完善自身功能，如调整由系统设定的相关性阈值等。,（7）相关信息的主动推荐：根据用户模型库记录的用户的相关信息，当用户完成一次检索后，按照用户设定的推送服务周期，智能搜索引擎能主动依据用户需求完成（1）至（6）步信息搜索过程，而其检索提问及检索提问的修改由系统自动进行，一旦检索到相关信息，则以一定方式推荐给用户。,10.3 网络智能搜索机理,智能搜索引擎进行搜索时要构设知识库和用户档案库。知识库是对信息综合、提取、概括与分析后产生的知识集合，它提供智能搜索引擎理解、处理用户提问的资源标识。用户档案库则用来存储用户注册的基本资料、用户访问记录、用户兴趣偏好、用户访问行为等用户信息。,智能搜索引擎内部共设有语义理解、指令组织、访问登记、兴趣识别、信息过滤、信息加工、页面定制七大功能模块。在具体的搜索过程中，语义理解模块依据知识库提供的资源标识，对用户提问进行分析、推理，然后由指令组织模块发出Http请求的搜索指令，同时由访问登记模块对用户提问、定题需求等进行用户角色与信息行为登记，将用户的访问记录、兴趣爱好等信息传递给用户档案库保存起来。一旦产生新的信息资源，智能搜索引擎便由兴趣识别模块激活，抽取用户的信息需求，进而由指令组织模块形成推荐推送服务的检索指令。在从网络信息库中搜索到相应的信息数据后，返回给智能搜索引擎的信息过滤和信息加工模块进行过滤、排序、组织、加工，然后经页面定制模块定制信息页面，将检索结果或推送信息提供给用户使用。,智能搜索引擎以用户需求为先导来进行信息搜集和信息加工，根据用户特定的需求以及在一段时期内的偏好为衡量标准来筛选信息；用户界面提供友好的自然语言查询，当用户的查询请求不明确时，系统会利用知识库中的推理机制推断用户的潜在需求，选择与用户习惯最相近的需求进行检索；检索完成后允许用户对结果进行满意度和相关度评价，这些评价被传回给知识库，一方面修正用户的兴趣加以学习，另一方面完善信息加工和信息相关度匹配的规则，以为下一次检索提供更可靠的保证。,（1）从字面匹配到概念匹配,单纯的字面匹配方式容易检索出大量冗余信息、误导和欺骗用户的信息，或者得不到任何信息。智能搜索引擎引入概念匹配的检索方式，对关键词进行有效控制，可以实现智能检索。,概念匹配（又叫语义检索、语义交互），是一种建立在信息的概念相关关系基础上的检索，它通过建立某种语义索引，对用户进行交互式的导航，从而实现信息的深度检索。基于概念检索的智能搜索引擎必须建立语义网络的相关知识库，在标引阶段，自动抽取文档中能表达内容的概念，据知识库标引为相应的概念或分类号；在检索阶段，对用户输入的检索词或提问式进行分析，取出其语义，有效识别用户的检索请求和相应概念，帮助用户选用合适的词语表达信息需求，再与标引库进行概念匹配，匹配在语义上相同、相近或包含的词语，从而检索出用户所需信息。,（2）从提供表层信息到挖掘深层信息,目前的搜索引擎沿用传统的关系数据库处理信息的思想，适于处理静态的、结构化的信息，其检索功能只能向用户提供表层信息，只是为了帮助用户从大量的数字化资源中找到满足用户需要的信息。智能搜索引擎使用网络挖掘技术能使用户摆脱表层信息的干扰，对网络数据作更深层次的分析与挖掘，使信息按内容特性聚类，体现一定的知识性。 网络挖掘不但能从网络的链接关系及组织结构中挖掘知识，还能对用户访问网络时的信息和用户个人信息进行挖掘。正是对网络知识和用户知识的深层次分析，智能搜索引擎才能知道用户的需求以为用户提供相关性高、知识性高的信息。,（3）从满足表层需求到预测用户需求,索引式搜索引擎通过关键词检索方式满足用户比较明确的检索目标，分类目录式搜索引擎则通过帮助用户从分类角度查找信息，适用于用户没有明确的目标而只想通过浏览方式了结一定信息的情形。而智能搜索引擎不但能满足用户提出的表层信息需求，还能分析用户潜在的信息需求，预测用户的信息需求。 智能搜索引擎通过与用户交互，获取用户信息，以准确理解关键词的含义和用户的检索目标。 另外，智能搜索引擎具有学习能力，能学习其它智能系统，及跟踪、分析用户信息，在实践中自主更新知识，实现“自我知识”的增长。,（4）从大众化服务到个性化、专业化服务,传统的搜索引擎由于基于字面的简单匹配，对于所有用户的相同关键字的检索，都会返回相同的结果，忽略用户的真正需求及其专业性质，这种非个性化、非专业化的检索方式不能快速选定用户感兴趣的主题，满足用户需要。而智能搜索引擎则可以为用户提供个性化、专业化的服务，方便用户的检索。,智能搜索引擎能实现信息的智能推拉，使用户可以选择服务方式和资源，使检索结果更贴近用户需求，从而提高主动服务的能力，实现完善的个性化服务。用户还能根据自己的需要，设置个性化选项。这样可以使搜索引擎观察不同用户的行为，了解用户的检索风格，从而调整自身以适应用户的爱好和需求，满足用户的个人需要。 另外，专题性的智能搜索引擎能查询特定学科和主题信息，能相对容易地实现文档的分析、处理和面向领域的知识库的建立，在该领域内向用户提供全面的、高质量的专业化信息，在满足用户的专业需求的同时，相对满足用户的个性化需求。,10.4 网络智能搜索策略,10.4.1 基于图的广度优先遍历策略,10.4.2 基于兴趣的启发式搜索策略,10.4.3 基于内容相似度的搜索策略,10.4.4 基于链接结构评价的搜索策略,10.4.5 基于巩固学习的搜索策略,10.4.6 基于“语境图”的搜索策略,10.4.1 基于图的广度优先遍历策略,广度优先遍历是通用搜索引擎常用的搜索策略。在通用搜索引擎系统中，搜索Web并获取页面的任务通常由一个“智能化”的搜索软件完成的。它通常从一个“种子集”（如用户查询、种子链接或种子页面）出发，通过HTTP协议请求并下载Web页面，分析页面并提取链接，然后再以循环迭代的方式访问Web。为了获得较高的Web覆盖率，通用搜索引擎网络搜索软件通常采用图的遍历算法搜索Web，如图10-4（a）所示。,在图10-4中，搜索引擎搜索时对所有结点进行遍历访问。基于广度优先的遍历是最简单的一种策略。当使用基于广度优先的策略时，搜索引擎只需要按照所遇到的链接的顺序将其加入到一个队列中，采用先进先出的顺序采集所有结点信息，由于这种方法没有使用任何知识，其性能是非常低的。 与通用搜索引擎相对应，图10-4（b）显示了专题搜索引擎搜索“O”主题时的搜索结点与顺序。为了寻找到具有相关信息的Web页面，需要判断结点的相关性，并预测、选取合适的搜索路径，因此广度优先遍历策略不适合专题搜索引擎。,10.4.2 基于兴趣的启发式搜索策略,采用启发式模式进行深度优先的搜索步骤（以图10-5所示的Web页面链接结构为例）：,（1）预先设定一个兴趣阈值IT和兴趣基准IB；,（2）计算起始页面Al的目标相关度IA1作为页面Al的兴趣值，并设定当前兴趣值I=IA1；,（3）如果I IT，则继续漫游后续页面Bl，否则结束漫游过程；,（4）漫游Bl页面，计算页面Bl的相关度IB1，令此时的兴趣值为I=I+（IB1IB）；,（5）如果IIT，则继续漫游后续页面Cl，否则返回Al，取I=IA1，开始漫游B2分支；,（6）按照上述步骤，直至漫游完Al的全部页面分支。这里有两个前提：一是漫游到叶子结点后，将返回起始页面；二是页面的兴趣值如果小于给定值，也返回起始页面。,10.4.3 基于内容相似度的搜索策略,基于内容相似度的搜索策略主要是通过计算Web页面中链接文本与搜索主题之间的相似度来衡量链接价值的高低，并以此决定其搜索策略。这里链接文本是指链接周围的说明文字和链接URLs上的文字信息；搜索主题可以用关键词、相关文档等表示。,基于相似度的计算主要有文本与关键词的相似度计算、文本与文本的相似度计算等。基于文本与关键词的相似度计算利用向量空间模型将查询串与文本转化为向量，然后使用布尔模型、词频或嫡来代表特征词的权重，再利用TFIDF等方法进行计算，评估文本与关键词之间的相似度。在进行文本与文本的相似度计算过程中，主要使用串距离方法、单词统计方法、文本结构方法与综合计算方法等。,基于内容相似度的搜索策略利用语义相似度的高低决定链接的访问顺序。这类方法起源于文本检索中对文本相似度的评价，优点是有较好的理论基础且计算简单。但这类方法忽略了链接结构本身的信息，因而在预测链接价值方面存在一些缺陷。,10.4.4 基于链接结构评价的搜索策略,基于链接结构评价的搜索策略通过对Web页面之间相互引用关系的分析来确定链接的重要性，进而决定链接访问顺序的方法。Page-rank和HITS是其中有代表性的两种方法。 Page-rank的基本思想是：一个页面被多次引用，即很多页面有指向它的链接，则这个页面很重要；一个页面尽管没有被多次引用，但被一个重要页面引用，则这个页面也可能很重要；一个页面的重要性被均匀的分布并传递到它所引用的页面。,HITS方法定义了两个重要概念：权威级别和中心级别。权威级别表示一个权威页面被其它页面引用的数量，即该权威页面的入度值，网页被引用的数量越大，则该网页的权威值越大。中心级别表示一个Web页面指向其它页面的数量，即该页面的出度值，网页的出度值越大，其中心值越高。,基于链接结构评价的搜索策略考虑了链接的结构和页面之间的引用关系，但忽略了页面与主题的相关性，在某些情况下，会出现搜索偏离主题的“主题漂移”问题。另外，搜索过程中需要重复计算Page-rank值或权威值及中心值权重，且计算复杂度随访问页面和链接数量的增长呈指数级增长。,10.4.5 基于巩固学习的搜索策略,巩固学习：一个能够感知环境的自治Agent通过学习能选择达到其目标的最优动作。在对某一特定的状态进行决策时，Agent不知道其正确的决策是什么，但当Agent在环境中作出每个动作时，施教者会提供奖励或惩罚信息，以表示结果状态的正确与否。因此，Agent的任务是从这个非直接的、有延迟的回报中学习，以便后续的动作产生最大的积累回报。在巩固学习算法中，可以选择许多种形式化的方法。,在基于巩固学习的搜索策略中，网络程序面对的Web环境代表状态，对链接的访问代表行动。搜索过程中，经过若干无关页面的访问之后才能获得的主题相关页面称为未来回报（或称远期回报），对未来回报的预测值称为未来回报价值。,在巩固学习模型中，若用Q表示未来回报价值，则其策略方法的核心就是学习如何计算链接的Q价值。为此，搜索过程被划分成训练和搜索两个阶段。训练阶段利用巩固学习算法计算每个链接的Q价值，并按价值大小将链接分类，然后用类中链接的文本信息训练一个朴素贝叶斯分类器；在搜索阶段，面对价值未知的链接，则根据链接文本，用所建立的朴素贝叶斯分类器计算链接落在每一类中的概率，并以这个概率为权值计算链接的综合Q价值。,基于巩固学习的搜索策略，实质上是通过训练学习得到哪些链接文本具有较高的Q价值，反过来，在搜索时又根据链接文本的Q价值估算出链接的价值。因为Q价值反映了对未来回报的预测值，所以，即使当搜索的页面与主题不相关时，搜索程序也可以根据未来回报价值确定正确的搜索方向。,由于目前的巩固学习算法不适于大状态、行动空间的学习，因而基于巩固学习的搜索策略存在学习效率低的问题；此外，由用户选择典型站点进行训练增加了用户的负担。,10.4.6 基于“语境图”的搜索策略,基于“语境图（Context Graph）”的搜索策略通过构建典型页面的Web“语境图”来估计离目标页面的距离，距离较近的页面较早得到访问。该方法分为训练和搜索两个阶段。训练阶段首先选择典型的主题相关页面作为种子集（目标页面的“实例集”），并从种子页面出发，利用某一通用搜索引擎检索出所有指向它们的页面；,其次，以得到的新页面作为第一层次集（表示到目标页面的距离为1），并用第一层次集中的页面文本训练一个分类器C1；再次，从第一层次集中的页面出发，按同样的方法得到第二层次集（表示到目标页面的距离为2）和分类器C2；如此重复，直到某个预先指定的层次。 由此，得到了一个表示种子页面集与周围页面之间层次关系的“语境图”。 搜索阶段 当下载完一个新的页面时，则利用训练阶段得到的分类器判断该页面属于哪个层次集，从而估计出该页面距离目标页面的远近，并优先访问距离目标较近的页面中的链接。,10.5 网络智能搜索引擎实例分析 10.5.1 Google的搜索机制,（1）网络爬行器与本地数据库几个分布的网络爬行器（Crawler）同时搜取网页，由URL服务器负责向Crawler提供URL列表。Crawler将找寻到的网页送到存储服务器（Store Server）中，存储服务器把这些网页压缩后存入数据库（repository，用于存储每个网页的全部HTML及其他有关信息）中，并赋予每个网页一个关联ID，称为docID。,（2）索引器和排序器索引功能通过索引器（Indexer）和排序器（Sorter）来实现。索引器从知识库中读取文档并将其转换成一组词的出现状况（word occurrences），称为采样（hits）。hits记录了词、词在文档中的位置、字号、大小写等。索引器把这些hits分配到一组桶“barrels”中，产生经过部分排序后的索引。同时，索引器还分析网页中所有的链接，并将重要信息存于链接描述文件（Anchors）中，该文件保存了链接描述文字和其他一些信息，足以判断一个链接被链入或链出的情况。,（3） URL分析器URL分析器（URL Resolver）阅读链接文件Anchors，把相对的URL转换成绝对的URL，与其docID号对应，形成链接文件的文本索引，Anchor文本与所指向的docID建立关联，产生了由docID对（pairs of docID)所组成的链接数据库，用于计算网页的PageRank值。,（4）搜索排序器读取桶中的词汇，并根据词的ID号（wordID）列表重新生成倒排文档。DumpLexicon程序则把以上形成的索引列表和由索引器产生的词表结合，形成一个新的字典供搜索器（Searcher）使用。搜索器由Web服务器实现，并根据DumpLexicon所生成的词表，结合上述倒排索引及页面等级来匹配用户的查询。,10.5.2 Google的智能行为分析,（1）检索技术的智能化, 网页采集技术分布式爬行系统,为了获取上亿网页，Google设计了一种分布式爬行器（Crawler）系统，由系统中的漫游遍历器（Googlebot）定期地（通常是28天）按预先设定的IP地址范围遍历对应网页，若网页发生变化或者发现新的网页，则获取此网页传回服务器，然后继续沿网络遍历，直至访问完所有链接。为了保证爬行器遍历信息的广度，Google事先设定了一些重要的链接。,Google可同时运行三个爬行器，当服务器将URL列表提供给爬行器后，每个爬行器同时保持与大约300个网络连接。最高速度时，Google每秒钟通过爬行器获取的网页可超过100个。影响爬行速度的一个重要因素是DNS查询，为此，每个爬行器需要一个维护自己的DNS缓冲。这样每个链接都处于不同的状态，包括：DNS查询、连接主机、发送请求、得到响应。该分布式爬行系统通过异步输入/输出来管理事件，通过一定数量的队列来管理获取网页过程中的状态迁移。, 机器翻译技术网页翻译功能,Google应用计算机翻译技术，支持多种语言检索，在操作界面中提供多达15种语言选择，包括英语、主要欧洲国家语言、日语、中文简繁体、韩语等，同时还可以用10种东欧语言进行查询，打破了语言上的障碍。, 检索对象的多样性,Google提供网页（Web）、图像（Images）、新闻群组即讨论区（Groups）和网页目录（Directory）的检索服务，以及购物搜索、在线答疑、书目搜索、大学院校搜索等特别主题搜索，以便从不同的检索途径尽可能地满足不同需求的用户。 Google还提供特定文件搜索功能，除HTML页面外，搜索结果中还包括以PDF、DOC等为后缀名的12种文档。同时，Google提供“View as HTML”（用HTML格式浏览）功能，以便未安装相应文档格式软件的用户也可查看。, 中文简繁体转换技术,Google采用Basis Technology的中文简繁体转换技术，可以实现汉字简繁字体的自动转换，从而使用户找到更多相关信息。该系统不是简单的字符变换，而是简体和繁体文本之间的“翻译”转换。当用户检索所有中文网页时，Google先对检索式进行简繁转换后，同时检索简体和繁体网页，并将检索结果的标题和摘要转换成和检索式相同类型的文本，便于用户阅读。,（2）检索结果处理的智能化,为了准确筛选索引中的网页信息和显示结果，Google打破了传统的网络分类概念，采用独树一帜的PageRank页面等级技术和超文本匹配分析技术（Hypertext-Matching Analysis）。, PageRank页面等级技术,Google利用网络自身的超链接结构给所有的网页确定一个重要性的等级数，即：如果一个页面被多次引用，那么这个页面很可能是重要的；如果一个页面尽管没有被多次引用，但被一个重要的页面引用，那么这个页面很可能是重要的；一个页面的重要性被平均分配到它所引用的页面。,在实际计算时，Google还考虑到网页A的所有链入网页（链接到某网页的其它网页称为该网页的链入网页）对它的推荐能力（即由于它们对网页A的链接,使人们认为网页A的重要程度）和推荐程度（即它们认为网页A的重要程度）。一个网页本身的PageRank值越高，则它对其链出网页（从某个网页链出的网页称为该网页的链出网页）的推荐能力就越大；一个网页的链出网页越少，那么它对其中一个链出网页的推荐程度就越高。,Google关于网页PageRank值的计算公式：,PR(A) =(1-d) +d (PR(T1) /C(T1) +PR(Tn) / C(Tn),其中：PR(A)是指网页A的PageRank值; T1，T2，Tn是网页A的链入网页; PR(Ti)是指网页Ti的PageRank值(i=1,2,n); C(Ti)是指网页Ti的链出网页的数量(i=1，2，n); d是一个衰减因子，0d1，通常取值为0.85。,对于一个查询，Google首先利用相似度函数计算其相似页面数的多少，然后计算每个页面的重要性。在计算每个页面的重要性之前，Google给每一个网页赋予一个初始PageRank值，再根据PageRank算法计算其PageRank值。排列检索结果时，将PageRank值高的网页依次排在列表的前面。,超文本匹配分析技术,一般的搜索引擎仅仅考虑关键词在文档中出现的次数，除此之外，Google还分析关键词在网页中出现时所用的字体、字号以及在网页中出现的精确位置，并对该网页的邻近网页（包括链入网页和链出网页）的内容加以分析，赋予不同的权重，通过计算得出最新的排列结果。Google认为关键词在网页中出现的位置及字体等因素可以充分体现该关键词在该网页中的重要程度。例如，若某关键词出现在网页A的标题中，而只是出现在网页B的正文中，则在不考虑其它因素的情况下，说明网页A与用户需求更匹配。,另外，Google引入了锚文本（Anchor Text，即超文本链接的文字描述）对网页内容进行分析。锚文本在一定程度上能更加准确地描述其链接网页的内容。Google会记录网页中所有的超文本链接情况，包括该链接的文字描述（即Anchor Text）、该链接的具体对象（主要是其URL）。例如，网页A中有一个关键词“人工智能”，且该关键词存储了一个超文本链接指向网页B，则关键词“人工智能” 可以很好地说明网页B的内容。此处的关键词“人工智能”就是Anchor Text，Google会记录关键词“人工智能”以及网页B的URL。,此外，Google的检索结果结果显示包括网站分类目录、标题、网址、网页摘录，其中匹配的关键字以粗体显示。 “网页快照（Cached）”功能能使用户查看Google已编入索引的网页的内容。而检出结果除按重要性先后排列（Viewing in Google Page Rank order）外，还可按字母顺序（Viewing in alphabetical order）排序。,Google对以上影响因素赋予不同的权重，通过计算得出最新的排列结果，提高查准率，更好地满足用户需求。,（3）检索服务的智能化,Google帐户,Google通过Google帐户为用户提供个性化Google体验，进行用户使用偏好设置。用户登录系统后，可查看并管理用户的搜索历史记录，基于用户的历史搜索，系统能为用户提供有用的相关结果和推荐内容，使用户获得最相关的搜索结果。,相关搜索,Google能够提供与原搜索相关的搜索词，这些相关的搜索词根据过去Google所有用户的搜索习惯和Google提供的计算两个搜索词之间相关度而产生，能帮助用户更快地找到更有价值的结果。,此外，Google能够纠正英文单词拼写错误、检查并帮助纠正可能有的错别字、提示常用人名及地名的最常见的书写方式、对拼音关键词进行自动中文转换并提供相应提示，而且英文状态下的Google具有成人内容过滤功能，能够过滤掉搜索结果中具有欺骗或其他不良企图的信息。,