搜索引擎架构概述

架构

对软件系统来讲,从一个层面对系统的各个组件进行抽象.描述它们各自的功能、提供的接口以及它们之间的关系.

需求

架构为应付需求而产生,对搜索引擎来讲,它主要的需求来自两个方面:

效果(effectiveness):搜索的结果质量如何. 效率(effeciency):返回结果的相应时间是不是够低,搜索服务的吞吐量是不是够高.

索引处理系统(Indexing Process)

从这样的需求出发,我们就不能顺着文档的每一个字或词来比较用户输入的查询关键字. 所以我们需要一种能提供高效的数据结构、算法和检索策略的东西,这就是索引处理系统. 这个系统大概像下面这样:

(欢迎关注公众号:IT技术精选文摘,微信号:ITHK01)

这幅图能告诉我们什么?

采集文本组件(Text acquisition)

这个组件用于发现、识别、和存储文档.为索引做准备.通常它必须具备以下几个功能:

1.爬虫 (Crawler)

一般搜索引擎中就是网络爬虫(web cralwer)了. 它负责通过超链接来源源不断地从互联网、文件服务器等信息源中爬取网页、新闻、email、话题等文档.并将这些信息加工后丢进文档数据库中.如上图所示. 爬虫要解决一个更新的问题,因为一个搜索引擎必须拥有对更新或时新的内容进行处理的能力.

2.信息源 (Feeds)

对于实时文档流,检测信息如果就能获得更新的消息那再好不过了.RSS就是一种信息源.它用XML来描述.

3.转换 (Conversion)

这里的转换的功能一些也可以丢给文本转换组件. 来自爬虫抓取或者信息源的文档集合,格式很多,比如html、xml、PDF、doc、ppt等,而我们更喜欢纯文本的格式以高效和有效处理.

4.文档数据库 (Document Data Store)

必须有一个能存储文档及其元数据的地方,否则索引再快,也没东西返回,虽然互联网上的文档可以时时抓取,但离线分析显然更快,这就需要一个文档数据库. 选择关系型数据库(RDBMS)还是NoSQL数据库,根据实际情况来.

文本转换组件(Text Transformation)

这个组件负责将文档转换成为索引项(index term)特征(feature). 所有词项组成的集合叫作*索引字表index vocabulary)*.

1.解析器 (parser)

这个组件负责分词或叫词素切分(tokenizing)和识别词素(tokens). 词素识别可以将文档中的结构化部分切分出来,比如链接、主题、图标等。 不仅是对文档,对查询也要做分词,这样查询和文档才能比较。

2.停用词处理 (stopping)

一些停用词,比如英文中的to、of、the,中文中的的、吗等,对文档内容贡献不大,但却大量出现。 去除停用词可以在相当的幅度上增加检索效率,但也可能带来错误的搜索结果。 停用词库的大小要斟酌,小了意义不大,大了容易过滤掉很多东西,导致查询的本意被改变或者变得不可读。比如一骗文章叫“论的字在生活中的作用”,去除了“的”之后,就会很囧。

3.词干提取 (parser)

同义词或英文中的派生词处理.

链接是网页内容的重要组成部分.大名鼎鼎的Google就是靠PageRank这种链接分析技术起家. 链接反映了网页内容之间的关系,这类似于图的边. 通过链接抽取和分析算法,可以得出一个页面的重要程度和被关注程度,这一信息可以用来为页面打分或赋予权重. 同时,链接文本可以更有语义地表达链接所指向的内容,这对于页面或文章分类也是有用的信息. 所以

链接分析对搜索结果意义重大.

5.信息提取 (information extraction)

考虑这样一句话,”搜索引擎是一个技术成熟但实现成本高的应用“,其中“搜索引擎”显然比“搜”、“索”、“引擎”更统一、更整体,对这样的名词短语进行抽取,对返回正确的搜索结果很有意义。 它还处理句法、语法、命名实体识别(named entity ),比如分类公司、人名、地名等。

6.分类器 (classifier)

这个组件用于识别文档中与类别相关(class related)的部分. 比如文档的标签或话题分类,可以是体育、政治或者计算机,甚至是吐槽。 显然,分类是基于有监督学习(supervized learning)的技术,因为实现知道了分类标签,而聚类则用于在一无所知的情况下对文档进行类别划分,比如google news,它就将新闻聚合成不同类别展现给用户.

创建索引组件 (Index Process)

索引往往比文档本身要小很多,比如lucene中的索引可以达到是原文档的20-30%,同时相对文档来讲更具可比较性。 这个组件必须有以下的能力:

1.文档统计 (Document Statistics)

