[Python]文字列の類似度計算3つの手法を実装・比較
はじめに
文字列の類似度を定量化する手法を調べたのでPythonでの実装方法と簡単な結果をメモします。
3つのアプローチを紹介します。
ゲシュタルトパターンマッチング
概要
文字列同士の連続する共通部分を抜き出し、抜き出した文字列の前後に対しても同じ処理を繰り返すというアプローチです。
Pythonの標準ライブラリdifflibが採用しています。
その考え方は、”junk” 要素を含まない最も長い互いに隣接したマッチ列を探すことです。ここで、 “junk” 要素とは、空行や空白などの、意味を持たない要素のことです。 (junk を処理するのは、Ratcliff と Obershelp のアルゴリズムに追加された拡張です。)この考え方は、マッチ列の左右に隣接するシーケンスの断片に対して再帰的にあてはめられます。この方法では編集を最小にするシーケンスは生まれませんが、人間の目からみて「正しい感じ」にマッチする傾向があります。
(引用元 : 公式ドキュメント)
実装サンプル
import difflib
rate = difflib.SequenceMatcher(None, str1, str2).ratio()
※ドキュメントによると、「str1とstr2の順序により結果が変わることがある」とのこと。
どのような場合にそうなるかは分かっていません…
レーベンシュタイン距離法
概要
文字列同士の最小編集距離で表される距離を用います。
よく使われている手法のようで、調べた記事にはほぼこの手法について言及がありました。
編集距離とは、ある文字列を別の文字列と一致させるまでの3つの編集操作:
- 挿入
- 削除
- 置換
の回数とそのコスト(各操作に対して任意で設定できる)の合計です。
そのままでは文字列の長さを考慮しないため、標準化という処理と合わせて使うことが多いようです。
具体的には、レーベンシュタイン距離を二つの文字列の長い方の文字数で割って算出します。
この場合、0が完全一致で1が完全不一致となります。他の指標と合わせて比較するには1から結果を引きます。
実装サンプル
まずはライブラリをインストール
pip install python-Levenshtein
import Levenshtein
# レーベンシュタイン距離の取得
lev_dist = Levenshtein.distance(str1, str2)
# 標準化(長い方の文字列の長さで割る)
devider = len(str1) if len(str1) > len(str2) else len(str2)
lev_dist = lev_dist / divider
# 指標を合わせる(0:完全不一致 → 1:完全一致)
lev_dist = 1 - lev_dist
ジャロ・ウィンクラー距離法
概要
文字列同士の一致する文字数と置換の要不要から距離を計算する手法です。レーベンシュタイン距離法と並んでよく目にする手法です。文字列の部分一致を見るため、スペルチェックなどに使われているようです。
文字列の長さと部分一致の数などからJaro Distanceという指標を計算し、
先頭から何文字目までが一致しているかを加味し、ジャロ・ウィンクラー距離を算出します。
実装サンプル
レーベンシュタイン距離法でインストールしたpython-Levenshteinライブラリに入ってます
import Levenshtein
jaro_dist = Levenshtein.jaro_winkler(str1, str2)
数値を比較
上記3つのアプローチを比較してみます。
サンプルデータ
text_matcher.tsv
| str1 | str2 |
|---|---|
| this | thus |
| ABCDE | ABCDG |
| ABCDE | ABCDEF |
| tide | diet |
| hello, world | hallo, world |
| あいうえお | あえいおう |
| ご覧ください | ご覧ださい |
| アンパンマン | アソパソマソ |
| コミュニケーション | コミニュケーション |
| こんにちは みなさん おげんき ですか？ | こんちには みさなん おんげき ですか？ |
実装
text_matcher.py
import difflib
import Levenshtein
from pprint import pprint
text_filepath = 'tests/text_matcher.tsv'
results = []
# ファイル読み込み・類似度算出処理
with open(text_filepath, 'r') as fr:
# # ヘッダー作成
header = fr.readline()
header = header.strip()
columns = header.split('\t')
columns.extend(['Gestalt_1','Gestalt_2','Levenshtein','Jaro_Winkler'])
results.append(columns)
for line in fr.readlines():
line = line.strip()
data = line.split('\t')
str1 = data[0]
str2 = data[1]
# 1. ゲシュタルトパターンマッチング
gestalt1 = difflib.SequenceMatcher(None, str1, str2).ratio()
gestalt2 = difflib.SequenceMatcher(None, str2, str1).ratio()
data.append(gestalt1)
data.append(gestalt2)
# 2. レーベンシュタイン距離
lev_dist = Levenshtein.distance(str1, str2)
## 標準化
divider = len(str1) if len(str1) > len(str2) else len(str2)
lev_dist = lev_dist / divider
lev_dist = 1 - lev_dist
data.append(lev_dist)
# 3. ジャロ・ウィンクラー距離
jaro_dist = Levenshtein.jaro_winkler(str1, str2)
data.append(jaro_dist)
# 表示用に小数点第4位で四捨五入
data[2:] = [round(x, 4) for x in data[2:]]
results.append(data)
# 結果書き出し
result_filepath = 'tests/text_matcher_result.tsv'
with open(result_filepath, 'w') as fw:
for result in results:
print('\t'.join(map(str, result)),file=fw)
結果
| str1 | str2 | Gestalt_1 | Gestalt_2 | Levenshtein | Jaro_Winkler |
|---|---|---|---|---|---|
| this | thus | 0.75 | 0.75 | 0.75 | 0.8667 |
| ABCDE | ABCDG | 0.8 | 0.8 | 0.8 | 0.92 |
| ABCDE | ABCDEF | 0.9091 | 0.9091 | 0.8333 | 0.9722 |
| tide | diet | 0.25 | 0.5 | 0.25 | 0.7222 |
| hello, world | hallo, world | 0.9167 | 0.9167 | 0.9167 | 0.95 |
| あいうえお | あえいおう | 0.6 | 0.6 | 0.2 | 0.88 |
| ご覧ください | ご覧ださい | 0.9091 | 0.9091 | 0.8333 | 0.9556 |
| アンパンマン | アソパソマソ | 0.5 | 0.5 | 0.5 | 0.7 |
| コミュニケーション | コミニュケーション | 0.8889 | 0.8889 | 0.7778 | 0.9704 |
| こんにちは みなさん おげんき ですか？ | こんちには みさなん おんげき ですか？ | 0.85 | 0.85 | 0.7 | 0.96 |
上記結果から分かること:
- ジャロ・ウィンクラー距離法は文字が一致していれば順番が多少前後しても数値が高い。
- ゲシュタルトアプローチとレーベンシュタイン距離はほぼ近い数字が出るが、レーベンシュタイン距離の方が低め。
- ゲシュタルトアプローチで順序を変えると結果が変わるのは
tideとdietのみ。
ジャロ・ウィンクラー距離法がスペルチェックで使われるというのはなんとなく理解できますね。
しかし、ゲシュタルトアプローチの数字が変わるケースがよくわかりません…
もしご存知の方いらしたらご指摘いただけると幸いです。
各手法の詳しい説明は以下リンクをご参考ください。