autocompletar Redis

Question

¿Cómo puedo implementar un autocompletar usando Redis?

decir, por ejemplo tengo una ["alfred","joel","jeff","addick"] matriz. Cuando escribo a consigo ["alfred", "addick"]

Espero que consigue el punto. ¿Cómo puedo aplicar esto utilizando comandos de Redis eficiente (si es posible, pero creo que es). Sería muy bueno si pudiera conseguir algunos comandos simples puedo probar, a través de telnet para imitar este comportamiento.

Gracias

P.S: ¡Feliz Navidad a todos ustedes:)

Answer 1

Si usted está tratando con un gran conjunto de datos, sugeriría considerando implementar esto como un trie. He improvisado un pequeño fragmento de Ruby que había de hacer esto:

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 ejemplo:

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

Leer más en Tries en la entrada de Wikipedia sobre Tries .

Usted definitivamente quiere optimizar su sugieren método para no devolver todos los valores, en lugar de regresar solamente el primer X valora que encuentra. Se frustraría el propósito de recorrer toda la estructura de datos.

Answer 2

[Sí, 2 años después de la pregunta fue publicada, pero no obstante pertinente]

En el sitio web de la Redis, hay un tutorial completo (en Ruby):

  

automática completa con Redis

Answer 3

También encontré este fragmento al leer impresionante de Simon Willison Redis tutorial .

Solución:

  

Hola Max,

     

Las llaves no es el camino a seguir, el mejor   cosa que puede hacer es utilizar en su lugar una   conjunto ordenado. Lo que se quiere es convertir   los primeros 4 o 5 caracteres del   Cuerdas en un entero (que puede   imaginar todos los Char como un dígito de un   radix 256 número por ejemplo, pero   hay una mejor representación) y   añadir todos sus nombres de usuario en un clasificado   set.

     

A continuación, utilizando ZRANGEBYSCORE puede obtener   todos los elementos entre un dado   gama.

     

Este método es mucho más escalable como   que es un O (log (N)) cosa.

     

Estoy cubriendo estas cosas en mi muy   lenta evolución libro Redis ...

     

Saludos, Salvatore

Answer 4

Aquí hay un algoritmo simple muertos en PHP para autocompletar alfabético con 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);

Con base en el artículo automática completa con Redis por Salvatore, excepto que Hax la necesidad de generar un diccionario de autocompletar adicional, a expensas de una pequeña poco de penalización en el rendimiento (un par de zadds y zrems adicionales), pero en la mayoría de los casos se debe realizar bien. La secuencia de comandos supone phpredis, pero debería ser prácticamente lo mismo con predis.

ejemplos de salida:

> 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

Este es un puerto de la implementación de Ruby antirez original en Python:

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

Answer 6

acabo de ir a través de un mensaje increíble que sirven el problema exacto que está hablando, y más. Comprobar fuera

Answer 7

Probablemente no relacionado, pero si usted aterrizó aquí, también puede estar interesado en el camino más fácil, adecuada, rápida y escalable para autocompletar campos de interfaz de usuario con sugerencias:

http: //www.elasticsearch. org / guía / es / elasticsearch / referencia / corriente / search-que sugirieron-completion.html