高校情報I ランレングス圧縮—連続の長さを記録して圧縮が逆効果になる条件も調べる｜武蔵野個別指導塾

タイル列を色と個数の組で記録します。個数欄の上限で分割し、復号して元の帯へ戻すと、保存量が増える理由も確かめられます。

よくあるのは、展示用のタイル模様を短く記録しようとして、同じ色が何個続くかだけを数える場面です。個数がわかっても、どの色をその個数だけ並べるかがわからなければ模様は戻せません。色の記録にも場所が必要です。連続が短い列では、その追加分が節約分を上回ることもあります。記録の規則を先に決め、実際に元へ戻してから、長さを比較しましょう。

問われ方と判断の道筋

一つ目は、タイル列を左から区切って符号にし、圧縮前後のビット数を比較する問題です。同じ色が続く部分をまとめますが、色の値と個数の両方の長さを数えます。途中で色が変わるたびに新しい組が要ります。結果が短くなったかどうかは、組の数と1組の長さを掛け、ヘッダの条件も加えて判断します。

二つ目は、個数の欄に入る上限を超えた連続を分ける問題です。同じ色でも、上限を超える分は別の組にします。色が変わったから分ける場合と、欄の上限でやむを得ず分ける場合を区別すると、隣り合う組が同じ色でも不自然ではありません。上限ちょうどと、その1個先を試すと境界を見つけやすくなります。

三つ目は、与えられた組を復号して元の列を作り、壊れた記録や不足した条件を見つける問題です。正しい長さの答えでも、色や順番を間違えれば元の模様にはなりません。個数が規則の範囲内か、組の途中で記録が切れていないかも調べます。途中まで読めたことと、列全体を復元できたことは別です。

連続のまとまりと記録の約束

ランレングス圧縮は、同じ値が連続する部分を、その値と連続個数の組で表す方法です。連続する部分をランと呼びます。例えば白白白黒黒なら、白が3個、黒が2個という2つのランです。離れた位置にある同じ色を合計してはいけません。順番と境界が消えてしまうからです。

ここから使うのは説明用に作った規則です。実際の画像形式を表す規格ではありません。白を0、黒を1とし、圧縮前はタイル1個を1ビットで表します。圧縮後は「色1ビット、個数3ビット」の順に並べます。個数は2進数で001から111まで、つまり1から7です。000は使いません。最初の色も各組に含め、別の開始値は置きません。ヘッダや区切りは付けず、4ビットごとに1組として左から読みます。

図1のように、組の左側は何を並べるか、右側は何個並べるかを指定します。例えば白3個は色0と個数011を合わせた0011です。黒2個は1010です。個数の先頭0も3桁を保つために必要です。区切りを紙に書くと読みやすくなりますが、この規則では区切り自体を保存しません。

図1の1組は必ず4ビットです。白が8個続く場合、個数を1000と4桁で書くのは規則違反です。白7個と白1個の2組に分けます。このように長いランは7個ずつ切り、残りがあればその個数を次の組にします。分割後も各組に色の1ビットが必要です。7個に満たない途中で分けても復元は可能ですが、ここでは比較を一定にするため、左から7個ずつ最大限にまとめます。

復号では4ビットを取り、最初の1ビットを色、残り3ビットを個数として読みます。その色を指定数だけ並べ、次の組へ進みます。000の個数は規則外です。また末尾が4ビットに満たないと、色や個数を最後まで読めません。その場合に残りを勝手に補うと、別の列を作るおそれがあります。

この規則で圧縮後の長さは、組の数に4ビットを掛けたものです。圧縮前はタイル数と同じビット数です。例えば1組で表せるランが4個なら前後とも4ビット、5個から7個なら1組では短くなります。ただし全体の増減はすべての組を合わせて決まります。短いランで増えた分を長いランの節約分が相殺することもあります。

実際の保存には、形式を識別する情報や寸法などが必要になる場合があります。ここではヘッダなしと明示して比較します。もし固定のヘッダを付ける条件なら、その長さを圧縮後に加えます。列の符号だけが短くても、ヘッダを含めた全体が短いとは限りません。条件の異なる二つの数字を比べないことが出発点です。

基本例題：2種類の列を同じ規則で比べる

展示の帯に白と黒を並べます。上の自作規則を使い、次の2列を左から最大7個ずつ組にしてください。組を4ビットずつ書き、圧縮前後のビット数と増減を整数のビットで答えます。ヘッダはありません。最後に復号して元の並びを確認します。

列Aは白白白白白白黒黒黒黒黒黒、列Bは白黒白黒白黒白黒白黒白黒です。どちらも12個です。図2のように、同じ個数でも連続の境目の数が違います。

列Aの最初のランは白6個です。色0と個数110を合わせ、0110とします。次の黒6個は色1と個数110で1110です。7個を超えるランはないので、組は2個です。保存する列は0110 1110、空白は見やすくするための表示です。圧縮前は12ビット、圧縮後は4ビットが2組で8ビットです。4ビット減ります。

復号すると0110は白6個、1110は黒6個です。白を6個並べた後に黒を6個並べれば、列Aの12個と順番まで一致します。合計が12個という確認に加え、境目が白6個の直後にあることを元の条件に戻して調べます。

列Bは色が1個ごとに変わるので、ランは12個です。白1個は0001、黒1個は1001です。この2組を交互に6回並べます。圧縮前は12ビット、圧縮後は4ビットが12組で48ビットです。36ビット増えます。0001を白1個、1001を黒1個として順に復号すると、白黒の組が6回現れ、元の12個に戻ります。

列Bでは個数がいつも1なので、数える作業は単純です。しかし1個ごとに色と3ビットの個数を保存するため、元の1ビットより大きくなります。圧縮という名前だけで結果を小さいと決めず、同じ条件で長さを出すことが必要です。列Aと列Bの違いは色の種類や総個数ではなく、連続の仕方です。

標準例題：上限を越える帯

同じ規則で、白が10個続いた後に黒が5個続く帯を記録します。左から最大7個ずつまとめ、4ビットの組、圧縮前後のビット数、復号した色と個数を答えてください。ヘッダはありません。

白10個を1組にはできません。まず白7個を0111、残りの白3個を0011とします。黒5個は1101です。保存する列は0111 0011 1101で、3組のため12ビットです。圧縮前は10個と5個で15ビットなので、3ビット減ります。

復号すると白7個、白3個、黒5個です。隣の白の組をつなぐと白10個となり、その後に黒5個が続きます。元の条件に戻りました。白の色を2回保存することは無駄に見えますが、この規則の各組には色が必要です。2組目の色を省くと4ビットの区切りが崩れ、後の組まで正しく読めなくなります。

同じ帯に固定のヘッダを4ビット付けるという別条件なら、圧縮後は12ビットに4ビットを加えた16ビットです。元の15ビットより1ビット増えます。ヘッダを付けない結果と矛盾するのではなく、比べた保存範囲が異なります。ヘッダの中身はこの比較には不要ですが、その長さは必要です。

発展例題：境界から必要な連続数を考える

黒だけが連続する帯を、同じ規則で左から最大7個ずつ組にします。ヘッダはなく、帯の長さは8個以上14個以下とします。圧縮後が圧縮前より短くなる最小のタイル数を整数で求め、組と復号も示してください。

この範囲では、黒7個の組と残りの黒の組が必要です。組はどの長さでも2個なので、圧縮後は8ビットです。圧縮前はタイル数と同じビット数ですから、短くなるのは元が8ビットより大きいときです。範囲内で最小は9個です。8個では8ビット同士で等しく、短くはなりません。

9個は黒7個と黒2個に分け、1111 1010と書きます。復号すれば黒7個と黒2個で黒9個になり、境目で色も変わりません。元の9ビットに対して8ビットなので1ビット減ります。14個なら黒7個が2組で、やはり8ビットです。15個になると3組目が必要で12ビットに増えるため、組数はなめらかではなく段階的に変わります。

逆算では「長いほど得」と感覚で決めず、まず組数の変わらない区間を作ります。その区間で圧縮後の長さを固定し、元の長さと比べます。上限を変えたり、ヘッダを足したりすれば境界も変わるので、答えの数字を別の規則へそのまま移してはいけません。

誤答を手掛かりに直す

列Aについて「6と6を記録するので6ビット」と答えたとします。3ビットの個数を2つ数えた考え方ですが、各組の色を落としています。図3のように、個数だけでは白6個の次が黒6個なのか、その逆なのかを決められません。色を各組に戻すと、1ビットと3ビットの組が2つで8ビットです。

