Redis AutoComplete

Question

Como posso implementar um preenchimento automático usando o Redis?

Diga, por exemplo, eu tenho uma matriz ["alfred","joel","jeff","addick"]. Quando eu digito a eu recebo ["alfred", "addick"]

Espero que voce tenha entendido. Como posso implementar isso usando comandos Redis com eficiência (se possível, mas acho que é). Seria ótimo se eu pudesse obter alguns comandos simples que posso experimentar via Telnet para imitar esse comportamento.

Obrigado

PS: Merry X-Mas a todos vocês :)

Answer 1

Se você estiver lidando com um grande conjunto de dados, sugiro considerar implementar isso como um trie. Eu joguei um pequeno pouco de rubi que faria isso:

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)

Por exemplo:

$ 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
[]

Leia mais sobre tentativas em Entrada da Wikipedia sobre tentativas.

Definitivamente, você desejará otimizar seu método sugerido para não retornar todos os valores, em vez de retornar apenas os primeiros valores X encontrados. Derrotaria o objetivo de iterar toda a estrutura de dados.

Answer 2

Sim, 2 anos após a publicação da pergunta, mas ainda assim relevante

No site da Redis, há um tutorial completo (em Ruby):

Auto completo com redis

Answer 3

Eu também encontrei esse trecho ao ler impressionante de Simon Willison Tutorial de Redis.

Solução:

Olá Max,

Keys não é o caminho a percorrer, a melhor coisa que você pode fazer é usar um conjunto classificado. O que você quer é transformar os primeiros 4 ou 5 caracteres das cordas em um número inteiro (você pode imaginar cada char como um dígito de um número da Radix 256, por exemplo, mas há melhor representação) e adicionar todos os seus nomes de usuário em um conjunto classificado .

Em seguida, usando o ZrangeByScore, você pode obter todos os elementos entre um determinado intervalo.

Esse método é muito mais escalável, pois é uma coisa O (log (n)).

Estou cobrindo essas coisas no meu livro Redis em evolução muito lenta ...

Saúde, Salvatore

Answer 4

Aqui está um algoritmo simples morto no PHP para preenchimento autocompleto alfabético com 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);

Com base no artigo Auto completo com redis Por Salvatore, exceto que eu tenho a necessidade de gerar um dicionário adicional de preenchimento automático, às custas de uma pequena penalidade de desempenho (alguns Zadds e Zrems extra), mas na maioria dos casos deve ter um bom desempenho. O script assume phpredis, mas deve ser praticamente o mesmo com o Predis.

Exemplos de saída:

> 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 5

Aqui está um porto da implementação do Ruby de Antirez original em Python:

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

Answer 6

Acabei de passar por um post incrível que serve o problema exato de que você está falando e muito mais. Confira

Answer 7

Provavelmente não relacionado, mas se você aterrissar aqui, também poderá estar interessado na maneira fácil, adequada, rápida e escalável de preencher os campos de interface do usuário com sugestões:

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