D 言語で実装する可逆圧縮アルゴリズム入門

D 言語で実装する可逆圧縮アルゴリズム入門
Let’s make a lossless data compression program in D language
無線部開発班
2015 年 12 月 29 日改訂
無線部
1
D 言語で実装する可逆圧縮アルゴリズム入門
開発班
はじめに
本稿では、Huﬀman 符号による圧縮展開プログラムを D 言語で追実装しつつ情報源符号化を復習する。
2
概念
2.1
情報源符号化
ある確率分布に従って、記号の系列を出力する装置を情報源と呼び、出力される記号をシンボルと呼ぶ。
また、情報源が出力する記号の全集合をアルファベットと呼び、アルファベット間の写像を符号と呼ぶ。
Table 1: 固定長符号の例
記号
符号語
出現確率
A
00
0.5
B
01
0.2
C
11
0.2
D
10
0.1
写像の値域に属する個別の元を符号語と呼ぶ。Table 1 に示す符号は、系列 ABC を 000111 に変換する。
固定長符号では、符号 C の符号語長 L(C) は、情報源 S のアルファベット AS の要素数により定まる。
L(C) ≥ ⌈log2 |AS |⌉ = log2 4 = 2
(1)
ASCII は各文字に 8bit の符号語を割り当てた固定長符号だが、各文字の出現頻度は均等とは限らない。
Table 2 に示す可変長符号ならば、符号語長の平均値 L(C) を Table 1 の固定長符号よりも圧縮できる。
Table 2: 可変長符号の例
L(C) =
∑
記号
符号語
出現確率
A
0
0.5
B
10
0.2
C
110
0.2
D
111
0.1
P (s)L(s) = 0.5 × 1 + 0.2 × 2 + (0.2 + 0.1) × 3 = 1.8
(2)
s∈AS
情報源が記号 s を出力したとき、その記号がいかに価値ある情報であるか示す量 I(s) を情報量と呼ぶ。
情報理論では、価値ある情報は珍しいと考える。I(s) を記号の出現確率 P (s) の反比例で定義してみる。
I(s) =
2
1
P (s)
(3)
無線部
D 言語で実装する可逆圧縮アルゴリズム入門
開発班
式 (3) はごく自然な定義であるように思えるが、直観に反する面もある。情報量の加法性の問題である。
例えば、ある記号 x が出現した後に、別の記号 y が出現した場合、情報量 I(xy) は式 (4) で与えられる。
I(xy) =
1
1
1
=
= I(x)I(y)
P (x)P (y)
P (x) P (y)
(4)
しかし、情報量が情報の価値を示す量であるなら、情報量 I(xy) は I(x) と I(y) の和になるべきである。
この直観を情報量の加法性と呼ぶ。対数関数を導入して、式 (3) の定義を式 (5) に示すように修正する。
I(s) = log2
1
= − log2 P (s)
P (s)
(5)
情報量の議論は、Table 2 の可変長符号がどこまで符号語を圧縮できるかを吟味する上で不可避である。
平均符号語長の下限を与える Shannon の第 1 基本定理ないし情報源符号化定理が存在するためである。
H(S) ≤ L(C) ≤ H(S) + ϵ
(ϵ ∈ N)
(6)
H(S) は情報源 S が出力する記号 s の情報量の平均値であり、平均情報量、またはエントロピーと呼ぶ。
H(S) =
∑
P (s)I(s) = −
s∈As
2.2
∑
P (s) log2 P (s)
(7)
s∈As
ハフマン符号
エントロピー符号とは、記号 s に対する符号語 cs の長さが情報量 I(s) と等しくなるような符号である。
現実には I(s) は整数値を取らない。そこで、Huﬀman 符号は、近似的にエントロピー符号を実現する。
Fig 1 に示す Huﬀman 木は、記号 s の出現頻度に基づいて最適な符号語 cs を割り当てる仕組みである。
Fig. 1: Huﬀman 木の例
例えば、頻度 0.36 の記号 A に符号語 00 を割り当てて、頻度 0.08 の記号 E に符号語 111 を割り当てる。
Huﬀman 符号では、記号 s の出現頻度 P (s) を調べ、下記の手順を繰り返して Huﬀman 木を作成する。
1. 最も出現頻度の低いノード n1 と n2 を選ぶ
2. ノード n1 と n2 を合併して親ノードを作る
Huﬀman 符号は瞬時符号である。つまり、復号時に前後の符号語を憶えずとも一意に復号可能である。
これは、語頭条件を満たしている、つまり、任意の符号語 c1 が他の符号語 c2 の語頭でないためである。
なお、Huﬀman 木は復号時も必要なので、圧縮時に何らかの方法で Huﬀman 木を埋め込む必要がある。
2.3
算術符号
算術符号は、符号語を実数で表現することで、より高い圧縮率を得る符号であるが、特許問題が根深い。
3
無線部
D 言語で実装する可逆圧縮アルゴリズム入門
3
実装
3.1
実装の概略
開発班
第 3 章で実装する reef は e コマンドで圧縮し、d コマンドで復元する。以降は入力元・出力先である。
例えば、下記のコマンドは alice.txt を圧縮して bob.rz を出力し、そこから alice.txt を復元する。
$ ./reef e alice.txt bob.rz
$ ./reef d bob.rz alice.txt
圧縮ファイルは先頭の 8byte で圧縮前の byte 数を、続く 256byte で各シンボルの出現頻度を表現する。
264byte 目以降はファイル末端まで Huﬀman 符号化されたビット列を左端から右端まで順に格納する。
生成されたファイルが正しく Huﬀman 符号化されているか確認するには、xxd コマンドが便利である。
$ xxd -b -g 1 -c 8 bob.rz
3.2
実装の詳細
第 3 章で実装する reef は、Huﬀman 符号によりバイト列を圧縮し、或いは復元するプログラムである。
reef.d
import
import
import
import
import
core.bitop;
std.algorithm;
std.bitmanip;
std.conv;
std.file;
まず、符号化と復号で使う Huﬀman 木を実装する。本稿では、構造体の代わりに静的配列で表現する。
reef.d
size_t
size_t
size_t
size_t
parent[511];
child0[511];
child1[511];
weight[511];
findRareSymbol 関数は、前掲の配列 weight を走査して、出現頻度が最も低いノードの組を探索する。
reef.d
size_t findRareSymbol(size_t exclusion) {
size_t idx = exclusion;
size_t min = size_t.max;
foreach(i, c; weight) if(c) {
if(i == exclusion) continue;
if(c < min) min = c,idx = i;
}
return idx;
}
addHuffmanTreeNode 関数は、findRareSymbol 関数が見つけたノードを子に持つノードを生成する。
4
無線部
D 言語で実装する可逆圧縮アルゴリズム入門
開発班
reef.d
bool addHuffmanTreeNode(const size_t n) {
size_t i = findRareSymbol(510);
size_t j = findRareSymbol(i);
if(i == j && i > 255) return true;
weight[n] = weight[i] + weight[j];
weight[i] = weight[j] = 0;
parent[i] = parent[j] = n;
child0[n] = i;
child1[n] = j;
return false;
}
createHuffmanTree 関数は、getRareSymbols 関数が新たなノードを見つける限りノードを生成する。
reef.d
size_t createHuffmanTree(ubyte[] count) {
weight[0..256] = to!(size_t[])(count);
size_t root = 0;
foreach(n; 256..511) {
if(!addHuffmanTreeNode(n)) root = n;
}
return root;
}
countSymbols 関数は、符号化前のバイト列を引数に取り、各シンボルの出現回数を数えて正規化する。
reef.d
ubyte[256] countSymbols(ubyte[] source) {
size_t count[256];
foreach(sym; source) count[sym]++;
size_t maxim = reduce!(max)(count);
foreach(s, cnt; count) if (cnt > 0) {
double deg = 255.0 * cnt / maxim;
count[s] = to!ubyte(max(deg, 1));
} else count[s] = 0;
return to!(ubyte[256])(count);
}
以上で、Huﬀman 木の実装を完了した。続く symbolToCodeWord 関数で、シンボル 1 件を符号化する。
reef.d
bool[] symbolToCodeWord(const size_t s) {
bool[] code = new bool[0];
for(long n=s; parent[n]; n=parent[n]) {
code ~= child1[parent[n]] == n;
}
return code.reverse;
}
encode 関数は、復元時の byte 数と、各シンボルの出現頻度を出力したのち、符号語を順番に出力する。
5
無線部
D 言語で実装する可逆圧縮アルゴリズム入門
開発班
reef.d
void encode(string from, string target) {
auto plain = cast(ubyte[]) read(from);
createHuffmanTree(countSymbols(plain));
ubyte[] coded = new ubyte[8];
coded.append!(size_t)(plain.length);
coded ~= countSymbols(plain);
ubyte buf, i;
foreach(s; plain) {
foreach(b; symbolToCodeWord(s)) {
if(b) buf |= 1; else buf &= ~1;
if(++i % 8 != 0) buf <<= 1;
else coded ~= buf, buf = 0;
}
}
if(i % 8) coded ~= buf <<= 7 - i % 8;
write(target , coded);
}
decode 関数は、入力ファイルを 1bit ずつ読み取って Huﬀman 木を巡回し、元のバイト列を復元する。
reef.d
void decode(string from, string target) {
auto coded = cast(ubyte[]) read(from);
auto size = coded[0..8].peek!size_t();
auto freq = coded[8..264];
size_t root = createHuffmanTree(freq);
size_t s = root;
ubyte[] plain;
foreach(size_t bits; coded[264..$]) {
foreach_reverse(i; 0..8) {
const int bit = bt(&bits, i);
s = (bit? child1: child0)[s];
if(s >= 256) continue;
plain ~= to!ubyte(s), s = root;
if(--size == 0) break;
}
}
write(target , plain);
}
最後に、main 関数を定義する。reef コマンドの引数はオプション、変換元、変換先の順に格納される。
reef.d
void main(string[] args) {
if(args[1] == "e") encode(args[2], args[3]);
if(args[1] == "d") decode(args[2], args[3]);
}
以上で Huﬀman 符号による圧縮展開プログラムが完成した。下記のコマンドによりコンパイルできる。
$ dmd reef -O -release -inline
6

Download Report