统计、汇总和记录词出现的频率、位置和其它特征等信息。 比如索引项在所有文档中出现的次数,在一组或一类文档中出现的次数,在文档中出现的位置,以及按照词素(tokens)数量统计的文档长度。 处理这些信息的目的是丢给排序组件,排序组件根据这些信息对文档进行打分. 具体需要统计什么是根据排序组件中的检索模型来定,统计结果用一种叫查找表(lookup table)的高效数据结构来保存。

2.附加权重 (Weighting)

计算索引项(或词项)的权重,词的权重反映了词在文章中的相对重要性,排序算法需要这些信息来为分档进行打分。 具体的权重形式由检索模型决定,加权操作也可以、有时也必须需要查询中的一些信息来确定,所以这个功能的一部分也可以由查询处理系统来提供。但为了查询处理的效率,在索引建立环节需要尽可能多的去计算。

如果用户输入了这样一个查询“我想买玩具”,“我”这个词一般会大量出现在各个文档中,这个词的权重就不应该比“玩具”高,否则将会返回大量的包含“我”的文档,这就是一次不成功的查询。

一般的加权方法主要使用tf.idf

tf-词频(term frequency)是指索引项在一个文档中出现的频率. idf-逆文档频率(inverse document frequency)是指索引项在所有文档集合中出现的频率. idf=logNn 其中,N是所有文档总数,n是包含某个词项的文档个数.

在上面的例子中,结合idf的公式,可以看出,包含“玩具”这个词的文档数目n一定小于包含“我”这个词的文档数量m,所以“玩具”这个词的权重更高. 权重信息也会放入查找表中。

3.倒排 (Inversion)

倒排组件是创建索引组件的核心,因为它事关效率。

倒排是将文档-索引项转换为索引项-文档,如下: (term,doc)=inverse(doc,term)

这个组件的挑战在于如何高效地处理倒排转换过程,应付全量和增量信息的索引建立任务。 同时为了减小索引的大小以提高效率,还会对索引进行压缩(compression)

4.分布索引 (Index Distrubition)

通常搜索引擎处理的文档集合非常大 ,那么就必须考虑索引的分布式问题。

document distrubition 为了能够并行的支持创建索引和查询,可以将文档子集的索引表派发到不同的计算机和站点上。 term distrubition 为了能够支持并行的查询,可以讲索引项子集的索引表派发到不同的计算机和站点上。

其它的分布方式还有p2p、复制(replication)等.

查询处理系统

查询处理系统主要包含三个构件:用户交互、排序和评价。

(欢迎关注公众号:IT技术精选文摘,微信号:ITHK01)

用户交互组件 (User interaction)

创建查询、完善查询以及向用户展示结果. 比如,将用户的查询转换为索引项. 并将从搜索引擎得到的有序文档列表组织成搜索结果,展示给用户.

1.查询输入 (Query Input)

为查询语言(query language)提供接口和解析器。 查询语言一般只有很少的几个操作符,这些操作符指示应该对查询作特殊处理。 比如布尔型操作符,AND、ORNOT,当然也包括临近操作符(proximity)。 查询语言的作用,一是用来描述更加复杂的查询,二是描述查询转换的结果。

2.查询转换 (Query Tranformation)

改进初始查询,在生成有序的文档前后提供完善处理。 包括一些文本转换的技术。 比如分词、停用词去除和词干提取,以生成可以和文档的索引项可以匹配的索引项。 拼写检查(spell checking)和查询建议(query suggestion)用于生成和用户查询相似的输出。 查询扩展(query expasion)和相关性反馈(relevance feedback)技术,使用额外的词项来修改初始查询。这些词项的来源,主要是对文档中词项的出现情况、用户认为相关的文档中出现的词项等分析为基础。

3.结果输出 (Results Output)

对已经排好序的文档结果进行展示。 包括生成文档摘要(snippets)和高亮关键字和关键段落(highlighting)。 另外,也可能包括对文档集进行聚类展示,并添加一些相关的广告。

排序组件 (Ranking)

利用查询和索引生成有序的文档列表. 这个搜索引擎的核心组件,它接收用户查询,并根据检索模型得到一个按分值排好序的文档列表. 排序必须满足高效、优质.

1.评分 (Scoring)

使用评分算法为文档进行评分,这是文档排序的基础。

评分组件是搜索引擎的核心.

一般的评分可描述为:

∑iqidi 其中qi和di分别是第i个查询词项和文档词项的权重. 评分方式依赖于检索模型,检索模型有很多,比如基于BM25、查询似然度的检索模型。

2.优化性能 (Performance optimization)

排序的效率对于搜索引擎的表现至关重要,所以需要进行性能优化。 性能优化设计排序算法和索引表的设计等,目的是降低响应延时、提高吞吐率。

