对软件系统来讲,从一个层面对系统的各个组件进行抽象.描述它们各自的功能、提供的接口以及它们之间的关系.
架构为应付需求而产生,对搜索引擎来讲,它主要的需求来自两个方面:
效果(effectiveness):搜索的结果质量如何. 效率(effeciency):返回结果的相应时间是不是够低,搜索服务的吞吐量是不是够高.
从这样的需求出发,我们就不能顺着文档的每一个字或词来比较用户输入的查询关键字. 所以我们需要一种能提供高效的数据结构、算法和检索策略的东西,这就是索引处理系统. 这个系统大概像下面这样:
(欢迎关注公众号:IT技术精选文摘,微信号:ITHK01)
这幅图能告诉我们什么?
这个组件用于发现、识别、和存储文档.为索引做准备.通常它必须具备以下几个功能:
一般搜索引擎中就是网络爬虫(web cralwer)了. 它负责通过超链接来源源不断地从互联网、文件服务器等信息源中爬取网页、新闻、email、话题等文档.并将这些信息加工后丢进文档数据库中.如上图所示. 爬虫要解决一个更新的问题,因为一个搜索引擎必须拥有对更新或时新的内容进行处理的能力.
对于实时文档流,检测信息如果就能获得更新的消息那再好不过了.RSS就是一种信息源.它用XML来描述.
这里的转换的功能一些也可以丢给文本转换组件. 来自爬虫抓取或者信息源的文档集合,格式很多,比如html、xml、PDF、doc、ppt等,而我们更喜欢纯文本的格式以高效和有效处理.
必须有一个能存储文档及其元数据的地方,否则索引再快,也没东西返回,虽然互联网上的文档可以时时抓取,但离线分析显然更快,这就需要一个文档数据库. 选择关系型数据库(RDBMS)还是NoSQL数据库,根据实际情况来.
这个组件负责将文档转换成为索引项(index term)或特征(feature). 所有词项组成的集合叫作*索引字表(index vocabulary)*.
这个组件负责分词或叫词素切分(tokenizing)和识别词素(tokens). 词素识别可以将文档中的结构化部分切分出来,比如链接、主题、图标等。 不仅是对文档,对查询也要做分词,这样查询和文档才能比较。
一些停用词,比如英文中的to、of、the,中文中的的、吗等,对文档内容贡献不大,但却大量出现。 去除停用词可以在相当的幅度上增加检索效率,但也可能带来错误的搜索结果。 停用词库的大小要斟酌,小了意义不大,大了容易过滤掉很多东西,导致查询的本意被改变或者变得不可读。比如一骗文章叫“论的字在生活中的作用”,去除了“的”之后,就会很囧。
同义词或英文中的派生词处理.
链接是网页内容的重要组成部分.大名鼎鼎的Google就是靠PageRank这种链接分析技术起家. 链接反映了网页内容之间的关系,这类似于图的边. 通过链接抽取和分析算法,可以得出一个页面的重要程度和被关注程度,这一信息可以用来为页面打分或赋予权重. 同时,链接文本可以更有语义地表达链接所指向的内容,这对于页面或文章分类也是有用的信息. 所以
链接分析对搜索结果意义重大.
考虑这样一句话,”搜索引擎是一个技术成熟但实现成本高的应用“,其中“搜索引擎”显然比“搜”、“索”、“引擎”更统一、更整体,对这样的名词短语进行抽取,对返回正确的搜索结果很有意义。 它还处理句法、语法、命名实体识别(named entity ),比如分类公司、人名、地名等。
这个组件用于识别文档中与类别相关(class related)的部分. 比如文档的标签或话题分类,可以是体育、政治或者计算机,甚至是吐槽。 显然,分类是基于有监督学习(supervized learning)的技术,因为实现知道了分类标签,而聚类则用于在一无所知的情况下对文档进行类别划分,比如google news,它就将新闻聚合成不同类别展现给用户.
索引往往比文档本身要小很多,比如lucene中的索引可以达到是原文档的20-30%,同时相对文档来讲更具可比较性。 这个组件必须有以下的能力:
统计、汇总和记录词出现的频率、位置和其它特征等信息。 比如索引项在所有文档中出现的次数,在一组或一类文档中出现的次数,在文档中出现的位置,以及按照词素(tokens)数量统计的文档长度。 处理这些信息的目的是丢给排序组件,排序组件根据这些信息对文档进行打分. 具体需要统计什么是根据排序组件中的检索模型来定,统计结果用一种叫查找表(lookup table)的高效数据结构来保存。
计算索引项(或词项)的权重,词的权重反映了词在文章中的相对重要性,排序算法需要这些信息来为分档进行打分。 具体的权重形式由检索模型决定,加权操作也可以、有时也必须需要查询中的一些信息来确定,所以这个功能的一部分也可以由查询处理系统来提供。但为了查询处理的效率,在索引建立环节需要尽可能多的去计算。
如果用户输入了这样一个查询“我想买玩具”,“我”这个词一般会大量出现在各个文档中,这个词的权重就不应该比“玩具”高,否则将会返回大量的包含“我”的文档,这就是一次不成功的查询。
一般的加权方法主要使用tf.idf:
tf-词频(term frequency)是指索引项在一个文档中出现的频率. idf-逆文档频率(inverse document frequency)是指索引项在所有文档集合中出现的频率. idf=logNn 其中,N是所有文档总数,n是包含某个词项的文档个数.
在上面的例子中,结合idf的公式,可以看出,包含“玩具”这个词的文档数目n一定小于包含“我”这个词的文档数量m,所以“玩具”这个词的权重更高. 权重信息也会放入查找表中。
倒排组件是创建索引组件的核心,因为它事关效率。
倒排是将文档-索引项转换为索引项-文档,如下: (term,doc)=inverse(doc,term)
这个组件的挑战在于如何高效地处理倒排转换过程,应付全量和增量信息的索引建立任务。 同时为了减小索引的大小以提高效率,还会对索引进行压缩(compression)。
通常搜索引擎处理的文档集合非常大 ,那么就必须考虑索引的分布式问题。
document distrubition 为了能够并行的支持创建索引和查询,可以将文档子集的索引表派发到不同的计算机和站点上。 term distrubition 为了能够支持并行的查询,可以讲索引项子集的索引表派发到不同的计算机和站点上。
其它的分布方式还有p2p、复制(replication)等.
查询处理系统主要包含三个构件:用户交互、排序和评价。
(欢迎关注公众号:IT技术精选文摘,微信号:ITHK01)
创建查询、完善查询以及向用户展示结果. 比如,将用户的查询转换为索引项. 并将从搜索引擎得到的有序文档列表组织成搜索结果,展示给用户.
为查询语言(query language)提供接口和解析器。 查询语言一般只有很少的几个操作符,这些操作符指示应该对查询作特殊处理。 比如布尔型操作符,AND、OR和NOT,当然也包括临近操作符(proximity)。 查询语言的作用,一是用来描述更加复杂的查询,二是描述查询转换的结果。
改进初始查询,在生成有序的文档前后提供完善处理。 包括一些文本转换的技术。 比如分词、停用词去除和词干提取,以生成可以和文档的索引项可以匹配的索引项。 拼写检查(spell checking)和查询建议(query suggestion)用于生成和用户查询相似的输出。 查询扩展(query expasion)和相关性反馈(relevance feedback)技术,使用额外的词项来修改初始查询。这些词项的来源,主要是对文档中词项的出现情况、用户认为相关的文档中出现的词项等分析为基础。
对已经排好序的文档结果进行展示。 包括生成文档摘要(snippets)和高亮关键字和关键段落(highlighting)。 另外,也可能包括对文档集进行聚类展示,并添加一些相关的广告。
利用查询和索引生成有序的文档列表. 这个搜索引擎的核心组件,它接收用户查询,并根据检索模型得到一个按分值排好序的文档列表. 排序必须满足高效、优质.
使用评分算法为文档进行评分,这是文档排序的基础。
评分组件是搜索引擎的核心.
一般的评分可描述为:
∑iqidi 其中qi和di分别是第i个查询词项和文档词项的权重. 评分方式依赖于检索模型,检索模型有很多,比如基于BM25、查询似然度的检索模型。
排序的效率对于搜索引擎的表现至关重要,所以需要进行性能优化。 性能优化设计排序算法和索引表的设计等,目的是降低响应延时、提高吞吐率。
一次一词项方式(term-at-a-time) 以词项为单位,先处理词项ti的倒排表,再处理ti+1,需要对每个未处理完的文档建立一个累加器。 一次以文档方式(document-at-a-time) 以文档为单位,先计算文档di,再计算di+1,需要文档在所有倒排表中的顺序一致。 安全方式优化(safe) 优化前后的文档排序结果相同。 非安全方式优化(unsafe) 优化前后的文档排序结果不同。
既然索引是分布式的,那么排序也可以采用分布式方法。 查询代理(query broker)可以将多个用户查询分发到不同的计算节点,并负责聚合各个计算节点的处理结果。 缓存(cache)也是一种分布式的方式,如果将前一个用户的查询结果保存在内存中,那么如果有其他用户使用类似的查询,将可直接从缓存中返回结果,这大大提高了查询的效率。
评价和监测搜索的质量和性能. 其中,利用日志系统来记录用户行为,并对其进行分析以优化搜索. 可以看出,评价系统会对排序系统做出改善和调整. 显然,评价系统是滞后的,所以一般它作为离线系统的一部分.
记录用户搜索行为日志,对于改进排序和查询处理意义重大。 用户的查询日志,可以作为拼写检查、查询推荐、查询缓存等任务的基础。 精准广告技术就依赖于用户的搜索行为分析。
用户对查询结果的处理方式可以用来反映文档对于用户查询是否是相关的。 如果用户在搜索引擎返回的排序文档中,点击了其中一个,那么这个文档可能就是和用户查询相关性比较高的一个。 同时,跟踪用户的点击流和页面驻留时间,可以用来评价和训练排序算法。
评价和改善搜索的有效性。 通过大量的查询-文档对,结合查询日志,可以判定一个排序算法的结果,用于和其它算法进行比较,以确定更优化的参数等来改善排序结果。
评价和改善搜索的效率。 监测和收集系统运行的性能指标。如响应时间、吞吐量、网络延时等等。
(完)
出处:http://www.cnblogs.com/foreach-break
版权申明:内容来源网络,版权归原创者所有。除非无法确认,我们都会标明作者及出处,如有侵权烦请告知,我们会立即删除并表示歉意。谢谢。