北京理工大学信息检索课件-2搜索引擎的架构

[e-mail]2012.9InformationRetrieval2Outline1.搜索引擎的软件架构2.索引组件3.查询处理组件搜索引擎的软件架构•软件体系结构•UIMA•搜索引擎的架构软件体系结构•软件体系结构是构建计算机软件实践的基础。•设计和构架：构架属于设计的一方面，它集中于某些具体的特征。•软件架构是指在一定的设计原则基础上，从不同角度对组成系统的各部分进行搭配和安排。•包括该系统的各个组件，组件的外部可见属性及组件之间的相互关系。UIMA•UIMA（UnstructuredInformationManagementArchitecture,非结构化信息管理架构）是一个面向大规模文本、音频、视频等非结构化信息管理系统的软件架构，为文本处理、检索、和知识管理等功能模块提供整合的标准。•这个框架的目的是为非结构化分析提供一个通用的平台，从而提供能够减少重复开发的可重用分析组件。•UIMA为组件定义了接口，使得系统在增加处理文本和其它非结构化数据的功能时候更加简单和规范。•例如Apache的UIMA项目（）就是对该架构的一个实现。2012/10/12搜索引擎的架构•搜索引擎的架构为搜索引擎提供组成部分并定义各个组件关系的高层描述。搜索引擎的两个主要目标是：–效果：对于用户的的查询，返回最准确的相关性排序文档。–效率：尽可能快速的返回满足用户的查询的检索结果。•为了提供准确的效果，搜索引擎对网页和日志等内容进行深入的加工和处理；为了高效率的服务，搜索引擎采用特殊的数据结构和缓存技术.索引组件索引查询处理索引文档数据库网页、文档返回日志相关文档索引组件文本采集索引创建预处理索引文档数据库网页、文档返回文本采集•文本采集组件用于发现文档。•文本采集通常通过爬行（crawing），建立检索的文档集合、元数据（metadata）库。•元数据不表示文档的文本内容，但是表示关于一篇文档的信息。如文档类型、文档结构、来源、日期、长度等信息。•爬虫•信息推送•文本转换•文档数据库1、爬虫•在大多数搜索引擎中，爬虫（crawler、robot、spider）组件对于搜索引擎来说具有获取文档来源的首要任务。•爬虫有不同种类，但是网络爬虫是最主要的爬虫。•网络爬虫的实现有很多方式，但是基本原理都是通过追踪网页上的URL来找到并下载页面。•由于网络上网页数量巨大，而且更新频繁，交叉连接和相互引用的情况复杂，如何爬虫以保证高的覆盖度和时新性，是一项极具挑战的任务。•网络爬虫既可以面向整个互联网，也可以被限制在一个或者多个专门的站点。例如新建网站自身的站内搜索。•主题爬虫（topicalcrawler）构件垂直搜索引擎（vertiacalsearch），专门搜索某一特定领域或主题的信息。•企业搜索或者个人硬盘搜索爬虫。2012/10/122、信息推送（InformationFeed）•搜索引擎还希望可以接受来自其它信息来源主动馈送（feed）的信息•网络爬虫可以精确的知道信息源更新的信息，从而节约大量的网络带宽•RSS（ReallySimpleSyndication，简易信息聚合）是互联网上信息馈送的通用标准。•音频和视频流也可以被馈送。3、文本转换-格式转换•搜索引擎内部工作在纯文本数据上。•网络文档格式有HTML、XML、PDF、MicrosoftOffice、WPS等。•在搜索引擎对其进行索引之前，需要将这些文档转换成统一的纯文本并提取元数据。•对于PDF和Office文档，需要第三方的转换程序给与支持。文本转换-编码转化•ASCII每个字符的取值范围为1-128，用7个二进制位表示。•扩展的ASCII用8个二进制位表示1-256范围的字符。•在中日韩等字符集中，具有上千个字符。•目前经常采用的统一编码集是一种变长的UNICODE编码：UTF-8。4、文档数据库•为快速生成摘要以及分析任务，有必要在搜索引擎本地保存原始文档的副本。•文档数据库管理的数据包括非结构化的文档内容和结构化的元数据。•小规模的文档集，可以采用关系数据库存储这些文档和元数据。•大规模的场景中，通常采用专门设计的文档数据库，存储大规模的文档数据库，并提供高速的内容存取。回索引组件文本预处理•文档格式解析•词素切分•去除停用词•词干提取•超链接的抽取与分析•信息抽取•文本分类器2012/10/121、文档格式解析•文档格式解析器使用标记语言中的句法(syntax)知识来识别文档的结构。•例如：h2Search/h2定义“TML和XML都使用标签(tag)来定义文档的元素Search”是HTML文档中的二级标题。•其他的文档类型，如电子邮件和OFFICE文件，由指定的格式和方法来定义文档的结构，需要使用相应的解析工具实现格式的解析。2、词素切分•词素切分(tokenizing)是文本预处理中的重要步骤。文档和查询中的文本必须以同样的方式转换为词素。•对于给定的文本，可能会有多种切分结果，这可能会影响到检索。•例如，“getup”“Ford”和“ford”，“on-line”？“O'Connor”？•在中日韩语言中，分词是个更复杂的问题。“上海市长江大桥”。“给学生安全带来危害”。3、去除停用词•停用词（stopword）是指在文档中出现最频繁且没有实际意义的词，例如典型的功能(function)词。如：“the”、“of”、“to”和“for”。•停用词去除组件的任务就是判断索引项是否为停用词，从而避免他们成为索引项。•研究中使用的停用词表包含几十个到几百个常用。•使用停用词表的问题是，用户如果提交查询“tobeornottobe”或“downunder”，搜索引擎不可能返回搜索结果。•索引阶段使用一个很小的停用词表（可能仅含有一个停用词“the”），查询时用一个较大的停用词表。4、词干提取•词干提取组件（或词干提取器，stemmer）的任务是把源于同一个词干（stem）的派生词进行归一化。例如，把“fish”、“fishes”、“fishing”归为一个等价类。•词干提取对排序的效果通常只有很小的改善。类似于停用词去除，词干提取可以有选择性的进行。•针对所有词进行词干提取可能会导致搜索问题。•“fishing”“fish”•只用“s”开来识别复数形式•阿拉伯语和土耳其语以及维吾尔语，具有更复杂的词汇形态（morphology），词干提取格外重要。对于中日韩语言，词形的变化很少，在这些语言上不必进行词干提取工作。5．超链接的抽取和分析•在对网页进行预处理的过程中，网页中的超链接和锚文本可以很容易地被识别并抽取出来。这些信息记录在文档数据库中，和文本内容分开索引。•网络搜索引擎通过使用像PageRank这样的链接分析（linkanalysis）算法，广泛地利用超链接和锚文本这些信息。•链接分析向搜索引擎提供一个页面的关注度，并且在一定程度上还向搜索引擎提供一个页面的权威度（authority，重要度的一个参考指标）。•对于有些类型的查询，这超链接和锚文本可以很大程度地改善检索效果。6．信息抽取•信息抽取用于识别更加复杂的索引项。中国第一艘航空母舰“辽宁舰”在按计划完成建造和试验试航工作•但通常的信息抽取需要更复杂的计算。例如抽取句法特征，如名词短语，需要某种形式的句法分析和词性标注（part-of-speechtagging）。•命名实体（namedentity）识别器，能够地识如人名、地名、机构名称、日期和等信息。更加复杂的事件抽取器识别与某事件相关联的实体、时间、事件等参数。7．文本分类器•分类技术给文档分配事先定义好的类别标签，这些标签代表性地表达话题的类别，如“科技”、“体育”、“政治”或“经济”。文本分类技术的典型应用如判断垃圾邮件，新闻网站的自动分类等。•信息检索中分类技术的两个重要实例:判别一个文档是否是垃圾文档，以及识别文档中的非内容部分，如广告。•聚类技术用于在没有事先定义类别标签的基础上，将相关的文档聚集在一起。在排序或用户交互过程中，文本聚类被以多种方式使用。回索引组件索引创建•索引项•文档统计•权重计算•倒排索引•索引分派2012/10/12索引项（indexterm）•文本转换组件将文档转化为索引项（indexterm）或者“特征”（feature）。•最简单的索引项是一个英语单词或者一个汉语字。•“特征”用于表示文档的内容。特征也可以作为索引项。•比较复杂的索引项和特征可以是短语、人名、日期、超链接等等。•索引项有时候简单的称为词项（term）。整个文档集合的所有词项集合，称为索引词表（indexvocabulary）。索引创建组件•索引创建组件利用文本转换组件的输出结果(term)创建索引数据结构，以便于实现快速的搜索。•索引创建在时间和空间上都必须是非常高效的。•倒排索引（Invertedindex）是几乎是搜索引擎目前使用的唯一的索引方法。1．文档统计•文档统计组件汇总和记录词、特征及文档的统计信息。排序组件使用该信息来计算文档的分值。•真正所需要的数据是由检索模型和排序算法来决定的。•通常所需要的数据包括•索引项在各文档中出现次数（词及更加复杂的特征）、•索引项在文档中出现的位置•索引项在一组文档（如所有标记为“体育”的文档或者整个文档集合）中出现的次数•以及按照词素数量统计的文档长度•文档统计结果存储在可以快速检索的查找表（lookuptable）中。2．权重计算•索引项的权值（weight）反映了文档中词的相对重要性，并且用于为排序计算分值。•加权组件利用文档统计结果计算权值，并将权值存储在查找表中。•权值的计算可以是查询处理的一部分，并且一些类型的权值需要关于查询的信息，但在索引过程中需要尽可能多的计算，这样可以提高查询处理的效率。•在过去的检索模型中，最普遍使用的一种加权方法称为tf.idf:TF.IDF=TF*(logN/n)3．倒排索引•倒排(inversion)组件是索引处理的核心组件。将文档--词项流转换为词项--文档流•如何高效完成这项工作是极富挑战性：•大量、更新。•倒排索引设计用于快速的查询处理，并且在一定程度上依赖于所采用的排序算法。•索引还被压缩以使于进一步提高效率。4．索引分派•索引分派组件将索引分发给多台计算机，很可能是网络中的多个站点。•通过分派文档子集的索引表（文档分派，documentdistribution），索引和查询处理都可以并行（parallel）进行。•分派词项子集的索引（词项分派，termdistribution）能够支持查询的并行处理。•复制（replication）是分派的一种形式，索引表或部分索引表存储于多个站点，由此查询处理能够通过减少通信延迟进一步提高效率。回索引组件查询处理组件用户交互排序评价索引文档数据库返回日志数据库用户交互•查询输入•查询转换•结果输出2012/10/12341．查询输入•查询输入组件为查询语提供接口和解析器。•在大多数网络搜索接口中使用的最简单的查询语言仅有少量的操作符（operator）。操作符使用户查询的意义更加清晰。例如“”操作符。•部分由于用户对操作符的未知，现实中典型的网络查询中仅包含少量的关键词（keyword），而没有操作符。•关键词是简单的词或词组，对于指定查询来说是很重要的。eg：“搜索引擎”和“搜索引擎中使用的经典技术和数据结构是什么”Tip：试试百度的“”操作复杂查询语言•对于熟悉搜索引擎技术的用户或者使用搜索引擎的可以使用更加复杂的查询语言。•这些查询语言也不是为搜索应用的终端用户设计的。•布尔型(Boolean)查询语言在信息检索中有着较长的历史。这种查询语言中使用的操作符包括AND、OR和NOT，以及一些邻近（proximity）操作符，用于指示关键字在指定的距离内一起同现。•Tip：试试百度的减号操作2．查询转换•查询转换组件在生成排好序的文档之前和之后改善初始查询。