一次一词项方式(term-at-a-time) 以词项为单位,先处理词项ti的倒排表,再处理ti+1,需要对每个未处理完的文档建立一个累加器。 一次以文档方式(document-at-a-time) 以文档为单位,先计算文档di,再计算di+1,需要文档在所有倒排表中的顺序一致。 安全方式优化(safe) 优化前后的文档排序结果相同。 非安全方式优化(unsafe) 优化前后的文档排序结果不同。

3.分布式 (Distribution)

既然索引是分布式的,那么排序也可以采用分布式方法。 查询代理(query broker)可以将多个用户查询分发到不同的计算节点,并负责聚合各个计算节点的处理结果。 缓存(cache)也是一种分布式的方式,如果将前一个用户的查询结果保存在内存中,那么如果有其他用户使用类似的查询,将可直接从缓存中返回结果,这大大提高了查询的效率。

评价组件 (Evaluation)

评价和监测搜索的质量和性能. 其中,利用日志系统来记录用户行为,并对其进行分析以优化搜索. 可以看出,评价系统会对排序系统做出改善和调整. 显然,评价系统是滞后的,所以一般它作为离线系统的一部分.

1.日志分析 (Logging)

记录用户搜索行为日志,对于改进排序和查询处理意义重大。 用户的查询日志,可以作为拼写检查、查询推荐、查询缓存等任务的基础。 精准广告技术就依赖于用户的搜索行为分析。

用户对查询结果的处理方式可以用来反映文档对于用户查询是否是相关的。 如果用户在搜索引擎返回的排序文档中,点击了其中一个,那么这个文档可能就是和用户查询相关性比较高的一个。 同时,跟踪用户的点击流和页面驻留时间,可以用来评价和训练排序算法。

2.排序分析 (Ranking Analysis)

评价和改善搜索的有效性。 通过大量的查询-文档对,结合查询日志,可以判定一个排序算法的结果,用于和其它算法进行比较,以确定更优化的参数等来改善排序结果。

3.性能分析 (Performance Analysis)

评价和改善搜索的效率。 监测和收集系统运行的性能指标。如响应时间、吞吐量、网络延时等等。

(完)

出处:http://www.cnblogs.com/foreach-break

版权申明:内容来源网络,版权归原创者所有。除非无法确认,我们都会标明作者及出处,如有侵权烦请告知,我们会立即删除并表示歉意。谢谢。

本文分享自微信公众号 - IT技术精选文摘(ITHK01)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-07-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据文摘

手把手:一张图看清编程语言发展史,你也能用Python画出来!

42430
来自专栏CDA数据分析师

怎样用Python给宝宝取个好名字?

每个人一生中都会遇到一件事情,在事情出现之前不会关心,但是事情一旦来临就发现它极其重要,并且需要在很短的时间内做出重大决定,那就是给自己的新生宝宝起个名字。 ...

367100
来自专栏大数据文摘

想入门深度学习不会搭建环境?手把手教你在Amazon EC2上安装Keras

61520
来自专栏杨建荣的学习笔记

数据库收缩数据文件的尝试(二)(r11笔记第10天)

在之前自己的一个测试环境中,因为本身磁盘空间不足,导致一个测试库数据目录溢出,最后花了点功夫,将一个2G左右的文件经过收缩的操作后,竟然收缩为7M。详情可以参考...

367110
来自专栏WeTest质量开放平台团队的专栏

UPA深度性能报告解读

原文链接:http://wetest.qq.com/lab/view/403.html

13520
来自专栏人工智能头条

图解TensorFlow架构与设计

1.2K60
来自专栏ThoughtWorks

GEEK的心思你别猜

#ThoughtWorkers好声音#第十二期(图片:网络) 都说Geek的世界高深莫测,无法轻易探究。有多高深? 就是写幻灯片都用文本格式,更Geek的做法...

26840
来自专栏UML

用例图教程(示例指南)

用例是系统分析中用于识别,澄清和组织系统需求的方法。用例由特定环境中系统和用户之间的一组可能的交互序列组成,并且与特定目标相关。它由一组元素(例如,类和接口)组...

32130
来自专栏企鹅号快讯

如何在Python中快速进行语料库搜索:近似最近邻算法

选自Medium 作者:Kevin Yang 机器之心编译 参与:路雪 最近,我一直在研究在 GloVe 词嵌入中做加减法。例如,我们可以把「king」的词嵌入...

29550
来自专栏张善友的专栏

负载均衡的基本算法

负载均衡的基本算法,主要有以下几种(参考F5产品): 随机:负载均衡方法随机的把负载分配到各个可用的服务器上,通过随机数生成算法选取一个服务器,然后把连接发送给...

32670

扫码关注云+社区

领取腾讯云代金券