04 November 2017

前言

搜索引擎解决的问题是什么?帮助用户快速获取所需数据?如果仅仅是这样,很多情况下关系型数据库如mysql就已经满足所需了:支持大数据存储,支持基于查询条件构建索引上的高性能查询,支持索引实时更新及事务性。换个角度想,已经有了mysql这种神器,为何还需要使用Elasticsearch?

数据模型

解决问题的方式,还是得回到自己的数据模型中。通常文档数据被分为以下几类:

  • 结构化数据,文档中的每个字段都有固定的类型和长度,mysql面向的就是此类数据。
  • 非结构化数据,与结构化数据相反,文档可能是字符串,也可能是二进制,长度不固定,典型的如邮件内容,网页内容等。
  • 半结构化数据,这种是指文档中部分字段是结构化的,部分是无类型无长度的。比如xml格式数据,html格式数据,json数据。

从应用层来看,数据获取根据以上数据模型可以分成以下几类:

  • 结构化数据查询,根据查询条件扫描候选数据,单纯地进行是布尔型过滤,匹配则加入到结果集,否则跳过。
  • 非结构化数据检索,认为所有数据都符合条件,但针对每条数据,根据其匹配程度进行打分,分数越高则相关性更高,越有可能出现在搜索结果前面。
  • 半结构化数据的查询检索,这种文档的应用其实更加灵活,针对文档的部分字段进行检索,同时针对部分字段进行过滤,过滤结果不进行打分。

从检索底层来看,数据其实都是结构化的。针对在海量文本中搜索某个关键字这种需求,不可能循环扫描所有文档,然后对文档内容进行逐一匹配。传统的结构化数据方式实现不了,但有需求就要解决,而且百度、谷歌都已经解决了这种问题。那么他们是怎么解决的呢?把非结构化文档进行拆分成一个个单词,形成结构化文档。搜索基于这些单词进行,拆分后单词组形成了一个字典目录,指向包含这个词的文档,这就我们常说的索引。

全文本(full-text)搜索

search

如上图所示(图片来自此处),搜索引擎的核心有三点:

  • 索引建立及存储
  • 索引查询
  • 结果集排序优化

下面简要提一下这三点涉及到的知识点。

索引建立及存储

索引的建立主要包括文档的预处理、根据词法语法分词、停用词过滤,索引存储等。实现索引存储最重要的数据结构是倒排表,而实现倒排表又会用到有限状态转移机,跳跃表这两个数据结构。

倒排是相对正排列来说的,在这里正排是文档到分词的排列,而倒排则是分词到文档的排列,如下图所示: index table

inverted index table

图片很直观,如果用代码去实现,使用数组+链表就行了,但考虑到海量数据情况下词典对内存的占用及文档检索效率的性能要求,仅有数组和链表是不够的。这时候会有更高端数据结构来代替,比如lucene里,数组使用fst数据结构实现,链表用skiplist实现,关于这两个数据结构详情,可以自己搜索相关文档了。

索引查询

同建立索引时对文档进行词法语法分析、分词过滤等一样,待检索的语句(query)也会被分割成多个词(term),针对每个词,查询倒排表,然后对匹配结果进行合并。一般搜索引擎支持多样的查询语法,如:

a and b # 查询同时包含关键字a和关键字b的文档
a or b # 查询包含关键字a或者关键字b的文档
a and not b # 查询包含关键字a,但不包含关键字b的文档

结果集排序优化

查询到匹配记录后,不能直接返回给用户,因为每个文档的匹配程度不一样,如果不加以干预,可能导致完全匹配的文档排在部分匹配的文档后面。因此对符合条件的文档,需要根据其相关性进行排序。什么是相关性呢?如何衡量一个文档的相关性呢?这里不得不提两个概念:

  • tf,全称term frequency,一个词在一篇文档出现的次数除以此篇文档所有词数量,一个词出现的越多,则认为越重要。
  • idf,全称inverted document frequency,出现一个词的文档数量除以全部文档数量,一个词。出现的越多,则认为越不重要。

有了这两个数字后,就可以计算一个词的权重了,有如下公式:

tf-idf

得到词的权重后,就可以计算文档之间的相关性了。有两种比较常见的算法:向量空间模型Okapi_BM25。具体实现参考文档即可。

上面谈了全文本搜索的基本原理,接下来聊聊如何正确使用ELasticsearch,下一篇文档见。

参考

1、全文检索的基本原理

2、Search in depth