Search Engines: Information Retrieval in Practice - 第2章

第2章:Architecture of a Search Engine (搜索引擎的整体结构)

1、搜索引擎的两个目标:Effectiveness(效果quality)和Efficienct(性能speed)。

2、搜索引擎的组成
(1) Indexing Process (建索引)
包括:
Text Acquistion (文档获取),典型的有:Crawling (爬虫), Metadata (元信息抽取)。
Text Transformation (文档转换),主要是:把获取的文档转化为Terms (词项),Features (属性,如姓名、日期等)。这之中就要涉及到分词、Stemming等。
Index Creation (建索引),建索引需要高效,且支持高效的更新。数据结构主要是Inverted indexes (倒排索引)和inverted files (倒排文件)。

(2) Query Process (查询处理)
包括:
User Interaction (交互),前交互:按照Text Transformation的处理,将Query转化为Index terms,之后交给Ranking。后交互:Ranking后,按照文档List,生成Snippet (摘要)、Highlight (高亮)等。
Ranking (排序),搜索引擎的核心。根据检索模型,给所有文档按照公式打分,并排序,返回。性能依赖于文档,效果依赖于检索模型。
Evaluation (评价),在实际中,评价依赖于User Log中的反馈。它可以对搜索效果进行反馈,并帮助不断改进搜索效果。

3、Text Acquisition (文档获取)
Crawler (爬虫)
最常见的是Web Crawler,它不仅要保证爬去性能,还需要考虑及时获取网页的更新
主题爬虫Focused Crawler/ Topical Crawler,使用分类等方法,只爬去某个主题的网页,常见于垂直搜索
在桌面搜索、企业搜索等应用范畴,爬去的范围不限于网页,也可能是文档、邮件、甚至通信录。

Feeds (订阅)
Crawler是一个Poll的过程,而Feeds则提供了一种类似Push的订阅过程。常见于博客、新闻等频道的RSS订阅。订阅可以确保我们及时获取更新。

Conversion (转化)
如上面所述,我们爬到的一般都不是纯文本,以HTML、WORD、PDF等结构化文档居多。此时就需要抽取、转化格式等。另外,编码问题是很头疼的问题,一般要将编码统一为UTF-8,而不规范的HTML,往往导致错误的编码识别。

Document data store (文档存储)
文档服务器压缩存储了文档的各个部分,如元信息、抽取的文本,标题,锚文本等。RDBMS是一个选择,但面对海量数据,一般都会有自己的存储系统,如NoSQL集群。当然对企业搜索、桌面搜索等应用,由于获取文档很快,就不需要单独存储了。

4、Text Transformation
Parser (解析、抽取)
Tokenizing (分词),是把文档转化为Term的过程。英文分词最简单的是按空格分开,而中文就没这么简单了。另外对于标点等细节问题,也是要考虑的。此外,还要按照HTML、XML的格式解析。

Stopping (停用词)
选取适当的停用词表,可以极大的减小索引体积,如the、a等DF超高的词。但是Google等大型搜索引擎,更倾向于不使用停用词,以防某些特殊Query:“To be or not to be”。

Stemming (词干还原/归一化)
顾名思义,就是把同词根衍生出来的词归一化,如fish, fishes, fising。适当的规则可以提升检索性能,但也会降低在某些Query下的准确性。Stemming主要用于西文,在中文词干还原是无效的。

Link extraction and analysis (链接抽取/分析)
从HTML中,可以比较容易的抽取出链接。搜索引擎广泛的采用了Link Analysis (链接分析算法),如PageRanks,HITS。锚文本也可以显著提升检索效果。

Information extraction (信息识别)
不在局限于对词的研究,而是分析其予以,进行named entity (命名实体)识别,如识别出电话、公司名称、日期、地点等。

Classifier (分类)
将文档分类,打上标签,如运动、政治等。典型的应用如Faceting Search、Spaming识别。

 5、Index Creation
Document statistics (文档统计信息)
在建索引的过程中,记录下Term、Feature、Document的统计信息。比如词频,词位置、DF,文档长度等。

Weighting (权重)
实际是为Query时计算权重做准备。最常见的是基于tf-idf的权重计算。tf就是词频,idf是在所有文档中出现频率的倒数。

Inversion (反转/倒置)
创建倒排索引的过程,即倒置:将从docs->terms转化为terms->docs。性能非常重要。此外,索引文件格式将影响查询性能,比如各种压缩和优化

Index Distribution (分布式索引)
要索引的文档会很多,单机索引往往扛不住,需要进行分布式索引。即将索引分布式到若干机器上,并行建索引/检索。为了进一步提高性能,还可以对单个索引做Replication,提高并发性。

6、User Interaction
Query input (Query输入)
每个搜索系统都有Query Language (查询语法),包含Operators (操作符,如AND/OR/NOT),Web Search Engine常见的就是一些Keywords组成的,没有语法。近年来,也有人探讨过SQL query language,但是效果不好。

Query Transformation (Query转化)
为了能匹配Index中的Term,必须做同样地Tokenizing, Stopping, stemming。此外,Spell checking (拼写检查)、Query suggestion (查询建议)等,有助于提升检索效果。而基于Query Log分析的Query expansion (查询拓展)会添加某些Term以提高精确率。Relvance feedback (相关反馈)根据用户反馈(如Query Log是否点击、停留时间)而判断出检出的结果是否相关,从而做出进一步反馈,以提升检索效果。

Results output (结果输出)
在Ranking之后展示输出结果:生成snippets (摘要),highlighting (高亮),必要的话,翻译多语言。

 7、Ranking (打分、排序)
Scoring (打分)
打分也称为Query Processing,计算文档的Ranking得分,并按照此进行排序。
权重模型:Σqi·di,i为每个Query中包含的词数量。qi是查询中第i个词对应的权重,di是文档中第i个词对应的文档权重。具体的qi和di计算方法,可以有VSM的、概率模型的BM25、语言模型的likeihood (查询似然)

Performance Optimization (性能优化)
关于如何计算得分,有term-at-a-time和document-at-a-time两种,没太读明白。Ranking算法需要不断的优化,以提升响应时间和查询吞吐量。Safe优化能保证与优化前一致,Unsafe优化无法保证与之前一致,速度要稍快。

Distribution (分布式)
与Index Distribution一样,查询也是分布式的。Query Broker将Query分发到N个索引上,然后收集所有结果,整理出最终结果。Cache将最近的查询结果放到内存中,提升性能。

8、Evaluation (评价)
Logging (日志)
用户的Query Log是重要的分析数据来源。例如用户是否点击、用户的停留时间。

Ranking Analysis (排序分析)
根据用户数据,分析相关性排序是否合理,并以此改进Ranking算法。

Performance Analysis (性能分析)
throghput (吞吐)、 response time (响应时间)

 

Leave a Reply

Your email address will not be published. Required fields are marked *