一覧CS-11-1 · 情報量・圧縮・誤り

情報量・エントロピーとハフマン符号

出現確率に応じた符号長を作り、固定長符号との総ビット数を比較します。

説明

出現確率pの出来事の情報量を-log₂pビットと定義します。頻繁に起こる出来事は小さく、珍しい出来事は大きくなります。各出来事の情報量を確率で重み付けして平均したものがエントロピーです。これは文章の意味や価値を評価する量ではありません。

Aが8個、Bが4個、CとDが2個ずつある16文字を使います。確率と情報量を求め、4種類を2ビットずつにする固定長符号と、頻度の高い文字を短くするハフマン符号を比較します。符号の区切りを判定できる接頭語条件も調べます。

1頻度と確率

16文字を作り、各文字の頻度を数えます。ここではこの分布を符号設計に使う確率モデルとします。

from collections import Counter; import math, heapq頻度・対数・最小値取得; message = 'AAAAAAAABBBBCCDD'対象文字列; counts = Counter(message)各文字の個数; probabilities = {ch: count/len(message) for ch, count in counts.items()}全体に対する割合; heap = [(n, i, ch) for i, (ch, n) in enumerate(counts.items())]; heapq.heapify(heap); serial = len(heap)頻度順の候補と同順位用の番号; counts, probabilities頻度と確率

確率はAが1/2、Bが1/4、CとDが1/8です。各文字を独立にこの確率で出すモデルで考え、文字の並びの規則性は今は利用しません。

2珍しさをビットで表す

各確率の負の2進対数を計算します。確率が半分になると情報量は1ビット増えます。

information = {ch: -math.log2(p) for ch, p in probabilities.items()}-log₂pを計算; information文字ごとの情報量

Aは1、Bは2、CとDは3ビットです。これは確率モデルから決まる量で、ASCIIなど実際の文字コードの格納サイズとは別です。

3平均情報量と一様分布

各情報量にその確率を掛けて足します。4文字が等確率なら各情報量は2ビットです。

entropy = sum(probabilities[ch]*information[ch] for ch in counts)確率で重み付けした平均; entropy今回の値, -sum(0.25*math.log2(0.25) for _ in range(4))4種類が一様な場合

今回のエントロピーは1.75、一様分布は2ビットです。出現が偏ると、頻出文字を短く表すことで平均符号長を減らせる余地があります。

4固定長符号で表す

4種類には2ビットあれば足ります。A=00、B=01、C=10、D=11として符号化します。

fixed = {'A': '00', 'B': '01', 'C': '10', 'D': '11'}固定長の対応表; fixed_bits = ''.join(fixed[ch] for ch in message)符号を連結; fixed_bits, len(fixed_bits)ビット列と長さ

16文字×2ビットで32ビットです。文字の種類ごとに長さが同じなので、2ビットずつ区切れば復号できます。

5頻度の小さい二つを結合

ハフマン法では最小頻度の二つをまとめ、その合計を新しい候補として戻します。C2とD2、B4とCD4、A8とBCD8の順になります。

while len(heap) > 1:根一つになるまで left = heapq.heappop(heap)最小頻度を取得 right = heapq.heappop(heap)次の最小頻度 parent = (left[0]+right[0], serial, (left[2], right[2]))重みを足して親を作る heapq.heappush(heap, parent)候補へ戻す serial += 1同頻度の順序番号 print(left[0], right[0], parent[0], parent[2])結合した重みと部分木

同じ頻度の候補があるため左右の割当ては一意ではありません。ここではAを根の左、Bを右部分木の左、CとDをその下に置きます。葉までの辺の本数が符号長になります。

6木の左右を0・1にする

根から左の辺を0、右を1として葉までの経路を符号にします。

encode_tree = lambda node, prefix='': {node: prefix} if isinstance(node, str) else encode_tree(node[0], prefix+'0') | encode_tree(node[1], prefix+'1')葉まで左右の0・1をつなぐ; code = encode_tree(heap[0][2])完成した木から符号を生成; [(ch, code[ch], len(code[ch]), counts[ch]*len(code[ch])) for ch in counts]文字・符号・長さ・総費用

Aは1、Bは2、CとDは3ビットです。各文字の総費用は8・8・6・6ビットとなります。頻出のAを短くした利益が、CとDを長くした費用を上回ります。

7接頭語条件を検査

ある文字の符号が、別の文字の符号の先頭全体になっていないことを調べます。

violations = [(a, b) for a in code for b in code if a != b and code[b].startswith(code[a])]他符号の接頭語になっていないか; bits = ''.join(code[ch] for ch in message)可変長で符号化; violations, bits, len(bits), len(bits)/len(message)条件・ビット列・総長・平均

違反は空、総長28ビット、平均1.75ビットです。今回の確率が2の負の整数乗なので、ハフマン符号の平均長がエントロピーに一致します。一般には符号長は整数であり、常に一致するわけではありません。

8区切りを復元する

短い符号から一致を見つける復号関数を作ります。接頭語条件があるので、一つの符号に一致した時点で確定できます。

def decode(bits, code):ビット列と符号表 reverse = {word: ch for ch, word in code.items()}符号から文字への表 current, output = '', ''未確定分と復号結果 for bit in bits:一ビットずつ読む current += bit未確定分へ追加 if current in reverse:一文字の符号に一致 output += reverse[current]文字を確定 current = ''次の符号へ return output, current結果と未確定分

currentはまだ文字に確定していないビット列です。最後に残りがあれば符号が途中で切れています。この関数は今回の符号表を使う例で、任意の不正入力を詳しく診断するものではありません。

9元の文字列と照合

復号結果が元と一致するか調べます。総ビット数の比較には、ここまで符号表の伝達費用を含めていません。

restored, tail = decode(bits, code)復号; restored, tail, restored == message結果と一致判定, len(fixed_bits)-len(bits)本文だけの節約量

元の16文字と一致し、未確定分は空、本文の節約は4ビットです。実際のファイルでは符号表や長さなどの付加情報が必要で、小さいデータではその費用で全体が大きくなる場合があります。

まとめ

情報量は確率から、エントロピーはその平均から決まります。文字コードの格納サイズとは別です。

ハフマン法は小さい頻度を結合し、頻出文字に短い符号を割り当てます。

接頭語条件で文字の境界を復元できます。圧縮率には本文だけでなく付加情報の費用も関わります。

操作履歴と解説を振り返れます。

Python 3

1
from collections import Counter; import math, heapq; message = 'AAAAAAAABBBBCCDD'; counts = Counter(message); probabilities = {ch: count/len(message) for ch, count in counts.items()}; heap = [(n, i, ch) for i, (ch, n) in enumerate(counts.items())]; heapq.heapify(heap); serial = len(heap); counts, probabilities
(Counter({'A': 8, 'B': 4, 'C': 2, 'D': 2}), {'A': 0.5, 'B': 0.25, 'C': 0.125, 'D': 0.125})
2
information = {ch: -math.log2(p) for ch, p in probabilities.items()}; information
{'A': 1.0, 'B': 2.0, 'C': 3.0, 'D': 3.0}
3
entropy = sum(probabilities[ch]*information[ch] for ch in counts); entropy, -sum(0.25*math.log2(0.25) for _ in range(4))
(1.75, 2.0)
4
fixed = {'A': '00', 'B': '01', 'C': '10', 'D': '11'}; fixed_bits = ''.join(fixed[ch] for ch in message); fixed_bits, len(fixed_bits)
('00000000000000000101010110101111', 32)
5
while len(heap) > 1: left = heapq.heappop(heap) right = heapq.heappop(heap) parent = (left[0]+right[0], serial, (left[2], right[2])) heapq.heappush(heap, parent) serial += 1 print(left[0], right[0], parent[0], parent[2])
2 2 4 ('C', 'D')
4 4 8 ('B', ('C', 'D'))
8 8 16 ('A', ('B', ('C', 'D')))
6
encode_tree = lambda node, prefix='': {node: prefix} if isinstance(node, str) else encode_tree(node[0], prefix+'0') | encode_tree(node[1], prefix+'1'); code = encode_tree(heap[0][2]); [(ch, code[ch], len(code[ch]), counts[ch]*len(code[ch])) for ch in counts]
[('A', '0', 1, 8), ('B', '10', 2, 8), ('C', '110', 3, 6), ('D', '111', 3, 6)]
7
violations = [(a, b) for a in code for b in code if a != b and code[b].startswith(code[a])]; bits = ''.join(code[ch] for ch in message); violations, bits, len(bits), len(bits)/len(message)
([], '0000000010101010110110111111', 28, 1.75)
8
def decode(bits, code): reverse = {word: ch for ch, word in code.items()} current, output = '', '' for bit in bits: current += bit if current in reverse: output += reverse[current] current = '' return output, current
9
restored, tail = decode(bits, code); restored, tail, restored == message, len(fixed_bits)-len(bits)
('AAAAAAAABBBBCCDD', '', True, 4)
演習完了