你的位置:首页 > 数据库

[数据库]全文检索基本概念


1.分词

全文检索必须要分词,所谓分词就是把一句话切分成一个个单独的词。分词有很多算法,比如自然分词、n-gram分词、字典分词等等。对中文来说没有自然分隔符,一般采用字典分词,再加上对人名、地名的特殊处理,提高分词的准确性。

我们使用ik分词组件,ik有两种分词策略:smart策略、max word策略。

例如这个句子:

1939年的德国,9岁的小女孩莉赛尔和弟弟被迫送往慕尼黑远郊的寄养家庭。6岁的弟弟不幸死在了路途中。在冷清的葬礼后,莉赛尔意外得到她的第一本书《掘墓人手册》。

 看一下分词的结果,先看smart策略:

1939年/德国/9岁/小女孩/莉/赛/尔/和/弟弟/被迫/送往/慕尼黑/远郊/寄养/家庭/6岁/弟弟/不幸/死/路/途中/冷清/葬礼/后/莉/赛/尔/意外/得/到她/第一/本书/掘墓人/手册

 

Elasticsearch支持分词接口,比如这个接口:

http://localhost:9200/index/_analyze?text=1939年的德国&analyzer=ik_smart

可以执行一个分词计算,使用的分词器是ik_smart。在分词结果中可以看到每个词的位置和类型。 

句子按照中文语法被分割成一个个词,仔细观察一下可以看到两个现象:

1. 标点符号都不见了
2. 少了一些字,比如“的”、“在”、“了”

这个处理叫做“预处理”,预处理过程会去掉句子中的符号、停止词(stop word),这两种元素在检索中没有什么作用,对排序还会造成很大的干扰,在索引的时候就被去除掉了。

对于英文等西方文字,由于词之间存在自然分割,所以分词的难度低,准确性高。拼音文字一般存在单复数、时态、词性等词尾的变化,比如make、made、makes,索引的时候还需要做词形变换,全部处理成原型。

从分词结果中还可以看到,一些分词结果不准确,比如“1939年”、“得/到她”,因为分词不准确,当用户搜索“1939”、“得到”就检索不到这个文档,尽管文档中出现了这些词。还有“莉/赛/尔”,ik不能识别这个词,分割成了三个独立的字。如果用户搜索“赛莉尔”,也能搜出文档。

为了避免分词不准确影响召回率的情况,可以使用max word策略:

1939/年/德国/9/岁/小女孩/小女/女孩/莉/赛/尔/和/弟弟/被迫/迫/送往/慕尼黑/慕/尼/黑/远郊/郊/寄养/寄/养家/家庭/家/庭/6/岁/弟弟/不幸/死/路途/途中/途/中/冷清/冷/清/葬礼/葬/礼/后/莉/赛/尔/意外/得到/到她/第一本/第一/一本书/一本/一/本书/本/书/掘墓人/墓/人手/手册/册

max word多分出了很多词,这样就增加了检索的召回率,但是正确率有所降低,也增加了索引的体积。

我们的策略是:对fulltext字段使用max_word分词策略进行索引。term检索不对查询词做分词处理,输入什么词就检索什么词。match_query检索对查询词用smart策略。span_near_query检索对查询词使用max_word策略,确保分词结果一致。这样做准确率和召回率都比较合适。

2.反向索引

反向索引也叫倒排索引,存储了词在文档中的位置。比如有下面三个文档,已经做好了分词:

doc1: A/BC/D/EF
doc2: BC/D/XY/Z/Z
doc3: BC/E/MN/XY

首先统计这三个文档中出现的所有的词,给这些词编号,并且统计词频:

编号词频
A11
BC23
D32
EF41
XY52
Z62
E71
MN81

然后统计这些词出现在哪些文档中,以及出现的位置:

词编号文档和位置
1(doc1,0)
2(doc1,1),(doc2,0),(doc3,0)
3(doc1,2),(doc2,1)
4(doc1,3)
5(doc2,2),(doc3,3)
6(doc2,3,4)
7(doc3,1)
8(doc3,2)

 这样反向索引就建立起来了。现在进行检索,输入“BDC”。首先对输入条件进行分词,得到“BC/D”,分别检索BC和D的集合,查反向索引:

{doc1, doc2, doc3} AND {doc1, doc2} = {doc1, doc2}

得到搜索结果集合doc1和doc2。

Elasticsearch是一个分布式的全文检索数据库,封装了Lucene的功能,倒排索引的功能是在Lucene中实现的。Lucene的数据目录中保存的就是倒排索引数据,包括了词典和文档数据,压缩存储。Lucene的索引是分域存储的,比纯粹的文本索引复杂的多,具体的原理可以看Lucene代码。

3.排序

把关键词从文档的海洋中检索出来只是万里长征走完了第一步,后面还有一件更重要、难度也更大的事情:排序。对于海量数据来说,排序不合理和检索不正确造成的后果其实没有多大的区别(甚至要更严重,个人观点)。

Lucene默认的排序方式是根据关键词文档相关性,默认的算法是TF-IDF。TF词频(Term Frequency),IDF逆向文件频率(Inverse Document Frequency)。

具体的公式这里就不写了,维基百科上有个例子,https://zh.wikipedia.org/wiki/TF-IDF,这里说明一下:

首先计算单词的TF-IDF:假如一篇文件的总词语数是100个,而词语“母牛”出现了3次,那么“母牛”一词在该文件中的词频就是3/100=0.03。一个计算文件频率(DF)的方法是测定有多少份文件出现过“母牛”一词,然后除以文件集里包含的文件总数。所以,如果“母牛”一词在1,000份文件出现过,而文件总数是10,000,000份的话,其逆向文件频率就是log(10,000,000 / 1,000)=4。最后的TF-IDF的分数为0.03 * 4=0.12。

再计算关键词与文档的相关性:根据关键字k1,k2,k3进行搜索结果的相关性就变成TF1 * IDF1 + TF2 * IDF2 + TF3 * IDF3。比如document1的term总量为1000,k1,k2,k3在document1出现的次数是100,200,50。包含了k1, k2, k3的document总量分别是 1000,10000,5000。document set的总量为10000。 TF1 = 100/1000 = 0.1 TF2 = 200/1000 = 0.2 TF3 = 50/1000 = 0.05 IDF1 = In(10000/1000) = In (10) = 2.3 IDF2 = In(10000/10000) = In (1) = 0; IDF3 = In(10000/5000) = In (2) = 0.69 这样关键字k1,k2,k3与document1的相关性 = 0.1 * 2.3 + 0.2 * 0 + 0.05 * 0.69 = 0.2645 其中k1比k3的比重在document1要大,k2的比重是0.

这是理论上的相关性算法,实际上可以根据其他因素来修正。比如Google的page rank算法,会提前根据连接数和引用数算出网页的page rank得分,计算关键词相关性的时候还会考虑关键词在网页上出现的位置(title、meta、正文标题、正文内容、侧边栏等等),给出不同的相关度。也可以根据某个业务属性强制排序(比如create_time等等)。

Elasticsearch是一个分布式的Lucene,排序工作实际上是Lucene做的,Elasticsearch做了一个分步执行、集中排序。

4.检索方式

4.1 term检索

term检索的条件写法,用SQL表达就是:

SELECT * FROM index/type WHERE status='yes'

term是不分词检索,也就是对检索条件不分词。所以一般对非文本字段、不分词的文本字段使用这样的检索。对分词文本字段用term检索要慎重。比如对这样的文档:

fulltext: AB/CD/E/FG

如果用term检索:

WHERE fulltext='CDE'

由于文档的fulltext字段中不存在“CDE”这个词,所以检索不到文档。

4.2 matchQuery检索

matchQuery条件写法:

SELECT * FROM index/type WHERE fulltext=matchQuery('ABE')

matchQuery是分词检索,先对检索条件进行分词,得到“AB/E”,然后寻找fulltext中同时包含“AB”和“E”的文档。我们对fulltext进行ik max word分词,matchQuery使用ik smart分词,这样能够最大限度的避免分词不准确对效果的影响。

4.3 spanNearQuery检索

spanNearQuery条件写法:

SELECT * FROM index/type WHERE fulltext=spanNearQuery('ABE')

spanNearQuery是分词检索,同时要求条件在文档中一定要连续出现。所以spanNearQuery要求索引和检索一定要使用完全相同的分词策略。比如对“远郊寄养家庭”,分词后是“远郊/郊/寄养/寄/养家/家庭/家/庭”,如果检索条件是:

WHERE fulltext=spanNearQuery('寄养家庭')

搜索时先对条件使用同样的分词策略,然后判断fulltext中是否连续出现搜索词。

4.4 query检索

query条件写法:

SELECT * FROM index/type WHERE fulltext=query('chin*')

query也是分词检索,首先在字典中寻找符合“chin*”通配符的词,比如“china”、“chinese”等等。然后寻找含有任一词的文档。

5.自定义词典

ik分词组件使用词典分词,可以修改词典定义提高分词的准确性。

ik组件可以使用自定义词典,配置文件:/server/elasticsearch/config/ik/IKAnalyzer.cfg.

<?<!DOCTYPE properties SYSTEM "http://java.sun.com/dtd/properties.dtd">
<properties>
  <comment>IK Analyzer 扩展配置</comment>
  <!--用户可以在这里配置自己的扩展字典 -->
  <entry key="ext_dict">custom/mydict.dic;custom/single_word_low_freq.dic</entry>
  <!--用户可以在这里配置自己的扩展停止词字典-->
  <entry key="ext_stopwords">custom/ext_stopword.dic</entry>
  <!--用户可以在这里配置远程扩展字典 -->
  <entry key="remote_ext_dict">http://localhost/ext_dict.php</entry>
  <!--用户可以在这里配置远程扩展停止词字典-->
  <entry key="remote_ext_stopwords">http://localhost/ext_stopwords.php</entry>
</properties>

修改本地词典和停止词文件,需要在每个Elasticsearch节点上修改文件,修改后重启。

使用远程字典可以集中维护字典文件,并且不需要重启Elasticsearch。ik每分钟向远程地址发出请求,请求有一个“If-Modified-Since”消息头。如果字典没有变动,返回“304 Not Modified”,ik不会更新字典。如果字典内容有变动,返回字典内容和新的“Last-Modified”,ik更新字典。