N-gramで文字列の類似度を測る

2011 年 11 月 4 日 by 山平

とある2つの文字列がどれぐらい似ているのかを比較するにはどうすればいいのかを調べる必要があったので、ネットで検索してみました。
perlにはString::Trigramというモジュールがあるようです。

String::Trigram でテキストの類似度を測る

rubyで同じようなものが見つからなかったので、取り急ぎ作って見ました。

#!/usr/bin/ruby

#類似度の比較
class String
def ngram(string, part_len = 3)
string = string.dup.gsub(/[\s\n ]+/u, "")
strlen = string.split(//u).length
points = []
source = self.gsub(/[\s\n ]+/u, "")
srcarr = source.split(//u)
sourcelen = srcarr.length
return nil if part_len > sourcelen #比較部分文字が作れない
return nil if part_len > strlen #比較対象文字より短いと比較できない
[string, source].each {|cmpstr|
counter = 0.0
(0..(sourcelen - part_len)).each{|start|#比較文字開始位置ポインタのループ
part = srcarr[start, part_len].join("") # 比較対象文字
hit = cmpstr.scan(/#{Regexp.quote(part)}/).size
counter += hit
}
points << counter
}
points.shift / points.shift #比較文字の類似度 ÷ 自分自身の類似度(基準値)
end
end

String::Trigramの動作を見ていないので同じ挙動かどうかは確認できていませんが、String自身と比較対象文字がどれくらい似ているのかを百分率で返します。
何文字ずつ比較するかを設定できますが、比較できないような長さを設定するとnilが返ります。

動作確認として、上のlivedoor Techブログさまで比較している文字列を使って実行してみましょう。

“ライブドアでブログを書く”.ngram(“ブログをライブドアで書く”)
=> 0.6
“梅雨(ばいう、つゆ)とは、北海道と小笠原諸島を除く日本や朝鮮半島南部、華南や華中の沿海部や台湾において見られる特有の気象で、5月から7月半ばにかけて毎年めぐってくる、雨の多い期間のこと。梅雨の時季が始まることを梅雨入り、梅雨が終わって夏になることを梅雨明けと言い、日本では、各地の地方気象台・気象庁が梅雨入り・梅雨明けの発表をする。”.ngram(“「梅雨」北海道と小笠原諸島を除く日本において見られる特有の気象で、5月から7月半ばにかけて毎年めぐってくる、雨の多い期間のこと。梅雨に入ることを梅雨入り、梅雨が終わって夏になることを梅雨明けと言い、日本各地の地方気象台・気象庁が梅雨入り・梅雨明けの発表をする。”)
=> 0.733333333333333

長い文字列の結果がちょっと違いますね。。。
念のため、もう少し比べてみます。

“鳴かぬなら殺してしまえホトトギス”.ngram(“鳴かぬなら鳴くまで待とうホトトギス”)
=> 0.428571428571429
“鳴かぬなら鳴くまで待とうホトトギス”.ngram(“鳴かぬなら殺してしまえホトトギス”)
=> 0.4

“織田信長は、桶狭間で今川義元を破り、天下統一の足がかりを作った”.ngram(“徳川家康は、二度に渡る大阪の陣で豊臣家を滅ぼし、名実共に天下人となった”)
=> 0.0
“織田信長は、桶狭間で今川義元を破り、天下統一の足がかりを作った”.ngram(“徳川家康は、二度に渡る大阪の陣で豊臣家を滅ぼし、名実共に天下人となった”, 2)
=> 0.1
“徳川家康は、二度に渡る大阪の陣で豊臣家を滅ぼし、名実共に天下人となった”.ngram(“織田信長は、桶狭間で今川義元を破り、天下統一の足がかりを作った”)
=> 0.0
“徳川家康は、二度に渡る大阪の陣で豊臣家を滅ぼし、名実共に天下人となった”.ngram(“織田信長は、桶狭間で今川義元を破り、天下統一の足がかりを作った”, 2)
=> 0.0882352941176471

実用に耐える程度には抽出できているようなので今回はここまでです。

タグ:

TrackBack