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

Если вы имеете дело с большим набором данных, я бы посоветовал рассмотреть возможность реализации этого как дерева. Я собрал небольшой кусочек 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. Это нарушило бы цель итерации всей структуры данных.

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

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

Автозавершение с Redis

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

Решение:

Привет Макс,

KEYS - это не лучший вариант, лучшее, что вы можете сделать, - это использовать вместо этого отсортированный набор. Вы хотите превратить первые 4 или 5 символов строк в целое число (например, вы можете представить каждый символ как цифру числа с основанием 256, но есть лучшее представление) и добавить все свои имена пользователей в отсортированный набор .

Затем, используя ZRANGEBYSCORE, вы можете получить все элементы между заданным диапазоном.

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

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

Ура, Сальваторе

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

На основании статьи Сальваторе Auto Complete with 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"]

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

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

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

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

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