Redis автозаполнение

Question

Как я могу реализовать автозаполнение с помощью Redis?

Скажем, например, у меня есть массив ["alfred","joel","jeff","addick"]. Когда я печатаю a, я получаю ["alfred", "addick"]

Надеюсь, вы поняли. Как я могу реализовать это с помощью команд Redis эффективно (если это возможно, но я думаю, что это так). Было бы здорово, если бы я мог получить несколько простых команд, которые я мог бы попробовать через telnet, чтобы имитировать это поведение.

Спасибо

P.S: С Рождеством всех вас:)

Answer 1

Если вы имеете дело с большим набором данных, я бы посоветовал рассмотреть возможность реализации этого как три. Я собрал небольшой кусочек Ruby, который сделает это:

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

Узнайте больше о попытках на Википедия о попытках .

Вы определенно захотите оптимизировать предложенный метод, чтобы он не возвращал ВСЕ значения, а возвращал только первые значения X, которые он обнаружил. Это лишило бы цели итерацию всей структуры данных.

Answer 2

[Да, через 2 года после того, как вопрос был опубликован, но тем не менее актуален]

На веб-сайте Redis есть полное руководство (на Ruby):

Авто с Redis

Answer 3

Я также нашел этот фрагмент при чтении впечатляющего руководства Redis .

.

Решение:

Привет Макс,

КЛЮЧИ не путь, лучший что вы можете сделать, это использовать вместо отсортировано множество. То, что вы хотите, это повернуть первые 4 или 5 символов строки в целое число (вы можете представьте каждый символ как цифру например, число с основанием 256, но есть лучшее представление) и добавить все ваши имена пользователей в отсортированном установлен.

Тогда с помощью ZRANGEBYSCORE вы можете получить все элементы между данным диапазон.

Этот метод гораздо более масштабируемый, чем это O (log (N)) вещь.

Я освещаю этот материал в моем очень медленно развивающаяся книга Redis ...

Приветствия, Сальваторе

Answer 4

Вот простой мертвый алгоритм в 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);

Основано на статье Автозаполнение с помощью Redis , написанной Сальваторе, за исключением того, что я пытаюсь создать дополнительный словарь автозаполнения за счет небольшого снижения производительности (пара zadds и zrems дополнительно) но в большинстве случаев это должно хорошо работать. Сценарий предполагает phpredis, но он должен быть практически таким же, как и predis.

Примеры вывода:

> 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

Я только что прочитал потрясающий пост, в котором рассказывается о той проблеме, о которой вы говорите, и многое другое. Проверьте это

Answer 6

Вот порт оригинальной антивирусной реализации Ruby в Python:

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

Answer 7

Возможно, не связано, но если вы попали сюда, вас также может заинтересовать простой, правильный, быстрый и масштабируемый способ автозаполнения полей пользовательского интерфейса с предложениями:

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