武蔵野個別指導塾の特徴

高校情報I 文字列のデータ量—固定長と可変長で必要な保存量が変わる理由を計算する｜武蔵野個別指導塾

公開 2026.11.14更新 2026.11.14武蔵野個別指導塾の特徴高校情報I 情報社会の問題解決と情報デザイン

自作の符号表で区切りと復号を確かめ、出現回数と符号長から比べるのが文字列のデータ量です。

よくあるのは、展示の短い見出しを保存するとき、高校生が文字数だけを数えてファイル容量を決める場面です。同じ文字数でも、1文字に割り当てるビット数が異なれば、文字列を表す部分の長さは変わります。さらにファイル全体には、文字列以外の情報や端数を埋めるビットが加わる場合があります。何を数える問題なのかを先に確かめましょう。

問題の入口を見分ける

出方の1つは、符号表と文字列から、文字列を表すビット数を求めるものです。固定長なら文字数に1文字分の長さを掛けられます。可変長なら各文字の出現回数に、それぞれの符号長を掛けて合計します。同じ長さの文字列でも、どの文字が何回現れるかが結果に関係します。

別の出方は、固定長と可変長の2つの表で同じ文字列を表し、差とその理由を説明するものです。短い符号が多く使われると合計が小さくなることがありますが、可変長ならいつも小さくなるとは限りません。両方の表について実際に数え、符号列を元の文字列に戻せることも確かめます。

さらに、上限から許される文字数を逆算したり、途中で切れた符号列を判定したりする問いもあります。符号表、対象の文字列、区切りの規則、ヘッダや端数の扱いが条件です。これらが欠けるときは勝手に補わず、何が不足しているかを答えます。

文字数からビット数へ

ビットは0または1を表す単位です。ここでは各文字を0と1の並びに対応させた、自作の符号表を使います。文字列のデータ量として、まず文字に対応する符号を順番につないだ部分の長さをビットで数えます。実在する文字コードの割当てや保存時のバイト数を、この表から推測することはできません。

固定長符号では、表にあるどの文字も同じ長さの符号を持ちます。例えば1文字が3ビットなら、表に含まれる文字を6文字並べたとき、符号部分は18ビットです。どの文字が多いかにかかわらず、各文字の寄与が同じだからです。ただし、表にない文字はこの表では表せません。文字数が数えられても、符号が未定の文字を含む列の長さは決まりません。

可変長符号では、文字によって符号長が異なります。ある文字が1ビット、別の文字が3ビットなら、後者の出現1回は前者の3回と同じ長さを使います。表の行ごとに「出現回数」と「1回分の長さ」を対応させ、積を足します。0回の文字も表に残して数えれば、数え落としを見つけやすくなります。

図1のように、文字列から出現回数を調べ、符号表から長さを取り出して合計します。文字数は出現回数の合計、ビット数は長さを重みとして付けた合計です。両方を別の欄に置くと混同を防げます。

図1の流れで求めた値は、定めた符号列の長さです。保存の単位を1バイト8ビットとする問題でも、端数をどう保存するかは別の条件です。例えば18ビットをバイト単位で収め、最後の不足分を埋める規則なら3バイトですが、埋め方を定めずに18ビットを単に8で割ると2.25バイトです。後者はビット数を8で表した値であり、必ずそのまま保存に必要な整数バイト数になるわけではありません。

区切りも必要です。可変長の符号を連結した列が元に戻るには、読み手が文字の境界を決められなければなりません。ここでは、どの符号も他の符号の先頭部分にならない表を使います。この条件なら左から読んで表の符号に一致したところで区切れます。一致した符号を別の長い符号の途中として読み直す必要がないためです。この条件は一意に復号できる表の作り方の1つであり、一意に復号できる表が必ずこの形に限られるという意味ではありません。

基本例題：同じ見出しを2通りに表す

展示の見出しを「アイアウア」とします。空白は文字の区別のための表示で、保存しません。自作の表Aはアを00、イを01、ウを10とします。表Bはアを0、イを10、ウを11とします。どちらも表の3文字だけを扱い、区切り記号とヘッダは付けません。各表で符号化した列と長さをビット単位の整数で求め、復号して元に戻るか確認してください。

まず出現回数はアが3回、イが1回、ウが1回です。合計5回なので、見出しの5文字と一致します。表Aは各文字2ビットですから、5回分で10ビットです。順に並べると「00 01 00 10 00」で、空白を除くと「0001001000」です。左から2ビットずつ区切り、ア、イ、ア、ウ、アに戻ります。

表Bではアが1ビット、イとウが各2ビットです。アの3回分は3ビット、イとウはそれぞれ2ビットなので、合計は7ビットです。符号を順につなぐと「0 10 0 11 0」、空白を除くと「0100110」です。左から0を読むとア、次の10はイ、次の0はア、次の11はウ、最後の0はアです。

図2のように、同じ文字列でも各文字に割り当てる長さが変わると合計が変わります。この見出しでは表Bが表Aより3ビット短くなります。表Bで短い符号を持つアが3回出ることが、その差を生む理由です。

図2の2つの列は、見た目のビット数だけでなく、各表で元の見出しに戻ることも確認しました。表Bの0、10、11のどれも別の符号の先頭ではありません。したがって符号の間に目印を追加せず、表に従って区切れます。もし区切り記号を保存する条件なら、その分を別に加える必要があります。

標準例題：文字の偏りが変わったら

表Aと表Bをそのまま使い、別の見出し「イウイウイウ」を保存します。空白は保存せず、ヘッダや端数を埋めるビットも考えません。各表のビット数を整数で求め、どちらが短いか答えてください。

