DevelopersIO RSS feed【非公式】 on Nostr: 【Pythonで文字列の一致率を計算してみた】 はじめに ...

【Pythonで文字列の一致率を計算してみた】
はじめに ある日、文字列の類似性って取れるのかなって疑問に思いました。ちょっと調べてみると、2つの方法を見つけたので遊んでみて違いなどまとめようと思います。 アルゴリズム 今回見つけた方法が、 difflib.SequenceMatcher.ratio() Levenshtein.distance() の2つでした。どうやらこれらは計算のアルゴリズムやそもそも測っているものが違うようです。 Gestalt pattern matching difflib.SequenceMatcher.ratio()で使われているアルゴリズムです。ぱっと見読めないんですが、ゲシュタルトと読むっぽいです。崩壊しがちなやつですね。 アルゴリズムの内容としては、各部分文字列の文字列長の総和に2をかけたものを2つの文字列の和で割ることで求めるっぽいです。 例えば、s1 = classmethod, s2 = classroom とすると、 部分文字列の文字列長の和の2倍: 2×(|class| + |o|) = 2×(5 + 1) = 12 文字列長の和: |classmethod| + |classroom| = 11 + 9 = 20 割り算: 12 / 20 = 3 / 5 = 0.6 となります。実際に実行したら結果が0.6となったので一致しています。 Levenshtein distance Levenshtein.distance()で使われているアルゴリズムです。 アルゴリズムの内容は至ってシンプルで、文字列Aと文字列Bがあるときに、文字列Aを文字列Bに置換するのに必要な操作回数(コスト)を算出します。このコストの文字列長による商が、2つの文字列の距離（差）となります。一致率を取る場合は1-距離　というようにするとよさそうです。 これも、例としてs1 = classmethod, s2 = classroomとすると、 mをrに置き換え: classrethod eをoに置き換え: classrothod tを削除: classrohod hを削除: classrood dをmに置き換え: classroom となり、コストは5であることがわかります。これを長い方の文字列長: 11で割って、0.455になります。 実際に計算すると一致しました。 コード Gestalt pattern matching Levenshtein distance パフォーマンス どうやらGestalt pattern matchingは計算量がO(n^2)ほどになるらしいです。文字列長を少しずつ変えて確認してみます。 全然違いました。使う上で決定的な違いになりそうです。ただし、「標準パッケージ」というのはかなり大きなメリットではあります。　文字列長が短いときはGestalt pattern matchingを使う、みたいな棲み分けはできてそうですね。 最後に これらのアルゴリズムはDNAの一致率を計算するのにも使われていたりするらしいです。
https://dev.classmethod.jp/articles/calc-python-string-distance/