20

redis を使用してオートコンプリートを実装するにはどうすればよいですか?

たとえば、配列があるとし["alfred","joel","jeff","addick"]ます。入力するaと取得します["alfred", "addick"]

要点を理解していただければ幸いです。redisコマンドを使用してこれを効率的に実装するにはどうすればよいですか（可能であれば、そうだと思います）。この動作を模倣するために telnet 経由で試すことができるいくつかの簡単なコマンドを取得できれば素晴らしいことです。

ありがとう

PS: 皆さん、メリークリスマス :)

4

4 に答える 4

19

大規模なデータ セットを扱っている場合は、これをトライとして実装することを検討することをお勧めします。これを行うための小さな 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
    []

ウィキペディアの Tries に関するエントリで、 Tries の詳細を参照してください。

すべての値を返すのではなく、最初に見つかった X 値のみを返すように、suggest メソッドを最適化することをお勧めします。データ構造全体を反復するという目的が無効になります。

于 2009-12-27T15:18:44.920 に答える
6

また、Simon Willison の印象的なRedis チュートリアルを読んでいるときに、このスニペットを見つけました。

解決：

こんにちはマックス、

KEYS は適していません。代わりにソート済みセットを使用するのが最善の方法です。必要なのは、文字列の最初の 4 または 5 文字を整数に変換し (たとえば、すべての文字を基数 256 の数字として想像できますが、より適切な表現があります)、すべてのユーザー名を並べ替えられたセットに追加することです。 .

次に ZRANGEBYSCORE を使用すると、指定された範囲内のすべての要素を取得できます。

このメソッドは O(log(N)) であるため、はるかにスケーラブルです。

私は非常にゆっくりと進化しているRedisの本でこのことをカバーしています...

乾杯、サルヴァトーレ

于 2010-04-27T21:17:53.887 に答える
4

以下は、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);

Salvatore による記事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"]
于 2012-09-03T14:13:51.553 に答える
2

これは Python での元の antirez の Ruby 実装の移植です。

http://www.varunpant.com/posts/auto-complete-with-redis-python
于 2012-07-10T10:39:13.447 に答える