使用redis进行搜索自动补全

待我称王封你为后i 2022-11-14 14:38 192阅读 0赞

参考《Redis In Action》：

1、自动补全最近联系人

在Web领域里面，自动补全（autocomplete）是一种能够让用户在不进行搜索的情况下，快速找到所需东西的技术。自动补全一般会根据用户已输入的字母来查找所有以已输入字母为开头的单词，有些自动补全甚至可以在用户输入句子开头的时候自动补充完整个句子；

第一个自动补全通过使用联系人列表来记录用户最近联系过的100个人，并尝试尽可能地减少实现自动补全所需的内存；

并且和Redis提供的其他结构相比，列表占用的内存是最少的，所以我们选择使用列表来存储用户的联系人信息；

构建最近联系人自动补全列表通常需要对Redis执行3个操作。第一个操作就是添加或者更新一个联系人，让他成为最新的被联系用户，这个操作包含以下3个步骤。

a、如果指定的联系人已经存在于最近联系人列表里面，那么从列表里面移除他。

b、将指定的联系人添加到最近联系人列表的最前面。

c、如果在添加操作完成之后，最近联系人列表包含的联系人数量超过了100个，那么对列表进行修剪，只保留位于列表前面的100个联系人。

以上描述的3个操作可以通过依次执行LREM命令、LPUSH命令和LTRIM命令来实现，并且为了确保操作不会带有任何竞争条件，我们会使用由MULTI命令和EXEC命令构成的事务包裹起LREM、LPUSH和LTRIM这3个命令。代码清单1展示了这个操作的具体实现代码。

/**
         * 先移除已经存在的所有联系人，然后再重新添加到列表最左端，同时只保留最近100   		个联系人
         * 
    * @param conn
    * @param user
    * @param contact
    */
    public void addUpdateContact(Jedis conn, String user, String contact) {
       String acList = "recent:" + user;
       Transaction trans = conn.multi();
       trans.lrem(acList, 0, contact);
       trans.lpush(acList, contact);
       trans.ltrim(acList, 0, 99);
       trans.exec();
    }

2、通讯录自动补全

（1）分析解决思路

对于非常长的列表来说，仅仅为了找到几个元素而获取成千上万个元素，是一种非常浪费资源的做法。因此，为了对包含非常多元素的列表进行自动补全，我们必须直接在Redis内部完成查找匹配元素的工作。

为了在客户端进行自动补全的时候，尽量减少服务器需要传输给客户端的数据量，我们将使用有序集合来直接在Redis内部完成自动补全的前缀计算工作。

在大多数情况下，我们使用有序集合是为了快速地判断某个元素是否存在于有序集合里面、查看某个成员在有序集合中的位置或索引，以及从有序集合的某个地方快速地按范围取出多个元素。然而这一次，我们将把有序集合里面的所有分值都设置为0——这种做法使得我们可以使用有序集合的另一个特性：当所有成员的分值都相同时，有序集合将根据成员的名字来进行排序；而当所有成员的分值都是0的时候，成员将按照字符串的二进制顺序进行排序。为了执行自动补全操作，程序会以小写字母的方式插入联系人的名字，并且为了方便起见，程序规定用户的名字只能包含英文字母，这样的话就不需要考虑如何处理数字或者符号了。

那么我们该如何实现这个自动补全功能呢？首先，如果我们将用户的名字看作是类似abc，abca，abcd，…，abd这样的有序字符串序列，那么查找带有abc前缀的单词实际上就是查找介于abbz...之后和abd之前的字符串。如果我们知道第一个排在abbz之前的元素的排名以及第一个排在abd之后的元素的排名，那么就可以用一个ZRANGE调用来取得所有介于abbz...和abd之间的元素，而问题就在于我们并不知道那两个元素的具体排名。为了解决这个问题，我们需要向有序集合分别插入两个元素，一个元素排在abbz...的后面，而另一个元素则排在abd的前面，接着根据这两个元素的排名来调用ZRANGE命令，最后移除被插入的两个元素。

