当用户在文本编辑器或者文字处理软件中搜索一个单词或者句子的时候,软件就会对文件进行扫描并寻找那个单词或者句子。如果读者曾经使用过linux、Unix或者OS X的grep程序,或者曾经使用过windows内置的文件搜索功能来查找包含特定单词或者句子的文件,那么应该就会注意到,被搜索文件的数量越多、体积越大,搜索花费的时间也会越长。
与在本地电脑上面进行的搜索不同,在Web上面搜索Web页面或者其他内容的速度总是非常快的,即使在文档的体积和数量都非常巨大的情况下,也是如此。在这一节中,我们将学习如何改变程序搜索数据的方式,并使用redis来减少绝大部分基于单词或者关键字进行的内容搜索操作的执行时间。
为了给遇到问题的用户予以帮助,Fake Garage创业公司建立了一个由疑难解答文章组成的知识库。最近几个月以来,随着知识库文章的数量和品种不断增多,使用数据库驱动的搜索程序也变得越来越慢。因为Redis具备构建内容搜索引擎所需的全部功能,所以我们决定使用Redis来构建一个新的搜索程序,从而提高对知识库文章的搜索速度。
我们首先要做的就是思考这样一个问题:比起一个单词接一个单词地扫描文档,如何才能以更快的速度对文档进行搜索?
为了获得比扫描文档更快的搜索速度,我们需要对文档进行预处理,这个预处理步骤通常被称为建索引(indexing),而我们要创建的结构则被称为反向索引(inverted indexes)。反向索引是互联网上绝大部分搜索引擎所使用的底层结构,它在搜索领域里面几乎无人不知。从很多方面来看,创建反向索引就像是在生成一些类似于书本末尾的索引那样的东西。我们选择使用Redis来创建反向索引的原因在于,Redis自带的集合和有序集合①都非常适合于处理反向索引。
具体来说,反向索引会从每个被索引的文档里面提取出一些单词,并创建表格来记录每篇文章都包含了哪些单词。对于只包含标题《lord of the rings》的文档docA以及只包含标题《lord of the dance》的文档docB,程序将在Redis里面为lord这个单词创建一个集合,并在集合里面包含docA和docB这两个文档的名字,以此来表示docA和docB这两个文档都包含了单词lord。图7-1展示了程序为这两个文档创建的所有反向索引。
图7-1 为docA和docB创建的反向索引
在知道了索引操作的最终执行结果就是产生一些Redis集合之后,我们接下来要了解的就是生成这些集合的具体方法。
为了给文档构建索引集合,程序首先需要对文档包含的单词进行处理。从文档里面提取单词的过程通常被称为语法分析(parsing)和标记化(tokenization),这个过程可以产生出一系列用于标识文档的标记(token),标记有时候又被称为单词(word)。
生成标记的方法有很多种。用于处理Web页面的方法,与处理关系数据库的行或者处理文档数据库的文档所使用的方法,可能会有所不同。为了让标记化过程保持简单,我们认定单词只能由英文字母和单引号(')组成,并且每个单词至少要有两个字符长。这一规则可以覆盖大部分英文单词,并忽略诸如I和a这样的单词。
标记化的一个常见的附加步骤,就是移除内容中的非用词(stop word)。非用词就是那些在文档中频繁出现但是却没有提供相应信息量的单词,对这些单词进行搜索将返回大量无用的结果。移除非用词不仅可以提高搜索性能,还可以减少索引的体积。图7-2展示了对示例文本进行标记化并移除非用词的过程。
图7-2 将本节的一部分原文标记化为多个单词,并移除其中的非用词
因为不同类型的文档都有各自的常用单词,而这些常用单词也许会对非用词产生影响,所以移除非用词的关键就是要找到合适的非用词清单。代码清单7-1展示了从非用词清单,以及对文档进行标记化处理、移除非用词并创建索引的函数。
代码清单7-1 对文档进行标记化处理并创建索引的函数
因为of和the都是非用词,所以在使用代码清单7-1展示的标记化函数和索引函数去处理之前提到的docA和docB的时候,程序将为单词lord、rings和dance创建相应的集合,而不是为单词lord、of、the、rings和dance都创建集合。
从索引里面移除文档 如果被索引文档的内容可能会随着时间而出现变化,那么就需要有一个功能来自动删除文档已有的索引并重新建立索引,或者智能地为文档删除无效的索引并添加新索引。实现这个功能的一个比较简单的方法,就是使用JSON编码的列表把文档已经建立了索引的单词记录起来,并通过SET命令将这个列表存储到一个键里面,最后再在index_document()函数的开头添加一些删除不必要索引的代码。
既然我们已经掌握了为知识库文档生成反向索引的方法,那么接下来是时候学习如何搜索这些文档了。
在索引里面查找一个单词是非常容易的,程序只需要获取单词集合里面的所有文档就可以了。但是要根据两个或多个单词查找文档的话,程序就需要把给定单词集合里面的所有文档都找出来,然后再从中找到那些在所有单词集合里面都出现了的文档。第3章中曾经介绍过如何使用Redis的SINTER命令和SINTERSTORE命令来找出那些同时存在于所有给定集合的元素,而这一次,我们同样可以使用这两个命令来找出那些包含了所有给定单词的文档。
使用交集操作处理反向索引的好处不在于能够找到多少文档,甚至不在于能够多快地找出结果,而在于能够彻底地忽略无关的信息。在以文本编辑器的方式对文本进行搜索的时候,很多无用的数据都会被仔细检查,但是因为反向索引已经知道了每篇文档包含的单词,所以程序只需要对文档进行过滤,找出那些包含了所有给定单词的文档就可以了。
用户有些时候可能会想要使用多个具有相同意思的单词进行搜索,并把它们看作是同一个单词,我们把这样的单词称为同义词。为了处理这种情况,程序可以取出同义词对应的全部文档集合,并从中找出所有独一无二的文档,或者直接使用Redis内置的SUNION命令或者SUNIONSTORE命令。
除此之外,用户可能偶尔也想要搜索那些包含了某些特定单词或者句子,但是并不包含另外一些单词或句子的文档,使用Redis的SDIFF和SDIFFSTORE这两个集合命令可以做到这一点。
通过使用Redis的集合操作以及一些辅助代码,程序可以对文档执行各种复杂的单词查询操作。代码清单7-2展示了一组辅助函数,它们可以对给定单词对应的集合执行交集计算、并集计算和差集计算,并将计算结果存储到一个默认过期时间为30秒的临时集合里面。
代码清单7-2 对集合进行交集计算、并集计算和差集计算的辅助函数
函数intersect()、union()和difference()都会调用同一个辅助函数来完成实际的工作,因为它们要做的事情本质上是一样的:准备好相关的数据库键,执行正确的集合命令,更新过期时间并返回新集合的ID。图7-3以文氏图的方式形象地展示了3个不同的集合命令SINTER、 SUNION和SDIFF的执行过程。
图7-3 在文氏图上进行交集计算、并集计算和差集计算的样子
以上就是实现一个搜索引擎所需的全部代码,我们接下来要考虑的是如何对用户给定的搜索查询语句进行语法分析。
到目前为止,我们已经具备了建立索引和进行搜索所需的绝大部分工具,包括标记化函数、索引函数以及基本的交集计算函数、并集计算函数和差集计算函数,唯一缺少的就是一个将文本查询语句转换成搜索操作的函数。为此,我们将实现一个搜索函数,它可以查找那些包含了所有给定单词的文档,并允许我们指定同义词以及不需要的单词。
最基本的搜索旨在找出那些包含了所有给定单词的文档。如果用户只是单纯地给出了一些单词,那么搜索程序只需要直接执行一个intersect()调用就可以了。如果用户在某个单词的前面加上了一个减号(-),那么就表示用户不希望包含这个单词的文档出现在搜索结果里面,搜索程序就需要使用difference()移除相应的文档。如果用户在某个单词的前面加上了一个加号(+),那么就表示这个单词是前一个单词的同义词,搜索程序首先会收集各个同义词组并对它们执行union()操作,然后再执行高层次的intersect()调用(如果带+号的单词前面有带-号的单词,那么程序会略过那些带-号的单词,并把最先遇到的不带-号的单词看作是同义词)。
根据以上介绍的区分同义词和不需要单词的规则,代码清单7-3展示了一段代码,它可以将用户输入的查询语句解释为一个Python列表,这个列表里面记录了哪些单词是同义词,哪些单词是不需要的单词。
代码清单7-3 搜索查询语句的语法分析函数
为了对这个语法分析函数进行测试,我们需要使用它在知识库里面搜索一些与连接聊天室有关的问题。我们想要找的是一些包含connect、connection、disconnect或disconnection以及chat等一系列单词的文章。此外,因为我们没有使用代理,所以我们希望能够跳过那些带有proxy或proxies单词的文档。以下交互示例展示了这一查询的执行过程(为了方便阅读,对代码进行了分组格式化):
从执行结果可以看到,函数正确地为connect和disconnect提取出了同义词,并将chat单独划分为一个单词,另外还找出了不需要的单词proxy和proxies。除非是为了进行调试,否则这些分析结果一般都不会被传递到其他地方——因为parse_and_search()函数会在内部直接调用parse()函数,并根据需要使用union()函数对各个同义词列表进行并集计算,使用intersect()函数对最终挑选出的单词列表进行交集计算,以及使用difference()函数移除那些不需要的单词。代码清单7-4展示了parse_and_search()函数的完整代码。
代码清单7-4 用于分析查询语句并搜索文档的函数
和之前介绍的集合计算辅助函数一样,parse_and_search()函数也会返回一个集合ID作为执行结果,这个ID对应的集合里面包含了与用户给定的搜索参数相匹配的文档。现在,Fake Garage创业公司只要使用之前介绍过的index_document()函数为他们的所有文档创建索引,就可以使用parse_and_search()函数对那些文档进行搜索了。
虽然我们现在拥有了一个能够根据给定条件搜索文档的程序,但是随着文档数量变得越来越大,能够让搜索结果根据特定的顺序进行排序将变得非常重要。为了做到这一点,我们需要学习如何对搜索结果进行排序。
虽然我们已经可以根据给定的单词对索引内的文档进行搜索,但这只是我们检索所需信息的第一步。搜索程序在取得多个文档之后,通常还需要根据每个文档的重要性对它们进行排序——搜索领域把这一问题称为关联度计算问题,而判断一个文档是否比另一个文档具有更高关联度的其中一种方法,就是看哪个文档的更新时间最接近当前时间。接下来我们将学习如何在搜索结果中引入对关联度的支持。
本书在第3章中曾经介绍过,Redis的SORT命令可以对列表或者集合存储的内容进行排序,甚至还可以引用外部数据。Fake Garage创业公司的知识库把每篇文章的相关信息都存储在散列里面,这些信息包括文章的标题、文章创建时的时间戳、文章最后一次更新时的时间戳以及文档ID。图7-4展示了一个存储着文档信息的散列示例。
图7-4 使用散列存储文档信息的示例
对于图7-4这种存储在散列里面的文档,使用SORT命令可以根据文档的不同属性对文档进行排序。虽然前面介绍的parse_and_search()函数会为搜索结果设置较短的过期时间,使得搜索结果在使用完毕之后能够尽快被删掉,但是对于排序之后的搜索结果,我们可以多保存它们一会儿,以便在有需要的时候对它们进行重新排序或者执行分页操作。代码清单7-5展示了一个整合了结果缓存功能以及重新排序功能的搜索函数。
代码清单7-5 分析查询语句然后进行搜索,并对搜索结果进行排序的函数
search_and_sort()函数除了可以搜索文档并对结果进行排序之外,还允许用户通过更新start参数和num参数对搜索结果进行分页;通过sort参数改变排序依据的属性,从而改变结果的排列顺序;通过修改ttl参数改变结果的缓存时间;以及通过id参数引用已有的搜索结果,从而节约计算时间。
尽管这些搜索函数还不足以让我们创建一个媲美google的搜索引擎,但笔者当初就是因为被这个问题以及它的解决方法所吸引,才开始使用Redis的。SORT命令的一些限制使得我们需要使用有序集合才能实现形式更为复杂的文档搜索操作,其中包括基于多个分值进行的复合排序操作,具体的信息将在接下来的一节介绍。
上一节主要讨论了如何使用Redis实现搜索功能,并通过引用存储在散列里面的数据对搜索结果进行排序。这种排序方法非常适合在元素的排列顺序(sort order)可以用字符串或者数字表示的情况下使用,但它并不能处理元素的排列顺序由几个不同分值组合而成的情况。本节将展示如何使用集合以及有序集合实现基于多个分值的复合排序操作,它能够提供比SORT命令更高的灵活性。
稍早之前,在使用SORT命令从散列里面获取排序所需数据的时候,散列的作用与关系数据库里面的行非常相似。如果我们把文章的更新时间存储到有序集合里面,然后通过ZINTERSTORE命令以及它的MAX聚合函数,对存储了文章搜索结果的集合以及存储了文章更新时间的有序集合执行交集计算,那么就可以根据文章的更新时间对搜索结果内的所有文章进行排序。
本文摘自《Redis实战》