Question

ルナ

情報で例題が分かりません。解説お願いします。下は答えです

15
レングス圧縮によるデータの圧縮
例題2
図のデータ (16×16ビット) のAの部分を0, Bの部分を1として,
以下の約束に従って1行ごとに圧縮すると, データ量は何ビットに
①最初のビット: はじまりがAの場合は 0, Bの場合は1とする。
なるか。 また, 圧縮率はどのようになるか計算しなさい。
② 次の4ビット : AまたはBが続く個数を表す。 ただし, 「個数 - 1」
として表現する。
考え方 圧縮率は, 「圧縮後のデータ量圧縮前のデータ量」で求め
られる｡
[解答例
1~3行は,1が16個なので, 「11111」で5ビット。
4.5行は,1が3個 0 3個 14個,0が3個,1が3
個なので,「10010001000110010 0010」で21ビット。
6~16行は,「00101 00110101」なので,13ビット。
各行のビット数を合計すると, 5×3+21×2+ 13×11 = 200
よって, データ量は200ビットとなる。
また, 圧縮率は,
200
16x16
×100=78.125 となり, 約78%である。
考察圧縮率が高いということは,よりデータ量が少なくなること
であり, また圧縮率の数値はより小さくなることを意味する。

Answer 1

✨ ベストアンサー ✨

Tyra()

高校の教科書でどのように表記されているのか分かりませんが、
この問題は、現れる文字が2種類(AとBだけなど)である時に使う、ランレングス圧縮です。

注意すべき点は、【「個数-1」として表現する】です。
つまり、AAAAAAのように、Aが6個連続しているときに、
A→0　が　6 - 1→5　回連続している。
と表現したいので、どちらも2進数に直して、
0 0101
になります。

問題の図がないので、解答例から察するしかありませんが、
このように考えると、
1-3行目は、(Bが16個連続しているから)1が16個なので、(最初のビットを0ではなく、1に。また、16-1=15で、さらに二進数に直して、1111に。)「1 1111」で5ビット。
4、5行目は、(Bが3個連続しているから)1が3個なので、(最初のビットを1に。また、3-1=2で、二進数10。そして、4ビットなのであまりを0で埋めて、0010。)、
(同じように考えて)0が3個(つまり、3-1=2、0010)、
1が4個(つまり、4-1=3、0011)、
0が3個(0010)、1が3個(0010)。
全部合わせて、「1 0010 0010 0011 0010 0010」で21ビット。
同じように、6-16行目も考えます。

各行のビット数を合計すると、
(1、2、3行目が「1 1111」の5ビット)3×5=15
(4、5行目が「1 0010 0010 0011 0010 0010」の21ビット)2×21=42
(6から16行目が「0 0101 0011 0101」の13ビット)11×13=143
15+42+143=200 ビット

圧縮率の式に当てはめて、
200÷(16×16)×100=78.125　で約78%

4行目以降は、Aが3個で途切れて、その次に別の文字Bが3個続く。みたいなことが起きますよね。
1 0010 0 0010　素直に変換するならこうなりますよね。
でも、Aが途切れる。ということは、次に別の文字が続くってことですよね？3種類以上の時は、Aではない文字ってBかCか分かりませんよね。でも、2種類ならAじゃないならB、BじゃないならAって分かりますよね。
だから、
1 0010(Bが3個) 0010(Aが3個)　っていう表し方ができるんですね。