因为在ASCII编码里面，排在z后面的第一个字符就是左花括号\{，所以我们只要将\{拼接到abc前缀的末尾，就可以得出元素abc\{，这个元素既位于abd之前，又位于所有带有abc前缀的合法名字之后。同样的，只要将\{追加到abb的末尾，就可以得出元素abb\{，这个元素位于所有带有abc前缀的合法名字之前，可以在按范围查找所有带有abc前缀的名字时，将其用作起始元素。另一方面，因为在ASCII编码里面，第一个排在a前面的字符就是反引号\`，所以如果我们要查找的是带有aba前缀的名字，而不是带有abc前缀的名字，那么可以使用\`ab作为范围查找的起始元素，并将aba\{用作范围查找的结束元素。

综上所述，通过将给定前缀的最后一个字符替换为第一个排在该字符前面的字符，可以得到前缀的前驱（predecessor），而通过给前缀的末尾拼接上左花括号，可以得到前缀的后继（successor）。为了防止多个前缀搜索同时进行时出现任何问题，程序还会给前缀拼接一个左花括号，以便在有需要的时候，根据这个左花括号来过滤掉被插入有序集合里面的起始元素和结束元素。如下代码清单展示了这个根据给定前缀生成查找范围的函数。

@SuppressWarnings("unchecked")
    public Set<String> autocompleteOnPrefix(Jedis conn, String guild, String prefix) {
        String[] range = findPrefixRange(prefix);
        String start = range[0];
        String end = range[1];
        String identifier = UUID.randomUUID().toString();
        start += identifier;
        end += identifier;
        String zsetName = "members:" + guild;
    
        conn.zadd(zsetName, 0, start);
        conn.zadd(zsetName, 0, end);
    
        Set<String> items = null;
        while (true) {
            // watch确保有序集合在范围查找过程中发生变化时，进行重试
            conn.watch(zsetName);
            // 获取返回的插入元素的开始位置
            int sindex = conn.zrank(zsetName, start).intValue();
            // 获取返回的插入元素的结束位置
            int eindex = conn.zrank(zsetName, end).intValue();
            Transaction trans = conn.multi();
            // 移除刚才插入的额外元素
            trans.zrem(zsetName, start);
            trans.zrem(zsetName, end);
            trans.zrange(zsetName, sindex, eindex - 2);
            List<Object> results = trans.exec();
            // items即是要查找匹配的集合对象
            if (results != null) {
                items = (Set<String>) results.get(results.size() - 1);
                break;
            }
        }
    
    /**
     * 在ASCII码中，排在z后面的第一个字符是{，排在a前面的第一个字符时`
     * 查找带有abc前缀的单词实际上就是查找介于abb之后和abd之前的字符串
     */
    private static final String VALID_CHARACTERS = "`abcdefghijklmnopqrstuvwxyz{";
     /**
     * 根据给定前缀生成查找范围
     * @param prefix
     * @return
     */
    public String[] findPrefixRange(String prefix) {
        int posn = VALID_CHARACTERS.indexOf(prefix.charAt(prefix.length() - 1));
        char suffix = VALID_CHARACTERS.charAt(posn > 0 ? posn - 1 : 0);
        String start = prefix.substring(0, prefix.length() - 1) + suffix + '{';
        String end = prefix + '{';
        return new String[]{start, end};
    }

参考博客：[http://bboyjing.github.io/2016/12/15/Redis%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0%E5%8D%81%E4%BA%8C%E3%80%90%E4%BD%BF%E7%94%A8Redis%E6%9E%84%E5%BB%BA%E5%BA%94%E7%94%A8%E7%A8%8B%E5%BA%8F%E7%BB%84%E4%BB%B6-%E8%87%AA%E5%8A%A8%E8%A1%A5%E5%85%A8%E3%80%91/][http_bboyjing.github.io_2016_12_15_Redis_E5_AD_A6_E4_B9_A0_E7_AC_94_E8_AE_B0_E5_8D_81_E4_BA_8C_E3_80_90_E4_BD_BF_E7_94_A8Redis_E6_9E_84_E5_BB_BA_E5_BA_94_E7_94_A8_E7_A8_8B_E5_BA_8F_E7_BB_84_E4_BB_B6-_E8_87_AA_E5_8A_A8_E8_A1_A5_E5_85_A8_E3_80_91]

[http_bboyjing.github.io_2016_12_15_Redis_E5_AD_A6_E4_B9_A0_E7_AC_94_E8_AE_B0_E5_8D_81_E4_BA_8C_E3_80_90_E4_BD_BF_E7_94_A8Redis_E6_9E_84_E5_BB_BA_E5_BA_94_E7_94_A8_E7_A8_8B_E5_BA_8F_E7_BB_84_E4_BB_B6-_E8_87_AA_E5_8A_A8_E8_A1_A5_E5_85_A8_E3_80_91]: http://bboyjing.github.io/2016/12/15/Redis%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0%E5%8D%81%E4%BA%8C%E3%80%90%E4%BD%BF%E7%94%A8Redis%E6%9E%84%E5%BB%BA%E5%BA%94%E7%94%A8%E7%A8%8B%E5%BA%8F%E7%BB%84%E4%BB%B6-%E8%87%AA%E5%8A%A8%E8%A1%A5%E5%85%A8%E3%80%91/