分享

阿里面试宝典(五):搜索引擎

本帖最后由 levycui 于 2020-11-24 20:03 编辑
问题导读:
1、搜索引擎有哪些特点(优势)?
2、搜索引擎使用到哪些场景中?
3、如何将原文档传给分次组件?
4、如何将得到的词(Term)传给索引组件(Indexer)?



上一篇:阿里面试宝典(四):消息队列

搜索引擎

概述
全文搜索就是对文本数据的一种搜索方式,文本数据的都多,可以分为顺序搜索法和索引搜索法,,全文检索使用的是索引搜索法

特点(优势):
  • 做了相关度排序
  • 对文本中的关键字做了高亮显示
  • 摘要截取
  • 只关注文本,不考虑语义
  • 搜索效果更加精确——基于单词搜索,比如搜索Java的时候找不到JavaScript,因为它们是不同的两个单词


使用场景:
  • 替换数据库的模糊查询,提高查询速度,降低数据库压力,增强了查询效率
  • 数据库模糊查询缺点:查询速度慢,左模糊和全模糊会使索引失效,没有相关度排序,没有对文本中关键字
  • 做高亮显示,搜索效果不好
  • 全文检索是搜索引擎的基础
  • 只对“指定领域”的网站进行索引和搜索,即垂直搜索
  • 可以在word、pdf等各种各样的数据格式中检索内容
  • 其他场合,比如输入法等


倒排索引
正向索引的结构如下:
“文档1”的ID > 单词1:出现次数,出现位置列表;单词2:出现次数,出现位置列表;…………。
“文档2”的ID > 此文档出现的关键词列表。

2020-11-24_200518.jpg
当用户在主页上搜索关键词“华为手机”时,假设只存在正向索引(forward index),那么就需要扫描索引库中的所有文档,找出所有包含关键词“华为手机”的文档,再根据打分模型进行打分,排出名次后呈现给用户。因为互联网上收录在搜索引擎中的文档的数目是个天文数字,这样的索引结构根本无法满足实时返回排名结果的要求。
所以,搜索引擎会将正向索引重新构建为倒排索引,即把文件ID对应到关键词的映射转换为关键词到文件ID的映射,每个关键词都对应着一系列的文件,这些文件中都出现这个关键词。

得到倒排索引的结构如下:
“关键词1”:“文档1”的ID,“文档2”的ID,…………。
“关键词2”:带有此关键词的文档ID列表。

2020-11-24_200557.jpg

创建索引
全文检索的索引创建过程一般有以下几步:
一些要索引的原文档(Document)
为了方便说明索引创建过程,这里特意用两个文件为例:
文件一:Students should be allowed to Go out with their friends, but not allowed to drink beer.
文件二:My friend Jerry went to school to see his students but found them drunk which is not allowed.

将原文档传给分次组件(Tokenizer)
分词组件(Tokenizer)会做以下几件事情( 此过程称为Tokenize) :
1. 将文档分成一个一个单独的单词。
2. 去除标点符号。
3. 去除停词(Stop word) 。
所谓停词(Stop word)就是一种语言中最普通的一些单词,由于没有特别的意义,因而大多数情况下不能成为搜索的关键词,因而创建索引时,这种词会被去掉而减少索引的大小。
英语中挺词(Stop word)如:“the”,“a”,“this”等。
对于每一种语言的分词组件(Tokenizer),都有一个停词(stop word)集合。
经过分词(Tokenizer) 后得到的结果称为词元(Token) 。
在我们的例子中,便得到以下词元(Token):
“Students”,“allowed”,“go”,“their”,“friends”,“allowed”,“drink”,“beer”,“My”,“friend”,“Jerry”,“went
”,“school”,“see”,“his”,“students”,“found”,“them”,“drunk”,“allowed”。


将得到的词元(Token)传给语言处理组件(Linguistic Processor)
语言处理组件(linguistic processor)主要是对得到的词元(Token)做一些同语言相关的处理。
对于英语,语言处理组件(Linguistic Processor) 一般做以下几点:
1. 变为小写(Lowercase) 。
2. 将单词缩减为词根形式,如“cars ”到“car ”等。这种操作称为:stemming 。
3. 将单词转变为词根形式,如“drove ”到“drive ”等。这种操作称为:lemmatization 。

Stemming 和 lemmatization的异同:
相同之处:Stemming和lemmatization都要使词汇成为词根形式。

两者的方式不同:
Stemming采用的是“缩减”的方式:“cars”到“car”,“driving”到“drive”。
Lemmatization采用的是“转变”的方式:“drove”到“drove”,“driving”到“drive”。

两者的算法不同:
Stemming主要是采取某种固定的算法来做这种缩减,如去除“s”,去除“ing”加“e”,将“ational”变为“ate”,将“tional”变为“tion”。

Lemmatization主要是采用保存某种字典的方式做这种转变。比如字典中
有“driving”到“drive”,“drove”到“drive”,“am, is, are”到“be”的映射,做转变时,只要查字典就可以了。
Stemming和lemmatization不是互斥关系,是有交集的,有的词利用这两种方式都能达到相同的转换。
语言处理组件(linguistic processor)的结果称为词(Term) 。

在我们的例子中,经过语言处理,得到的词(Term)如下:
“student”,“allow”,“go”,“their”,“friend”,“allow”,“drink”,“beer”,“my”,“friend”,“jerry”,“go”,“schoo
l”,“see”,“his”,“student”,“find”,“them”,“drink”,“allow”。
也正是因为有语言处理的步骤,才能使搜索drove,而drive也能被搜索出来。


将得到的词(Term)传给索引组件(Indexer)
索引 组件(Indexer)主要做以下几件事情:
1. 利用得到的词(Term)创建一个字典。
在我们的例子中字典如下:
2020-11-24_200756.jpg
2020-11-24_200810.jpg

2. 对字典按字母顺序进行排序。
2020-11-24_200904.jpg
2020-11-24_200919.jpg

3. 合并相同的词(Term) 成为文档倒排(Posting List) 链表。
2020-11-24_201010.jpg
在此表中,有几个定义:
  • Document Frequency 即文档频次,表示总共有多少文件包含此词(Term)。
  • Frequency 即词频率,表示此文件中包含了几个此词(Term)。
所以对词(Term) “allow”来讲,总共有两篇文档包含此词(Term),从而词(Term)后面的文档链表总共有两项,第一项表示包含“allow”的第一篇文档,即1号文档,此文档中,“allow”出现了2次,第二项表示包含“allow”的第二个文档,是2号文档,此文档中,“allow”出现了1次。
到此为止,索引已经创建好了,我们可以通过它很快的找到我们想要的文档。

而且在此过程中,我们惊喜地发现,搜索“drive”,“driving”,“drove”,“driven”也能够被搜到。因为在我们的索引中,“driving”,“drove”,“driven”都会经过语言处理而变成“drive”,在搜索时,如果您输入“driving”,输入的查询语句同样经过我们这里的一到三步,从而变为查询“drive”,从而可以搜索到想要的文档。


最新经典文章,欢迎关注公众号



没找到任何评论,期待你打破沉寂

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

推荐上一条 /5 下一条