[小西ホームページ]   [目次・索引]   [前の授業]   [次の授業]

コンピュータIIL(情報科学入門)第8回

目次 索引
8.1 データ圧縮
8.2 演習8
8.3 レポート課題
8.4 参考文献

8.1 データ圧縮


h2 データ圧縮 toc-data-compression

h3 符号化と復号 toc-encode-decode

文字列などのデータを数種類の記号の列に変換することを、
index 符号化 encoding ふこうか
と言います。
符号化されたデータを元に戻すことを、
index 復号 decoding ふくこう
と言います。

コンピュータが使われるまでは、
数字の列に変換することが多かったのですが、
コンピュータでデータを処理する現在は、
普通はビットの列に変換します。

符号化は、データを保存するときに行われます。
つまり、データは符号化されてビット列になり、
各ビットがハード・ディスクなどの磁気状態として記録されます。
また、データを転送するときにも符号化が行われます。
各ビットは銅線などの電気信号として通信されます。

今回は、文字列の符号化について考えます。

文字の符号化で国際標準となっているのが、
index ASCII 符号 ASCII code ASCIIふこう
です。
以下は、ASCII 符号の一部です。

文字 符号
A    01000001
B    01000010
C    01000011
D    01000100
E    01000101
F    01000110
G    01000111
H    01001000
I    01001001
J    01001010
K    01001011
L    01001100
M    01001101
N    01001110
O    01001111
P    01010000
Q    01010001
R    01010010
S    01010011
T    01010100
U    01010101
V    01010110
W    01010111
X    01011000
Y    01011001
Z    01011010

符号化で重要なことは、復号して正確に元に戻ることです。
このことを、
index 一意的に復号化可能 uniquely decodable いちいてきにふくこうかかのう
と言います。
一意的に復号化可能であるためには、
異なるデータは異なるビット列に符号化されなければなりません。

ASCII 符号は一意的に復号化可能です。
なぜなら、ビット列を 8 ビットごとに区切ればよいからです。
例えば、文字列 "ABC" は、

010000010100001001000011

と 24 ビットで符号化されます。
復号するときは、これを

01000001 01000010 01000011

と 8 ビットごとに区切り、それぞれを復号すれば、
文字列 "ABC" に戻ります。

h3 固定長符号 toc-fixed-length-code

符号化を工夫することによってビット列を短くすることを、
index データ圧縮 data compression てえたあつしゆく
と言います。
データによっては工夫の余地がないものもありますが、
多くのデータは何らかの符号化によって圧縮可能です。
データ圧縮には多くのメリットがあります。
ハード・ディスクにより多くのデータが記録できますし、
データを通信するときの時間や費用が節約できます。

今回は文字列のデータ圧縮を考えるわけですが、
まず注目すべきなのは、文字列に現れる文字の種類です。
文字の種類が少なければ少ないほど、
1 文字をより短いビット列で符号化できます。
具体的には、次の表の通りです。

ビット長 文字数
1 ビット   2 文字
2 ビット   4 文字
3 ビット   8 文字
4 ビット  16 文字
5 ビット  32 文字
6 ビット  64 文字
7 ビット 128 文字

例として、文字列

AAAAAAAABBBBBBCCCCDD

を圧縮します。
ASCII で符号化しますと、160 ビットになります。
一方、文字は A, B, C, D の 4 種類しかありませんので、
A を 00, B を 01, C を 10, D を 11 と、
1 文字 2 ビットで符号化しますと、

00 00 00 00 00 00 00 00 01 01 01 01 01 01 10 10 10 10 11 11

と、40 ビットで符号化されます。

なお、すべての文字を同じ長さのビット列に符号化する符号のことを、
index 固定長符号 fixed-length code こていちようふこう
と呼びます。
固定長符号は一意的に復号化可能です。

h3 ランレングス符号 toc-run-length-code

index ランレングス符号 run-length code らんれんくすふこう
は、同じ文字が連続して現れるときに効果的な圧縮法です。
これは、上記の文字列

AAAAAAAABBBBBBCCCCDD

を、いったん

8A6B4C2D

に変換してから符号化するものです。

変換結果を固定長符号で符号化しますと、
文字の種類は元の 4 種類と数字の 10 種類ですので、
次のように 1 文字 4 ビットで符号化できます。

文字 符号
0    0000
1    0001
2    0010
3    0011
4    0100
5    0101
6    0110
7    0111
8    1000
9    1001
A    1010
B    1011
C    1100
D    1101

したがって、

