質問
私はRedisのを使用してオートコンプリートを実装する方法を教えてください。
セイ例えば、私は、配列["alfred","joel","jeff","addick"]
を持っています。私が入力するとa
I GET ["alfred", "addick"]
私はあなたのポイントを得る願っています。どのように(可能ならば、私はそれだと思う)私は効率的に使用してこれRedisのコマンドを実装することができます。私は模倣この動作へのTelnet経由で試すことができますいくつかの簡単なコマンドを取得することができればそれは素晴らしいことだ。
おかげ
P.S:あなたのすべてにメリーXマス:)
解決
、私はトライとしてこれを実装する検討を示唆しています。私はこれを行うだろうルビーの小さなビットを一緒に投げています:
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
[]
続きを読むトライの Wikipediaのエントリでトライにします。
あなたは間違いなく、代わりにのみ、最初に見つかったX値を返す、すべての値を返さないようにご提案する方法を最適化することになるでしょう。これは、データ構造全体を反復するために目的を台無しにしてしまう。
他のヒント
私も、このスニペットを見つけました。
ソリューション:の
こんにちはマックス、
KEYS、最良の進むべき道ではありません あなたがすることができるものではなく、使用することです ソートセット。何が欲しいのは有効にすることです の最初の4つのまたは5文字 整数への文字列(のことができます。 Aの数字として、すべての文字を想像 基数256例えば数が、 より良い表現)が存在し、 ソートにすべてのあなたのユーザ名を追加 セットます。
次に、あなたが得ることができるZRANGEBYSCOREを使用して 与えられたとの間のすべての要素 レンジます。
この方法では、はるかにスケーラブルであるとして それO(ログ(N))のことだ。
私は非常にこのようなものをカバーしています ゆっくりと進化Redisのブック...
乾杯、サルヴァトーレ
ここでのRedisとアルファベットの自動補完のためのPHPで死んでシンプルなアルゴリズムがあります:
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);
記事I HAX除くサルヴァトーレにより、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"]
ここではPythonで元antirezのRubyの実装のポートがあります:
http://www.varunpant.com/posts/auto-complete-with-redis-python
私はちょうどあなたが話している正確な問題に役立つ素晴らしいポストを経て、そしてより多くの。 チェックそれアウトする
おそらく無関係な、しかし、あなたがここに上陸した場合、あなたはまた、提案を自動補完UIフィールドに簡単に、適切、迅速かつスケーラブルな方法に興味があるかもしれません。
ます。http://www.elasticsearch。 ORG /ガイド/ EN / elasticsearch /参照/電流/検索suggesters-completion.html の