Ruby: gem `amatch` を使って文字列同士の類似度を測る👩‍🔬

こんにちは、まどぎわです(・∀・)
rubyで文字の類似度とか測るgemとか無いかなーと探してたらamatchというgemを見つけたので、使い方とかをメモしておきます✍

amatchとは？

This is a collection of classes that can be used for Approximate matching, searching, and comparing of Strings. They implement algorithms that compute the Levenshtein edit distance, Sellers edit distance, the Hamming distance, the longest common subsequence length, the longest common substring length, the pair distance metric, the Jaro-Winkler metric. https://github.com/flori/amatch#description

私は全然詳しくないのでよくわからないのですが、色々な文字の類似度を計測するためのアルゴリズム(ハミング距離、レーベンシュタイン距離等)を使うことが出来るgemみたいです👀

github.com

最後のリリースがon 5 Jul 2017なのが気になりますが、starも330とそこそこあるみたいですね⭐

使い方

👇使い方は下記の通り結構簡単です。

require 'amatch'
include Amatch

m = Sellers.new("pattern")
# => #<Amatch::Sellers:0x40366324>
m.match("pattren")
# => 2.0

該当するアルゴリズムのClassのinitializeに対象の文字列を渡してオブジェクトを生成し、 matchメソッドの引数に比較対象の文字列を渡すと結果が返却されます👩‍🔬

実際に解析してみた

今回は下記のような簡単なwrapperクラスを用意してPairDistanceを使って試してみました👀

require 'amatch'

class SimilarMeasurer
  include Amatch

  def self.pair_distance_call(target, comparison)
    PairDistance.new(target).match(comparison)
  end
end

まずは普通の短い文字でやってみるとこんな感じになりました。1に近ければ1近いほど似ている文字のようです👀

a = 'type'
b = 'typo'
puts SimilarMeasurer.pair_distance_call(a, b)
#=> 0.6666666666666666

ヤフーニュースからとってきた全然違う記事のタイトルで、試してみた結果。

a = '常磐道あおり運転で指名手配の男、大阪で逮捕'
b = '世界で最もハンサムな顔ランキング　世界一は日本人デザイナーが見出したヒーロー'
puts SimilarMeasurer.pair_distance_call(a, b)
#=> 0.12571428571428572

ヤフーニュースからとってきた似たような記事のタイトルで、試して結果。やはり似ている記事の方が先程よりも類似度が高くなりましたね🙌

a = '常磐道あおり運転で指名手配の男、大阪で逮捕'
b = '「あおり男」確保、知人とみられる女性も警察車両に'
puts SimilarMeasurer.pair_distance_call(a, b)
#=> 0.2556390977443609

パフォーマンス

1000回、PairDistanceを使って実施してみましたけど、パフォーマンスも結構いいですね👀

a = 'サンプルサンプルサンプルサンプルサンプル'
targets = (1..1000).map { 'サンプルサンプルサンプルサンプルサンプルサンプルサンプル' }
Benchmark.bm(10){ |r| r.report { targets.each { |b| SimilarMeasurer.pair_distance_call(a, b) } } }

    user     system      total        real
0.004143   0.000100   0.004243 (  0.004276)

おわりに

文字列解析とかを検索するとpythonの情報がかなり多くて、こういう分野ではやはり強いんですね🐍
でもrubyでもこういうライブラリがあったりとか自分が知らないだけで沢山あるのかもしれないですね🙌

参考

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

ハミング距離 - Wikipedia