Redis::Asm

Fast fuzzy string search on Redis using Lua. UTF-8 Ready.

Description

Fast ASM(Approximate String Matching) by calculating edit distance within the collections such as ZSET, HASH, LIST, SET on Redis using Lua script.
Redis::Asm provides you to search multi-byte characters correctly, because it recognizes lead-byte of UTF-8 strings.

Prerequisites

This library requires a Redis server with Lua scripting support (EVAL and EVALSHA commands). This support was added in Redis 2.6.

Installation

Add this line to your application's Gemfile:

gem 'redis-asm'

And then execute:

$ bundle

Or install it yourself as:

$ gem install redis-asm

Usage

To initialize Redis::Asm with host and port:

redis = Redis.new(:host => REDIS_HOST, :port => REDIS_PORT)
asm = Redis::Asm.new(redis)

To execute fuzzy search from Redis collections:

require 'json'

# asm.search(KEY, NEELDE, MAX_RESULTS=10)

# To search from SET or LIST

result = asm.search(SET_OR_LIST_KEY, 'example')
puts JSON.parse(result).to_yaml
# ---
# - haystack: example
#   match: 1
# - haystack: samples
#   match: 0.5
# - haystack: abampere
#   match: 0.42857142857143
.
.

# To search from HASH

# Redis::Asm matches HASH values
# each item has 'field' property

result = asm.search(HASH_KEY, '東京都')
puts JSON.parse(result).to_yaml
# ---
# - haystack: "東京都"
#   field: '126'
#   match: 1
# - haystack: "京都府"
#   field: '125'
#   match: 0.33333333333333

# To search from ZSET
# each item has 'score' property

result = asm.search(ZSET_KEY, '東京都')
puts JSON.parse(result).to_yaml
# ---
# - haystack: "東京都"
#   score: '126'
#   match: 1
# - haystack: "京都府"
#   score: '125'
#   match: 0.33333333333333

Performance

  • PC: MBP 2.6 GHz Intel Core i5 16GM DD3 RAM
  • OS: Mac OSX 10.9.5
  • ruby 2.1.5p273 [x86_64-darwin13.0]
  • Redis server v=2.6.17 bits=64
# search from 10,000 items of SETS
# each item contains UTF-8 characters, and consists of between 1 and 30 chars.
% ruby search_bench.rb stone
      user     system      total        real
  0.000000   0.000000   0.000000 (  0.038567)
% ruby search_bench.rb 東京都
      user     system      total        real
  0.000000   0.000000   0.000000 (  0.022540)

% ruby search_bench.rb 弊社といたしましては
      user     system      total        real
  0.000000   0.000000   0.000000 (  0.063109)

Contributing

  1. Fork it ( https://github.com/krt/redis-asm/fork )
  2. Create your feature branch (git checkout -b my-new-feature)
  3. Commit your changes (git commit -am 'Add some feature')
  4. Push to the branch (git push origin my-new-feature)
  5. Create a new Pull Request