2013-05-25

情報理論の基礎4章メモ、エントロピーからHuffman符号まで

手計算が厳しくなってきたので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]:
$$H(x) = \sum_{i=0}^{k} P_{i} \log{\left (\frac{1}{P_{i}} \right )}$$
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]:
$$D(P,Q) = \sum_{i=0}^{k} P_{i} \log{\left (\frac{P_{i}}{Q_{i}} \right )}$$
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))
1.88128539659
2.33333333333
2.88128539659

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)))
入力
[0.6, 0.3, 0.075, 0.025]
符号
['0', '10', '1110', '111110']
符号長
[1.0, 2.0, 4.0, 6.0]
KL情報量
0.273410343316

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)))
入力
[0.6, 0.3, 0.075, 0.025]
符号
['0', '10', '110', '111']
符号長
[1, 2, 3, 3]
KL情報量
0.123410343316
Huffman符号の方がKL情報量が小さい、つまり理想的な符号に近い事がわかる。



このエントリーをはてなブックマークに追加