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

武蔵野個別指導塾の特徴

共通テスト情報I 可変長符号の区切り—途中から読むと復号が一つに決まるか調べる|武蔵野個別指導塾

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

接頭語符号の列を途中から読み直すと何が変わるか、切断位置と復号結果を対比します。区切りに注目ください。

高校生が、先頭から復号できる符号なら途中のどこからでも読めると思う場面を考えます。記録の先頭からは、符号表に従って記号を順に取り出せました。ところが、先頭の一部が失われた後で、残った0と1を新しい先頭として読むと、見かけ上は最後まで読めても、元の記号の並びとは違うことがあります。

鍵になるのは、符号表の性質と、今見ている位置が元の符号の境界かどうかを分けることです。どちらも正しい開始位置がわかっている場合の判定に役立ちますが、片方からもう片方を決めることはできません。短い自作の表と列で、読み直した結果を元の列へ戻しながら確かめます。

何を判定するのか

問いの形は大きく3つあります。1つ目は、符号表と正しい開始位置を使い、列を左から区切って記号列を求める問いです。まず符号に一致する最初の位置で区切り、次の位置から同じ操作を繰り返します。最後に元のビット列へ符号化し直して、抜けや重複がないかを見ます。

2つ目は、元の先頭から数えた指定位置で切り、残りを新しい先頭として読んだ結果を比較する問いです。切る位置が元の符号の境界なら、元の記号列の対応する後半を読めます。一方、符号の途中なら、別の記号として読める場合も、最後に未完成の符号が残る場合もあります。切断後の読みが成立することと、元の境界を取り戻せたことは別の判定です。

3つ目は、途中からでも必ず元どおりに読めるという主張に対し、反例を挙げる問いです。表が接頭語符号であること、元の列が正しい符号の連結であること、切る位置と切断後の結果を示します。1例でも主張に合わない例があれば、その主張は成り立ちません。逆に、1例で偶然うまく読めても、どの位置でもうまくいく証明にはなりません。

比較では符号表と元のビット列を固定し、開始位置だけを変えます。表まで変えてしまうと、結果の違いが位置によるものか、対応の変更によるものか判断できません。指定された切断位置が「そのビットの前」か「そのビットの後」かにも注意します。以下では、左端を1番目と数え、指定位置のビットを残すと明記します。

符号の終わりと次の始まり

次の表は説明のために作ったもので、実在の文字コードを表していません。記号アに0、イに10、ウに110、エに111を割り当てます。長さが異なるため可変長符号です。ここでは表にある各ビット列を1つの符号と呼び、その連結を記録とします。

記号 符号
ア 0
イ 10
ウ 110
エ 111

接頭語とは、ある列の先頭から続く部分です。例えば110の先頭の2ビットは11です。この表では、どの符号も別の符号の先頭部分になっていません。0で始まる符号は0だけであり、10を先頭に持つ別の符号もありません。110と111も同じ長さで異なります。このような条件を満たす符号を、ここでは接頭語符号と呼びます。

図1のように、正しい境界から読めば、0ならア、10ならイ、11まで来たら次の1ビットでウかエと決まります。ある符号に一致した時点で、さらに後ろまで延ばして別の符号になる心配がありません。したがって、正しい境界から始まる完成済みの記録なら、左から順に区切りを決められます。

図1 接頭語符号の分岐と記号の対応をたどる図

ただし、この性質は開始位置が正しい境界だという前提の上で使います。例えばウの110の途中にある2番目の1から読み始めると、残りの10はイの符号として読めます。読んだ部分そのものは表に合っていますが、元のウを復元したわけではありません。開始位置の情報は、符号表とは別に必要です。

また、接頭語符号であることと、切断された位置がどこだったかがわかることは同じではありません。残りの列だけを見て読めた場合も、失われた部分に何があったかは別途与えられなければ決まりません。表が保証するのは、正しい境界からの読み方であり、欠けた記録の履歴ではありません。

基本例題:切断後の読みを比べる

上の表を用います。元の記録は 11010 で、正しい開始位置は左端の1番目のビットです。左から2番目のビットを残し、それより左を取り除きます。元の記号列と、残った列を新しい先頭から最後まで読んだ記号列をそれぞれ答えてください。区切りも示します。

