LoginSignup
21
17

More than 5 years have passed since last update.

@krt(Masato Yamaguchi)

Redisでマルチバイト文字列を高速にあいまい検索するLuaスクリプトとruby gemを作ってみた

Last updated at Posted at 2015-01-03

やりたいこと

Redisのコレクションに入っている日本語の文字列中から、あいまいマッチでの検索結果を取得したい。

例：「 私元気です 」->

[
{"haystack":"元気そうです",   "match":0.5},
{"haystack":"元気なはずです", "match":0.429},
{"haystack":"寒そうです",    "match":0.4},
{"haystack":"書いたんです",   "match":0.333},
{"haystack":"死ぬそうです",   "match":0.333},
{"haystack":"楽しそうです",   "match":0.333},
{"haystack":"よかったです",   "match":0.333},
{"haystack":"よさそうです",   "match":0.333},
{"haystack":"学生なんです",   "match":0.333},
{"haystack":"寒かったんです", "match":0.286}
]

こういうの。全然元気そうじゃないがまあいい。

編集距離を計算して、編集距離 / haystackの文字長 で match score を算出、上位N件だけredisから返してもらう。

文字列のあいまい検索をガチでやるならば、全文検索系のDB使って、N-gramで切って転置インデックス作って・・・となるのだが、そこまでやるまでもないようなフレーズの類を そこそこ高速に 検索したいとなると、気軽に試せるのはRedisしかない（当社比）と判断し、冬休みを用いてLuaスクリプトを書いてみた。ついでに gemにしてrubyから気軽に試せるようにしてみたのでその紹介とハマり所を書いていく。

成果物

いきなり成果物から。

上記ページに行ってとりあえずスターを付けておけば、2015年の貴方は好きな人から告白されるわ宝くじは当たるわ出世しまくるわ体の悪い所全部治るわでえらい事です

gem自体の使い方はこれでもかというくらい丁寧にREADMEに書いてるんで、割愛。
ここでは「Ruby? 何言ってんだお前死ねよ」な方のために、内部で使われてるLuaスクリプトの詳細について説明する。

前提 Redis編

Redisでは組み込みでLuaが使えるので、ちょっとしたスクリプティングが行える。
たとえばこんなケースで利用できそう。

  • 楽観ロックで対処が難しそうなトランザクショナルな処理。
    Redis上のLuaはシングルスレッドで動き、その間ほかのリクエストをブロックするので、
    言わばデータベースロックがかかっているような状態になる。
  • データの中から簡単な条件絞り込みをしたものを返す
  • データに簡単な計算処理をしたものを返す

後者２つが本来想定している使い方で、最初のヤツは言ってしまえば副作用。Redisのユースケースを考えるに、リクエストをブロックされるのは本来いろいろヤバイ。できるだけLua上では簡単な処理に留めるのが定石。

今回は、個人的な気の迷いで、RedisニキとLuaニキの限界を知りたくなったため、あえて、あかん使い方をしてみた。

前提 あいまい検索編

あいまい検索を大量の長文から高速に行う用途では、前述したような転置インデックスを用いた オフライン検索 を使うのが定番。今回のような オンライン検索 は、最悪O(n^2)をm個のアイテムに対して行う時間食いなので、常にベンチマークを取りながらチューニングを行っていく。

Luaコード

全文はここ
https://github.com/krt/redis-asm/blob/master/lib/redis_asm.lua

前述したようにお年玉の代わりにスターを付けておくと好きな人から告(ry

Luaコード単体での使い方

Luaコード単体での使い方は、冒頭のコメントにあるように、redis-cliをおもむろに立ち上げ、

EVAL "このコードの内容" 1 KEY NEEDLE MAX_RESULTS

とかすればおｋ
もちろん

SCRIPT LOAD このコードの内容

して返ってきたSHA1ハッシュを覚えて、

EVALSHA sha1 1 KEY NEEDLE MAX_RESULTS

でも良い。

これから、いくつかコードを抜粋しながら、Luaスクリプトでのハマりどころを挙げていく

マルチバイト対応

Luaには文字エンコードという概念がない。すべてバイト列。なので、素直にLua上でLevenshtein距離の計算を行うコードを書くと、 「こころ」と「みかん」が部分マッチする。なので、UTF-8を利用するという前提条件を最初においてしまう。で、文字列をUTF-8で区切る処理を書いた。

-- mapping utf-8 leading-byte to byte offset
local byte_offsets = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3,
3, 3, 3, 3, 3, 3, 3}

