読者です 読者をやめる 読者になる 読者になる

何かを書き留める何か

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

世界で戦うプログラミング力を鍛える本「1.1 重複のない文字列」

CtCI Python

『世界で戦うプログラミング力を鍛える本』なる本を購入した。

www.kinokuniya.co.jp

「全プログラマー”必読”」というアオリが若干気になるが、せっかくなので問題を解くことにした。 原著ではJavaで解説されているので、Pythonで解いてみる。

1.1 重複のない文字列

文字列が与えられ、その文字列に重複がないかを判定するアルゴリズムを実装する。 Pythonの場合は辞書を使えば簡単にハッシュテーブルが実装できるし、標準モジュールcollectionを使えばもはや実装する必要すらない(この本の趣旨に反する気がする)。

テストケースはhttps://github.com/careercup/CtCI-6th-Edition-Python/blob/master/Chapter%201/1_Is%20Unique/IsUnique.pyを参照した。

from collections import Counter


def is_unique_string(s: str) -> bool:
    """
    >>> is_unique_string("abcd")
    True
    >>> is_unique_string("23ds2")
    False
    """
    c = Counter(s)
    if max(c.values()) <= 1:
        return True
    else:
        return False

collecitons.Counterを使わない場合はcollections.defaultdictを使うとよいかもしれない。

from collections import defaultdict

def is_unique_string_without_counter(s: str) -> bool:
    """
    >>> is_unique_string_without_counter("s4fad")
    True
    >>> is_unique_string_without_counter("hb 627jh=j ()")
    False
    """
    d = defaultdict(int)
    for c in s:
        d[c] += 1
    if max(d.values()) <= 1:
        return True
    else:
        return False

計算量

collecitons.Counterを使うと分かりにくいが、文字列を一通りなめて利用回数を数え上げているのでO(n)となる。 c.values()とかd.values()で最大値を調べているがこれもO(n)となるはず。

テストケースで引用したスクリプトの場合では1回だけ文字列をなめて判定をしているので僕の実装よりも効率が良いがO(n)である。 ASCII文字だけとは一言も書いていないが、ASCII文字のみの場合は文字列の長さが128文字以上となると鳩の巣原理より必ず文字が重複する。

Pythonだとあまり新たに学んだ気がしないから別の言語でやるべきかもしれない。

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

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函数のように爆発するのではと一瞬思ったのはここだけの秘密である。

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

Yahoo! JAPAN MeetUp #9 EC技術カンファレンスに参加しました

Others

私は統計警察でも統計ヤクザでもなければ無限警察でもない。

去る2017年2月18日にYahoo! JAPANにて『Yahoo! JAPAN MeetUp #9 EC技術カンファレンス』に参加した。 きっかけは先日参加した『Python 3.6 リリースパーティ』における宣伝である。 土曜日で気兼ねなく参加できるし、今の自分の仕事と重なる部分も多そうと思い参加した。 ヤフーのシステム的な内部事情も知りたいし、縁があれば面接を受けるかもしれないとも思ったからである。

以下に講演中に取ったメモとツイートを掲載する。 最初はメモを取っていたが、だんだん面倒になりツイートで代替した。

Yahoo! ショッピングの技術の話

  • ショッピングは1999年スタート。2012年に売り上げが前年割れして2013年にeコマース革命を行った。
  • 出店料無料、手数料無料。すると商品数3倍、店舗数16倍。
  • 2015年から11月11日(だったかな)を「いい買い物の日」と定めた。トラフィック量が急増。決済がダウンして偉い人に詰められる。
  • 中国アリババを訪問。トラフィックの平準化の秘訣を聞いたところ「お客様の買い物体験を優先させよ」というシステム面ではなくユーザビリティからのアドバイスを受ける。
  • カード後決済、サーキットブレーカを導入。2016年は乗り切った。
  • システム構成はPHPC++、たまにnode.js。今後はJava、node.js、C++でたまにPHPを使う。DBはOracle, MySQL, Cassandra, Redisを使っていく。
  • テクニカルディレクターとして意識しているのはトラブル検知の徹底、テストコードの徹底。
  • XPの導入、PaaSの導入、アリババのようなトラブルの自動検知及び自動解決を行っていきたい。

