Redis zur automatischen Vervollständigung

Question

Wie kann ich ein Autocomplete mit redis implementieren?

Nehmen wir zum Beispiel ich ein Array ["alfred","joel","jeff","addick"] haben. Wenn ich tippe a I get ["alfred", "addick"]

Ich hoffe, Sie erhalten den Punkt. Wie kann ich dies mit redis implementieren Befehlen effizient (wenn möglich, aber ich denke, es ist). Es wäre toll, wenn ich ein paar einfachen Befehle bekommen kann ich über Telnet zu imitieren dieses Verhalten ausprobieren kann.

Danke

P. S: Merry X-mas an euch alle:)

Answer 1

Wenn Sie mit einer großen Datenmenge zu tun hat, würde ich angesichts vorschlägt dies als Trie-Implementierung. Ich habe zusammen ein kleines bisschen von Ruby geworfen, die dies tun würde:

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)

Zum Beispiel:

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

Lesen Sie mehr auf Tries unter Wikipedias Eintrag auf Tries .

Sie werden auf jeden Fall Ihre optimieren möchten vorschlagen Methode nicht alle Werte zurück, sondern nur die ersten X-Werte zurückkehr es findet. Es würde den Zweck Iterierte die gesamte Datenstruktur besiegen.

Answer 2

[Ja, 2 Jahre nach wurde die Frage gepostet, aber dennoch relevant]

Auf der der Redis Website gibt es ein komplettes Tutorial (in Ruby):

  

Auto Complete mit Redis

Answer 3

Ich fand auch diese Schnipsel, wenn Simon Willison beeindruckende Redis Tutorial .

Lösung:

  

Hallo Max,

     

KEYS ist nicht die Art und Weise, die besten zu gehen   was Sie tun können, ist stattdessen eine verwenden,   sortierte Menge. Was Sie wollen, ist zu drehen   die ersten 4 oder 5 Zeichen des   Strings in eine ganze Zahl (man kann   vorstellen, jedes Zeichen als eine Ziffer eines   Radix 256 Anzahl zum Beispiel, aber   es gibt bessere Darstellung) und   Fügen Sie alle Ihre Benutzernamen in eine sortierte   Satz.

     

Dann ZRANGEBYSCORE verwenden, können Sie bekommen   alle Elemente zwischen einem gegebenen   Bereich.

     

Diese Methode ist viel besser skalierbar als   es ist ein O (log (N)) Sache.

     

Ich bin bedeckt dieses Zeug in meinem sehr   langsam Redis Buch entwickelt sich ...

     

Cheers, Salvatore

Answer 4

Hier ist ein toter einfacher Algorithmus in PHP für die alphabetische zum automatischen Vervollständigung mit 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);

Auf der Grundlage des Artikel Auto Complete mit Redis von Salvatore, außer ich hax die Notwendigkeit, ein zusätzliches Wörterbuch zur automatischen Vervollständigung, auf Kosten eines winzigen wenig Leistungseinbuße (ein paar zadds und zrems extra), aber in den meisten Fällen zu erzeugen, sollte es gut funktionieren. Das Skript geht davon aus phpredis, aber es sollte praktisch gleich mit Predis sein.

Ausgabe Beispiele:

> 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

Dies ist eine Portierung von original antirez der Ruby-Implementierung in Python:

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

Answer 6

Ich ging gerade durch eine wunderbare Stelle, die das genaue Problem dient über Sie sprechen, und vieles mehr. prüfen it out

Answer 7

Wahrscheinlich nicht verwandte, aber wenn Sie hier gelandet ist, könnten Sie auch in der einfachen, richtigen interessiert sein, schnell und skalierbare Möglichkeit automatisch zu vervollständigen UI Felder mit Vorschlägen:

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