この記事でやること
- 最近表題の2つの"距離"に触れる機会があったのだが、知らなかったのでまとめる
- ライブラリを使った計算方法もまとめる
まず最初に導入として編集距離について説明する。
編集距離とは
2つの文字列がどれくらい似ているかを調べたいとする。
このとき、編集距離を使うと便利。
編集距離とは、挿入(insertion)、削除(deletion)、置換(substitution) を何回行えば
同じ文字にすることができるか、で考えることができる。
「編集距離が大きい = 文字列を揃えるのにコストがかかる = 類似度が低い」と言える。
編集距離は上記の組み合わせによって複数パターンが考えられるが、その中でも最小ものを最短編集距離と呼ぶ。
例えば「おにぎり」と「おまいり」と比較するとする。
この場合、「に→ま」、「ぎ→い」 と2回置換すれば一致できる。
一方で置換の作業を 「に」を削除→「ま」を挿入 という手順を踏めば、編集手順は長くなる。
このように編集距離はいろんなパターンが考えられるが、ここでは「2回置換」が一番最小コストで済むので
最短編集距離は2となる。
「おにぎり」と「こんぶおにぎり」 の場合は「こんぶ」の3文字を挿入すれば一致するため、
最短編集距離は3になる。
ハミング距離
「おにぎり」と「おまいり」の例のように文字数が揃っている場合は、上で見たように置換だけで
文字を一致することができる。
この時に必要な編集距離をハミング距離という。
例えば4桁の数字で
"1101"と"0001"のハミング距離は2になる。
「おにぎり」と「こんぶおにぎり」 のように文字列が揃っていない場合は、挿入、削除処理が必要になるので以下で述べるレーベンシュタイン距離などを用いる。
レーベンシュタイン距離
上記のように挿入(insertion)、削除(deletion)、置換(substitution) を使って何回で文字列を一致させることができるかをレーベンシュタイン距離という。
つまり上で述べた最短編集距離と同じだ。
ただ、これは挿入、削除、置換のコストを全て同じ(=1)とおいた場合であり、別々にコストを設定することもできる。
その場合は最短編集距離とは一致しないので注意。
Pythonで計算する場合はLevenshteinというライブラリを使えば簡単に計算することができる。
import Levenshtein
str1 = 'おにぎり'
str2 = 'こんぶおにぎり'
dist = Levenshtein.distance(str1, str2)
print(dist) # 3
先ほども述べたように、
レーベンシュタイン距離が大きい = 類似度が低い と言える。
ただし、「おにぎり」と「ボンゴレ」の距離が4なのに対して「おにぎり」「ツナマヨおにぎり」の距離も4であり、これは直感に合わない。
直感的には後者の方が類似しているように見えるからだ。
そこで、文字列で割って規格化することでより直感に近い数字を出すことができる。
例えば前者の場合は文字数4で割るため距離は1、後者の場合は長い方の文字数8で割るため距離は0.5となり、後者の方が類似度が高くなる。
ジャロ・ウィンクラー距離
もう一つジャロ・ウィンクラー距離を紹介する。
こちらもレーベンシュタイン距離と同じく二つの文字列がどれくらい一致している/一致していないかを表すが、やや式が複雑なので、順番に計算していく。
ジャロ類似性
まずはジャロ類似性を以下のように定義する。
sim_{j} = W_{1}\frac{c}{|s_{1}|} + W_{2}\frac{c}{|s_{2}|} + W_{3}\frac{c-\tau}{c}
|s1|, |s2|はそれぞれ文字列s1, s2の長さを表す。
W1、W2はそれぞれ1つ目の文字列、2つ目の文字列の重みを表し、W3は置換に関わる重みを表す定数である。
これらはすべて等しく1/3とおくのが一般的だ。
そうすると先程の式は
sim_{j} = \frac{1}{3} \left(\frac{c}{|s_{1}|} + \frac{c}{|s_{2}|} + \frac{c-\tau}{c}\right)
となる。
次にcの定義について説明する。
s1の文字列を最初から順番に見ていったときに、s2の文字列においてn文字以内に同じ文字があればカウントアップしていく。
このときカウント数がcになる。
このときのnの定義は以下
n = \frac{\rm{max}(|s_{1}|, |s_{2}|)}{2} - 1
これは2つの文字のうち長い方の長さを2で割って、1引いたものだ。
例えば |s1| = 7, |s2| = 8 だと
8/2 - 1 = 3
となる。
この場合s1とs2を比較して3文字以内に同じ文字があればカウントアップしていく。
また、文字は一致しているものの位置が入れ替わっている場合を転置としてカウントし、2で割った値をτとする。
以下のサイトの図解がわかりやすいかった。
https://mieruca-ai.com/ai/levenshtein_jaro-winkler_distance/
ジャロ類似性は0-1の範囲を取る。
もし二つの文字列が完全に一致していた場合は|s1| = |s2| = c, τ = 0となるため、ジャロ類似性は
1/3(1+1+1) = 1 となる。
逆にc=0の場合はジャロ類似性は0と定義する。
ジャロ・ウィンクラー距離の定式化
次に、ジャロ類似性に少し手を加える。
一般に、打ち間違いをした場合でも最初の数文字は一致している可能性が高い。
例えば"measure"を"measrue"と打ち間違えることはあっても"emasure"と打ち間違えることは稀だろう。
なので、先程のジャロ類似性に「先頭のl文字が一致した場合」のボーナスポイントを追加してあげる。
こうして新しく定義した以下の値をジャロ・ウィンクラー類似度という。
sim_{w} = sim_{j}+lp(1-sim_{j})
ここでlの上限は4とする。
つまり、先頭の5文字が一致していた場合でも4とする。
類似度の上限を1にするためにはpは0.25以下の定数として設定する必要があるが、p=0.1とするのが標準らしい。
さて、類似度は大きいほどs1とs2は似ており、一方で距離は小さいほど似ていることを考え、ジャロ・ウィンクラー距離を
d_{w} = 1-sim_{w}
と定義する。
定義よりジャロ・ウィンクラー距離も0-1の範囲を取るが、厳密にはこの値は三角不等式を満たさないため"距離"ではないらしい。
ジャロ・ウィンクラー類似度もライブラリを使って簡単に実装できる。
import Levenshtein
str1 = 'おにぎり'
str2 = 'こんぶおにぎり'
str3 = 'うめおにぎり'
dist_jaro1 = Levenshtein.jaro_winkler(str1, str2)
print(dist_jaro1) # 0.0
dist_jaro2 = Levenshtein.jaro_winkler(str1, str3)
print(dist_jaro2) # 0.8888..
"こんぶおにぎり"と"おにぎり"を比較してみると、それぞれ文字数は7, 4文字なので、
n=7/2 - 1 = 2
となる。（7/2は切り捨て）
"こんぶ"の3文字があることによって、"おにぎり"のそれぞれの文字は3文字（つまり、2文字より大きく）離れてしまっているため、ジャロ・ウィンクラー距離は0になる。
逆に"さけおにぎり"と"おにぎり"の場合は n = 6/2 - 1 = 2であり、"おにぎり"の4文字は2文字以内の距離に収まっているため、ジャロ類似度は
sim_{j} = \frac{1}{3} \left(\frac{4}{6} + \frac{4}{4} + \frac{4-0}{4}\right) = \frac{8}{9} = 0.888...
となる。
また、最初の文字から一致していないためボーナスポイントはなしとなり、ジャロ・ウィンクラー類似度はジャロ類似度と同じ0.888..となる。
このLevenshtein.jaro_winkler(str1, str2)の部分はネットの記事を漁ると"ジョン・ウィンクラー距離"として紹介されているものが多いが、厳密には"ジョン・ウィンクラー類似度"と言う方が正しい気がしている。（何か他に理由があるのかな？）
その他の方法
文字列全体のうち何文字が部分一致しているかを調べたければ、Pythonの標準ライブラリであるdifflib.SequenceMatcherを使って類似度の比較ができる。
詳細は割愛するが、使い方は以下
import difflib
str1 = 'おにぎり'
str2 = 'うめおにぎり'
sim = difflib.SequenceMatcher(None, str1, str2).ratio()
print(sim) # 0.8
10文字中8文字が一致しているため出力は0.8となる。
参考: https://qiita.com/aizakku_nidaa/items/20abcd8aa32152786687
まとめ
- "レーベンシュタイン距離"と"ジャロ・ウィンクラー距離"についてまとめた
- どちらも二つの文字列の類似度に関連している
- ライブラリ
Levenshteinを使えば簡単に計算することができる