Pythonで文字列の一致率を計算してみた

はじめに

ある日、文字列の類似性って取れるのかなって疑問に思いました。ちょっと調べてみると、2つの方法を見つけたので遊んでみて違いなどまとめようと思います。

アルゴリズム

今回見つけた方法が、

1. difflib.SequenceMatcher.ratio()
2. Levenshtein.distance()

の2つでした。どうやらこれらは計算のアルゴリズムやそもそも測っているものが違うようです。

Gestalt pattern matching

difflib.SequenceMatcher.ratio()で使われているアルゴリズムです。ぱっと見読めないんですが、ゲシュタルトと読むっぽいです。崩壊しがちなやつですね。

アルゴリズムの内容としては、各部分文字列の文字列長の総和に2をかけたものを2つの文字列の和で割ることで求めるっぽいです。 例えば、s1 = classmethod, s2 = classroom とすると、

1. 部分文字列の文字列長の和の2倍: 2×(|class| + |o|) = 2×(5 + 1) = 12
2. 文字列長の和: |classmethod| + |classroom| = 11 + 9 = 20
3. 割り算: 12 / 20 = 3 / 5 = 0.6

となります。実際に実行したら結果が0.6となったので一致しています。

Levenshtein distance

Levenshtein.distance()で使われているアルゴリズムです。

アルゴリズムの内容は至ってシンプルで、文字列Aと文字列Bがあるときに、文字列Aを文字列Bに置換するのに必要な操作回数(コスト)を算出します。このコストの文字列長による商が、2つの文字列の距離（差）となります。一致率を取る場合は1-距離　というようにするとよさそうです。 これも、例としてs1 = classmethod, s2 = classroomとすると、

1. mをrに置き換え: classrethod
2. eをoに置き換え: classrothod
3. tを削除: classrohod
4. hを削除: classrood
5. dをmに置き換え: classroom

となり、コストは5であることがわかります。これを長い方の文字列長: 11で割って、0.455になります。 実際に計算すると一致しました。

コード

Gestalt pattern matching

from difflib import SequenceMatcher

s1 = "classmethod"
s2 = "classroom"

sm = SequenceMatcher(a=s1, b=s2)
print(sm.ratio())

Levenshtein distance

# こっちは標準ではないので、pip install Levenshtein が必要
from Levenshtein import distance

s1 = "classmethod"
s2 = "classroom"

print(distance(s1, s2)/max(len(s1), len(s2)))

パフォーマンス

どうやらGestalt pattern matchingは計算量がO(n^2)ほどになるらしいです。文字列長を少しずつ変えて確認してみます。

全然違いました。使う上で決定的な違いになりそうです。ただし、「標準パッケージ」というのはかなり大きなメリットではあります。　文字列長が短いときはGestalt pattern matchingを使う、みたいな棲み分けはできてそうですね。

最後に

これらのアルゴリズムはDNAの一致率を計算するのにも使われていたりするらしいです。