示例：使用反向索引构建商品筛选器

在光顾网店或者购物网站的时候，我们经常会看见图 5-15 这样的商品筛选器，对于不同的条件，这些筛选器会给出不同的选项，用户可以通过点击不同的选项来快速找到自己想要的商品。

图 5-15 笔记本电脑商品筛选器_images/IMAGE_PRODUCT_FILTER.png

比如对于图 5-15 展示的笔记本电脑筛选器来说，如果我们点击图中“品牌”一栏的“ThinkPad”图标，那么筛选器将只在页面里展示 ThinkPad 品牌的笔记本电脑。如果我们继续点击“尺寸”一栏中的“13.3英寸”选项，那么筛选器将只在页面里展示 ThinkPad 品牌的 13.3 英寸笔记本电脑，诸如此类。

实现商品筛选器的其中一种方法是使用反向索引，这种数据结构可以为每个物品添加多个关键字，然后根据关键字去反向地获取相应的物品。举个例子，对于 "X1 Carbon" 这台笔记本电脑来说，我们可以为它添加 "ThinkPad" 、 "14inch" 、 "Windows" 等关键字，然后通过这些关键字来反向获取 "X1 Carbon" 这台电脑。

实现反向索引的关键是要在物品和关键字之间构建起双向的映射关系，比如对于刚刚提到的 "X1 Carbon" 电脑来说，反向索引程序需要构建出图 5-16 所示的两种映射关系：

  • 第一种映射关系将 "X1 Carbon" 映射至它带有的各个关键字；

  • 而第二种映射关系则将 "ThinkPad" 、 "14inch" 、 "Windows" 等多个关键字映射至 "X1 Carbon" 。

图 5-16 X1 Carbon 电脑及其关键字的映射关系_images/IMAGE_X1_INDEX_1.png_images/IMAGE_X1_INDEX_2.png

代码清单 5-9 展示了一个使用集合实现的反向索引程序，对于用户给定的每一件物品，这个程序都会使用一个集合去储存物品带有的多个关键字；与此同时，对于这件物品的每一个关键字，程序都会使用一个集合去储存关键字与物品之间的映射。因为构建反向索引所需的这两种映射都是一对多映射，所以使用集合来储存这两种映射关系的做法是可行的。

代码清单 5-9 反向索引程序：/set/inverted_index.py

  1. def make_item_key(item):
  2.     return "InvertedIndex::" + item + "::keywords"
  3.  
  4. def make_keyword_key(keyword):
  5.     return "InvertedIndex::" + keyword + "::items"
  6.  
  7. class InvertedIndex:
  8.  
  9.     def __init__(self, client):
  10.         self.client = client
  11.  
  12.     def add_index(self, item, *keywords):
  13.         """
  14.         为物品添加关键字。
  15.         """
  16.         # 将给定关键字添加到物品集合中
  17.         item_key = make_item_key(item)
  18.         result = self.client.sadd(item_key, *keywords)
  19.         # 遍历每个关键字集合，把给定物品添加到这些集合当中
  20.         for keyword in keywords:
  21.             keyword_key = make_keyword_key(keyword)
  22.             self.client.sadd(keyword_key, item)
  23.         # 返回新添加关键字的数量作为结果
  24.         return result
  25.  
  26.     def remove_index(self, item, *keywords):
  27.         """
  28.         移除物品的关键字。
  29.         """
  30.         # 将给定关键字从物品集合中移除
  31.         item_key = make_item_key(item)
  32.         result = self.client.srem(item_key, *keywords)
  33.         # 遍历每个关键字集合，把给定物品从这些集合中移除
  34.         for keyword in keywords:
  35.             keyword_key = make_keyword_key(keyword)
  36.             self.client.srem(keyword_key, item)
  37.         # 返回被移除关键字的数量作为结果
  38.         return result
  39.  
  40.     def get_keywords(self, item):
  41.         """
  42.         获取物品的所有关键字。
  43.         """
  44.         return self.client.smembers(make_item_key(item))
  45.  
  46.     def get_items(self, *keywords):
  47.         """
  48.         根据给定的关键字获取物品。
  49.         """
  50.         # 根据给定的关键字，计算出与之对应的集合键名
  51.         keyword_key_list = map(make_keyword_key, keywords)
  52.         # 然后对这些储存着各式物品的关键字集合执行并集计算
  53.         # 从而查找出带有给定关键字的物品
  54.         return self.client.sinter(*keyword_key_list)

为了测试这个反向索引程序，我们在以下代码中，把一些笔记本电脑产品的名称及其关键字添加到了反向索引里面：

  1. >>> from redis import Redis
  2. >>> from inverted_index import InvertedIndex
  3. >>> client = Redis(decode_responses=True)
  4. >>> laptops = InvertedIndex(client)
  5. >>> laptops.add_index("MacBook Pro", "Apple", "MacOS", "13inch")  # 为电脑及其关键字建立索引
  6. 3
  7. >>> laptops.add_index("MacBook Air", "Apple", "MacOS", "13inch")
  8. 3
  9. >>> laptops.add_index("X1 Carbon", "ThinkPad", "Windows", "13inch")
  10. 3
  11. >>> laptops.add_index("T450", "ThinkPad", "Windows", "14inch")
  12. 3
  13. >>> laptops.add_index("XPS", "DELL", "Windows", "13inch")
  14. 3

在此之后，我们可以通过以下语句来找出 "T450" 电脑带有的所有关键字：

  1. >>> laptops.get_keywords("T450")
  2. set(['Windows', '14inch', 'ThinkPad'])

也可以使用以下语句来找出所有屏幕大小为 13 英寸的笔记本电脑：

  1. >>> laptops.get_items("13inch")
  2. set(['MacBook Pro', 'X1 Carbon', 'MacBook Air', 'XPS'])

还可以使用以下语句来找出所有屏幕大小为 13 英寸并且使用 Windows 系统的笔记本电脑：

  1. >>> laptops.get_items("13inch", "Windows")
  2. set(['XPS', 'X1 Carbon'])

或者使用以下语句来找出所有屏幕大小为 13 英寸并且使用 Windows 系统的 ThinkPad 品牌笔记本电脑：

  1. >>> laptops.get_items("13inch", "Windows", "ThinkPad")
  2. set(['X1 Carbon'])

图 5-17 展示了以上代码在数据库中为物品创建的各个集合，而图 5-18 则展示了以上代码在数据库中为关键字创建的各个集合。

图 5-17 反向索引程序为物品创建的集合_images/IMAGE_II_ITEM_INDEX.png

图 5-18 反向索引程序为关键字创建的集合_images/IMAGE_II_KEYWORD_INDEX.png