2011-09-17

rubyで文字列の似てるっぷりをチェックする

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク
rubyで2つの文字列が似ているかどうかを判別してみます。

文字列の似てるっぷりの判別にレーベンシュタイ距離(編集距離)というのを使います。
詳しくは
http://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2
を見てもらうとよいです。

簡単に言ってしまえば、何回文字を変更したり追加したり削除すれば同じ文字列になるかを数値化したものです。なのでレーベンシュタイ距離が0の場合、完全に一致していることになります。

でrubyで似てるっぷりの判別です。


Levenshteinモジュールを使うのでgemでまずインストールです。


gem install levenshtein

コードは以下のような感じにしてみました。


require 'levenshtein'
def similar(a,b)
  lev = Levenshtein.distance(a,b)
  return true if lev == 1 or lev == 2
  if a.size > b.size
    len = a.size
  else
    len = b.size
  end
  return true if lev.to_f/len < 0.2
  return false
end

とりあえず、1文字か2文字違うだけであれば似てるのでは?
としてみました。
さらに、文字列の長い方の文字列長とレーベンシュタイ距離の比が一定以下であっても似ているとしています。
ここいら辺は、好みで調整がいると思います。

本当であれば、二つの文字列を、全角に統一とか空白を事前に除去とかするともっとよいのだろうなぁと思ったりもします。

ざっくり似た感じの判別には、上のやり方でもいけるかなぁとか思ったりしています。


0 件のコメント: