文字列の距離
仕事で文字列の類似度を計算する必要があったのでちょっとだけ頑張ってみた。 要件として、2つの文字列が与えられ、その類似度を実数与える、類似度は0から1の間に収まる、である。
Cosine Similarity
まず、最初に類似度と聞いて思い浮かべたのは余弦である。 文字列を何らかのベクトルで表して、そのベクトルがなす角の余弦を計算すれば類似度が計算できる。
文字列のベクトルとして、比較する文字で使われている文字からなるベクトルを採用した。
例えば、docとcatを比較するならばベクトルは[a, c, d, o, t]とする。
使われている成分は1を、使われていない成分を0とするとdocは[0, 1, 1, 1, 0]、catは[1, 1, 0, 0, 1]となる。
あとはこのベクトルのなす角（5次元空間！）の余弦を計算すればよい。
import math import operator import typing class CosineSimilarity: """余弦による文字列の類似度を計算する""" Vector = typing.List[float] @staticmethod def dot_product(vec1: Vector, vec2: Vector, sum=sum, map=map, mul=operator.mul) -> float: """ベクトルの内積を計算する""" return sum(map(operator.mul, vec1, vec2)) @staticmethod def norm(vec: Vector, sum=sum, map=map, mul=operator.mul) -> float: """ベクトルのEuclidノルムを計算する""" return math.sqrt(sum(map(operator.mul, vec, vec))) def cosine(self, vec1: Vector, vec2: Vector) -> float: """ベクトルのなす角の余弦を計算する""" return self.dot_product(vec1, vec2) / (self.norm(vec1) * self.norm(vec2)) def __call__(self, a: str, b: str) -> float: """文字列の類似度を計算する。類似度は0から1の間で1に近いほど類似度が高い。""" a_charset, b_charset = set(a), set(b) common_char_list = list(a_charset.union(b_charset)) a_vector = [1 if c in a_charset else 0 for c in common_char_list] b_vector = [1 if c in b_charset else 0 for c in common_char_list] return self.cosine(a_vector, b_vector)
ほぼ定義通りの実装である。
dot_product及びnormはhttps://docs.python.jp/3/library/itertools.htmlの末尾にこっそり書いてある実装を参考にした。
Callableなクラスにした理由は、利用する函数をまとめて管理したかったからである。
今回はあまりやる意味は薄いが、ノルムの計算をEuclidノルムではなく一般のノルムで計算したい場合、パラメータを与えてインスタンスを生成すれば中身を変えずにできる。
Levenshtein Distance
次に思い出したのがLevenshtein距離である。 Levenshtein距離は編集距離とも呼び、文字列を削除、追加、置換の操作で置き換える最短手数である。
思い出した理由は、誰かがTwitterでLevenshtein距離についてツイートしていたのを覚えていたからである。 三重大の奥村先生だったような気がするが誰がツイートしていたかははっきり思い出せない。
Levenshtein距離の定義は英語版のWikipediaにきちんと書いてあるのでそれを愚直に実装すればよい。
Levenshtein distance - Wikipedia
import functools class LevenshteinSimilarity: """Levenshtein距離による文字列の類似度を計算する""" @functools.lru_cache(maxsize=None) def levenshtein_distance(self, a: str, b: str) -> int: """文字列間のLevenshtein距離を計算する""" if not a: return len(b) if not b: return len(a) return min(self.levenshtein_distance(a[1:], b[1:]) + (a[0] != b[0]), self.levenshtein_distance(a[1:], b) + 1, self.levenshtein_distance(a, b[1:]) + 1) def __call__(self, a: str, b: str) -> float: """文字列の類似度を計算する。類似度は0から1の間で1に近いほど類似度が高い。""" distance = self.levenshtein_distance(a, b) try: return 1 / (distance + 1) except ZeroDivisionError: return 1
Levenshtein距離は編集の最短手数なので、類似度としてその逆数を採用した。
単純に同一文字を比較するとゼロ除算になるのでちょっと細工をしてある。
実装はhttps://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Pythonに手を加えただけであるが、定義通りであることがわかると思う。
定義から、動的計画法のアルゴリズムであることもわかる。
そのため、functools.lru_cacheでメモ化を実現している。メモ化なしで定義通りに実装すると恐らく破綻するであろう。
実験
2つの手法を比較してみる。
if __name__ == "__main__": cosine = CosineSimilarity() lev = LevenshteinSimilarity() hoge = "hoge" foo = "foobar" print("ほげほげとふーばーの類似度") print("Cosine Similarity:", cosine(hoge, foo)) print("Levenshtein Similarity:", lev(hoge, foo)) print() hogehoge = "hogehoge" print("ほげとほげほげの類似度") print("Cosine Similarity:", cosine(hoge, hogehoge)) print("Levenshtein Similarity:", lev(hoge, hogehoge)) print() yahoo = "http://www.yahoo.co.jp/" google = "https://www.google.co.jp/" print("Yahoo!のアドレスとGoogleのアドレスの類似度") print("Cosine Similarity:", cosine(yahoo, google)) print("Levenshtein Similarity:", lev(yahoo, google))
ほげほげとふーばーの類似度 Cosine Similarity: 0.22360679774997896 Levenshtein Similarity: 0.16666666666666666 ほげとほげほげの類似度 Cosine Similarity: 1.0 Levenshtein Similarity: 0.2 Yahoo!のアドレスとGoogleのアドレスの類似度 Cosine Similarity: 0.7715167498104596 Levenshtein Similarity: 0.125
考察
少し冷静になって考えるとわかるが、上記の余弦類似度は文字集合しか見ていない。
そのため、同じような文字が使われていると1に近い値を出してしまう。
上記の実験でhogeとhogehogeを比較して1の値を出している。
確かに似てはいるが1を出されると困ってしまう。
単純な文字集合ではなく、単語の集合でベクトルを算出すればよくなるかもしれない。
一方、Levenshtein距離による類似度はそれらしい値を出している。 しかし、1文字違うだけで（距離1)類似度は0.5となり、距離が離れるほど急に類似度が減少する。 単純な逆数を取るのではなく、もう少し緩やかに変化する値を考えたい。
そういう訳で、単純な逆数ではなく指数函数を採用する。
math.exp(-x/a)にLevenshtein距離を代入すればよい。
パラメータa>0を適当に調整すれば類似度の変化も調整することができる。
クラスで函数を定義してよかった気分になってきた。
class LevenshteinSimilarity: """Levenshtein距離による文字列の類似度を計算する""" def __init__(self, param=5): """paramは類似度算出のためのパラメータ。値が大きくなるほど変化がゆるやかになる。""" self.param = int(abs(param)) @functools.lru_cache(maxsize=None) def levenshtein_distance(self, a: str, b: str) -> int: """文字列間のLevenshtein距離を計算する""" if not a: return len(b) if not b: return len(a) return min(self.levenshtein_distance(a[1:], b[1:]) + (a[0] != b[0]), self.levenshtein_distance(a[1:], b) + 1, self.levenshtein_distance(a, b[1:]) + 1) def __call__(self, a: str, b: str) -> float: """文字列の類似度を計算する。類似度は0から1の間で1に近いほど類似度が高い。""" distance = self.levenshtein_distance(a, b) return math.exp(-distance / self.param)
Levenshtein距離は0以上の整数なので、math.exp(-distance / self.param)の値は0から1の間に収まる。
if __name__ == "__main__": lev = LevenshteinSimilarity(10) hoge = "hoge" foo = "foobar" print("ほげほげとふーばーの類似度") print("Levenshtein Similarity:", lev(hoge, foo)) print() hogehoge = "hogehoge" print("ほげとほげほげの類似度") print("Levenshtein Similarity:", lev(hoge, hogehoge)) print() yahoo = "http://www.yahoo.co.jp/" google = "https://www.google.co.jp/" print("Yahoo!のアドレスとGoogleのアドレスの類似度") print("Levenshtein Similarity:", lev(yahoo, google))
ほげほげとふーばーの類似度 Levenshtein Similarity: 0.6065306597126334 ほげとほげほげの類似度 Levenshtein Similarity: 0.6703200460356393 Yahoo!のアドレスとGoogleのアドレスの類似度 Levenshtein Similarity: 0.4965853037914095
必要に応じてパラメータを調整すれば何かに役に立つだろう。
感想
Levenshtein距離の定義が簡潔でよい。 Ackermann函数のように爆発するのではと一瞬思ったのはここだけの秘密である。
このように数学が絡むプログラミングは色々考えることが多くてとても楽しい。 そういえばこのブログはそういうのを扱う場所であった。原点回帰である。
