Повторное автозаполнение
-
21-09-2019 - |
Вопрос
Как я могу реализовать автозаполнение с помощью redis?
Скажем, например, у меня есть массив ["alfred","joel","jeff","addick"]
.Когда я печатаю a
Я получаю ["alfred", "addick"]
Я надеюсь, вы поняли, к чему я клоню.Как я могу эффективно реализовать это с помощью команд redis (если это возможно, но я думаю, что это так).Было бы здорово, если бы я мог получить несколько простых команд, которые я могу опробовать через telnet, чтобы имитировать это поведение.
Спасибо
P.S:Счастливого Рождества всем вам :)
Решение
Если вы имеете дело с большим набором данных, я бы предложил рассмотреть возможность реализации этого в виде trie.Я собрал небольшой кусочек 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
[]
Подробнее о попытках читайте на Статья в Википедии о попытках.
Вы определенно захотите оптимизировать свой метод suggest, чтобы не возвращать ВСЕ значения, вместо этого возвращая только первые найденные значения X.Это сводило бы на нет цель повторения всей структуры данных.
Другие советы
[Да, через 2 года после публикации вопроса, но, тем не менее, он актуален]
На веб-сайте Redis есть полное руководство (на Ruby):
Я также нашел этот фрагмент, читая книгу Саймона Уиллисона "Впечатляющий Учебное пособие Redis.
Решение:
Привет, Макс,
КЛЮЧИ - это не лучший вариант, лучшее что вы можете сделать, это использовать вместо них отсортированный набор.То, что вы хотите повернуть первые 4 или 5 знаков строки в целочисленное значение (вы можете представьте, что каждый char в качестве цифры радикс 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);
На основе статьи Автоматическое завершение с помощью 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:
http://www.varunpant.com/posts/auto-complete-with-redis-python
Я только что прочитал потрясающий пост, в котором описана именно та проблема, о которой вы говорите, и многое другое. Зацени это
Возможно, это не связано, но если вы попали сюда, вас также может заинтересовать простой, правильный, быстрый и масштабируемый способ автозаполнения полей пользовательского интерфейса предложениями: