表記ゆれを検知する手段として、
2つの文字列の類似度を計算するgemを探していた。
どうやら手法はいくつかあるようで、「3-gram（n-gram）」と
「レーベンシュタイン距離（編集距離）」にてgemを発見することができた。
trigram gem
3-gramでの類似度を計算してくれる。
require 'trigram'
Trigram.compare("giiko_", "giik0") #=> 0.4
Trigram.compare("キャノン", "キヤノン") #=> 0.0
Trigram.compare("twitter", "facebook") #=> 0.0
levenshtein gem
編集距離は「距離」なので遠いほど大きいのだが、
使用者としては0.0〜1.0で近いほど大きい戻値であるとうれしい。
require 'levenshtein'
module Levenshtein
def self.similarity(str1, str2)
1 - normalized_distance(str1, str2)
end
end
Levenshtein.similarity("giiko_", "giik0") #=> 0.6666666666666667
Levenshtein.similarity("キャノン", "キヤノン") #=> 0.6
Levenshtein.similarity("twitter", "facebook") #=> 0.0
速度の比較
Intel Core i5-4288U @ 2.60GHzにて、
ランダムな100文字どうしを比較させる処理が何秒かかるかを、それぞれの方法で計測した。
require 'trigram'
require 'levenshtein'
require 'benchmark'
def randstr(n)
s = ("a".."z").to_a
n.times.map{ s.sample }.join
end
Benchmark.realtime do
10000.times{ Trigram.compare(randstr(100), randstr(100)) }
end / 10
# => 0.35059819999999997
Benchmark.realtime do
1000.times{ Levenshtein.normalized_distance(randstr(100), randstr(100)) }
end
# => 6.048197
文字列生成の時間を無視するとして、1回の試行にかかった平均時間は、
trigramが0.35ms、レーベンシュタイン距離が6.05msであった。
100文字どうしの比較において、両者には約17倍の速度差があるといえる。
そのほか、trigramについてわかったこと（実験コードは上の数字を変えただけなので省略）は
- 処理あたりの実行時間は、文字列長さの合計である n0 + n1（上のコードではn0, n1 = 100, 100）に比例している。
- [a-z]の100文字ではなく[ァ-ン]の100文字を用いると、処理時間が8%増える。