図3では同じ個数の並びから、色の順序が異なる帯が作れます。復号先が複数ある記録は、元の列を一意に戻すためには不足です。はじめの色を別に保存し、以後は色が必ず交互に変わるという別規則も考えられます。しかし上限による分割では同じ色の組が続くので、そのままでは判断できません。規則の変更は、その費用と復号方法まで示してから比較します。

別の誤りは、白8個を0と1000で書いて5ビットとすることです。個数欄は3ビットなので、1000を入れられません。7個と1個に分けて0111 0001とし、8ビットと数えます。先頭の0を消して桁を詰めることも、固定長の区切りを失わせます。

壊れた入力にも同じ注意が要ります。例えば0011 10は、白3個の後に2ビット残っています。残りから完全な1組を読めないため、列全体の復号は確定できません。読み取れた白3個は部分的な結果にとどめ、元の記録を確認します。また0000は色0に続く個数000が禁止されているので、白0個として黙って飛ばさず規則外と判断します。入力が途中で切れた場合と、完全な長さでも値が無効な場合は原因が異なります。

自分で試す5問

いずれも上の自作規則を使い、ヘッダなし、左から最大7個ずつ組にします。空白は組の区切りを示し、保存量には含めません。答えは組を4ビットずつ、長さを整数のビットで書き、復号して元の条件と照合してください。

1. 通路の表示は黒黒黒黒黒白白白白白です。組と圧縮前後の長さ、増減を求めてください。
2. 札の模様は白白黒黒白白黒黒です。組と圧縮前後の長さ、増減を求めてください。
3. 枠の模様は黒が11個、続いて白が2個です。組と圧縮前後の長さを求めてください。
4. 黒だけの帯が1個以上7個以下です。圧縮後が圧縮前より短くなる個数をすべて整数で答え、それぞれの範囲を理由とともに示してください。
5. 保存列が1011 0000 01と届きました。規則に照らして列全体を復号できるか、読める部分と問題点を順に説明してください。途中を推測して補わないものとします。

答えと照合

1. 黒5個は1101、白5個は0101なので、1101 0101です。元は10ビット、後は8ビットで2ビット減ります。復号すると黒5個の後に白5個が続き、通路の10個に一致します。どちらも5個なので個数が同じでも、各組の色の違いを残します。

2. 白2個は0010、黒2個は1010です。答えは0010 1010 0010 1010です。元の8ビットに対して後は16ビットで、8ビット増えます。各組を順に展開すると白白黒黒が2回現れ、元の並びに戻ります。白4個と黒4個という合計だけでは、交互の境界を確認できません。

3. 黒11個は7個と4個に分け、1111 1100です。白2個は0010なので、全体は1111 1100 0010です。元は13ビット、後は12ビットです。復号後の黒7個と黒4個を合わせると黒11個で、続く白2個とともに元の13個に一致します。黒の2組目も色を記録する点が境界の注意です。

4. 1個から7個はいずれも1組なので、圧縮後は4ビットです。圧縮前は個数と同じビット数です。したがって短くなる個数は5、6、7です。4では等しく、1から3では増えます。各個数は個数欄にそのまま収まり、復号すると指定した個数の黒に戻ります。8以上は問題の範囲外であり、この結論をそのまま延ばしません。

5. 最初の1011は黒3個と読めます。次の0000は4ビットありますが、個数000が禁止なので無効です。さらに末尾01は4ビットに足りず、完全な組ではありません。黒3個は読めても、その後を含む列全体は確定できません。無効な組と途中で切れた組を別々に指摘し、正しい保存列の再確認が必要です。

覚えておくこと

• 同じ値の連続を値と個数で表し、順番を保ちます。
• 個数の上限を超えたら分割し、各組の値も数えます。
• ヘッダを含む条件をそろえて前後の長さを比べます。
• 復号して色、順番、個数を元の列と照合します。
• 無効な個数や途中で切れた組は推測で補いません。

どこで迷ったかを見分ける

境目の位置に印を付けてもらい、色が変わる場所と上限で分ける場所を別々に説明できるかを見ます。境目は正しいのに長さが違う場合は、組ごとの色やヘッダを数え落としていないか、書いた表を確認します。個別指導では、完成した符号を本人に復号してもらい、元の列の何個目まで対応するかをたどります。途中で切れた符号を示し、読める部分と確定できない部分を区別できるかも確かめます。ランレングス圧縮の答えは、元に戻る道筋まで示して初めて確かなものになります。