冬期講習 2026-2027、募集中。総復習は売りません。90分×完全1対1で、穴だけを塞ぎます 詳しく →
電話 0422-27-7828チャットで質問無料相談を予約

武蔵野個別指導塾の特徴

共通テスト情報I 可逆圧縮と連続しない列—短くならない場合も元へ戻せるか調べる|武蔵野個別指導塾

学習のイメージ写真 武蔵野個別指導塾
X LINE Facebook

交互の記号を連続数との組にして、保存量と復元結果を別々に判定します。増えても可逆です。

よくあるのは、高校生が可逆圧縮なら交互の記号列も必ず短くなると考える場面です。連続する同じ記号をひとまとめにすれば短くなりそうですが、記号が切り替わるたびに新しい組を作る方式では、各組に回数を記録する分も必要です。一方、長くなった記録でも、決めた手順で元の並びに戻せるなら可逆です。保存量の大小と復元の成否を、別の問いとして追いましょう。

何を比べる問いなのか

この方式では、隣り合う同じ記号のまとまりを見つけ、記号とその連続数を1組にします。例えば同じ記号が長く続けば、何個も記号を書き直す代わりに、1個の記号と回数を記録します。ところが交互列では、隣同士が異なるため、各記号がそれぞれ長さ1のまとまりです。組数が元の記号数と同じになり、組ごとの回数欄が加わります。

問われる型は大きく3つです。第1に、元の列をどこで区切るかです。第2に、各欄の長さとヘッダを使って、変換前後の総量を比べます。第3に、得られた組を順番に展開し、元の列と一致するかを調べます。第2と第3は連動しますが、答える内容は異なります。容量が増えたという結果から、復元に失敗したとは言えません。

比較するときは、記号1個の長さ、回数欄の長さ、ヘッダの長さと、元の記録に何を含めるかを固定します。変えるのは列の並びや長さです。以下の数値は計算用の自作条件であり、実際のファイル形式の定めではありません。すべての組の回数は、その問題で定めた回数欄に収まるものとします。

組を作る場所と復元する手順

連続した同じ記号の、途中で区切らない最大のまとまりを、ここでは連なりと呼びます。左から右へ見て、記号が変わった直前で区切ります。1個だけでも連なりです。順番を変えず、各連なりを「記号、回数」の順の組にします。元の列が空でない場合、最初と最後にもそれぞれ連なりがあります。

図1のように、同じ記号が3個なら1組で表します。その組の2つの欄は、記号の種類と繰り返す数という異なる役目です。復元では記号を回数の数だけ並べ、組を左から順につなぎます。元の長さは回数の合計からも調べられますが、長さが同じだけでは並びの一致を保証しません。記号と順序も照合します。

図1 連続する記号を組にして元の列へ戻す関係

図1の例では、Aを3回並べればAAAです。組を作るときに「3」という情報を残すため、元の何個目までが同じ記号だったかを復元できます。Aの直後に別の記号があれば、そこで次の組に移ります。変換後の記録が壊れていないことと、読み手が同じ欄の規則を使うことは、この復元の前提です。

保存量には、組の中身のほか、変換後の記録に付くヘッダを含めます。ヘッダは先頭に置く付加情報で、ここでは指定された長さを加える対象です。具体的な内容は問いません。組が1個なら記号欄と回数欄を各1回、組が複数なら各組について数え、最後にヘッダを1回足します。元の記録についても、問題が指定した長さを用い、勝手にヘッダを足しません。

基本例題:交互の列を戻す

【問題】記号PとQの列PQPQPQを保存します。各記号は変換前には2 bitで表し、元の記録に付加分はありません。変換後は連なりごとに記号欄2 bitと回数欄3 bitの組を作り、全体に4 bitのヘッダを1回付けます。回数欄には1から7まで記録できます。末尾の補充はありません。変換前後の長さをbitで求め、短くなるかを答えてください。また、組を順に書き、復元列を示してください。

まず隣の記号は毎回変わるので、図2のように6個の連なりに区切ります。回数はいずれも1で、指定範囲内です。順番に並べた組は(P,1)、(Q,1)、(P,1)、(Q,1)、(P,1)、(Q,1)です。

図2 交互の6記号を6組に分けて保存量を比べる

図2の区切りを元の列に戻すと、P、Q、P、Q、P、Qとなります。各組の回数に従って1個ずつ展開し、順につなぐとPQPQPQです。最初から最後まで記号と順番が一致するので、この記録は元に戻せます。

元の長さは6 × 2で12 bitです。変換後は1組が2と3の合計で5 bit、6組で30 bitです。ヘッダ4 bitを1回加えるので34 bitです。34 bitは12 bitより22 bit大きく、短くなりません。組の数を数えた後、ヘッダを組ごとに加えず、全体に1回だけ足すことが条件に合っています。

復号列が元に一致するという判定と、34 bitが12 bitを上回るという判定は両立します。可逆という言葉は元の列を取り戻せる性質を表し、各入力の記録が元より短いという約束ではありません。この交互列は、必ず短くなるという主張に対する具体的な反例です。

並びを変えたときの境目

【標準例題】記号RとSは各2 bit、変換前に付加分はありません。変換後は記号欄2 bit、回数欄3 bitの組と、全体で4 bitのヘッダを使います。回数は1から7まで、末尾補充なしです。列RRRRSSSSの変換前後の長さをbitで求め、復元列を示してください。

連なりはRRRRとSSSSの2つです。組は(R,4)、(S,4)で、どちらの回数も欄に収まります。元は8 × 2で16 bit、変換後は2 × 5に4を加えて14 bitです。2 bit短くなります。Rを4個、Sを4個並べてつなぐとRRRRSSSSです。元の8個と順序が一致するので、容量が減った場合も復元を確かめられます。

基本例題とは入力の長さも違うので、その差だけを連続性の効果だと決めることはできません。同じ8個でRSRSRSRSを使えば、8組になり、変換後は8 × 5に4を加えて44 bitです。元の16 bitと比べて増えます。記号数と欄の条件をそろえて並びだけを変えた比較では、連なりの数の違いが保存量の差になります。

【発展例題】記号UとVの列は6個で、各記号は変換前に3 bit、付加分はありません。変換後は記号欄3 bit、回数欄2 bitの組を作り、ヘッダを全体に3 bit付けます。回数は1から3まで記録でき、末尾補充はありません。各連なりの長さが3以下の列に限ります。変換後が元より短くなる組数を整数で答え、ちょうど同じ長さの列を1つ示して復元してください。

元は6 × 3で18 bitです。組数をkとすると、変換後は1組5 bitなので、5 × kに3を加えた長さです。短くするには5 × kに3を加えた値が18より小さくなります。kが3なら18 bitで同じ、kが4以上ならそれより大きくなります。kが2なら13 bitで短くなります。6個を長さ3以下の連なりに分けるので、1組では表せず、可能な組数は2から6です。したがって短くなる組数は2です。

同じ長さになる例はUUVVUUです。組は(U,2)、(V,2)、(U,2)で3組、保存量は18 bitです。それぞれUU、VV、UUに戻してつなぐと元のUUVVUUです。同じ記号の組が離れた位置にあっても、間のVを飛ばしてまとめることはできません。まとめると順番が変わるからです。

この境界は欄の長さやヘッダが変われば移動します。ヘッダを0にしても、交互列で組ごとに回数欄が必要なら、その欄の分だけ元より増えます。他方、ヘッダがある場合、組が少なくても付加分が節約分を上回ることがあります。先に「圧縮」という名前で決めず、元の長さと総量を同じ単位で比べます。

誤答を最初のずれから直す

基本例題で「Pが3個、Qが3個なので(P,3)、(Q,3)の2組、14 bit」とする答えを考えます。図3のように、最初のPの次はQです。Pを3個続けると、この2文字目ですでに元の列と食い違います。全体にある個数を数えたこと自体は正しくても、連続数として記録してはいけません。

図3 全体の個数を連続数とした誤りと最初の不一致

図3の誤った2組を実際に展開するとPPPQQQです。元のPQPQPQと長さはともに6ですが、2文字目が異なります。長さの一致だけでなく各位置を比べる必要があります。正しくは変化のたびに区切って6組とし、34 bitを得ます。

別の誤答は「34 bitに増えたので復元不能」です。この場合は区切りではなく、容量の比較から復元の成否へ飛んだことが原因です。正しい6組を展開すれば元の列に一致します。逆に、たまたま短い記録ができても、回数や順番を書き間違えれば元には戻りません。保存量と復号結果をそれぞれ検査して修正します。

自分で試す5問

