Comments for post Auto Complete with Redis
lior writes: Nice post! I think I will try it since I need rapid development and I have allot of auto completion scenarios
you can control the range of the set by adding another zrank command :
redis> zrank zset fo --> start Index
redis> zrank zset g --> end Index
Even though the lexicography sort is not perfect
you can get a range of results and then sort them in your local app machine by another logic
Subhranath Chunder writes: Already implemented a very basic version of it using Python and Django.
It was basically my first tryout on Redis, and it seems good.
TobyM writes: @antirez
I think the command to suggest a completion for a query would be ZREVRANGE <prefix>, 0, 4 since the zset is sorted from low to high. ZRANGE would give the _least_ frequent queries.
@Dhruv
Each prefix becomes a key pointing to a zset; each zset contains the fully query (and the score reflects how common that query is). To see the top 'k' items for a prefix 'p', just look up the 'k' highest ranked elements of the zset at the key 'p'.
Dhruv writes: Hello Antirez,
I didn't quite get how you can compute the top 'k' items by prefix and frequency as you have explaine above. Please could you explain it with an example or something more easier?
antirez writes: @Pablete: the problem is not in the data structure, adding a new "COMPLETE" command would work without adding prefixes. But our goal is trying to solve a lot of problems with a reasonably small API!
@Pedro: thanks you, fixed.
@Salman: it's done in the second part of the article, using multiple sorted sets.
@teleo: we should use strcoll() or something like that, and a version that is case insensitive probably too, before releasing Redis 2.2 (this way you can control this using environment vars). This is a known limitation indeed... also the same problem applies to SORT.
Thanks for the comments!
teleo writes: Hi Salvatore,
Thanks for the interesting post.
Most real-life cases require case-insensitive lookup, though (while preserving the original case of the results). In addition, sometimes a particular locale needs to be used.
How would you implement these cases in Redis? Also, is it possible to control the specific implementation of lexicographical sort used by Redis?
Thanks,
Te.
Pedro Melo writes: I think your code for def complete is wrong. You can end up with words in results that lack the prefix you want.
Inside the range.each you also need to break and return if the prefix of the current element is no longer the same as the prefix argument.
Salman writes: It would also be interesting to add some sort of dynamic ordering based on historical searches.
pablete writes: Would it make sense to have Ternary Search Trees (http://www.cs.princeton.edu/~rs/strings/) implemented in redis as a basic data type like t_set.c t_hash.c etc ? TST combine the time efficiency of digital tries with the space efficiency of binary search trees.
home