Redis autocomplete

Question

Comment puis-je mettre en œuvre une saisie semi-automatique à l'aide Redis?

Disons, par exemple, j'ai un ["alfred","joel","jeff","addick"] de tableau. Quand je tape a je reçois ["alfred", "addick"]

J'espère que vous obtenez le point. Comment puis-je mettre en œuvre cette aide des commandes Redis efficacement (si possible, mais je pense qu'il est). Ce serait génial si je pouvais obtenir quelques commandes simples, je peux essayer via telnet pour imiter ce comportement.

Merci

P.S: Merry x-mas à vous tous:)

Answer 1

Si vous avez affaire à un grand nombre de données, je suggère envisager la mise en œuvre cela comme une structure arborescente. Je l'ai jeté ensemble un petit peu de Ruby qui ferait ceci:

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)

Par exemple:

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

En savoir plus sur Tries à entrée de Wikipedia sur Tries .

Vous voulez certainement d'optimiser votre méthode pour suggérer ne pas retourner toutes les valeurs, au lieu que le premier retour X valeurs qu'il trouve. Il irait à l'encontre du but pour itérer toute la structure de données.

Answer 2

[Oui, 2 ans après la question a été publiée, mais néanmoins pertinente]

Sur le site du Redis, il y a un tutoriel complet (en Ruby):

  

Auto complet avec Redis

Answer 3

J'ai aussi trouvé cet extrait lors de la lecture Redis tutoriel .

Solution:

  

Bonjour Max,

     

TOUCHES n'est pas la voie à suivre, le meilleur   chose que vous pouvez faire est d'utiliser à la place un   ensemble trié. Ce que vous voulez est de tourner   les 4 ou 5 premiers caractères du   les chaînes dans un entier (vous pouvez   Imaginez que chaque char comme un chiffre d'un   radix 256 numéro, par exemple, mais   il y a une meilleure représentation) et   ajouter tous vos noms d'utilisateur dans un tri   ensemble.

     

Ensuite, en utilisant ZRANGEBYSCORE vous pouvez obtenir   tous les éléments entre une donnée   gamme.

     

Cette méthode est beaucoup plus évolutif que   il est une chose O (log (N)).

     

Je couvre ce genre de choses dans ma très   évoluant lentement livre Redis ...

     

Cheers, Salvatore

Answer 4

Voici un algorithme simple mort en PHP pour autocomplete alphabétique avec 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);

D'après l'article Auto Complete avec Redis par Salvatore, sauf que je Hax la nécessité de générer un dictionnaire de saisie semi-automatique supplémentaire, au détriment d'un petit peu de pénalité de performance (un couple de zadds et zrems supplémentaires), mais dans la plupart des cas, il devrait bien fonctionner. Le script suppose phpredis, mais il devrait être pratiquement la même chose avec prédispose.

Exemples de sortie:

> 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

Voici un port de mise en œuvre Ruby antirez originale en Python:

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

Answer 6

Je viens suis passé par un poste génial qui servent le problème exact que vous parlez, et plus encore. Vérifier it out

Answer 7

Probablement sans rapport, mais si vous avez atterri ici, vous pourriez être également intéressé par la voie facile, bon, rapide et évolutive à l'interface utilisateur de saisie semi-automatique des champs avec des suggestions:

http: //www.elasticsearch. org / Guide / fr / ElasticSearch / référence / courant / recherche-suggesters-completion.html