元の列を左から追います。最初の1だけでは表の符号に一致しません。次の1を加えた11も完成していないので、さらに0を加えます。110はウです。残りは10で、これはイです。よって元の区切りは 110|10、元の記号列はウ、イです。

切断後は2番目からの 1010 です。新しい先頭から10を読むとイ、残りの10もイです。区切りは 10|10、記号列はイ、イとなります。図2のように、2番目は元のウの内部にあります。新しい読みが最後まで成立しても、最初のイは元のウの残りから作られています。

図2 元の列と切断後の列の区切りを比較する図

元の答えを符号に戻すとウ、イは110と10で 11010 です。切断後の答えイ、イを戻すと10と10で 1010 です。どちらも各問いの入力に一致します。この往復で読み間違いは確認できますが、切断後の読みが元の記号列の後半と一致する保証にはなりません。

ここで問われている「一つに決まるか」には、対象が2つあります。残った1010を新たな境界から読むという条件の下では、表による読みはイ、イに決まります。しかし、それが元の記録のどの記号から始まったかは、残りの列と表だけでは決まりません。たとえば1010自体を正しい先頭から記録した場合も、同じ残りの列になります。

標準例題:境界から始めた場合

同じ表で、元の記録を 1110110 とします。正しい開始位置は1番目です。4番目のビットを残して左側を取り除いた場合と、5番目のビットを残して左側を取り除いた場合を比べ、それぞれ最後まで読めるか、読めるなら記号列を答えてください。

元の区切りは 111|0|110 です。エ、ア、ウを符号に戻すと111、0、110となり、元の記録に一致します。位置は、エが1〜3番目、アが4番目、ウが5〜7番目です。したがって4番目も5番目も元の境界です。

4番目からは 0110 です。0|110 と区切れてア、ウになります。5番目からは 110 でウです。いずれも残る元の記号の並びと一致します。違いは開始位置にあり、4番目ではアも残し、5番目ではアを含む前の部分を取り除いています。

境界から読むと元の後半を得られる理由は、元の記録が符号の連結であり、切断後の先頭もその連結の始まりだからです。ただし、元の境界かどうかを知らずに切断後の列だけを渡されたとき、読みが成立した事実から境界を断定してはいけません。基本例題の1010も最後まで読めたからです。

発展例題:末尾が残る場合

同じ表で、元の記録を 110111 とし、正しい開始位置を1番目とします。3番目のビットを残して左側を取り除き、残った列を新しい先頭から読みます。完成した記号と、最後に残る未完成のビット列を答えてください。未完成部分を勝手に補わないものとします。

元の区切りは 110|111 でウ、エです。切断後は 0111 です。先頭の0はアで、残る111はエです。したがってこれは最後まで読め、ア、エになります。元のウの末尾の0がアになったことが違いです。

続けて、同じ元の記録の6番目を残す場合を考えます。残りは 1 です。1はイ、ウ、エのいずれかの始まりですが、表に1単独の符号はありません。完成した記号はなく、未完成部分は1です。元の列を右端まで使っても、途中から読み直した結果は未完成になり得ます。

未完成部分が出たとき、「1だからイ」と決めるのは早すぎます。次のビットが0なら10でイ、1ならまだ110または111の可能性が残るためです。ただし、この問題では記録がそこで終わるので、存在しない次のビットを想像して答えに加えません。最後まで読めた場合も、途中で止まった場合も、与えられた列の範囲で結論を出します。

誤答を直す:読めたことと元どおりを分ける

基本例題で「1010はイ、イと読めるので、元の列もイ、イだった」と答えたとします。切断後の復号自体は正しいものの、元の開始位置を切断後の開始位置に置き換えた点が誤りです。最初に食い違うのは、元の1番目を捨て、ウの内部の2番目を新たな境界とみなした位置です。

図3のように、元の110の途中から始めると、その残り10がイとして完成します。修正するには、まず元の開始位置から 110|10 と区切り、その境界を記録してから指定位置で切ります。その後で残りを別に読み、2つの結果を照合します。

図3 符号の途中を新たな境界とした誤りの位置

もう一つの誤りは、切断後に未完成の1が残ったとき、表の中から好きな記号を選ぶことです。1だけではどの符号か決まらず、しかも問題にないビットを付け足してはいけません。完成した符号と未完成の残りを分けて書けば、結果が成立しない理由を示せます。

