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

武蔵野個別指導塾の特徴

共通テスト情報I 非可逆処理と復元—後から可逆圧縮しても失った違いを戻せるか調べる|武蔵野個別指導塾

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

値の統合と可逆な符号化を順にたどり、元の列を特定できる条件を見極める練習です。復元の分岐をたどりましょう。

よくあるのは、高校生が、記録を小さくする途中で値をまとめても、最後に可逆圧縮を使えば削除した違いまで取り戻せると考える場面です。可逆という言葉は強い手がかりですが、どの段階の入力に戻せるのかまで読まないと、答えを取り違えます。後の処理を逆向きにたどって到着するのは、その処理に渡した中間列です。さらに前の元の列を特定できるかは、統合の表と元の入力条件を調べて決めます。

要点(結論から)

  • 後段の可逆性が保証するのは、その後段への入力の復元です。
  • 統合先から元候補を表で逆引きし、位置ごとに調べます。
  • 異なる元の列が同じ保存列になると、一意に決められません。

どこまで戻す問いか

判定の型は大きく3つあります。1つ目は、元の列から統合表と符号表を順番に使い、保存する列を求める型です。2つ目は、保存列を後ろから戻して中間列を求め、元の候補を列挙する型です。3つ目は、異なる元の列を2つ示して、同じ保存列になることから元を一意に決められないと説明する型です。どれも表を使いますが、求めるものはそれぞれ違います。

表と入力できる値の範囲は問題の条件として固定します。統合表にある値を別の値へ勝手に変えたり、符号表にない記号を補ったりはしません。一方、異なる元の列を比べるときは、その入力列だけを変えます。同じ結果が得られる2列が見つかれば、保存列を見ただけでどちらだったか決められない反例になります。

元の列がたまたま1つに絞れる場合もあります。非可逆な表を使ったという名前だけで、どの記録も必ず元を特定できないと決めるのは早すぎます。入力範囲に加え、記録された中間値に対応する候補の数を調べましょう。表にない入力や壊れた保存列については、表の適用条件が満たされないため、勝手に正常な列に直して判定しません。

統合と可逆な対応を分ける

元の各値を別の記号に置き換える表を考えます。たとえば値 1 と 2 をともに A に、値 3 を B にする表です。ここでは 1 と 2 の違いが A という同じ記号へ統合されます。前向きにはどちらからも A が得られますが、逆向きに A から出発すると候補は 1 と 2 の2つです。B の逆向きの候補は 3 だけです。

その後に A を 0、B を 1 に対応させるとします。各記号に異なる1桁を割り当てたので、0 から A、1 から B へ戻せます。この後段の対応は、対象を A と B の列に限れば可逆です。図1のように、後段の逆変換で戻る場所と、最初の統合の手前にある場所を区別します。

図1 統合と可逆な対応で戻る範囲を分ける図

図1では 1 と 2 の両方が A に集まります。0 を A に戻せても、A の左側のどちらを通ったかは示されていません。可逆とは、対象の入力を対応する出力から元どおりに特定できる性質です。ここでの後段は中間記号の違いを保存しますが、前段ですでに一緒になった違いを新たに記録するわけではありません。

反対に、元の値が 3 だった箇所は B を経て 1 となり、表の範囲では 3 に戻せます。非可逆という処理全体の性質と、特定の出力について元候補が1つかどうかは別の問いです。また、実際の圧縮方式を表した図ではありません。ここでの後段は追跡しやすい自作の可逆な符号化で、短くなることを条件にしていません。

基本例題:同じ保存列へ集まる2つの入力

ある展示の明るさを3個の値で記録します。元の各値は 1、2、3 のいずれかです。各位置で 1 と 2 を A、3 を B に統合し、その後 A を 0、B を 1 に置き換えます。順序や位置は保存し、別の情報は付けません。元の列が「1、3、2」と「2、3、1」のとき、それぞれの中間列と保存列を順に書き、保存列から元の列を一意に決められるか答えてください。復元目標は統合前の3個の値です。

最初の列では、1 が A、3 が B、2 が A です。中間列は「A、B、A」、保存列は「0、1、0」です。次の列では、2、3、1 の順に A、B、A となるため、保存列も「0、1、0」です。図2のように異なる入口から同じ結果に到着します。

図2 異なる元の二列が同じ保存列に至る追跡

保存列「0、1、0」から後段を逆にたどると「A、B、A」です。これは中間列と一致するので、後段の往復は成功しています。しかし先頭の A は 1 でも 2 でもよく、末尾の A も同様です。元の候補は「1、3、1」「1、3、2」「2、3、1」「2、3、2」の4列です。各候補を統合するといずれも A、B、A に戻り、符号化すると 0、1、0 になります。したがって元の列は一意に決まりません。

候補を数えるときには、各位置を別々に考えます。先頭は2通り、中央は1通り、末尾は2通りなので、2 × 1 × 2 で4通りです。この掛け算は、元の各位置に別の制約がないという問題の条件によります。たとえば元の列に同じ値を繰り返してはいけないという条件があれば、その条件に合わない候補を除く必要があります。

候補が1つになる境界

標準例題です。基本例題と同じ統合表と後段の対応を使います。元の各位置には 1、2、3 のどれでも置け、位置間の制約はありません。保存列「1、1、1」から、中間列と元の列をそれぞれ3個の記号または値で書き、元を一意に決められるか答えてください。

各 1 を B に戻すので中間列は「B、B、B」です。表で B に対応する元の値は 3 のみですから、元は「3、3、3」の1列に決まります。前向きに確かめると B、B、B を経て 1、1、1 となり、保存列に一致します。表には 1 と 2 が統合される箇所があっても、この保存列の各位置ではその統合先が現れていません。処理全体を非可逆と呼ぶことと、この記録に限って元の候補が1列であることは両立します。

発展示題です。同じ表を使いますが、元の列は3個の値からなり、1、2、3 をそれぞれ1回ずつ使うと追加でわかっています。保存列が「0、1、0」のとき、条件に合う元の列をすべて書き、一意に決まるか答えてください。

逆変換した中間列は「A、B、A」です。中央の B は 3 と決まります。先頭と末尾の A はそれぞれ 1 または 2 ですが、1 と 2 をそれぞれ1回使う条件があるので「1、3、2」と「2、3、1」の2列に限られます。どちらも前向きに変換すると保存列は 0、1、0 です。候補は減りましたが2列残るので、一意には決まりません。

追加条件が候補を減らすことと、欠けた情報を後段の符号が取り戻すことは異なります。追加条件が最初から共有されていれば、それを使って候補を除外できます。しかし、残った2列を区別する情報は保存列にも追加条件にもありません。候補のうち1列を選ぶ規則を勝手に設けても、それが実際の元の列と一致する保証はありません。

誤った戻し方を直す

基本例題の保存列「0、1、0」を見て、「後段が可逆だから元は 1、3、2 だ」と答える間違いを考えます。図3では、後段を逆に戻して A、B、A を得るところまでは正しい一方、最初の A を必ず 1 とするところで条件からはみ出します。

図3 逆変換で元の値を一つに決められない位置

図3の A には 1 と 2 の両方が対応します。元の列が実際に 1、3、2 だったとしても、保存列を受け取った側がその事実を別に知らなければ、2、3、1 も候補です。正しい修正は、後段を逆変換した後に統合表を逆向きに調べ、各位置の候補と追加条件を照合することです。

別の誤答は「非可逆だから何も戻せない」です。可逆な後段からは中間列を正確に戻せますし、B に対応する元の値も表の範囲では特定できます。どの段階を目標にしているかを書き添えるだけで、この2種類の言い過ぎを避けられます。

なお、保存列に表で定められていない記号が混ざった場合は、後段の逆対応を適用できません。欠けた記号を推測して埋めるのではなく、与えられた表では復元結果を決められないと判断します。これは複数の正常な元候補がある場合とも、正常な候補が1列に定まる場合とも異なります。

元の候補が複数ある場合、候補のどれかを実際の元と断定するには、保存列とは別の情報が必要です。たとえば元の値の使用順序まで既知なら候補が減ることがあります。ただし、その情報が与えられたかどうかは問題文で確かめます。記号の名前や表示順から、存在しない優先順位を読み取ってはいけません。候補を残す判断も、条件に忠実な答えです。

確かめる5問

次の5問はそれぞれ独立した自作の条件です。列の順序と位置は保存され、問題に書いた情報以外は付けません。各問で復元目標は統合前の元の列です。記号は表に書いたものをそのまま用いてください。

  1. 工作の材料の値 4、5、6 を、4 と 5 は P、6 は Q に統合し、P を 7、Q を 8 に対応させます。元の列「4、6、5」について、中間列と保存列をそれぞれ3個の記号で書いてください。また保存列から元を一意に決められるか答えてください。
  2. 気温の区分として使う値 7、8、9 を、7 は R、8 と 9 は S に統合し、R を 2、S を 3 に対応させます。保存列「2、2」を逆にたどり、中間列と元の列を2個ずつ書き、一意に決まるか答えてください。
  3. 音量の値 10、11、12、13 を、10 と 11 は T、12 と 13 は U に統合し、T を 4、U を 5 に対応させます。保存列「4、5」の元になり得る2個の値の列をすべて書き、各候補が保存列に戻ることを示してください。
  4. 明るさの値 14、15、16 を、14 と 15 は V、16 は W に統合し、V を 6、W を 9 に対応させます。元の2個の値は異なるとわかっています。保存列「6、6」の元候補をすべて書き、一意に決まるか答えてください。
  5. 模様の値 17、18、19 を、17 と 18 は X、19 は Y に統合し、X を 0、Y を 1 に対応させます。受け取った列は「0、2」です。表にある記号以外への対応は定めていません。中間列と元の列を、この表だけで一意に復元できるか理由とともに答えてください。

答えとたどり直し

  1. 4、6、5 を表に通すと P、Q、P、さらに 7、8、7 です。逆向きには 7、8、7 から P、Q、P まで正確に戻ります。P の各位置は 4 と 5 のどちらも候補なので、例えば 4、6、5 と 5、6、4 の双方が同じ保存列になります。元は一意に決まりません。元の列を前向きに戻して、各位置が 7、8、7 になることも確かめられます。

  2. 2、2 の逆対応は R、R です。R になる元の値は 7 のみなので、元は 7、7 の1列です。7、7 を再び変換すると R、R、次に 2、2 となります。S に集まる2値が表に存在しても、今回の保存列に対応する中間列は R のみです。

  3. 4、5 の逆対応は T、U です。T の元候補は 10、11、U の元候補は 12、13 なので、候補は「10、12」「10、13」「11、12」「11、13」です。4列はいずれも統合すると T、U、さらに 4、5 となります。各位置に2候補ずつあり、2 × 2 の4列を列挙しています。異なる候補が残るため一意には決まりません。

  4. 6、6 の逆対応は V、V です。各位置は 14 または 15 ですが、2個の値は異なるという条件により「14、15」と「15、14」が残ります。両方を前向きにたどると V、V、次に 6、6 です。条件を使って同じ値の組を除いても、順序の違いは残るので一意には決まりません。

  5. 最初の 0 は X に戻せますが、2 に対応する中間記号は表にありません。したがって列全体の中間列をこの表で復元できず、元の列も一意に復元できません。2 を 1 の誤りと見なせば Y を推測できますが、その修正は問題の条件にありません。表にない入力を正常な符号に直す規則が与えられない限り、推測と復元結果を区別します。

要点

つまずきの位置を見る

説明を聞くときは、まず保存列からどの表を逆向きに使ったかを確かめます。中間列まで正しく戻せた後で元の値を1つに決めているなら、統合表の同じ行き先を持つ値を指して、別の元候補も同じ保存列になるか試します。逆に、途中まで戻せることを見落としているなら、後段の記号を1位置ずつ逆対応させます。

個別に確認する際は、候補を出した後に追加条件と前向きの変換の両方を通せるかを見ると、列挙漏れや余分な候補に気づけます。表にない記号を含む列では、どの位置で規則が途切れるかを示します。復元の成否は、どの段階を目標にして、どの条件が残っているかで決まります。

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

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

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

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

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

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

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