schedule2018-07-17

06. 集合

はじめに

言語処理100本ノック 2015

Pythonを勉強するため、東京工業大学の岡崎教授が出題されている言語処理100本ノック 2015を解いていきます。

より深く理解するため、別解や利用したライブラリの解説もまとめていきます。

環境

Python3.6

OS : mac

問題

06. 集合
"paraparaparadise"と"paragraph"に含まれる文字bi-gramの集合を,それぞれ, XとYとして求め,XとYの和集合,積集合,差集合を求めよ.さらに,'se'というbi-gramがXおよびYに含まれるかどうかを調べよ.

集合演算

参考 Python, set型で集合演算(和集合、積集合や部分集合の判定など)

参考というか、まんま答えにたどり着いてしまったのですが、上記のリンクを参考にしています。

集合は要素の集まりです。重複する要素はありません。重複を許した場合は多重集合となります。

解答

x_str = "paraparaparadise"
y_str = "paragraph"


def n_gram(sentence, N):
    """
    文字のn-gramを返す。
    """
    result = []
    for it in range(len(sentence)):
        if it + N > len(sentence):
            return result
        result.append(sentence[it: it+N])

X = set(n_gram(x_str, N=2))
Y = set(n_gram(y_str, N=2))

print(X)
# => {'is', 'se', 'ad', 'di', 'ap', 'ar', 'pa', 'ra'}
print(Y)
# => {'ph', 'gr', 'ra', 'ap', 'ar', 'pa', 'ag'}

# 和集合
_sum = X | Y

print(_sum)
# => {'ar', 'ad', 'is', 'ag', 'pa', 'ap', 'ph', 'ra', 'gr', 'di', 'se'}

# 積集合
_intersection = X & Y

print(_intersection)
# => {'ra', 'ap', 'pa', 'ar'}

# 差集合
_diff_X = X - Y
_diff_Y = Y - X

print(_diff_X)
# => {'is', 'se', 'di', 'ad'}
print(_diff_Y)
# => {'ag', 'gr', 'ph'}

# `se`を含むか

print('se' in X)
# => True

print('se' in Y)
# => False

解説

Pythonには集合を扱うset型が用意されています。

4.9. set(集合)型 — set, frozenset

set型には集合演算も標準で付いているため、今回はこれを利用しました。

X = set(n_gram(x_str, N=2))
Y = set(n_gram(y_str, N=2))

print(X)
# => {'is', 'se', 'ad', 'di', 'ap', 'ar', 'pa', 'ra'}
print(Y)
# => {'ph', 'gr', 'ra', 'ap', 'ar', 'pa', 'ag'}

n-gram()で計算したbi-gramをset()で集合に変換しています。 n-gramは前回作成した関数を使います。

set型は{}で囲まれ、要素の順序は不定となります。

和集合

和集合は2つの集合をくっつけた集合です。

|演算子またはset.union()で求めることが出来ます。

# 和集合
_sum = X | Y

print(_sum)
# => {'ar', 'ad', 'is', 'ag', 'pa', 'ap', 'ph', 'ra', 'gr', 'di', 'se'}

もしくは

# 和集合
_sum = X.union(Y)

積集合

積集合は2つの集合の共通分を抜き出した集合です。

&演算子またはset.intersection()で求めることが出来ます。

# 積集合
_intersection = X & Y

print(_intersection)
# => {'ra', 'ap', 'pa', 'ar'}

もしくは

# 積集合
_intersection = X.intersection(Y)

差集合

差集合は別の集合に含む要素を除いた集合です。

-演算子またはset.difference()で求めることが出来ます。

# 差集合
_diff_X = X - Y
_diff_Y = Y - X

print(_diff_X)
# => {'is', 'se', 'di', 'ad'}
print(_diff_Y)
# => {'ag', 'gr', 'ph'}

もしくは

_diff_X = X.difference(Y)

部分集合

'se'というbi-gramがXおよびYに含まれるかどうか

要素が集合に含まれているかはinを使って判定できます。

# `se`を含むか

print('se' in X)
# => True

print('se' in Y)
# => False

また、ある集合を含むかを調べる場合は、<=を使います。

print({'se', 'ap'} <= X)
# => True

print({'se', 'ap'} <= Y)
# => False

print(X - Y <= X)
# => True

終わりに

set型の使い方を一通り覚えることができました。 集合の扱いを簡単な演算子でできるのは大変便利です。

続いての記事

Python3で言語処理100本ノックまとめ

前の問題:03. 円周率

次の問題:06. 集合