Redis自动完成

如果您处理的是大型数据集,我建议您考虑将其作为trie实现。我把一小块红宝石放在一起,可以做到:

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's entry on Tries .

您肯定希望优化建议方法,使其不返回所有值,而只返回找到的前x个值。它将破坏迭代整个数据结构的目的。

[是的,问题发布后2年,但仍然相关]

在Redis网站上,有一个完整的教程(在Ruby中):

Auto Complete with Redis

我在阅读西蒙·威利森的《令人印象深刻》时也发现了这段话。 Redis tutorial .

Solution:

你好,马克斯,

钥匙不是最好的方法 你能做的就是用 排序集。你想要的是转身 的前4或5个字符 字符串转换为整数(可以 把每个字符想象成 例如,基数256,但是 有更好的表现力)和 将所有用户名添加到已排序的 集合。

然后使用zrangebyscore 在给定的 范围。

这种方法的可扩展性比 这是一个O(log(n))的东西。

我在我的 正在缓慢发展的Redis图书…

干杯,萨尔瓦多

下面是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);

根据文章 Auto Complete with Redis 萨尔瓦多,除了我需要生成一个额外的自动完成字典,以牺牲一点点的性能惩罚(几个zadds和zrems额外),但在大多数情况下,它应该表现良好。脚本假定phpredi,但实际上它应该与predi相同。

输出示例:

> 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"]

下面是在python中原始Antirez的Ruby实现的一个端口:

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

我刚读了一篇很棒的文章,它提供了你所说的确切问题,等等。 Check it out

可能不相关,但是如果您在这里登陆,您可能也会对简单、正确、快速和可扩展的方式感兴趣,以便用建议自动完成UI字段:

http://www.elasticsearch.org/guide/en/elasticsearch/reference/current/search-suggesters-completion.html