| 記号 | A | B | C | D | E |
|---|---|---|---|---|---|
| 出現回数 | 8 | 5 | 3 | 2 | 2 |
①出現回数の最も少ない2つをまとめて1つのグループにし、回数を合計する。
②グループも1つの記号とみなして、全体が1つになるまで①を繰り返す。
③まとめた2つの一方に0、もう一方に1を割り当て、最後にまとめた所から順にたどって符号を作る。何回もまとめられた記号ほど、符号が長くなる。
この文字列をハフマン符号で表したときの全体のビット数(符号と記号の対応表のデータ量は含めない)と、5種類を区別できる最小のビット数の固定長符号で表したときと比べた圧縮率の組合せとして、最も適切なものはどれか。ここでは、圧縮率=ハフマン符号で表したビット数÷固定長符号で表したビット数(%)とする。
- ①39ビット、約65%
- ②43ビット、約140%
- ③43ビット、約72%
- ④67ビット、約112%
答えと解説を見る
正解は「43ビット、約72%」。
手順
①まとめる順:D(2回)とE(2回)で4、C(3回)と4で7、B(5回)と7で12、A(8回)と12で20。
②符号の長さは、まとめられた回数と同じ。Aは1ビット、Bは2ビット、Cは3ビット、DとEは4ビット(例:A=0、B=10、C=110、D=1110、E=1111)。
③全体のビット数:8×1+5×2+3×3+2×4+2×4=43ビット。
④固定長符号:5種類を区別するには3ビット必要(2ビットでは4種類まで)なので、20×3=60ビット。圧縮率は43÷60=約72%。実際のファイルでは対応表の分も加わります。圧縮率の言い方は資料によって違い、元の何%になったかを言う場合と、何%減ったかを言う場合があるので、問題文の定義を必ず確かめます。
ひっかけ注意
・「39ビット、約65%」…A〜Cを1・2・3ビット、DとEも3ビットとした誤り。この長さの組合せでは符号の区切りが一意に決まらないため、ハフマン木を作って長さを決める。
・「43ビット、約140%」…割る向きが逆(60÷43)。定義は、ハフマン符号のビット数÷固定長符号のビット数で、100%より小さければ小さくなったことを表す。
・「67ビット、約112%」…多く出る記号に長い符号を付けた場合(A・Bを4ビット、Eを1ビットなど)。出現回数の多い記号ほど短い符号にするのがハフマン符号の考え方。