--[[
* Split utf-8 string into multi-byte chunks according to its leading-byte.
* @param {string}
* @return {Array.<string>} Array of multi-byte strings.
--]]
local function split_into_utf8_bytes(str)
  local codes = {}
  local i
  local offset = 0

  local mb_str, byte, offset_pos

  for i = 1, #str do
    offset_pos = i + offset
    if offset_pos > #str then
      break
    end

    byte = byte_offsets[s_byte(str, offset_pos, offset_pos)] or 0

    mb_str = s_sub(str, offset_pos, offset_pos + byte)
    codes[#codes + 1] = mb_str
    offset = offset + byte
  end
  return codes
end

はい、「なにこれダサイ」言わない。Luaにはcaseに相当する構文がないので、if ... elseif ... elseif ... endとなるのだが、 厳格かつ精緻なベンチマークの結果、 offsetテーブルからオフセット値を取ってくる処理が速かった。

ここでもうひとつ注意事項。
「このデータ、、、ループ回しながらオフセットテーブル作ればいいじゃない」
Luaのテーブルは、値を追加する度毎にメモリをアロケートする処理が入るらしい。最初から項目数が決まっているテーブルは、テーブルリテラルとしてゴリゴリ記述していく方が速い。

さらにもうひとつ注意事項。
「なんかforループのロジック変じゃね。つかwhile true do...endのほうがすっきりするし」
厳格かつ精緻なベンチマークの結果、 向いてようが向いてまいがfor i = 1 ... を使うのが3倍ほど速いらしい。 @umisama の http://qiita.com/umisama/items/79a6a162549f4248427e を参照。実際ヤバイくらい速度が変わった。

もうひとつ
「UTF-8って6バイトまで許されてるはずだけど、これ想定してるの4バイトまでだよね」
はい仕様です。

マルチバイト切りすることで、最大9倍ほど、日本語のあいまい検索の速度が速くなった。だいたい3バイト毎に切ってるので、O(n^2)なら妥当な結果といえる。ベンチマークについては先ほどのリポジトリのREADME参照。

遅い

自分、Lua速い速いってよくネットで書かれてたの読んでたんで油断してたッス。
前項のUTF-8切りのとこでも速度についてすこし書いたが、ベンチマークとりながらいろんな情報を総合すると、Luaで速度を出すにはいろいろとコツがいるらしい。

組み込み関数はローカルへの参照を持っておく

local cjson = cjson
local s_byte = string.byte
local s_sub = string.sub
local s_find = string.find
local m_min = math.min
local m_max = math.max
local m_floor = math.floor
local m_ceil = math.ceil
local t_sort = table.sort

冒頭の方でこんなんやってるが、string.byte ("abc", 2)を呼び出すよりも、ローカルに作った参照s_byteを使ってs_byte ("abc", 2)を呼び出した方が速い。
http://www.lua.org/gems/sample.pdf より抜粋

for i = 1, 1000000 do
local x = math.sin(i)
end
runs 30% slower than this one:
local sin = math.sin
for i = 1, 1000000 do
local x = sin(i)
end

30%変わるのか、、

table.insertなにそれ速いの？

table.insert(t, "hoge")

よりも、

t[#t + 1] = "hoge"

の方が高速。（テーブルを配列使用している場合。というかテーブルはできるだけ配列使用で使うと速度が稼げるらしい）

三項演算子は a and b or c

@MOKYN の http://qiita.com/MOKYN/items/feec4678ee57a0e2c7d9 参照

intが無いので数値計算に気をつける

計算はincrementであっても全部float扱いだよ！

stringの破壊操作はしない

まあそうだよね

その他もっといろいろパフォーマンス上のハマリ所があったような気がしたが、、、忘れた。
結果として最初に書いたバージョンのLuaスクリプトから200倍ほど高速化した。
（ただし、前向き/後ろ向きの枝狩りで探索数を減らしたのが大きかった。）

というわけで

30文字程度の日本語が10,000件ほどあるコレクションから、10文字程度の日本語をあいまい検索する

というユースケースにおいては、20ms~30ms程度で結果を返せるようになった。
プロダクトによっては用途があるのではないかと思っている。
というわけなので、気軽にあいまい検索をしたい方は是非お試しください。

21
17
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
21
17