何かを書き留める何か

数学や読んだ本について書く何かです。最近は社会人として生き残りの術を学ぶ日々です。

第74回Python Mini Hack-a-thonに参加しました。

去る2017年3月25日に第74回Python Mini Hack-a-thonが行われた。

PyHackは第58回、第59回、第64回、第65回、第67回、第69回、第70回に参加している。 参加レポートがあるのは初参加の第58回のみである。もっと参加していたり、レポートを書いているつもりであったが気のせいであった。

xaro.hatenablog.jp

参加記録

内容は『Effective Debugging』を読み進めていた。

参加といいつつも大幅に遅刻して参加するという体たらくであったので、きちんと11時ごろに到着した。

デバッグの技術を66個伝える本なのに精神論が堂々とエントリされていることに驚く。

「起きてからさあ今日は数学をやるぞ」という心構えでは駄目という界隈に伝わる名言。

他の人の会話に耳を立てている。

正弦定理とか余弦定理とかは定理に名前を冠しているので覚えているが、正接はあまり思い出にない。

この後の記述にノートPCのケースが出てきた。

ヤングジャンプに連載されている『嘘喰い』にはラビリンス編とエア・ポーカーでモールス信号がでてきた。やはりいざという場合に役に立つか。

2章は総論なので長いという側面もあったが。

@mizuecastellaさんの発表に対する感想。趣味にプログラムを駆使するのはとてもよい。

PyHackの成果発表では@shinyorkeさんが発表時間を計測している。計測するようになってから時間内に終わるようになった。素晴らしい。

東京マラソンの個人記録をスクレイピングしようとした結果。懐かしい響きである。

youtu.be

本当に余談であるが、ノるどん2000の歌詞に「行き先 終点三つ前」とあるが、この時も終電の終点の3つ前が目的地であった。

今後の決意

今回、久しぶりにPyHackの参加記録を書こうと思ったのは理由がある。 1つは 2017/01/24 書き初め - 清水川Webを読んで「イベントに参加したらblogを書く」という一節にほうと感心したからである。 そのため、今年参加したイベントはいずれも参加記録を残している。このエントリが参加から時間がたっていたのは仕事で疲れ果てて書く気力が中々わかなかったからである。 今回このように書くことができてちょっと心の荷が下りたと思う。

もう1つは、PyHack後の打ち上げで@takanoryさん、@terapyonさん、@aodagさんから色々とやってみなよと励まされたからである。その記録を残して自分の励みにしようと思ったからである。

@takanoryさんからはPyCon JP 2016 1日目のLTからPython 3.6リリースパーティのLTの進歩(?)に触れ「海外のPyConでLTしなよ!」と。 @terapyonさんからは『Effective Python』『アルゴリズムクイックリファレンス 第二版』『初めてのPHP』の査読に触れ「技術書の監修・監訳をやろう!」と。 @aodagさんからは「PyConのプロポーザルだせ」と。

全部できるのかはわからないが、どれもできない話ではない。挑戦しよう。 僕はPythonと数学ができるのでそれらがテーマである技術書の監修・監訳・査読のお話があればTwitter経由でご連絡下さい。

僕が世間に出てきたのはPyCon JP 2015あたりからである。まだ仕事を初めて3年目であるが年数に関係なく躍進していきたい。

『初めてのPHP』の査読を担当しました

20167年3月18日にオライリージャパンから『初めてのPHP』の邦訳が発売される。

www.oreilly.co.jp

この度、邦訳の査読者として参加させていただいた。

オライリージャパンの方から話があったのは1月頃であった。 原著の『Learning PHP』が初心者向けならば、他言語の経験がある人の立場から見て、という体で引き受けた。 仕事でPythonを使い始め、Web周りの技術を扱っているのでそのような人間がPHPに入門したら、というイメージである。 前書きの「本書の対象読者」にも「PHPを抑えておきたいPerlPythonRubyプログラマ。」とある。

大まかに4部構成となっていて、第一部はPHPの基本として言語的な話、第二部は実践編としてPHPを使ったWeb開発、第三部はPHPに限らないプログラム開発の一般論、最後の第四部は各論という内容である。 旧版にあたる『初めての PHP5 増補改訂版』と比べてPHPを使ったWeb開発、一般論、各論が充実している。 旧版を読んだ方も改めて読めばPHP7向けに知識をアップデートする以上の利益を得ることができるであろう。

私は、今回初めてPHPに触れた。 印象として「細かい罠が多いな」というものがある。

世の中には「入門」と書いてあるのに門前払いされる場合も多々あるが、PHPはすぐに入門できる。 しかし、=====で振る舞いが違うとか、セキュリティ面で問題があるとか、入門から中級者への段差が高い印象を受けた。 PHPの公式リファレンスは日本語も充実しているので、この本や『プログラミングPHP』などで基礎体力をつけてPHPエンジニアを目指していただけば幸いである。

文字列の類似度をPythonで計算する

文字列の距離

仕事で文字列の類似度を計算する必要があったのでちょっとだけ頑張ってみた。 要件として、2つの文字列が与えられ、その類似度を実数与える、類似度は0から1の間に収まる、である。

Cosine Similarity

まず、最初に類似度と聞いて思い浮かべたのは余弦である。 文字列を何らかのベクトルで表して、そのベクトルがなす角の余弦を計算すれば類似度が計算できる。

文字列のベクトルとして、比較する文字で使われている文字からなるベクトルを採用した。 例えば、doccatを比較するならばベクトルは[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及びnormhttps://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に近い値を出してしまう。 上記の実験でhogehogehogeを比較して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函数のように爆発するのではと一瞬思ったのはここだけの秘密である。

このように数学が絡むプログラミングは色々考えることが多くてとても楽しい。 そういえばこのブログはそういうのを扱う場所であった。原点回帰である。