时间戳

首页 > 解决方案 > Search-As-You-Type with Redis（“包含”类型搜索而不是“开始于”类型搜索）

search - Search-As-You-Type with Redis（“包含”类型搜索而不是“开始于”类型搜索）

问题描述

我正在使用 Redis 开发一个按你输入的搜索功能。我需要的搜索类型是“<em>includes”类型搜索，而不是“<em>starts with”类型搜索。我已经知道 ZRANGEBYLEX 非常适合“<em>starts with”搜索，但它不能满足我的需要。例如，如果用户输入“a”，他们将看到“<strong>Ally”、“<strong>avril”、“D a ve”和“Lind a ”。如果他们输入“av”，他们将看到“<strong>avril”和“D av e”。搜索还需要不区分大小写并返回 N 个结果，按字母顺序排序。

  1. 有什么方法可以打败这种类型的搜索的线性时间？
  2. 如果没有，您是否看到任何优化以下线性时间算法的方法？

储藏：

寻找：

一些进一步的考虑： 最大用户数将低于 20,000。这就是为什么我只使用光标执行一个 SSCAN 而不循环它的原因。

谢谢！

标签： searchredisautocomplete

解决方案

您可以使用排序集构建 n-gram 索引：

Ally的 n-gram 列表是：

  • 一个、一个、一个、一个、一个、一个、一个、一个、一个、一个、一个、一个、一个、一个、一个盟友
  • 我，我，我
  • l , ly
  • 是的

对于每个 n-gram，调用ZADD以将项目添加到排序集中。每个项目由 3 个部分组成：

n-gram-in-lowercase : word-in-lowercase : original-word

例如：

zadd kkk 0 a:ally:Ally 0 al:ally:Ally 0 all:ally:Ally 0 ally:ally:Ally
zadd kkk 0 l:ally:Ally 0 ll:ally:Ally 0 lly:ally:Ally
zadd kkk 0 l:ally:Ally 0 ly:ally:Ally
zadd kkk 0 y:ally:Ally

索引所有单词后，您可以使用ZRANGEBYLEX命令进行搜索：

127.0.0.1:6379> zrangebylex kkk [a "[a\xff" limit 0 10
 1) "a:ally:Ally"
 2) "a:avril:avril"
 3) "a:dave:Dave"
 4) "a:linda:Linda"
 5) "al:ally:Ally"
 6) "all:ally:Ally"
 7) "ally:ally:Ally"
 8) "av:avril:avril"
 9) "av:dave:Dave"
10) "ave:dave:eDave"

结果已排序，但可能包含重复项，因此您需要在客户端删除这些重复项。

此解决方案将构建一个非常大的索引，还有另一种解决方案可以通过在客户端做额外的工作来减少索引大小：仅索引 n-gram 索引的一部分：

zadd k 0 ally:Ally
zadd k 0 lly:Ally
zadd k 0 ly:Ally
zadd k 0 y:Ally

搜索时，ZRANGEBYLEX命令的结果是 NOT SORTED 并且可能有重复项。因此，您需要删除重复的项目并在客户端对结果进行排序。此外，因为它没有排序，你不能使用LIMIT offset count选项，并且必须检索所有匹配的项目以找出前 N 个匹配的项目。

推荐阅读