今後採用する技術としてJavaを選ぶあたりに、Yahoo!って大きい会社なんだなあという印象を持った。 開発規模が大きくなるとJavaの方がメリットが大きいのであろう。

これは「Q&A」のコーナーでFAQとして出てきた「どこでもオフィス」の利用率に関する回答に対する嫌味感想。 例えば、利用率の当初の想定が対象者の5%だったけど実際は10%も利用している、という状況でも「結構利用している」と答えて何ら違和感はない。 恐らく、割合を言えるほど利用者はいないのではと邪推するが、果たしてどうか。

ゼロからわかるヤフオク!システム超入門

ヤフオク!のシステムは米国Yahoo!ローカライズ版から始まったが2005年に日本独自システムが完成。 色々とレガシーな部分をどうにかこうにかリファクタリングを行っている。 現在の構成はマイクロサービスっぽい印象(そうは言っていなかったが)、かつFacadeパターンっぽい(Mediatorパターンも使っていたかも)。

これは「平行開発」という誤字を発見してほくそ笑んでいたらその誤字の真意に気づいてしまったツイート。

ヤフオク!の開発を支える技術

インフラチームによる発表でCIツールやらPaaSやらに関する話。 しっかりテストをしてるんだなー。

Yahoo! JAPANの決済 -これまでとこれから-

決済周りのシステムの開発の話。 縦軸に目盛りがない「単調増加」のグラフや言葉尻にかみついてみたりと自分の性格の悪さをひしひしと感じる。

ショッピングデータプラットフォームとデータ利活用

データプラットフォーム整備の話。 こんなに組み合わせがあります!というのをアピールするより好きな組み合わせで分析できる、のが主題である。 「可能性は無限大」と言っていたが、有限の選択肢なので高々可算である。

懇親会

ヤフオク!のインフラチームの方々、ショッピングのエンジニアの方、学生の方と雑談を行っていた。 料理はオードブルとお寿司であった。 場所が場所だけに(千代田区紀尾井町)怖くてお寿司を頼めない。

感想

日本インターネット業界の巨人『Yahoo! JAPAN』という見出しから始まる記事もある通り、ヤフーは日本のインターネットの代表の1つである。

codeiq.jp

その日本を代表するインターネット系企業の花形事業であるEC分野のシステムの様子を垣間見たのである。 その姿は、最新技術をどんどん取り入れて所謂イケてる企業、という姿ではなく長年インターネットを支えてきた、レガシーとなってしまったシステムと戦う姿であった。 システムの由来が米国Yahoo!であるものも多かった。利用者も非常に多いのでサービスを稼働させながらのリファクタリングは相当難しいだろう。 クラウド化も進んではいるものの、という印象。自前でできてしまうという面もあるし、AWSに移行させてもメリットが少ないのであろう。

社内がカンパニー制で区切られているが、カンパニーごとに文化が微妙に異なるらしい。良いことなのか悪いことなのかはちょっとすぐには判断できない。

「縁があれば面接を受けるかもしれない」と書いた。果たして僕は応募するだろうか? 率直な感想を綴ると、僕のスキルセット(Python少々、AWS少々、学部数学科レベルの数学(?)、修士(工学))とかみ合うだろうか?という思いがある。 事業は面白そうであり、全国規模(世界規模?)なので影響範囲も大きくやりがいもありそうである。 スキルに関しては今後伸ばせばよいではないか、という話でもあるのでかみ合わなそうだからやらないというのは違う気もする。

最後に、Yahoo!のスタッフの皆さんは丁寧に誘導を行ったり対応を行ったりしてとても楽しく時間を過ごすことができた。 楽しく時間を過ごしておいてグラフにケチをつけるという恩を仇で返す行為を平然と行う自分の行為を恨みつつ…。