各問の記号欄の長さは元の各記号の長さと同じです。元には付加分がなく、変換後のヘッダは全体に1回付けます。末尾補充はありません。連なりは途中で分けず、回数は指定された範囲内とします。各問で組と復元列を示し、長さはbitで答えてください。

  1. 列XYXYXを扱います。記号は各3 bit、回数欄は2 bitで1から3を表し、ヘッダは2 bitです。前後の長さと大小を求めてください。
  2. 列MMMMNNNを扱います。記号は各2 bit、回数欄は3 bitで1から7を表し、ヘッダは1 bitです。前後の長さと大小を求めてください。
  3. 列ABBAABを扱います。記号は各4 bit、回数欄は2 bitで1から3を表し、ヘッダは6 bitです。前後の長さと大小を求めてください。
  4. 列CCCDDDを扱います。記号は各2 bit、回数欄は2 bitで1から3を表し、ヘッダは4 bitです。前後の長さと大小を求めてください。
  5. 列EFEFFEFを扱います。記号は各3 bit、回数欄は2 bitで1から3を表し、ヘッダは3 bitです。前後の長さと大小を求めてください。

5問の解答と照合

  1. 区切りはX・Y・X・Y・Xで、組は(X,1)、(Y,1)、(X,1)、(Y,1)、(X,1)です。元は5 × 3で15 bit、後は5 × 5に2を加えて27 bitです。12 bit増えます。各組を1回ずつ展開するとXYXYXとなり、元の5位置と一致します。
  2. 区切りはMMMM・NNNで、組は(M,4)、(N,3)です。元は7 × 2で14 bit、後は2 × 5に1を加えて11 bitです。3 bit減ります。Mを4個、Nを3個つなぐとMMMMNNNです。回数の合計も7で、元の個数に戻ります。
  3. 区切りはA・BB・AA・Bで、組は(A,1)、(B,2)、(A,2)、(B,1)です。元は6 × 4で24 bit、後は4 × 6に6を加えて30 bitです。6 bit増えます。展開するとA・BB・AA・B、すなわちABBAABです。離れたAを一つの連なりにしないことが順序を保つ鍵です。
  4. 区切りはCCC・DDDで、組は(C,3)、(D,3)です。元は6 × 2で12 bit、後は2 × 4に4を加えて12 bitです。同じ長さです。CCCとDDDをつなげばCCCDDDになり、回数も3と3で元の6個に一致します。同じ長さは、短くなった場合には含めません。
  5. 区切りはE・F・E・FF・E・Fで、組は(E,1)、(F,1)、(E,1)、(F,2)、(E,1)、(F,1)です。元は7 × 3で21 bit、後は6 × 5に3を加えて33 bitです。12 bit増えます。組を展開してE・F・E・FF・E・FをつなぐとEFEFFEFです。隣り合う2個のFだけが1組になることを位置ごとに確かめます。

覚えておくこと

連なりは、隣り合う同じ記号のまとまりです。
保存量は組ごとの欄と全体のヘッダを足します。
交互列では組が増え、元より長くなることがあります。
可逆かどうかは、展開した列が元と一致するかで判定します。

つまずいた位置を見つける

組数が合わないときは、元の列の隣同士を左から指し、変化した場所ごとに区切りがあるか見ます。全体の個数を使っていたら、離れた同記号の間に何があるかを問い直します。展開した列を元と1位置ずつ照らすと、最初に順序が変わった場所を特定できます。

容量だけが合わないときは、1組の長さ、組数、ヘッダの順に別々に書いてもらいます。ヘッダを何回足したか、前後ともbitで比べたかを確かめます。個別指導では、増加した記録を実際に戻してもらい、容量と復元が別の判定である理由を説明できるかを見ます。交互列の各切れ目を追えば、長さが増えても元に戻ることを具体的に示せます。

もう「日東駒専」を目標にしないでください。

武蔵境駅徒歩30秒、講師1人に生徒1人の完全1対1。授業のあいだ、先生は隣を離れません。いまの詰まりを、無料相談でそのまま話してください。

まず15分だけ電話で話したい方は、無料電話相談(15分)から。塾からお電話を差し上げます。

本気になった日が、入塾の日。

お子様の教育、迷ったら「丸投げ」してください。必ず、期待以上の結果で返します。武蔵野で育む、武蔵境で学ぶ。

電話は年中無休。365日、24時間、お電話可能。

チャットで質問チャット
無料相談を予約する 電話 0422-27-7828電話 LINE チャット
で質問