WedX - журнал о программировании и компьютерных науках

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

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

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

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

Спасибо

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

24.12.2009

Ответы:


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. Это нарушило бы цель итерации всей структуры данных.

27.12.2009
  • Привет, Алекс, Спасибо за ответ. Мой следующий вопрос: будет ли у этого хорошая производительность, или вы бы реализовали это по-другому. Я хочу, чтобы он хорошо масштабировался. Спасибо 28.12.2009
  • Метод add_word довольно близок к тому, что я использовал для развертывания. Вы можете изменить регулярное выражение, если вставляете более сложные слова. Я бы, вероятно, убрал все струны по мере их поступления, в зависимости от того, как их использовать. Как я уже упоминал в посте, я бы также предложил остановиться, как только получит X результатов. Вы не хотите, чтобы он обрабатывал весь Trie, когда вы передаете ему пустую строку. 28.12.2009
  • Я думаю, что приведенный выше код Ruby использует старую версию redis. Вместо zset_add и zset_range команды для более новых версий должны быть zadd и zrange. 17.05.2011

  • 2

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

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

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

    08.01.2012

    3

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

    Решение:

    Привет Макс,

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

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

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

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

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

    27.04.2010

    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);
    

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

    5

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

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

    6

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

    23.04.2014

    7

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

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

    14.04.2014
    Новые материалы

    Как проанализировать работу вашего классификатора?
    Не всегда просто знать, какие показатели использовать С развитием глубокого обучения все больше и больше людей учатся обучать свой первый классификатор. Но как только вы закончите..

    Работа с цепями Маркова, часть 4 (Машинное обучение)
    Нелинейные цепи Маркова с агрегатором и их приложения (arXiv) Автор : Бар Лайт Аннотация: Изучаются свойства подкласса случайных процессов, называемых дискретными нелинейными цепями Маркова..

    Crazy Laravel Livewire упростил мне создание электронной коммерции (панель администратора и API) [Часть 3]
    Как вы сегодня, ребята? В этой части мы создадим CRUD для данных о продукте. Думаю, в этой части я не буду слишком много делиться теорией, но чаще буду делиться своим кодом. Потому что..

    Использование машинного обучения и Python для классификации 1000 сезонов новичков MLB Hitter
    Чему может научиться машина, глядя на сезоны новичков 1000 игроков MLB? Это то, что исследует это приложение. В этом процессе мы будем использовать неконтролируемое обучение, чтобы..

    Учебные заметки: создание моего первого пакета Node.js
    Это мои обучающие заметки, когда я научился создавать свой самый первый пакет Node.js, распространяемый через npm. Оглавление Глоссарий I. Новый пакет 1.1 советы по инициализации..

    Забудьте о Matplotlib: улучшите визуализацию данных с помощью умопомрачительных функций Seaborn!
    Примечание. Эта запись в блоге предполагает базовое знакомство с Python и концепциями анализа данных. Привет, энтузиасты данных! Добро пожаловать в мой блог, где я расскажу о невероятных..

    ИИ в аэрокосмической отрасли
    Каждый полет – это шаг вперед к великой мечте. Чтобы это происходило в их собственном темпе, необходима команда астронавтов для погони за космосом и команда технического обслуживания..


    Для любых предложений по сайту: [email protected]