Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
99
Help us understand the problem. What is going on with this article?

More than 5 years have passed since last update.

@giiko_

文字列の類似度を計算するgem

表記ゆれを検知する手段として、
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%増える。

関連リンク

n-gram

レーベンシュタイン距離

その他

99
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
99
Help us understand the problem. What is going on with this article?