表Aは6文字に各2ビットを使い、12ビットです。表Bではイが3回、ウが3回で、どちらも2ビットですから、6ビットと6ビットを足して12ビットです。今回は同じ長さです。表Bに1ビットの符号が存在しても、その文字が現れなければ短縮には寄与しません。

元の見出しへ戻して確認します。表Aの列は「01 10 01 10 01 10」、表Bの列は「10 11 10 11 10 11」です。各表で区切って読むと、どちらもイとウが交互に3回ずつ現れます。文字数が1つ増えたかどうかだけでなく、どの文字の回数が変わったかを調べることが比較の要点です。

発展例題：上限から回数を決める

表Bを使い、イを2文字、ウを1文字含む見出しの先頭にアを並べます。符号部分の上限は9ビットで、区切り記号やヘッダはありません。アは0文字でもよいものとします。上限内で置けるアの最大文字数を整数で求め、その列を復号して確認してください。

イ2回には4ビット、ウ1回には2ビットが必要です。既に6ビットを使うので、残りは3ビットです。アは1回につき1ビットなので、最大3文字を置けます。見出しを「アアアイイウ」とすると符号列は「0 0 0 10 10 11」で、合計9ビットです。左から区切るとア3文字、イ2文字、ウ1文字に戻ります。アをもう1文字加えると10ビットとなり、上限を超えます。

条件を変えて、文字列のほかに2ビットの目印も同じ9ビットの枠に入れる場合を考えます。文字に使えるのは7ビットですから、イとウの6ビットを引くとアは最大1文字です。目印を忘れると上限を満たさない計画になります。逆に目印が枠の外にある問題では、その2ビットを引いてはいけません。

誤答を直す：回数と長さを結び付ける

基本例題で「3種類の文字があるので、表Bは1と2と2を足して5ビット」と答えたとします。これは表の各行を1回ずつ使った長さであり、見出しのアが3回あることを反映していません。図3のように、文字ごとの回数を対応させてから足し直します。アの分を1ビットから3ビットへ直すと合計7ビットです。

図3の修正では、回数の合計も5文字に戻して確認します。計算結果だけを直しても、どの文字を数え落としたかが残らなければ、別の文字列で同じ誤りを繰り返します。表にない文字が出た場合は0ビットとして扱わず、符号表の不足を報告します。

もう1つの誤りは、符号の長さが決まれば、どんな表でも連結した列を復号できると考えることです。例えばアを0、イを01、ウを1とすると、列01はイとも、アの後にウとも読めます。長さの合計が2ビットであることと、元の文字列が一意に決まることは別の条件です。復号できない表を見つけたら、読み方を2通り示し、符号表や区切り規則を見直します。

列が途中で切れた場合も、最後を都合よく補ってはいけません。表Bの列「0101」を読むと、最初の0はア、次の10はイですが、最後の1は10または11の途中です。残りは未完成なので、列全体を表の文字列として復号できません。入力の終端や欠落を調べることが先です。同じく保存や読み取りの道具が失敗したとき、表示された一部だけを完全な結果として数えず、元の列と成功した範囲を確認します。

練習：符号と条件を読み取る

次の問題の表は問題内で定めた自作のものです。空白は見やすくするためのもので保存しません。特に指定がなければ、区切り記号、ヘッダ、端数を埋めるビットはありません。長さはビット単位の整数で答えてください。

表Cはカを00、キを01、クを10、ケを11とします。「カキカケクキ」の符号列と長さを求め、復号した文字列も書いてください。
表Dはカを0、キを10、クを110、ケを111とします。「カキカケクキ」を表Dで表した符号列と長さを求め、問1と比べて何ビット短いか答えてください。
表Dで「ケケクキ」を表す長さを求めてください。同じ4文字を表Cで表す長さと比べ、どちらが何ビット長いかも答えてください。
表Dで、キを2文字含み、その後にカを並べます。符号部分の上限を8ビットとするとき、カは最大何文字置けますか。最大のときの符号列と復号結果も書いてください。
表Dで受け取った列が「0111」と「011」の場合をそれぞれ考えます。列全体を復号できるか判定し、できる場合は文字列を、できない場合は読み取れた部分と残りを示してください。

練習の答えと確かめ

「00 01 00 11 10 01」で、空白を除くと「000100111001」です。6文字に各2ビットなので12ビットです。2ビットずつ区切ればカ、キ、カ、ケ、ク、キに戻り、元の6文字と一致します。
「0 10 0 111 110 10」で、空白を除くと「010011111010」です。カ2回で2ビット、キ2回で4ビット、クとケは各3ビットなので合計12ビットです。問1と差は0ビットで、短くはなりません。左から表Dに一致するところで切ると元の6文字に戻ります。
ケ2回で6ビット、ク1回で3ビット、キ1回で2ビットなので、表Dでは11ビットです。表Cでは4文字に各2ビットを使い8ビットです。表Dが3ビット長くなります。「111 111 110 10」を表Dで戻すとケ、ケ、ク、キとなり、回数も合っています。短い符号が存在しても、長い符号の文字が多い列では逆転します。
キ2文字に4ビットを使い、残りは4ビットです。カは1文字1ビットなので最大4文字です。列は「10 10 0 0 0 0」、空白を除いて「10100000」です。復号するとキ、キ、カ、カ、カ、カとなり、8ビットを使います。カを5文字にすると9ビットで、上限を超えます。
「0111」は「0 111」と区切れ、カ、ケです。「011」は最初の0がカですが、残る11はクの110かケの111の途中です。したがって列全体は復号できません。欠けたビットを推測してクやケと決めず、送り直しや元データの確認が必要です。