Python で文字列の類似度を比較する

日本語の処理をしているときに厄介なのが表記揺れですよね。
「コンピューター」と「コンピュータ」、「問い合わせ」と「問い合せ」など。人間が見れば同じ単語だと分かっても、プログラムで処理する際に単純に等号で比較してしまうと別の単語扱いになってしまいます。

今回は類似度を用いて二つの単語を評価することで、表記揺れの問題に対処してみます。

単語間の類似度を算出する

単純に文字列が 等しいか/異なるか 二者択一で評価するのではなく、類似度 を用いて評価してみましょう。

類似度は 0～1 の float で表される値で、二つの単語が全く異なれば 0 、全く一致すれば 1 に評価されます。
そして、全て一致しないにしても似ている単語同士であれば 1に近い少数 に評価されます。

「一致はしないけど、まぁまぁ似てるから同じ単語なんちゃう？」というファジーな評価をするわけですね。

今回は Python を使います。はっきり言って、ものすごく簡単です。

差分計算のための difflib というライブラリがあり、その中の difflib.SequenceMatcher クラスで類似度が出せそうです。

# -*- coding: utf-8 -*-

import difflib


str1 = u"スパゲッティー"
str2 = u"スパゲティ"

s = difflib.SequenceMatcher(None, str1, str2).ratio()

print str1, "<~>", str2
print "match ratio:", s, "\n"

# >> スパゲッティー <~> スパゲティ
# >> match ratio: 0.833333333333

という訳で、「スパゲッティー」と「スパゲティ」の類似度は 83.3% です。
いい感じですね。

いろいろな単語同士を比較する

似ていない単語同士を比べた場合も見てみたいので、もうちょっといろいろなパターンを試しましょう。

# -*- coding: utf-8 -*-

import difflib


# 互いに類似度を比較する文字列のリスト
strs = [
    u"スパゲッティー",
    u"ｽﾊﾟｹﾞｯﾃｨ",
    u"スパゲティ",
    u"カペッリーニ",
]

# リスト内包表記で strs の中の文字列から重複なしの組み合わせを作る
for (str1, str2) in [
        (str1, str2)
        for str1 in strs
        for str2 in strs
        if str1 < str2
    ]:
    print str1, "<~>", str2

    # 類似度を計算、0.0~1.0 で結果が返る
    s = difflib.SequenceMatcher(None, str1, str2).ratio()
    print "match ratio:", s, "\n"

# >> スパゲッティー <~> ｽﾊﾟｹﾞｯﾃｨ
# >> match ratio: 0.0
# >>
# >> スパゲッティー <~> スパゲティ
# >> match ratio: 0.833333333333
# >>
# >> スパゲティ <~> ｽﾊﾟｹﾞｯﾃｨ
# >> match ratio: 0.0
# >>
# >> カペッリーニ <~> スパゲッティー
# >> match ratio: 0.307692307692
# >>
# >> カペッリーニ <~> ｽﾊﾟｹﾞｯﾃｨ
# >> match ratio: 0.0
# >>
# >> カペッリーニ <~> スパゲティ
# >> match ratio: 0.0

「カッペリーニ」と「スパゲッティー」の類似度 30.8% を高いと見るか低いと見るか微妙なところですが、75% あたりで線引きするのがよさそうです。

ところで、「スパゲティ」と「ｽﾊﾟｹﾞｯﾃｨ」の類似度 0% に注目してください。

日本語には 半角文字/全角文字 というもう一つ厄介なものがありましたね。
おそらく同じ物を指しているであろう単語でも半角カタカナでタイピングするだけで類似度が 0% に。これはまずい。

半角文字/全角文字を正規化してから比較する

類似度の算出に掛ける前処理として、

半角カタカナ → 全角カタカナ
全角英数字 → 半角英数字

と変換を掛けてあげるのがいいでしょう。

unicodedata.normalize() を使います。

# -*- coding: utf-8 -*-

import unicodedata


str1 = u"ｽﾊﾟｹﾞｯﾃｨ"
print str1

# >> ｽﾊﾟｹﾞｯﾃｨ

normalized_str1 = unicodedata.normalize('NFKC', str1)
print normalized_str1

# >> スパゲッティ

先ほどのコードを書き換えましょう。

# -*- coding: utf-8 -*-

import unicodedata
import difflib


# 互いに類似度を比較する文字列のリスト
strs = [
    u"スパゲッティー",
    u"ｽﾊﾟｹﾞｯﾃｨ",
    u"スパゲティ",
    u"カペッリーニ",
]

# リスト内包表記で strs の中の文字列から重複なしの組み合わせを作る
for (str1, str2) in [
        (str1, str2)
        for str1 in strs
        for str2 in strs
        if str1 < str2
    ]:
    # unicodedata.normalize() で全角英数字や半角カタカナなどを正規化する
    normalized_str1 = unicodedata.normalize('NFKC', str1)
    normalized_str2 = unicodedata.normalize('NFKC', str2)

    print str1, "<~>", str2

    # 類似度を計算、0.0~1.0 で結果が返る
    s = difflib.SequenceMatcher(None, normalized_str1, normalized_str2).ratio()
    print "match ratio:", s, "\n"

# >> スパゲッティー <~> ｽﾊﾟｹﾞｯﾃｨ
# >> match ratio: 0.923076923077
# >>
# >> スパゲッティー <~> スパゲティ
# >> match ratio: 0.833333333333
# >>
# >> スパゲティ <~> ｽﾊﾟｹﾞｯﾃｨ
# >> match ratio: 0.909090909091
# >>
# >> カペッリーニ <~> スパゲッティー
# >> match ratio: 0.307692307692
# >>
# >> カペッリーニ <~> ｽﾊﾟｹﾞｯﾃｨ
# >> match ratio: 0.166666666667
# >>
# >> カペッリーニ <~> スパゲティ
# >> match ratio: 0.0

「スパゲティ」と「ｽﾊﾟｹﾞｯﾃｨ」の類似度は 90.9% ！今度こそいい感じです。

difflib.SequenceMatcher について補足

ドキュメントを読むと、difflib.SequenceMatcher クラスは4つの引数を受け取れることになっています。

isjunk - 類似度を比較するときに無視する文字を評価関数で指定する。デフォルトは None
a - 比較される文字列の一つめ
b - 比較される文字列の二つめ
autojunk - 自動 junk ヒューリスティック の有効化/無効化フラグ。デフォルトは True(有効)

a と b は比較される二つの文字列です。

s = difflib.SequenceMatcher(a=str1, b=str2)

というように名前付きで指定することも可能です。

isjunk に関数を渡すと、類似度を算出するときに無視させる文字を指定することができます。
c を文字列の中の一文字として、isjunk(c) が True を返せばその文字は無視される。isjunk(c) が False を返せばそのまま使われる。といった具合ですね。

単語のつなぎとしてのハイフン - や括弧 (, ) などを無視させたければ、

isjunk = lambda c: c in ["-", "(", ")"]
s = difflib.SequenceMatcher(isjunk=isjunk, a=str1, b=str2)

というように適当な無名関数を渡してあげればよさそうです。

autojunk については日本語ドキュメントの説明をそのまま引用させてもらいます。

自動 junk ヒューリスティック: SequenceMatcher は、シーケンスの特定の要素を自動的に junk として扱うヒューリスティックをサポートしています。このヒューリスティックは、各個要素がシーケンス内に何回現れるかを数えます。ある要素の重複数が (最初のものは除いて) 合計でシーケンスの 1% 以上になり、そのシーケンスが 200 要素以上なら、その要素は “popular” であるものとしてマークされ、シーケンスのマッチングの目的からは junk として扱われます。このヒューリスティックは、 SequenceMatcher の作成時に autojunk パラメタを False に設定することで無効化できます。

difflib — 差分の計算を助ける

英語圏では is や the などの一般的な単語が多出するので、それを無視するためのものなのでしょう。

まとめ

Python で類似度の算出をやってみました。

驚きだったのは、類似度算出の difflib.SequenceMatcher にしても、半角/全角正規化の unicodedata.normalize() にしても、標準ライブラリだけでサクッと処理できてしまうことですね。いやー、Python すごい。

さて、表記揺れに対処するという視点で言えば、日本語にはまだまだ厄介な問題が多くあります。

「Excel」と「エクセル」のような、アルファベット/カタカナの表記揺れ
「スターバックス」と「スタバ」のような、略語の表記揺れ
「後程」と「のちほど」のような、漢字表記をひらく/ひらかない表記揺れ

これらについては今回とは違ったアプローチで対処していく必要があります。それぞれ場合へのアプローチについては、また別のエントリーで解説していきたいと思います。

私からは以上です。

無駄と文化

実用的ブログ

Python で文字列の類似度を比較する

単語間の類似度を算出する

いろいろな単語同士を比較する

半角文字/全角文字を正規化してから比較する

difflib.SequenceMatcher について補足

まとめ

単語間の類似度を算出する

いろいろな単語同士を比較する

半角文字/全角文字 を正規化してから比較する

difflib.SequenceMatcher について補足

まとめ

半角文字/全角文字を正規化してから比較する