1000 1010 0110 1011 0100 1100 0010 1101

と、32 ビットで符号化されます。
単純な固定長符号では 40 ビットでしたので、
ランレングス符号によって、より圧縮されたことが分かります。

ランレングス符号では、
元の文字列に数字が現れないようにする必要があります。
また、連続しない文字を 1E のようにしますと、逆に長くなりますので、
これは E のままにします。

h3 ハフマン符号 toc-huffman-code

上記の文字列

AAAAAAAABBBBBBCCCCDD

を並び替えた文字列

ABCACBABDAABCACBABDA

の圧縮を考えます。
ランレングス符号では圧縮できませんので、
他の符号化を考えます。

方針は、よく現れる文字は短いビット列で符号化し、
あまり現れない文字は長いビット列で符号化することです。
このような、文字によってビット列の長さを変える符号を、
index 可変長符号 variable-length code かへんちようふこう
と呼びます。

可変長符号では、一意的に復号化可能であることに注意が必要です。
例えば、A を 0, B を 01, C を 10 に符号化しますと、
010 は "AC" にも "BA" にも復号されます。
一意的でないのは、A の符号 0 が B の符号 01 の語頭だからです。
ここで、
index 語頭 prefix ことう
とは、先頭からの部分列のことです。
どの文字の符号も他の文字の符号の語頭でないという、
index 語頭条件 prefix condition ことうしようけん
を満たせば、一意的に復号化可能です。

可変長符号では、
index ハフマン符号 Huffman code はふまんふこう
が最もよい圧縮法です。
以下にその作り方を示します。

まず、文字列における文字の出現頻度を調べます。
上記の文字列では、A=8, B=6, C=4, D=2 です。
次に、出現頻度の低いほうから 2 つを「合併」します。
この場合は、C=4 と D=2 を合併して、C+D=6 とします。
この合併を、1 つになるまで繰り返します。
この場合は、

A=8, B=6, C=4, D=2 → A=8, B=6, C+D=6
                   → A=8, B+(C+D)=12
                   → A+(B+(C+D))=20

です。
そして、合併の過程をトーナメント表にします。
この場合は、

          |
   +------+------+
   |             |
   |       +-----+-----+
   |       |           |
   |       |       +---+---+
   |       |       |       |
   A       B       C       D

となります。
最後に、トーナメント表の上からたどり、
左側を 0 に、右側を 1 に対応させます。
この場合は、A は 0, B は 10, C は 110, D は 111 です。

ハフマン符号によって、元の文字列は

0 10 110 0 110 10 0 10 111 0 0 10 110 0 110 10 0 10 111 0

と、38 ビットで符号化されます。
固定長符号の場合は、
文字が 4 種類ですので 1 文字 2 ビットで符号化され、
元の文字列は 40 ビットで符号化されます。
ハフマン符号によって、より圧縮されたことが分かります。

例題 1.
文字列 ABCDBBDACA を固定長符号で符号化しますと、
文字が 4 種類ですので 1 文字 2 ビットで符号化され、
この文字列は 20 ビットで符号化されます。
ハフマン符号で符号化し、固定長符号と比較してください。

解答例 1.
この文字列における文字の出現頻度は、A=3, B=3, C=2, D=2 である。
頻度の低い 2 つを順次合併していくと、

A=3, B=3, C=2, D=2 → A=3, B=3, C+D=4
                   → A+B=6, C+D=4
                   → (A+B)+(C+D)=10

となる。
したがって、A は 00, B は 01, C は 10, D は 11 と符号化され、
元の文字列は 00 01 10 11 01 01 11 00 10 00 と、
20 ビットで符号化される。

h2 演習 8 toc-exercises

次の文字列を固定長符号で符号化しますと、
文字が 5 種類ですので 1 文字 3 ビットで符号化され、
それぞれの文字列は 36 ビットで符号化されます。
それぞれをハフマン符号で符号化し、固定長符号と比較してください。

  1. CBACADABEAAB
  2. CCABABADEAAD
  3. CBACBACBDAEA

8.2 演習8


8.3 レポート課題

今日の演習8の答案をkonishi@twcu.ac.jpあてにメールで送ってください。 メールには、学生番号、氏名、科目名、授業日(11月19日)を明記してください。


8.4 参考文献


[小西ホームページ]   [目次・索引]   [前の授業]   [次の授業]

2004年11月19日更新
konishi@twcu.ac.jp
Copyright (C) 2004 Zenjiro Konishi. All rights reserved.