手計算が厳しくなってきたのでiPython notebookでコードを書きつつメモ。実際に動作する物が残せて便利。
Huffman符号化は以前SICPで書いた記憶があったが、その時とは全く違ったコードになった。SchemeとPythonの違いだろうか。
4章 符号化と種々の情報量
- エントロピー
- KL情報量
- Fano符号、Shannon符号
- Huffman符号
In [128]:
%load_ext sympy.interactive.ipythonprinting
import sympy as sym
エントロピー
確率変数XのエントロピーH(X)はXの確率分布をP(X = i)として。
In [129]:
H, p, i, k = sym.symbols("H(x) P_i i k")
sym.Eq(H, sym.Sum(p*sym.log(1/p), (i, 0, k)))
Out[129]:
In [130]:
def calc_entropy(P):
return sum(map(lambda p: 0 if p == 0 else p * log2(1/p), P))
In [131]:
# Xが二値の場合、それぞれ同じ確率で出現する場合が一番エントロピーが大きい
x = linspace(0, 1, 100)
p = map(lambda x: [x, 1.0 -x], x)
plot(x,map(calc_entropy, p))
t = title('binary entropy (Figure 4.1)')
KL情報量 (Kullback-Leibler divergence)
クロスエントロピーとエントロピーの差、理想的な符号長を使った場合と、確率分布Qであるとみなして符号化したものとの差分
In [132]:
D = sym.Symbol("D(P,Q)")
p, q, i, k = sym.symbols("P_i Q_i i k")
sym.Eq(D, sym.Sum(p*sym.log(p/q), (i, 0, k)))
Out[132]:
In [133]:
def calc_KLD(P, Q):
ret = 0
for p, q in zip(P, Q):
ret += p * log2(p/q)
return ret
In [134]:
def calc_Q(code_lens):
ret = []
for l in code_lens:
ret.append(2 ** (-1 * l))
return ret
#符号長の平均をかえす
def len_ave(P):
return sum(map(lambda x:log2(1/x), P)) / len(P)
#切りあげた符号長の平均をかえす
def len_ceil_ave(P):
return sum(map(lambda x:ceil(log2(1/x)), P)) / len(P)
#符号長に1を足した平均をかえす
def len_plus1_ave(P):
return sum(map(lambda x:log2(1/x) + 1, P)) / len(P)
p = [0.4, 0.5, 0.1]
print(len_ave(p))
print(len_ceil_ave(p))
print(len_plus1_ave(p))
Shannon fano符号
In [142]:
class ShannonFanoEncoder(object):
def __init__(self, vals):
p_vals = vals[:]
p_vals.sort()
p_vals.reverse()
self.f_val = self.accumlate(p_vals)
self.code_lens = self.calc_code_lens(p_vals)
self.p_vals = p_vals
def encode(self):
codes = []
for f, l in zip(self.f_val, self.code_lens):
codes.append(self.get_bin_by_float(f, l))
return codes
def accumlate(self, p_val):
ret = []
tmp = 0
for p in p_val:
ret.append(tmp)
tmp += p
return ret
def calc_code_lens(self, p_val):
return map(lambda p: ceil(math.log(1/p, 2)), p_val)
def get_bin_by_float(self, f_val, bin_len):
"""
小数を二進数にして、小数点以下を指定した桁数でかえす
(0.5, 4) -> 1000
(0.25, 4) -> 0100
(0.125, 4) -> 0010
"""
bin_len = int(bin_len)
return format(int(math.floor(f_val * (2 ** (bin_len)))), 'b').zfill(bin_len)
In [148]:
# Shannon Fano符号
P = [0.025,0.075,0.3,0.6]
shannon_fano = ShannonFanoEncoder(P)
print('入力')
print(shannon_fano.p_vals)
print('符号')
print(shannon_fano.encode())
print('符号長')
print(shannon_fano.code_lens)
print('KL情報量')
print(calc_KLD(shannon_fano.p_vals, calc_Q(shannon_fano.code_lens)))
Huffman符号
In [137]:
class HuffmanEncoder(object):
"""
情報の各要素の出現確率を元にHuffman符号を作成する
"""
def __init__(self, vals):
self.p_vals = vals[:]
self.p_vals.sort()
self.p_vals.reverse()
def encode(self):
vals = self.p_vals[:]
# 木の構築
while len(vals) > 1:
tree = self.make_tree(vals.pop(), vals.pop())
vals.append(tree)
vals = self.sort_tmp_tree(vals)
# 木からコードを生成
def walk(node, code, codes):
def w(v):
if self.is_node(v[0]):
walk(v[0], code + v[1], codes)
else:
codes.insert(0, code + v[1])
w(node[1])
w(node[2])
return codes
return walk(vals[0], "", [])
def is_node(self, v):
return isinstance(v, tuple) and len(v) == 3
def make_tree(self, v1, v2):
return (self.sum(v1) + self.sum(v2), (v1, "1"), (v2, "0"))
def sum(self, v):
return v if isinstance(v, float) else v[0]
def sort_tmp_tree(self, vals):
return sorted(vals, cmp = lambda x, y: int(self.sum(y) - self.sum(x)))
In [147]:
# Huffman符号
P = [0.025,0.075,0.3,0.6]
huffman = HuffmanEncoder(P)
codes = huffman.encode()
code_lens = map(lambda p:len(p), codes)
print('入力')
print(huffman.p_vals)
print('符号')
print(codes)
print('符号長')
print(code_lens)
print('KL情報量')
print(calc_KLD(huffman.p_vals, calc_Q(code_lens)))
Huffman符号の方がKL情報量が小さい、つまり理想的な符号に近い事がわかる。
村田 昇
サイエンス社
売り上げランキング: 366609
サイエンス社
売り上げランキング: 366609