反対に、途中からの読みが元と異なる例を1つ見つけて「途中からは絶対に読めない」と結論するのも行き過ぎです。元の境界で切れば後半を正しく読めますし、内部で切っても別の記号列として完成することがあります。判定の対象を、読めるか、元の後半と一致するか、元の開始位置が特定できるかに分けてください。

練習問題

次の5問はすべて自作です。各表は接頭語符号であり、正しい開始位置は元の列の1番目です。位置は左から数え、指定した位置のビットを残してそれより左を取り除きます。切断後は残りの先頭を新しい境界とし、完成した記号と未完成部分を区別してください。

  1. 符号表はカが0、キが10、クが11です。元の列 10110 を3番目から残します。元の記号列と切断後の記号列を、区切りとともに答えてください。
  2. 符号表はサが1、シが00、スが01です。元の列 00101 を2番目から残します。元と切断後の記号列をそれぞれ答え、切断位置が元の境界か判定してください。
  3. 符号表はタが0、チが10、ツが110、テが111です。元の列 011011 を2番目から残します。元の列を区切り、切断後に完成する記号と未完成部分を答えてください。
  4. 符号表はナが1、ニが01、ヌが001、ネが000です。元の列 001101 を3番目から残します。元と切断後の記号列を求め、切断後の読みが元の記号列の後半に一致するか答えてください。
  5. 符号表はハが0、ヒが10、フが11です。元の列 11010 について、2番目から残す場合と3番目から残す場合を比較します。それぞれ区切りと記号列を示し、元の境界から始まるものを答えてください。

練習の答えと道筋

  1. 元は 10|11|0 でキ、ク、カです。3番目からは 110 となり、11|0 でク、カです。3番目は元のクの先頭なので境界です。ク、カを符号に戻すと110となり、残した列と一致します。

  2. 元は 00|1|01 でシ、サ、スです。2番目からは 0101、区切りは 01|01 でス、スです。2番目は元のシの途中なので境界ではありません。ス、スを戻すと0101ですが、元の記号列の後半をそのまま得たことにはなりません。

  3. 元は 0|110|11 と追えますが、末尾の11は表にない未完成部分です。問題文の元の列が完成済みとは指定されていないため、完成した記号はタ、ツ、未完成部分は11です。2番目からは 11011 で 110|11、完成した記号はツ、未完成部分は11です。ツを110に戻して残りの11を付けると、切断後の列を再現できます。

  4. 元は 001|1|01 でヌ、ナ、ニです。3番目からは 1101、1|1|01 でナ、ナ、ニです。元のヌの最後の1をナと読んでいるため、元の記号列の後半であるナ、ニとは一致しません。ナ、ナ、ニを戻すと1101で、切断後の列には一致します。

  5. 元は 11|0|10 でフ、ハ、ヒです。2番目からは 1010、10|10 でヒ、ヒです。3番目からは 010、0|10 でハ、ヒです。元の境界は1、3、4番目なので、指定された2つのうち境界から始まるのは3番目です。各記号列を符号に戻すと、それぞれ1010と010になります。

覚えておくこと

正しい境界から接頭語符号を読むと、符号の終わりを左から決められます。
途中からの読みが完成しても、元の記号の後半とは限りません。
未完成の末尾には、与えられていないビットを足しません。
区切りと記号を元の列へ戻し、切断位置も照合します。

どこで迷っているかを見る

元の列を区切る前に切断後の列だけを見ている場合は、元の開始位置と、各符号の最初と最後に印を付けて説明してもらいます。境界を指せるのに切断後の読みを誤る場合は、新しい先頭から表に一致するまで何ビット読んだかを確かめます。表の性質と切断位置のどちらを根拠にしているかが見えるからです。

最後まで読めた答えについては符号化し直し、未完成部分がある答えについては完成部分に残りをつないで入力へ戻します。その上で、復号した列が元の記号列の後半と一致するかを別に尋ねます。個別指導では、この2つを同じ判定として扱っていないかを確かめます。境界の情報を失うと、正しい表だけでは元の区切りを特定できない場合があります。

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

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

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

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

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

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

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