用 Redis 做 Autocomplete

by Andy Dai | category Ｗeb 技術, Python, 其他 | 1 則留言

前陣子接到了一個需求，客戶是個電商網站，想在搜尋列當中對產品名稱做 autocomplete，最簡單的做法當然可以直接用 SQL 裡面的 LIKE 來撈產品名稱比對，在要查詢的量不多的時候沒什麼問題。但是當產品的數量到數百萬筆的時候，這種方法在速度上就會變得難以接受。往常遇到這樣的需求的時候我會考慮用 ElasticSearch 試試看，不過這次想說來點不一樣的，就來試試看 redis 吧！

Redis

一般來說，大家會拿 Redis 當作 in-memory cache 用，另外也不少人會拿來做 task queue 的 backend 使用（如 Celery）。不過 Redis 的功能不僅於此，Redis 最強大的地方就在於它本身實作了多種好用的資料結構，關於 Redis 實作的資料結構有哪些其他的用途，就等到日後有機會再來介紹。今天主要會專注在 autocomplete 相關的部分。

Sorted Set

讓我們來介紹一下 redis 的 sorted set 吧。顧名思義，redis 的 sorted set 跟我們常用的 set 一樣。只是多了兩個很重要的特性：

1. set 當中的每個 member 都有屬於自己的分數

2. member 在 sorted set 當中排序是依照分數來排序，當分數一樣的時候，則依照 member 的字典順序來排列

下面是個簡單的 sorted set 例子

redis> zadd autocomplete 0 tea
(integer) 1
redis> zadd autocomplete 0 apple
(integer) 1
redis> zadd autocomplete 0 egg
(integer) 1
redis> zadd autocomplete 0 toast
(integer) 1
redis> zadd autocomplete 0 “apple pen”
(integer) 1
redis> zrange autocomplete 0 -1
1) “apple”
2) “apple pen”
3) “egg”
4) “tea”
5) “toast”

這邊可以看到我們前面分別在 autocomplete 這個 sorted set 當中輸入了 “apple”, “apple pen”, “egg”, “tea”, “toast” 這五筆單字，最後我們用 zrange 看了一下這個 sorted set 的結果，可以發現它們依照了字母順序來排序。不過光是這樣子是沒辦法做 auto complete 的，

接下來，我們可以透過 zrank 這個指令，這個指令可以透過告訴我們某個 query 在 sorted set 當中的位置，舉個例子來說：

redis> zrank autocomplete "apple pen"
(integer) 1

這就是告訴我們 “apple pen” 這個 query 是在 autocomplete 這個 sorted set 當中 index 為 1 的位置（注意 index 是從 0 開始）。

知道了 zrank 之後，我們再加點小技巧就可以把 auto complete 完成了。小技巧如下：

對於所有單字（像是 “apple”），我們把單字的所有前綴都加到 sorted set 當中。如 apple 就會把 “a”, “ap”, “app”, “appl”, “apple” 都加入 sorted set
如果某個字是真正要拿來做 auto complete 的候選，我們在最後加上 “*” 這個字元。

所以新的 sorted set 會長的像是這樣：

redis> zrange autocomplete 0 -1
 1) "a"
 2) "ap"
 3) "app"
 4) "appl"
 5) "apple"
 6) "apple "
 7) "apple p"
 8) "apple pe"
 9) "apple pen"
10) "apple pen*"
11) "apple*"
12) "e"
13) "eg"
14) "egg"
15) "egg*"
16) "t"
17) "te"
18) "tea"
19) "tea*"
20) "to"
21) "toa"
22) "toas"
23) "toast"
24) "toast*"

當我們要做 autocomplete 的時候，只要透過以下的指令

redis> zrank autocomplete t    # 查詢 t 的位置
(integer) 15
redis> zrange 16 50    # 從 t 的位置往後查 50 筆資料
1) "te"
2) "tea"
3) "tea*"
4) "to"
5) "toa"
6) "toas"
7) "toast"
8) "toast*"

這樣我們只要看到結尾是 * 的，我們就知道這是可以拿來做 auto complete 的候選單字。

以下是這個方法的 Python 實作

import redis


AUTO_COMPLETE_SET = 'complete'     # The sorted set to use in autocomplete
RANGE_LENGTH = 50                             # Range length

r = redis.StrictRedis(host='localhost', db=0)

def insert_words(words):
    for word in words:
        for index in range(1, len(word)+1):
            prefix = word[0:index]
            r.zadd(AUTO_COMPLETE_SET, 0, prefix)
        r.zadd(AUTO_COMPLETE_SET, 0, word+'*')


def autocomplete(query, count=10):
    candidates = []
    start_index = r.zrank(AUTO_COMPLETE_SET, query)

    if not start_index:
        return []

    while len(candidates) <= count:
        possible_candidates = r.zrange(
            AUTO_COMPLETE_SET,
            start_index,
            start_index+RANGE_LENGTH-1
        )
        start_index += RANGE_LENGTH

        if not possible_candidates:
            break

        possible_candidates = [
            candidate.decode('utf-8') for candidate in possible_candidates
        ]

        for candidate in possible_candidates:
            minlen = min(len(candidate), len(query))
            if candidate[0:minlen] != query[0:minlen]:
                return candidates

            if candidate[-1] == "*":
                candidates.append(candidate[0:-1])

    return candidates


if __name__ == '__main__':
    insert_words(['測試', '測看看', '中文', '華碩', '華視'])
    print(autocomplete('測'))
    print(autocomplete('華'))
    print(autocomplete('華碩'))

這樣就可以完成一個簡單而且效率不錯的 autocomplete 功能。

Reference: http://oldblog.antirez.com/post/autocomplete-with-redis.html