使用Redis构建搜索服务

Published on 2017 - 06 - 25

当用户在文本编辑器或者文字处理软件中搜索一个单词或者句子的时候,软件就会对文件进行扫描并寻找那个单词或者句子。如果读者曾经使用过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。图1展示了程序为这两个文档创建的所有反向索引。


[图1 为docA和docB创建的反向索引]

在知道了索引操作的最终执行结果就是产生一些Redis集合之后,我们接下来要了解的就是生成这些集合的具体方法。

基本索引操作

为了给文档构建索引集合,程序首先需要对文档包含的单词进行处理。从文档里面提取单词的过程通常被称为语法分析(parsing)和标记化(tokenization),这个过程可以产生出一系列用于标识文档的标记(token),标记有时候又被称为单词(word)。

生成标记的方法有很多种。用于处理Web页面的方法,与处理关系数据库的行或者处理文档数据库的文档所使用的方法,可能会有所不同。为了让标记化过程保持简单,我们认定单词只能由英文字母和单引号(')组成,并且每个单词至少要有两个字符长。这一规则可以覆盖大部分英文单词,并忽略诸如I和a这样的单词。

标记化的一个常见的附加步骤,就是移除内容中的非用词(stop word)。非用词就是那些在文档中频繁出现但是却没有提供相应信息量的单词,对这些单词进行搜索将返回大量无用的结果。移除非用词不仅可以提高搜索性能,还可以减少索引的体积。图2展示了对示例文本进行标记化并移除非用词的过程。


[图2 将本节的一部分原文标记化为多个单词,并移除其中的非用词]

因为不同类型的文档都有各自的常用单词,而这些常用单词也许会对非用词产生影响,所以移除非用词的关键就是要找到合适的非用词清单。代码清单1展示了从http://www.textfixer.com/ resources/获取的非用词清单,以及对文档进行标记化处理、移除非用词并创建索引的函数。

STOP_WORDS = set('''able about across after all almost also am among
an and any are as at be because been but by can cannot could dear did
do does either else ever every for from get got had has have he her
hers him his how however if in into is it its just least let like
likely may me might most must my neither no nor not of off often on
only or other our own rather said say says she should since so some
than that the their them then there these they this tis to too twas us
wants was we were what when where which while who whom why will with
would yet you your'''.split())                                          #A

WORDS_RE = re.compile("[a-z']{2,}")                                     #B

def tokenize(content):
    words = set()                                                       #C
    for match in WORDS_RE.finditer(content.lower()):                    #D
        word = match.group().strip("'")                                 #E
        if len(word) >= 2:                                              #F
            words.add(word)                                             #F
    return words - STOP_WORDS                                           #G

def index_document(conn, docid, content):
    words = tokenize(content)                                           #H

    pipeline = conn.pipeline(True)
    for word in words:                                                  #I
        pipeline.sadd('idx:' + word, docid)                             #I
    return len(pipeline.execute())                                      #J

#A We pre-declare our known stop words, these were fetched from http://www.textfixer.com/resources/
#B A regular expression that extracts words as we defined them
#C Our Python set of words that we have found in the document content
#D Iterate over all of the words in the content
#E Strip any leading or trailing single-quote characters
#F Keep any words that are still at least 2 characters long
#G Return the set of words that remain that are also not stop words
#H Get the tokenized words for the content
#I Add the documents to the appropriate inverted index entries
#J Return the number of unique non-stop words that were added for the document

因为of和the都是非用词,所以在使用代码清单1展示的标记化函数和索引函数去处理之前提到的docA和docB的时候,程序将为单词lord、rings和dance创建相应的集合,而不是为单词lord、of、the、rings和dance都创建集合。

从索引里面移除文档如果被索引文档的内容可能会随着时间而出现变化,那么就需要有一个功能来自动删除文档已有的索引并重新建立索引,或者智能地为文档删除无效的索引并添加新索引。实现这个功能的一个比较简单的方法,就是使用JSON编码的列表把文档已经建立了索引的单词记录起来,并通过SET命令将这个列表存储到一个键里面,最后再在index_document()函数的开头添加一些删除不必要索引的代码。

既然我们已经掌握了为知识库文档生成反向索引的方法,那么接下来是时候学习如何搜索这些文档了。

基本搜索操作

在索引里面查找一个单词是非常容易的,程序只需要获取单词集合里面的所有文档就可以了。但是要根据两个或多个单词查找文档的话,程序就需要把给定单词集合里面的所有文档都找出来,然后再从中找到那些在所有单词集合里面都出现了的文档。曾经介绍过如何使用Redis的SINTER命令和SINTERSTORE命令来找出那些同时存在于所有给定集合的元素,而这一次,我们同样可以使用这两个命令来找出那些包含了所有给定单词的文档。

使用交集操作处理反向索引的好处不在于能够找到多少文档,甚至不在于能够多快地找出结果,而在于能够彻底地忽略无关的信息。在以文本编辑器的方式对文本进行搜索的时候,很多无用的数据都会被仔细检查,但是因为反向索引已经知道了每篇文档包含的单词,所以程序只需要对文档进行过滤,找出那些包含了所有给定单词的文档就可以了。

用户有些时候可能会想要使用多个具有相同意思的单词进行搜索,并把它们看作是同一个单词,我们把这样的单词称为同义词。为了处理这种情况,程序可以取出同义词对应的全部文档集合,并从中找出所有独一无二的文档,或者直接使用Redis内置的SUNION命令或者SUNIONSTORE命令。

除此之外,用户可能偶尔也想要搜索那些包含了某些特定单词或者句子,但是并不包含另外一些单词或句子的文档,使用Redis的SDIFF和SDIFFSTORE这两个集合命令可以做到这一点。

通过使用Redis的集合操作以及一些辅助代码,程序可以对文档执行各种复杂的单词查询操作。代码清单2展示了一组辅助函数,它们可以对给定单词对应的集合执行交集计算、并集计算和差集计算,并将计算结果存储到一个默认过期时间为30秒的临时集合里面。

def _set_common(conn, method, names, ttl=30, execute=True):
    id = str(uuid.uuid4())                                  #A
    pipeline = conn.pipeline(True) if execute else conn     #B
    names = ['idx:' + name for name in names]               #C
    getattr(pipeline, method)('idx:' + id, *names)          #D
    pipeline.expire('idx:' + id, ttl)                       #E
    if execute:
        pipeline.execute()                                  #F
    return id                                               #G

def intersect(conn, items, ttl=30, _execute=True):          #H
    return _set_common(conn, 'sinterstore', items, ttl, _execute) #H

def union(conn, items, ttl=30, _execute=True):                    #I
    return _set_common(conn, 'sunionstore', items, ttl, _execute) #I

def difference(conn, items, ttl=30, _execute=True):               #J
    return _set_common(conn, 'sdiffstore', items, ttl, _execute)  #J

#A Create a new temporary identifier
#B Set up a transactional pipeline so that we have consistent results for each individual call
#C Add the 'idx:' prefix to our terms
#D Set up the call for one of the operations
#E Instruct Redis to expire the SET in the future
#F Actually execute the operation
#G Return the id for the caller to process the results
#H Helper function to perform SET intersections
#I Helper function to perform SET unions
#J Helper function to perform SET differences

函数intersect()、union()和difference()都会调用同一个辅助函数来完成实际的工作,因为它们要做的事情本质上是一样的:准备好相关的数据库键,执行正确的集合命令,更新过期时间并返回新集合的ID。图3以文氏图的方式形象地展示了3个不同的集合命令SINTER、 SUNION和SDIFF的执行过程。

[图3 在文氏图上进行交集计算、并集计算和差集计算的样子]

以上就是实现一个搜索引擎所需的全部代码,我们接下来要考虑的是如何对用户给定的搜索查询语句进行语法分析。

分析并执行搜索

到目前为止,我们已经具备了建立索引和进行搜索所需的绝大部分工具,包括标记化函数、索引函数以及基本的交集计算函数、并集计算函数和差集计算函数,唯一缺少的就是一个将文本查询语句转换成搜索操作的函数。为此,我们将实现一个搜索函数,它可以查找那些包含了所有给定单词的文档,并允许我们指定同义词以及不需要的单词。

最基本的搜索旨在找出那些包含了所有给定单词的文档。如果用户只是单纯地给出了一些单词,那么搜索程序只需要直接执行一个intersect()调用就可以了。如果用户在某个单词的前面加上了一个减号(-),那么就表示用户不希望包含这个单词的文档出现在搜索结果里面,搜索程序就需要使用difference()移除相应的文档。如果用户在某个单词的前面加上了一个加号(+),那么就表示这个单词是前一个单词的同义词,搜索程序首先会收集各个同义词组并对它们执行union()操作,然后再执行高层次的intersect()调用(如果带+号的单词前面有带-号的单词,那么程序会略过那些带-号的单词,并把最先遇到的不带-号的单词看作是同义词)。

根据以上介绍的区分同义词和不需要单词的规则,代码清单3展示了一段代码,它可以将用户输入的查询语句解释为一个Python列表,这个列表里面记录了哪些单词是同义词,哪些单词是不需要的单词。

QUERY_RE = re.compile("[+-]?[a-z']{2,}")                #A

def parse(query):
    unwanted = set()                                    #B
    all = []                                            #C
    current = set()                                     #D
    for match in QUERY_RE.finditer(query.lower()):      #E
        word = match.group()                            #F
        prefix = word[:1]                               #F
        if prefix in '+-':                              #F
            word = word[1:]                             #F
        else:                                           #F
            prefix = None                               #F

        word = word.strip("'")                          #G
        if len(word) < 2 or word in STOP_WORDS:         #G
            continue                                    #G

        if prefix == '-':                               #H
            unwanted.add(word)                          #H
            continue                                    #H

        if current and not prefix:                      #I
            all.append(list(current))                   #I
            current = set()                             #I
        current.add(word)                               #J

    if current:                                         #K
        all.append(list(current))                       #K

    return all, list(unwanted)                          #L

#A Our regular expression for finding wanted, unwanted, and synonym words
#B A unique set of unwanted words
#C Our final result of words that we are looking to intersect
#D The current unique set of words to consider as synonyms
#E Iterate over all words in the search query
#F Discover +/- prefixes, if any
#G Strip any leading or trailing single quotes, and skip anything that is a stop word
#H If the word is unwanted, add it to the unwanted set
#I Set up a new synonym set if we have no synonym prefix and we already have words
#J Add the current word to the current set
#K Add any remaining words to the final intersection

为了对这个语法分析函数进行测试,我们需要使用它在知识库里面搜索一些与连接聊天室有关的问题。我们想要找的是一些包含connect、connection、disconnect或disconnection以及chat等一系列单词的文章。此外,因为我们没有使用代理,所以我们希望能够跳过那些带有proxy或proxies单词的文档。以下交互示例展示了这一查询的执行过程(为了方便阅读,对代码进行了分组格式化):


  
从执行结果可以看到,函数正确地为connect和disconnect提取出了同义词,并将chat单独划分为一个单词,另外还找出了不需要的单词proxy和proxies。除非是为了进行调试,否则这些分析结果一般都不会被传递到其他地方——因为parse_and_search()函数会在内部直接调用parse()函数,并根据需要使用union()函数对各个同义词列表进行并集计算,使用intersect()函数对最终挑选出的单词列表进行交集计算,以及使用difference()函数移除那些不需要的单词。代码清单4展示了parse_and_search()函数的完整代码。

def parse_and_search(conn, query, ttl=30):
    all, unwanted = parse(query)                                    #A
    if not all:                                                     #B
        return None                                                 #B

    to_intersect = []
    for syn in all:                                                 #D
        if len(syn) > 1:                                            #E
            to_intersect.append(union(conn, syn, ttl=ttl))          #E
        else:                                                       #F
            to_intersect.append(syn[0])                             #F

    if len(to_intersect) > 1:                                       #G
        intersect_result = intersect(conn, to_intersect, ttl=ttl)   #G
    else:                                                           #H
        intersect_result = to_intersect[0]                          #H

    if unwanted:                                                    #I
        unwanted.insert(0, intersect_result)                        #I
        return difference(conn, unwanted, ttl=ttl)                  #I

    return intersect_result                                         #J

#A Parse the query
#B If there are no words in the query that are not stop words, we don't have a result
#D Iterate over each list of synonyms
#E If the synonym list is more than one word long, then perform the union operation
#F Otherwise use the individual word directly
#G If we have more than one word/result to intersect, intersect them
#H Otherwise use the individual word/result directly
#I If we have any unwanted words, remove them from our earlier result and return it
#J Otherwise return the intersection result

和之前介绍的集合计算辅助函数一样,parse_and_search()函数也会返回一个集合ID作为执行结果,这个ID对应的集合里面包含了与用户给定的搜索参数相匹配的文档。现在,Fake Garage创业公司只要使用之前介绍过的index_document()函数为他们的所有文档创建索引,就可以使用parse_and_search()函数对那些文档进行搜索了。

虽然我们现在拥有了一个能够根据给定条件搜索文档的程序,但是随着文档数量变得越来越大,能够让搜索结果根据特定的顺序进行排序将变得非常重要。为了做到这一点,我们需要学习如何对搜索结果进行排序。

对搜索结果进行排序

虽然我们已经可以根据给定的单词对索引内的文档进行搜索,但这只是我们检索所需信息的第一步。搜索程序在取得多个文档之后,通常还需要根据每个文档的重要性对它们进行排序——搜索领域把这一问题称为关联度计算问题,而判断一个文档是否比另一个文档具有更高关联度的其中一种方法,就是看哪个文档的更新时间最接近当前时间。接下来我们将学习如何在搜索结果中引入对关联度的支持。

Redis的SORT命令可以对列表或者集合存储的内容进行排序,甚至还可以引用外部数据。Fake Garage创业公司的知识库把每篇文章的相关信息都存储在散列里面,这些信息包括文章的标题、文章创建时的时间戳、文章最后一次更新时的时间戳以及文档ID。图4展示了一个存储着文档信息的散列示例。


[图4 使用散列存储文档信息的示例]

对于图4这种存储在散列里面的文档,使用SORT命令可以根据文档的不同属性对文档进行排序。虽然前面介绍的parse_and_search()函数会为搜索结果设置较短的过期时间,使得搜索结果在使用完毕之后能够尽快被删掉,但是对于排序之后的搜索结果,我们可以多保存它们一会儿,以便在有需要的时候对它们进行重新排序或者执行分页操作。代码清单5展示了一个整合了结果缓存功能以及重新排序功能的搜索函数。

def search_and_sort(conn, query, id=None, ttl=300, sort="-updated", #A
                    start=0, num=20):                               #A
    desc = sort.startswith('-')                                     #B
    sort = sort.lstrip('-')                                         #B
    by = "kb:doc:*->" + sort                                        #B
    alpha = sort not in ('updated', 'id', 'created')                #I

    if id and not conn.expire(id, ttl):     #C
        id = None                           #C

    if not id:                                      #D
        id = parse_and_search(conn, query, ttl=ttl) #D

    pipeline = conn.pipeline(True)
    pipeline.scard('idx:' + id)                                     #E
    pipeline.sort('idx:' + id, by=by, alpha=alpha,                  #F
        desc=desc, start=start, num=num)                            #F
    results = pipeline.execute()

    return results[0], results[1], id                               #G
#A We will optionally take an previous result id, a way to sort the results, and options for paginating over the results
#B Determine which attribute to sort by, and whether to sort ascending or descending
#I We need to tell Redis whether we are sorting by a number or alphabetically
#C If there was a previous result, try to update its expiration time if it still exists
#D Perform the search if we didn't have a past search id, or if our results expired
#E Fetch the total number of results
#F Sort the result list by the proper column and fetch only those results we want
#G Return the number of items in the results, the results we wanted, and the id of the results so that we can fetch them again later

search_and_sort()函数除了可以搜索文档并对结果进行排序之外,还允许用户通过更新start参数和num参数对搜索结果进行分页;通过sort参数改变排序依据的属性,从而改变结果的排列顺序;通过修改ttl参数改变结果的缓存时间;以及通过id参数引用已有的搜索结果,从而节约计算时间。

尽管这些搜索函数还不足以让我们创建一个媲美Google的搜索引擎,但笔者当初就是因为被这个问题以及它的解决方法所吸引,才开始使用Redis的。SORT命令的一些限制使得我们需要使用有序集合才能实现形式更为复杂的文档搜索操作,其中包括基于多个分值进行的复合排序操作,具体的信息将在接下来的一节介绍。

有序索引

上一节主要讨论了如何使用Redis实现搜索功能,并通过引用存储在散列里面的数据对搜索结果进行排序。这种排序方法非常适合在元素的排列顺序(sort order)可以用字符串或者数字表示的情况下使用,但它并不能处理元素的排列顺序由几个不同分值组合而成的情况。本节将展示如何使用集合以及有序集合实现基于多个分值的复合排序操作,它能够提供比SORT命令更高的灵活性。

稍早之前,在使用SORT命令从散列里面获取排序所需数据的时候,散列的作用与关系数据库里面的行非常相似。如果我们把文章的更新时间存储到有序集合里面,然后通过ZINTERSTORE命令以及它的MAX聚合函数,对存储了文章搜索结果的集合以及存储了文章更新时间的有序集合执行交集计算,那么就可以根据文章的更新时间对搜索结果内的所有文章进行排序。

使用有序集合对搜索结果进行排序

Redis允许用户将集合作为参数传入ZINTERSTORE和ZUNIONSTORE等有序集合命令里面,并把集合成员的分值看作是1来进行计算。本节暂时还不需要考虑如何处理集合的分值,但稍后的内容将对这方面做进一步的说明。

本节将介绍如何使用集合和有序集合来实现复合的搜索和排序操作。通过阅读本节,读者可以知道如何在搜索文档的同时,综合多个分值对文档进行排序,以及这样做的原因是什么。

在对文档进行搜索并得出结果集合之后,程序可以使用SORT命令对结果集合进行排序,但这也意味着程序每次只能基于单一的标准对结果进行排序,尽管能够方便地基于单一的标准进行排序正是我们当初使用索引进行排序的原因之一。

假设Fake Garage创业公司想要给知识库里面的文章添加投票特性,让用户能够标示出有用的文章,那么一个合乎情理的做法就是将投票计数结果存储到记录文章信息的散列里面,然后像之前一样使用SORT命令来排序文章。但如果用户还想要同时基于文章的更新时间以及文章的投票数量进行排序,那么这种做法就不太可行了。尽管我们可以预先定义好每次投票需要给文章的评分增加多少分,但是在缺少足够的信息来判断这个增量是否合理的情况下,在早期贸然地指定一个增量,必然会导致程序在找到正确的增量之后需要重新计算文章的评分。

为了解决这个问题,我们将使用两个有序集合来分别记录文章的更新时间以及文章获得的投票数量。这两个有序集合的成员都是知识库文章的ID,而成员的分值则分别为文章的更新时间以及文章获得的投票数量。代码清单6展示了search_and_zsort()函数的定义,这个函数是search_and_sort()函数的更新版本,两个函数接受的参数非常相似,不同之处在于search_and_zsort()函数可以只基于更新时间、只基于投票数量或者同时基于以上两者对搜索结果进行排序。

def search_and_zsort(conn, query, id=None, ttl=300, update=1, vote=0,   #A
                    start=0, num=20, desc=True):                        #A

    if id and not conn.expire(id, ttl):     #B
        id = None                           #B

    if not id:                                      #C
        id = parse_and_search(conn, query, ttl=ttl) #C

        scored_search = {
            id: 0,                                  #I 这个指的是权重,Weights
            'sort:update': update,                  #D
            'sort:votes': vote                      #D
        }
        id = zintersect(conn, scored_search, ttl)   #E

    pipeline = conn.pipeline(True)
    pipeline.zcard('idx:' + id)                                     #F
    if desc:                                                        #G
        pipeline.zrevrange('idx:' + id, start, start + num - 1)     #G
    else:                                                           #G
        pipeline.zrange('idx:' + id, start, start + num - 1)        #G
    results = pipeline.execute()

    return results[0], results[1], id                               #H

#A Like before, we'll optionally take a previous result id for pagination if the result is still available
#B We will refresh the search result's TTL if possible
#C If our search result expired, or if this is the first time we've searched, perform the standard SET search
#I We use the 'id' key for the intersection, but we don't want it to count towards weights
#D Set up the scoring adjustments for balancing update time and votes. Remember: votes can be adjusted to 1, 10, 100, or higher depending on the sorting result desired.
#E Intersect using our helper function that we define in listing 7
#F Fetch the size of the result ZSET
#G Handle fetching a "page" of results
#H Return the results and the id for pagination

search_and_zsort()函数的工作方式和之前介绍的search_and_sort()函数非常相似,它们之间的主要区别在于使用了不同的方式去对搜索结果进行排序:search_and_sort()函数通过调用SORT命令进行排序;而search_and_zsort()函数则通过调用ZINTERSTORE命令,基于搜索结果集合、更新时间有序集合以及投票数量有序集合这三者进行排序。

search_and_zsort()函数使用了辅助函数zintersect()和zunion()来执行创建临时ID、执行ZINTERSTORE/ZUNIONSTOR调用、为结果有序集合设置过期时间等操作,代码清单7展示了这两个辅助函数的定义。

def _zset_common(conn, method, scores, ttl=30, **kw):
    id = str(uuid.uuid4())                                  #A
    execute = kw.pop('_execute', True)                      #J
    pipeline = conn.pipeline(True) if execute else conn     #B
    for key in scores.keys():                               #C
        scores['idx:' + key] = scores.pop(key)              #C
    getattr(pipeline, method)('idx:' + id, scores, **kw)    #D
    pipeline.expire('idx:' + id, ttl)                       #E
    if execute:                                             #F
        pipeline.execute()                                  #F
    return id                                               #G

def zintersect(conn, items, ttl=30, **kw):                              #H
    return _zset_common(conn, 'zinterstore', dict(items), ttl, **kw)    #H

def zunion(conn, items, ttl=30, **kw):                                  #I
    return _zset_common(conn, 'zunionstore', dict(items), ttl, **kw)    #I

#A Create a new temporary identifier
#B Set up a transactional pipeline so that we have consistent results for each individual call
#C Add the 'idx:' prefix to our inputs
#D Set up the call for one of the operations
#E Instruct Redis to expire the ZSET in the future
#F Actually execute the operation, unless explicitly instructed not to by the caller
#G Return the id for the caller to process the results
#H Helper function to perform ZSET intersections
#I Helper function to perform ZSET unions
#J Allow the passing of an argument to determine whether we should defer pipeline execution

上面展示的辅助函数和之前在代码清单2里介绍过的集合辅助函数很相似,新函数的主要变化在于它们可以接受一个字典参数,并通过这个字典来指定排序时使用的多个分值,所以函数需要为每个输入的键正确地添加前缀。

本节讨论了如何组合使用集合和有序集合,并基于投票数量和更新时间计算出一个简单的复合值(composite value)。尽管本节展示的程序只使用了两个有序集合来计算复合值,但随着问题的不同,计算时涉及的有序集合数量也会有所增加或者减少。

在尝试使用更具灵活性的有序集合来完全代替SORT命令和散列的时候,我们很快就会受到“有序集合的分值只能是浮点数”这一规则的限制,为了解决这个问题,我们需要学会如何把非数值数据转换为数字。

使用有序集合实现非数值排序

常见的字符串比较操作都会一个字符接一个字符地对两个字符串进行检查,直到发现一个不相等的字符,或者发现其中一个字符串比另一个字符串更短,又或者确认两个字符串相等为止。为了给存储在Redis里面的字符串数据提供类似的功能,我们需要把字符串转换为数字。本节将介绍把字符串转换为数字的方法,并将这些数字存储到Redis的有序集合里面,从而实现基于字符串前缀的排序功能。通过阅读本节,读者可以了解到如何使用字符串对存储在有序集合里面的搜索结果进行排序。

将字符串转换为数字首先要做的就是了解这种转换的局限性。因为在Redis里面,有序集合的分值是以IEEE 754双精度浮点数格式存储的,所以转换操作最大只能使用64个二进制位,并且由于浮点数格式的某些细节,转换操作并不能使用全部64个二进制位。使用63个以上的二进制位从技术上来说是可行的,但带来的效果并不比只使用63个二进制位要好多少,为了简单起见,本节展示的例子只使用了48个二进制位,这使得我们的程序只能基于数据的前6个字节进行前缀排序,但是一般来说这种程度的前缀排序已经足够了。

代码清单8展示了将字符串转换为分值的具体代码。为了将字符串转换为整数,程序首先需要把长度超过6个字符的字符串截断为6个字符长,或者把长度不足6个字符的字符串扩展至6个字符长,接着把字符串的每个字符都转换成ASCII值,最后将这些ASCII值合并为一个整数。

def string_to_score(string, ignore_case=False):
    if ignore_case:                         #A
        string = string.lower()             #A

    pieces = map(ord, string[:6])           #B
    while len(pieces) < 6:                  #C
        pieces.append(-1)                   #C

    score = 0
    for piece in pieces:                    #D
        score = score * 257 + piece + 1     #D

    return score * 2 + (len(string) > 6)    #E

#A We can handle optional case-insensitive indexes easily, so we will
#B Convert the first 6 characters of the string into their numeric values, null being 0, tab being 9, capital A being 65, etc.
#C For strings that aren't at least 6 characters long, we will add place-holder values to represent that the string was short
#D For each value in the converted string values, we add it to the score, taking into consideration that a null is different from a place holder
#E Because we have an extra bit, we can also signify whether the string is exactly 6 characters or more, allowing us to differentiate 'robber' and 'robbers', though not 'robbers' and 'robbery'

string_to_score()函数的大部分代码都很简单易懂,只有两个地方需要做进一步的解释:一是程序在字符串长度不足6个字符时,会把−1追加到字符串的末尾;二是程序在将每个字符的ASCII值添加到分值之前,都会先将当前分值乘以257。对于很多应用程序来说,能否正确地区分hello\0和hello可能是一件相当重要的事情,为此,程序会给所有ASCII值加上1(这将使得空字节的ASCII值变为1,以此类推),并使用0(−1+1)作为短字符串的填充值。此外,为了处理那些前6个字符内容相同的字符串,程序还额外使用了一个二进制位来标示字符串的长度是否超过6个字符。

通过将字符串映射为分值,程序现在能够对字符串的前6个字符进行前缀对比操作。这种做法对于非数值数据来说基本上是合理的,因为这既不需要进行大量数值计算,也不必考虑Python语言之外的其他函数库在传输大整数的时候是否会把整数转换为双精度浮点数。

因为基于字符串生成的分值除了定义排列顺序之外并不具有实际的意义,所以它们通常只会用于单独进行排序,而不会与其他分值一起进行组合排序。

参考文档