ElasticSearch 2 (17) - 深入搜索系列之部分匹配
摘要
到目前为止,我们介绍的所有查询都是基于完整术语的,为了匹配,最小的单元为单个术语,我们只能查找反向索引中存在的术语。
但是,如果我们想匹配部分术语而不是全部改怎么办?部分匹配(Partial matching) 允许用户指定查找术语的一部分,然后找出所有包含这部分片段的词。
与我们想象的不一样,需要对术语进行部分匹配的需求在全文搜索引擎的世界并不常见,但是如果读者有SQL方面的背景,可能会在某个时候使用下面的SQL语句对全文进行搜索:
WHERE text LIKE "%quick%"
AND text LIKE "%brown%"
AND text LIKE "%fox%" #1
- #1 *fox* 会与 “fox” 和 “foxes” 匹配
当然,在ElasticSearch中,我们有分析过程,反向索引让我们不需要使用这种蛮力。为了解决同时匹配“fox”和“foxes”的应用场景,我们只需要简单的将它们的词干作为索引形式,不需要做部分匹配。
有人说,在某些情况下部分匹配会比较有用,这些应用场景如下:
- 匹配邮编,产品序列号,或其他未分析(not_analyzed)值,它们可以是以某个特定前缀开始,可以是与某种模式匹配,也可以是与某个正则式相匹配。
- 输入即查询——在用户输入搜索术语的时候就向用户呈现最可能的结果。
- 匹配如德语或荷兰语这样的语言,他们有很长的组合词,如:Weltgesundheitsorganisation (World Health Organization) 世界卫生组织。
我们的介绍会始于一个not_analyzed准确值字段的前缀匹配。
版本
elasticsearch版本: elasticsearch-2.x
内容
邮编与结构化数据(Postcodes and Structured Data)
我们会使用美国的邮编(UK postcodes)来说明如何用部分匹配查询结构化数据。这种格式的邮编有着良好的结构定义。例如,邮编 W1V 3DG 可以分解为:
-
W1V:这是邮编的外部,它定义了邮件的区域和行政区:
- W 代表区域(1或2个字母)
- 1V 代表行政区(1或2个数字,可能跟着一个字符)
-
3DG:内部定义了街道或建筑:
- 3 代表街区区块(1个数字)
- DG 代表单元(2个字母)
我们假设将邮编作为 not_analyzed 的准确值字段索引,我们可以为其创建索引:
PUT /my_index
{
"mappings": {
"address": {
"properties": {
"postcode": {
"type": "string",
"index": "not_analyzed"
}
}
}
}
}
然后索引一些邮编:
PUT /my_index/address/1
{ "postcode": "W1V 3DG" }
PUT /my_index/address/2
{ "postcode": "W2F 8HW" }
PUT /my_index/address/3
{ "postcode": "W1F 7HW" }
PUT /my_index/address/4
{ "postcode": "WC1N 1LZ" }
PUT /my_index/address/5
{ "postcode": "SW5 0BE" }
现在这些数据可供查询了。
前缀查询(prefix Query)
为了找到所有以 W1 开始的邮编,我们可以使用简单的前缀查询:
GET /my_index/address/_search
{
"query": {
"prefix": {
"postcode": "W1"
}
}
}
前缀查询是一个术语级别的低层次的查询,在搜索之前它不会分析查询字符串,它认为传入的前缀就是想要查找的前缀。
默认状态下,前缀查询不做相关度分数计算,它只是将所有匹配的文档返回,然后赋予所有相关分数值为1。它的行为更像是一个过滤器而不是查询。两者实际的区别就是过滤器是可以被缓存的,而前缀查询不行。
之前我们提到过:“我们只能找到反向索引中存在的术语”,但是我们并没有对这些邮编的索引做特殊处理,每个邮编还是以它们准确值的方式存在于每个文档的索引中,那么前缀查询是如何工作的呢?
回想反向索引包含了一个有序的唯一的术语列表(这个例子中是邮编),对于每个术语,反向索引都会将包含术语的文档ID列入 关联列表(postings list)。与我们例子对于的反向索引是:
Term: Doc IDs:
-------------------------
"SW5 0BE" | 5
"W1F 7HW" | 3
"W1V 3DG" | 1
"W2F 8HW" | 2
"WC1N 1LZ" | 4
-------------------------
为了支持前缀匹配,查询会做以下事情:
- 扫描术语列表并查找到第一个以 W1 开始的术语。
- 搜集关联的ID
- 移动到下一个术语
- 如果这个术语也是以 W1 开头,查询跳回到第二步再重复执行,直到下一个术语不以 W1 为止。
这对于小的例子当然可以正常工作,但是如果我们的反向索引中有数以百万的邮编都是以 W1 开头时,前缀查询则需要访问每个术语然后计算结果。
前缀越短需要访问的术语越多,如果我们要以 W 作为前缀而不是 W1,那么就可能需要做千万次的匹配。
前缀查询或过滤对于一些特定的匹配非常有效,但是使用时还是需要当心,当字段的术语集合很小时,我们可以放心使用,但是它的伸缩性并不好,会对我们的集群带来很多压力。可以使用较长的前缀来减小这种压力,这样可以大大减少需要访问的术语数量。
后面我们会介绍一个索引时的解决方案让前缀匹配更高效,不过在此之前,我们需要先看看两个相关的查询:模糊(wildcard) 和 正则(regexp)查询。
模糊查询与正则式查询(wildcard and regexp Queries)
与前缀查询的特性类似,模糊(wildcard)查询也是一种低层次基于术语的查询,与前缀查询不同的是它可以让我们给出匹配的正则式。它使用标准的 shell 模糊查询:? 匹配任意字符,* 匹配0个或多个字符。
这个查询会匹配包含 W1F 7HW 和 W2F 8HW 的文档:
GET /my_index/address/_search
{
"query": {
"wildcard": {
"postcode": "W?F*HW" #1
}
}
}
- #1 ? 匹配 1 和 2,* 与空格以及 7 和 8 匹配。
如果现在我们只想匹配 W 区域的所有邮编,前缀匹配也会匹配以 WC 为开始的所有邮编,与模糊匹配碰到的问题类似,如果我们只想匹配以 W 开始并跟着一个数字的所有邮编,正则式(regexp)查询让我们能写出这样更复杂的模式:
GET /my_index/address/_search
{
"query": {
"regexp": {
"postcode": "W[0-9].+" #1
}
}
}
- #1 这个正则表达式要求术语必须以 W 开头,紧跟0至9之间的任何一个数字,然后跟着1或多个其他字符。
模糊和正则查询与前缀查询的工作方式一样,他们也需要扫描反向索引中的术语列表才能找到所有的匹配术语,然后依次获得每个术语相关的文档ID,它与前缀查询唯一的不同是:它能支持更为复杂的匹配模式。
这也意味着我们需要注意与前缀查询中相同的性能问题,执行这些查询可能会消耗非常多的资源,所以我们需要避免使用左模糊这样的模式匹配(如,*foo 或 .foo* 这样的正则式)
依靠数据在索引时的准备可以帮助我们提高前缀匹配的效率,但是只能在查询时处理模糊匹配和正则表达式查询,虽然这些查询有他们的应用场景,但仍需谨慎使用。
注意
prefix、wildcard 和 regrep 查询是基于术语操作的,如果我们用它们来查询分析过的字段(analyzed field),他们会检查字段里面的每个术语,而不是将字段作为整体进行处理。
例如,我们说 title 包含 “Quick brown fox”会生成术语:quick、brown 和 fox。
下面这个查询会匹配:
{ "regexp": { "title": "br.*" }}
但是下面这两个查询都不会匹配:
{ "regexp": { "title": "Qu.*" }} #1
{ "regexp": { "title": "quick br*" }} #2
- #1 在术语表中存在的是 quick 而不是 Quick
- #2 quick 和 brown 在术语表中是分开的。
查询时输入即搜索(Query-Time Search-as-You-Type)
先把邮编的事情放一边,让我们先看看前缀查询是如果在全文查询中起作用的。用户已经渐渐习惯在他们输入查询内容的时候,搜索的结果就能展现在他们面前,这就是所谓的即时搜索(instant search)或 输入即搜索(search-as-you-type),不仅用户能在更短的时间内得到搜素结果,我们也能引导用户搜索我们索引中存在的结果。
比如,如果用户输入 johnnie walker pl,我们希望在用户结束搜索输入前就能得到结果:Johnnie Walker Black Label 和Johnnie Walker Blue Label。
就像猫的花色远不只一种,我们希望找到一个最简单的实现方式。我们并不需要对数据做任何准备,我们在查询时,就能对任意的全文字段实现 search-as-you-type 的查询。
在短语匹配(Phrase Matching)中,我们引入了 match_phrase 查询,它匹配相对顺序一致的所有文档,查询时的输入即搜索(search-as-you-type),我们可以使用 match_phrase 的一种特殊形式,即 match_phrase_prefix 查询:
{
"match_phrase_prefix" : {
"brand" : "johnnie walker bl"
}
}
这种查询的行为与 match_phrase 查询一致,不同的是它将查询字符串的最后一个词作为前缀使用,换句话说,可以把前面的例子看成:
- johnnie
- 跟着 walker
- 跟着 一个以 bl 开始的词
如果我们通过 validate-query 查询,explaination的结果为:
"johnnie walker bl*"
与 match_phrase 一样,它也可以接受 slop 参数让相对词序位置不那么严格:
{
"match_phrase_prefix" : {
"brand" : {
"query": "walker johnnie bl", #1
"slop": 10
}
}
}
- #1 尽管词语的顺序不正确,查询仍然能够匹配,因为我们为它设置了较高的slop值使匹配时的词序有更大的灵活性。
但是只有最后一个词才能作为前缀。
在之前的前缀查询(prefix Query)中,我们提示过前缀使用的风险,即前缀查询对于资源的消耗严重,这种方式(match_phrase_prefix)同样如此。一个以 a 开头的前缀可能会匹配成千上万的术语,这不仅会消耗很多系统资源,而且结果对用户也用处不大。
我们可以通过设置 max_expansions 参数来限制前缀扩展的影响,一个合理的值是可能是50:
{
"match_phrase_prefix" : {
"brand" : {
"query": "johnnie walker bl",
"max_expansions": 50
}
}
}
参数max_expansions控制着可以与前缀匹配的术语的数量,它会先查找第一个与前缀bl匹配的术语,然后依次查找搜集与之匹配的术语,直到没有更多可以匹配的术语或者当数量超过max_expansions时结束。
不要忘记,当用户每多输入一个字符的时候,这个查询又会执行一遍,所以这个查询需要非常快速,如果第一个结果集不是用户想要的,他们会继续输入直到能搜索出他们满意的结果为止。
索引时优化(Index-Time Optimizations)
到目前为止,所有谈到的解决方案都是在查询时(query time)实现的。这样做并不需要特殊的映射抑或特殊的索引模式,只是简单的使用已经索引好的数据。
查询时的灵活性通常会以牺牲搜索性能为代价,有些时候将这些消耗从查询过程中转移出去是有其意义的。在实时的网站应用中,100毫秒可能是一个难以忍受的巨大延迟。
我们可以通过在索引时处理数据来提高搜索的灵活性以及系统性能。为此我们仍然需要付出应有的代价:增加的索引空间与变慢的索引能力,但这与每次查询都需要付出代价不同,在索引时付出的代价是一次性的。
用户会感谢我们。
Ngram部分匹配(Ngrams for Partial Matching)
我们之前提到:“只能在反向索引中找到存在的术语”,尽管prefix、wildcard、以及 regexp 查询告诉我们这种说法并不完全正确,但单术语查找的确要比在术语列表中盲目挨个查找的效率要高得多。在搜索之前提前准备好供部分匹配的数据会提高搜索的性能。
在索引时准备数据意味着要选择合适的分析链,这里我们使用的工具叫 n-gram。可以把 n-gram 看成一个在词语上移动的窗子,n 代表这个“窗子”的长度,如果我们说要 n-gram 一个词 —— quick,它的结果依赖于我们对于这个长度 n 的选择:
- 长度 1 (unigram): [ q, u, i, c, k ]
- 长度 2 (bigram): [ qu, ui, ic, ck ]
- 长度 3 (trigram): [ qui, uic, ick ]
- 长度 4 (four-gram): [ quic, uick ]
- 长度 5 (five-gram): [ quick ]
朴素的 n-gram 对于词语内部的匹配非常有用,即我们在稍后 Ngram匹配复合词(Ngrams for Compound Words)介绍的那样。但是,对于输入即搜索(search-as-you-type)这种行为,我们会使用一种特殊的n-gram叫做 边界n-grams(edge n-grams)。所谓的边界 n-gram 是说它会固定词语开始的一边,以单词 quick 为例,它的边界n-gram的结果是:
- q
- qu
- qui
- quic
- quick
我们会注意到这与用户在搜索时输入 “quick” 的次序是一致的,换句话说,这种方式正好满足即时搜索(instant search)。
索引时输入即搜索(Index-Time Search-as-You-Type)
设置索引时输入即搜索的第一步是需要定义好我们的分析链,我们在 配置分析器(Configuring Analyzers) 中提到过,但是这里我们会对此再次说明。
准备索引(Preparing the Index)
第一步需要配置一个自定义的token过滤器 edge_ngram,我们将其称为 autocompleted_filter :
{
"filter": {
"autocomplete_filter": {
"type": "edge_ngram",
"min_gram": 1,
"max_gram": 20
}
}
}
这个配置的意思是:对于所有这个token过滤器收到的术语,它都会为之生成一个n-gram,这个n-gram固定的最小开始的位置为1,最大长度为20。
然后我们会在一个自定义分析器 autocomplete 中使用到上面的这个过滤器:
{
"analyzer": {
"autocomplete": {
"type": "custom",
"tokenizer": "standard",
"filter": [
"lowercase",
"autocomplete_filter" #1
]
}
}
}
- #1 这里使用的是我们自定义的 边界Ngram token过滤器。
这个分析器使用标准的标记器将字符串标记为独立的术语,并且将他们都变成小写形式,然后为每个术语生成一个边界Ngram。
创建索引、实例化token过滤器和分析器的完整例子如下:
PUT /my_index
{
"settings": {
"number_of_shards": 1, #1
"analysis": {
"filter": {
"autocomplete_filter": { #2
"type": "edge_ngram",
"min_gram": 1,
"max_gram": 20
}
},
"analyzer": {
"autocomplete": {
"type": "custom",
"tokenizer": "standard",
"filter": [
"lowercase",
"autocomplete_filter"
]
}
}
}
}
}
- #1 参考 被破坏的相关性(Relevance Is Broken)
- 首先自定义我们的token过滤器
- 然后在分析器中使用它
我们可以拿analyze API测试这个新的分析器:
GET /my_index/_analyze?analyzer=autocomplete
quick brown
返回正确的术语如下:
- q
- qu
- qui
- quic
- quick
- b
- br
- bro
- brow
- brown
我们可以用 update-mapping API 将这个分析器应用到具体字段:
PUT /my_index/_mapping/my_type
{
"my_type": {
"properties": {
"name": {
"type": "string",
"analyzer": "autocomplete"
}
}
}
}
现在我们创建一些测试文档:
POST /my_index/my_type/_bulk
{ "index": { "_id": 1 }}
{ "name": "Brown foxes" }
{ "index": { "_id": 2 }}
{ "name": "Yellow furballs" }
查询字段(Querying the Field)
如果我们使用简单 match 查询测试查询“brown fo”:
GET /my_index/my_type/_search
{
"query": {
"match": {
"name": "brown fo"
}
}
}
我们可以看到两个文档同时都能匹配,尽管 Yellow furballs 这个文档并不包含 brown 和 fo:
{
"hits": [
{
"_id": "1",
"_score": 1.5753809,
"_source": {
"name": "Brown foxes"
}
},
{
"_id": "2",
"_score": 0.012520773,
"_source": {
"name": "Yellow furballs"
}
}
]
}
validate-query API可以为我们提供一些线索:
GET /my_index/my_type/_validate/query?explain
{
"query": {
"match": {
"name": "brown fo"
}
}
}
explaination 告诉我们这个查询会查找边界Ngram里的每个词:
name:b name:br name:bro name:brow name:brown name:f name:fo
name:f 条件可以满足第二个文档,因为 furballs是以 f、fu、fur形式索引的。回过头看这并不令人吃惊,相同的autocomplete 分析器同时被应用于索引时和搜索时,这在大多数情况下是正确的,只有在少数场景下才需要改变这种行为。
我们需要保证索引表中包含边界Ngram的每个词,但是我们只想匹配用户输入的完整词组(brown 和 fo),可以通过在索引时使用 autocomplete 分析器,并在搜索时使用 standard 标准分析器来实现这种想法,只需要改变查询中搜索分析器的analyzer 参数即可:
GET /my_index/my_type/_search
{
"query": {
"match": {
"name": {
"query": "brown fo",
"analyzer": "standard" #1
}
}
}
}
- #1 覆盖了 name 字段 analyzer 的设置
换种方式,我们可以在映射中,为 name 字段分别指定 index_analyzer 和 search_analyzer。因为只想改变search_analyzer,这里只需更新现有的映射而不用对数据重新创建索引:
PUT /my_index/my_type/_mapping
{
"my_type": {
"properties": {
"name": {
"type": "string",
"index_analyzer": "autocomplete", #1
"search_analyzer": "standard" #2
}
}
}
}
- #1 在索引时,使用 autocompleted 分析器生成边界Ngram的每个术语。
- #2 在搜索时,使用 standard 分析器搜索用户输入的术语。
如果我们再次用 validate-query API查看请求,现在的 explaination是:
name:brown name:fo
这样结果中就只返回“Brown foxes”这个文档。
因为大多数工作是在索引时完成的,所有的查询只需要查找 brown 和 fo 这两个术语,这比使用 match_phrase_prefix 查找所有以 fo 开始的术语的方式要高效许多。
完成建议者(Completion Suggester)
使用边界Ngram进行输入即搜索的查询设置简单、灵活且快速,但是,有些时候它并不足够快,特别是当我们试图立刻获得反馈时,延迟的问题就会凸显,很多时候不搜索才是最快的搜索方式。
ElasticSearch里的 完成建议者(Completion Suggester) 采用了与上面完全不同的方式,我们需要为搜索条件生成一个所有可能完成的单词列表,然后将它们置入一个 有限状态机(finite state transducer)内,这是一个经过优化的图结构。为了搜索建议,ElasticSearch从图的开始处顺着匹配路径一个字符一个字符进行匹配,一旦它处于用户输入的末尾,ElasticSearch就会查找所有可能的结束当前路径,然后生成一个建议列表。
这个数据结构存在于内存里使得对前缀的查询非常快速,比任何一种基于术语的查询都要快很多,这对名字或品牌的自动完成非常适用,因为这些词通常是以普通顺序组织的:用“Johnny Rotten”而不是“Rotten Johnny”。
当词序不是那么容易被预见时,边界Ngram比完成建议者(Completion Suggester)更合适。如果说不可能所有的猫都是一个花色,那这只猫的花色也是相当特殊的。
边界n-grams与邮编(Edge n-grams and Postcodes)
边界n-gram的方式可以被用来查询结构化的数据,比如之前例子中的:邮编(postcode)。当然 postcode 字段需要是分析过的(analyzed)而不是未分析过的(not_analyzed),即使未分析过(not_analyzed),我们还是可以用关键词(keyword)标记器来处理它。
keyword 标记器是一个非操作型标记器,这个标记器不做任何事情,它接收的任何字符串都会被原样发出,因此它可以用来处理 not_analyzed 的字段值,但这也需要其他的一些分析转换,如:小写化。
下面这个例子使用 keyword 标记器将邮编转换成标记流(token stream),这样我们就能使用边界n-gram标记过滤器:
{
"analysis": {
"filter": {
"postcode_filter": {
"type": "edge_ngram",
"min_gram": 1,
"max_gram": 8
}
},
"analyzer": {
"postcode_index": { #1
"tokenizer": "keyword",
"filter": [ "postcode_filter" ]
},
"postcode_search": { #2
"tokenizer": "keyword"
}
}
}
}
- #1 postcode_index 分析器使用 postcode_filter 将邮编转换成边界n-gram形式。
- #2 postcode_search 分析器可以将搜索术语看成未索引的(not_indexed)。
Ngram匹配复合词(Ngrams for Compound Words)
最后,我们来看看n-gram是如何应用于搜索复合词的语言中的。德语闻名于它可以将许多小词组合成一个非常巨大的复合词以获得它准确而又复杂的意义。例如:
-
Aussprachewörterbuch
发音字典(Pronunciation dictionary)
-
Militärgeschichte
战争史(Military history)
-
Weißkopfseeadler
秃鹰(White-headed sea eagle, or bald eagle)
-
Weltgesundheitsorganisation
世界卫生组织(World Health Organization)
-
Rindfleischetikettierungsüberwachungsaufgabenübertragungsgesetz
法案考虑代理监管牛和牛肉的标记的职责(The law concerning the delegation of duties for the supervision of cattle marking and the labeling of beef)
有些人希望在搜索“Wörterbuch”(字典)的时候,能在结果中看到“Aussprachewörtebuch”(发音字典)。同样,搜索“Adler”(鹰)的时候,能将“Weißkopfseeadler”(秃鹰)包含在结果集中。
处理这种语言的一种方式可以是将复合词拆分成各自部分,然后用 组合词标记过滤器(compound word token filter),但这种方式的结果质量依赖于我们组合词字典的好坏。
另一种就是将所有的词用n-gram的方式进行处理,然后搜索任何匹配的片段——能匹配的片段越多,文档的相关度越大。
因为n-gram是一个词上的移动窗,一个具有所有长度的n-gram能涵盖所有的词。我们希望选择有足够长度让词有意义,但是也不能太长而生成过多的唯一术语,一个长度为3的trigram可能是一个不错的开始:
PUT /my_index
{
"settings": {
"analysis": {
"filter": {
"trigrams_filter": {
"type": "ngram",
"min_gram": 3,
"max_gram": 3
}
},
"analyzer": {
"trigrams": {
"type": "custom",
"tokenizer": "standard",
"filter": [
"lowercase",
"trigrams_filter"
]
}
}
}
},
"mappings": {
"my_type": {
"properties": {
"text": {
"type": "string",
"analyzer": "trigrams" #1
}
}
}
}
}
- #1 text 字段用 trigrams 分析器索引它的内容,这里n-gram的长度是3。
测试trigram分析器:
GET /my_index/_analyze?analyzer=trigrams
Weißkopfseeadler
返回的术语:
wei, eiß, ißk, ßko, kop, opf, pfs, fse, see, eea,ead, adl, dle, ler
创建复合词的测试文档:
POST /my_index/my_type/_bulk
{ "index": { "_id": 1 }}
{ "text": "Aussprachewörterbuch" }
{ "index": { "_id": 2 }}
{ "text": "Militärgeschichte" }
{ "index": { "_id": 3 }}
{ "text": "Weißkopfseeadler" }
{ "index": { "_id": 4 }}
{ "text": "Weltgesundheitsorganisation" }
{ "index": { "_id": 5 }}
{ "text": "Rindfleischetikettierungsüberwachungsaufgabenübertragungsgesetz" }
“Adler”(鹰)的搜索转化为查询三个术语 adl、dle和ler:
GET /my_index/my_type/_search
{
"query": {
"match": {
"text": "Adler"
}
}
}
正好可以与“Weißkopfsee-adler”相匹配:
{
"hits": [
{
"_id": "3",
"_score": 3.3191128,
"_source": {
"text": "Weißkopfseeadler"
}
}
]
}
类似查询“Gesundheit”(健康)可以与“Welt-gesundheit-sorganisation”匹配,同时也能与“Militär-ges-chichte”和“Rindfleischetikettierungsüberwachungsaufgabenübertragungs-ges-etz”匹配,因为它们同时具有trigram生成的术语 ges:
使用合适的 minimum_should_match 可以将这些奇怪的结果排除,只有当trigram最少匹配数满足要求时,一个文档才能被认为是匹配的:
GET /my_index/my_type/_search
{
"query": {
"match": {
"text": {
"query": "Gesundheit",
"minimum_should_match": "80%"
}
}
}
}
这有点像全文搜索中的猎枪法,可能会导致反向索引很大,尽管如此,在索引具有很多复合词的语言,或词之间没有空格的语言(如:泰语)时,它仍不失为一种通用的有效方法。
这种技术可以用来提升召回(Recall)——搜索结果中相关文档的数目。它通常会与其他技术(如:瓦片词shingles)一起使用以提高精度和每个文档的相关度分数。