[Ruby]文字の間違い(揺らぎ)を検知するレーベンシュタイン距離とJaro-Winkler距離をRubyで使う方法

Levenshtein距離とJaro-Winker距離

両方とも、二つの単語、文章の間の違い(距離)を調べる方法です。

Levenshtein Distance

レーベンシュタイン距離 - Wikipedia

• 1文字削った文字列の末尾にどのような文字を追加すれば一致するか見ることで、1文字削った文字列との距離から1文字加えた文字列との距離を求めることができる。
• 数値(距離)が低ければ低いほど、似ている文字列となる

Jaro-Winkler Distance

Jaro–Winkler distance - Wikipedia, the free encyclopedia

• ジャロ・ウィンクラー距離も同じく文字列間の距離を調べるが、こちらはミスタイプをより検知することが出来る。ミスタイプはミスワードとは違い、最初の数文字は正しいことが多いという研究結果から、こちらの方法ではPrefix bonusとして、最初の文字があっている場合は、より類似度が高いと判定される。
• こちらはレーベンシュタインとは逆に、値が大きければ大きいほど類似度が高くなるので注意が必要

使い方

Levenshtein Distance

require 'levenshtein'

distance = Levenshtein::normalized_distance(cmd1, cmd2)

Jaro-Winkler Distance

require 'jaro_winkler'

distance = JaroWinkler.distance(cmd1, cmd2)

ベンチマーク

require 'levenshtein'
require 'jaro_winkler'
require 'benchmark'

def randstr(n)
  s = ("a".."z").to_a
  n.times.map{ s.sample }.join
end

Benchmark.bm do |r|
  r.report "Leven" do
    100000.times{ Levenshtein.normalized_distance(randstr(10), randstr(10)) }
  end

  r.report "Jaro" do
    100000.times{ JaroWinkler.distance(randstr(10), randstr(10)) }
  end
end

$ ruby benchmark.rb
       user     system      total        real
Leven  9.830000   0.000000   9.830000 (  9.834368)
Jaro  1.450000   0.000000   1.450000 (  1.451235)

上記の様に、速度はJaro-winklerの方が早いようである。
しかし、ベースとする理論が両者とも違うので、使用する際には仕様にあわせて検討が必要である。

自分の中では

• ECサイトでの検索ボックスのような、ユーザ間で入力する文字に揺らぎがある場合にはレーベンシュタイン
• コマンド間違いのようなものを検知するにはJaro-Winkler

かなというイメージです