Redis 自动完成

Question

如何使用redis实现自动完成？

举例来说，我有一个数组

["alfred","joel","jeff","addick"]

。当我输入

a

时，我得到

["alfred", "addick"]

我希望你明白这一点。我怎样才能有效地使用redis命令来实现这个（如果可能的话，但我认为是这样）。如果我能得到一些可以通过 telnet 尝试模仿这种行为的简单命令，那就太好了。

谢谢

PS：祝大家圣诞快乐:)

Answer 1

如果您正在处理大型数据集，我建议考虑将其实现为特里树。 我已经拼凑了一小部分 Ruby 来做到这一点：

    require 'rubygems'
    require 'redis'
    
    class RedisTrie
      TERMINAL = '+'
    
      def initialize(prefix)
        @prefix = prefix
        @r = Redis.new
      end
    
      def add_word(word)
        w = word.gsub(/[^a-zA-Z0-9_-]/, '')
        key = "#{@prefix}:"
    
        w.each_char do |c|
          @r.zset_add key, c.bytes.first, c
          key += c
        end
    
        @r.zset_add key, 0, TERMINAL
      end
    
      def add_words(*words)
        words.flatten.compact.each {|word| add_word word}
      end
    
      def suggest(text)
        @r.zset_range("#{@prefix}:#{text}", 0, -1).map do |c|
          (c == TERMINAL) ? text : suggest(text + c)
        end.flatten
      end
    end
    
    rt = RedisTrie.new('trie')
    
    rt.add_words %w( apple automobile carwash oil-change cranky five ruthie axe auto )
    
    p rt.suggest(ARGV.shift.to_s)

例如：

    $ ruby RedisTrie.rb
    ["apple", "auto", "automobile", "axe", "carwash", "cranky", "five", "oil-change", "ruthie"]
    $ ruby RedisTrie.rb a
    ["apple", "auto", "automobile", "axe"]
    $ ruby RedisTrie.rb au
    ["auto", "automobile"]
    $ ruby RedisTrie.rb aux
    []

在 Wikipedia 关于 Tries 的条目中了解有关 Tries 的更多信息。

您肯定会想要优化您的建议方法，使其不返回所有值，而只返回它找到的第一个 X 值。 它会违背迭代整个数据结构的目的。

Answer 2

我在阅读 Simon Willison 令人印象深刻的 Redis 教程时也发现了这个片段。

解决方案：

你好，麦克斯，

KEYS 不是最好的方法，而是最好的方法 你可以做的就是使用 排序集。你想要的就是转 的前 4 或 5 个字符 字符串转换为整数（你可以 将每个字符想象为 a 的数字 例如基数 256 数字，但是 有更好的代表性）和 将您所有的用户名添加到排序中 设置。

然后使用ZRANGEBYSCORE你可以得到 给定之间的所有元素 范围。

此方法更具可扩展性，因为 这是一个 O(log(N)) 的事情。

我正在用我的方式覆盖这些东西 慢慢演变的 Redis 书...

干杯，萨尔瓦多

Answer 3

这里有一个非常简单的 PHP 算法，用于使用 Redis 进行字母顺序自动完成：

function getNextChar($char) {
    $char++;
    if(strlen($char) > 1) { $char--; }
    return $char;
}

function createDictionary($redis, $key, $wordList) {
    if(!$redis->exists($key)) {
        foreach($wordList as $word) {
            $redis->zadd($key, 0, $word);
        }
    }
}

function getLexicalAutocomplete($redis, $dictionaryKey, $input) {
    $inputNext = substr($input, 0, -1) . getNextChar(substr($input, -1)); //ab -> ac

    $redis->zadd($dictionaryKey, 0, $input);
    $redis->zadd($dictionaryKey, 0, $inputNext);

    $rangeStart = $redis->zrank($dictionaryKey, $input)+1;
    $rangeEnd = $redis->zrank($dictionaryKey, $inputNext)-1;

    $autocompleteResults = $redis->zrange($dictionaryKey, $rangeStart, $rangeEnd);

    $redis->zrem($dictionaryKey, $input);
    $redis->zrem($dictionaryKey, $inputNext);

    return $autocompleteResults;
}

$redis = new Redis();
$redis->connect('', 0); //Your redis server ip/port goes here

createDictionary($redis, "dict", array("alfred", "joel", "jeff", "addick"));
$result = getLexicalAutocomplete($redis, "dict", $argv[1]);

echo json_encode($result);

基于 Salvatore 的文章 Auto Complete with Redis，除了我不需要生成额外的自动完成字典，代价是一点点性能损失（额外的几个 zadds 和 zrems），但在大多数情况下它应该表现良好。该脚本假设使用 phpredis，但它实际上应该与 predis 相同。

输出示例：

> php redisauto.php a
["addick","alfred"]

> php redisauto.php ad
["addick"]

> php redisauto.php al
["alfred"]

> php redisauto.php j
["jeff","joel"]

> php redisauto.php je
["jeff"]

Answer 4

这是原始 antirez 在 Python 中的 Ruby 实现的移植：

http://varunpant.com/posts/auto-complete-with-redis-python