武蔵野個別指導塾の特徴

【情報I】データの圧縮と誤り検出を図解で総まとめ—可逆・非可逆・ランレングス・パリティ｜武蔵野個別指導塾

公開 2026.10.12更新 2026.10.12武蔵野個別指導塾の特徴高校情報I 単元解説

【情報I】データの圧縮と誤り検出を図解で総まとめ—可逆・非可逆・ランレングス・パリティのアイキャッチ武蔵野個別指導塾

ランレングス法の容量計算からハフマン符号の読み取り、パリティとチェックディジットまで、図と例題で確かめます。圧縮で残す情報と誤り検出で付け足す情報の役割を区別して学べます。

よくあるのは、部活帰りの自転車置き場で、止めてある自転車の横に立って練習動画を送ろうとし、容量を小さくする設定を見て「小さくしたら、動きの細部まで消えるのだろうか」と迷う場面です。文字のファイルをまとめて小さくする操作も、動画を軽くする操作も、どちらも圧縮と呼びます。しかし、元のデータへ完全に戻せるかどうかは同じではありません。

さらに、送ったデータが途中で変わっていないかを調べるためには、確認用の情報を付け足す方法があります。容量を減らす圧縮と、情報を増やす誤り検出を続けて習うと、反対のことをしているように感じるかもしれません。目的を「効率よく表すこと」と「変化を見つけること」に分けると、両方が必要な理由が見えてきます。数字をただ公式に入れるのではなく、何を数え、どの規則で元へ戻し、どんな変化を見逃すのかまで追っていきましょう。

この単元で身につけること

圧縮の目的を説明できます。保存容量や通信に必要なデータ量を減らす利点と、圧縮・復元の処理が必要になる点を結びつけます。
可逆圧縮と非可逆圧縮を区別できます。見た目が似ているかではなく、元のデータを完全に復元できるかを判断の基準にします。
ランレングス法で連続する記号をまとめられます。記号と回数の両方に必要なビット数を数え、かえって容量が増える場合も確かめます。
ハフマン法の入口を理解できます。出現頻度と符号の長さの関係を読み、区切り記号がなくても復号できる符号の条件を確認します。
パリティビットとチェックディジットを計算できます。規則から外れたことがわかる場合と、規則を満たしたまま誤る場合を分けて説明します。

前の単元で学ぶビット・バイトや文字・画像のデータ量が、圧縮前後を比べる土台になります。特に「1文字を何ビットで表すか」という条件を読み取る力が必要です。小学校や中学校で使った割合の計算も、圧縮後の容量が元の何％かを求めるところでそのまま役立ちます。

基本の考え方

圧縮は表し方を変えてデータ量を減らすことです

データの圧縮とは、保存や伝送に必要なデータ量を減らすために、データの表し方を変えることです。たとえば同じ記号が長く続くなら、その記号を何度も書く代わりに「その記号が何回続くか」を記録できます。復元するときは、その記録を約束した規則に従って展開します。このように、元の並びにある規則性を利用するのが圧縮の基本です。

同じ通信速度で同じ条件なら、送るデータ量が少ないほど、データ本体を送るのに必要な時間を短くできます。ただし、実際の所要時間には圧縮や復元の処理、通信の準備や待ち時間も含まれます。「容量が半分なら、操作を始めてから終わるまでの時間も必ず半分」とは限りません。問題で転送時間を計算するときは、どの時間を考えるのかを確かめます。

元のデータを完全に復元できる圧縮を可逆圧縮といいます。文章の1文字やプログラムの記号が変わると意味や動作に影響するため、こうしたデータでは完全に元へ戻せることが必要です。可逆圧縮は、内容を捨てずに表し方を工夫する方法だと考えるとよいでしょう。

一方、元のデータを完全には復元できない圧縮を非可逆圧縮といいます。画像や音では、人が気づきにくい違いなどを利用して一部の情報を失わせ、データ量を減らす方法が使われます。細かな色の違いが失われても、用途によっては十分に見やすいことがあります。ただし、気づきにくいことと、データが同じであることは別です。圧縮の程度や対象によって、輪郭の乱れや音の変化が目立つ場合もあります。

図1のように、復元したものを元のデータと比べると両者を区別できます。可逆・非可逆はファイルの見た目や大きさだけで決まる分類ではありません。非可逆圧縮したファイルをあとから可逆圧縮で保存しても、それ以前に失った情報は戻りません。編集を続ける資料では元のデータを残す、配布用には用途に合った容量を選ぶ、という使い分けにつながります。

連続回数と出現頻度は違う手がかりです

ランレングス法は、同じ値が連続するひとまとまりを、その値と連続回数で表す方法です。たとえば AAAABBBBCCCC は、組の順を「記号、回数」と決めれば、(A, 4)、(B, 4)、(C, 4) と表せます。このひとまとまりをランと呼びます。離れた場所に同じ記号があっても、途中に別の記号があれば別のランとして数えます。並び順を保存しなければ、元の列を復元できないためです。

ここで、紙に書いた A4 という2文字を見て、実際にも必ず2文字分の容量になると決めてはいけません。記号の表現に何ビット、回数の表現に何ビットを使うかを決めてから計算します。回数に使えるビット数には上限があるため、非常に長い連続を複数の組に分ける方式もあります。ランレングス法が得意なのは、同じ値が長く続くデータです。値が毎回変わると、各値に回数を付ける負担の方が大きくなります。

ハフマン法は、記号の出現頻度を使って符号を割り当てる可逆圧縮の方法です。よく出る記号を短い符号で表せるようにして、全体のビット数を小さくします。連続しているかではなく、全体で何回登場するかに着目する点がランレングス法と異なります。頻度が同じ記号に同じ長さの符号が付くとは限らず、頻度だけから符号そのものが一意に決まるわけでもありません。

ハフマン符号では、ある記号の符号が別の記号の符号の先頭部分にならないようにします。たとえば A を 0、B を 10、C を 110、D を 111 とすれば、左から読んで符号の終わりを判断できます。A を 0、B を 01 とすると、最初の 0 の時点で A なのか B の途中なのかを判断できず、この条件を満たしません。短い符号を自由に付ければよいのではなく、受け取る側が正しく区切れることが欠かせません。

実際の復号には、どの符号がどの記号に対応するかという情報も必要です。対応表をあらかじめ共有する場合も、圧縮データと一緒に保存する場合もあります。小さなデータでは、この付加情報の割合が大きくなります。計算問題では「対応表などの大きさを除く」といった条件を読んで、比較の範囲をそろえます。

誤り検出は確認用の情報を加えます

保存や伝送の途中で、ビットが 0 から 1、または 1 から 0 に変わることがあります。このような誤りに気づくため、元のデータから決めた確認用の値を付け加え、受け取った側でも同じ規則で調べます。規則に合わなければ、誤りがあるとわかります。しかし、規則に合うことだけで、元と完全に同じだと保証できるとは限りません。

パリティビットは、ビット列に付ける1ビットの確認用情報です。偶数パリティでは、データとパリティビットを合わせた 1 の個数を偶数にします。奇数パリティでは、合わせた 1 の個数を奇数にします。数えるのはビット列を数として読んだ値ではなく、並びの中にある 1 の個数です。通常の単純なパリティ検査だけでは、誤りがどの位置にあるかまでは特定できません。

チェックディジットは、番号などに付ける検査用の桁です。各桁から一定の計算で値を決め、入力された番号がその計算規則に合っているかを調べます。計算方式は用途によって異なり、桁ごとに重みを変える方式もあります。以下では、仕組みを追いやすいように、各桁の和を使う単純な規則を問題の条件として定めます。圧縮が表現の余分を減らすのに対し、誤り検出は検査に使う余分を意図的に加えるものです。

例題で解き方を確かめる

例題1　ランレングス法で容量を比較します

文字列 AAAABBBBCCCC を圧縮します。圧縮前は1文字8ビット、圧縮後は1組につき記号8ビットと回数4ビットを使います。回数は1から15まで表せるものとし、ほかの付加情報は考えません。圧縮後の容量と、圧縮後が圧縮前の何％になるかを求めます。

圧縮前の文字数を数えます。A、B、C が各4文字で合計12文字なので、12 × 8 = 96 ビットです。元の容量を先に出すと、比較の分母を間違えにくくなります。
連続する部分を分けます。(A, 4)、(B, 4)、(C, 4) の3組です。記号の種類だけでなく、実際に連続しているまとまりを数えるためです。
1組の容量を出します。8 + 4 = 12 ビットなので、圧縮後は 3 × 12 = 36 ビットです。回数を保存する領域も必ず含めます。
圧縮後を圧縮前で割ります。36 ÷ 96 × 100 = 37.5％です。削減した割合は 100 − 37.5 = 62.5％となり、問われた割合とは別の値です。

答え：圧縮後は36ビットで、圧縮前の37.5％になります。

図2のように、元の12文字は3組にまとまります。図の箱は文字や組を区別するためのもので、箱の横幅で容量比を示しているわけではありません。また、この例はビット単位の計算です。保存の仕組みでバイト境界にそろえる必要がある場合には、埋め合わせのビットが生じることもありますが、ここでは条件に含めません。

復元の規則を短い Python の例で確かめます。次のコードは、記号を回数だけ繰り返してつなぎます。ここで表示する組は考え方を表すためのもので、Python の変数自体が12ビットで保存されるという意味ではありません。

runs = [("A", 4), ("B", 4), ("C", 4)]
restored = "".join(symbol * count for symbol, count in runs)
print(restored)
print(len(restored))

出力は次のとおりです。

AAAABBBBCCCC
12

文字数だけでなく並びも元どおりです。同じ12文字でも ABCABCABCABC ならすべてのランが長さ1になるため、この条件では12組が必要で、12 × 12 = 144 ビットになります。圧縮方式の名前に「圧縮」と付いていても、すべての入力を必ず小さくできるわけではありません。

例題2　ハフマン符号の長さを求めます

A が8回、B が4回、C が2回、D が2回登場する16文字を考えます。4種類の文字を一律2ビットで表す場合と、A = 0、B = 10、C = 110、D = 111 で表す場合を比べます。対応表などの容量は除きます。また、符号列 010110111 を復号します。

一律2ビットの場合を求めます。16 × 2 = 32 ビットです。4種類は 00、01、10、11 の4通りに割り当てられるため、比較の基準を2ビットにできます。
符号の長さを読みます。A は1ビット、B は2ビット、C と D は3ビットです。文字数が同じでも1文字当たりの長さが異なるので、種類ごとに計算します。
出現回数を掛けて足します。8 × 1 + 4 × 2 + 2 × 3 + 2 × 3 = 28 ビットです。32 − 28 = 4 ビット減り、平均は 28 ÷ 16 = 1.75 ビットになります。
符号列を左から読みます。0、10、110、111 の順に区切れるので ABCD です。どの符号も別の符号の先頭部分ではないため、ここで区切ってよいと判断できます。

答え：一律なら32ビット、与えられた符号なら28ビットで、復号結果は ABCD です。

この符号は、ハフマン法で出現回数の小さいものから2つずつまとめて作れます。まず C の2回と D の2回を合わせて4回のまとまりにします。次にその4回と B の4回を合わせて8回にし、最後に A の8回と合わせます。各分岐に 0 と 1 を付け、根から各記号までの道順を符号にすると、上の割り当てが得られます。分岐の左右を交換すれば符号の数字は変わりますが、この例の符号長と合計ビット数は変わりません。

次のコードでも、頻度と符号長の積を足しています。len は長さを調べる操作です。平均1.75ビットとは、個々の文字を小数個のビットで表す意味ではなく、全体のビット数を文字数で割った値です。

freq = {"A": 8, "B": 4, "C": 2, "D": 2}
code = {"A": "0", "B": "10", "C": "110", "D": "111"}
bits = sum(freq[s] * len(code[s]) for s in freq)
print(bits)
print(bits / sum(freq.values()))

出力は次のとおりです。

28
1.75

例題3　偶数パリティで誤りを調べます

データ 1011001 の右端に偶数パリティのビットを付けます。その後、送信した列の左から3番目のビットだけが反転した場合に、誤りを検出できるかを求めます。ビットの追加や欠落はなく、指定の位置が反転するものとします。

元のデータの 1 を数えます。1、3、4、7番目にあるので4個です。7ビットという列の長さを数える計算とは区別します。
合計を偶数にするビットを選びます。すでに4個で偶数なので、付ける値は 0 です。送信列は 10110010 になります。
3番目を 1 から 0 に変えます。受信列は 10010010 となり、1 は3個です。奇数になったため、偶数パリティの規則から外れたとわかります。

答え：付けるビットは 0、送信列は 10110010 で、指定の1ビットの反転は検出できます。

次のコードの % 2 は、2で割った余りを求めます。1 の個数が偶数なら余りは0、奇数なら1なので、その値を追加すると全体が偶数になります。最後の True は、今回の受信列が偶数パリティの条件を満たしていないことを示します。

data = "1011001"
parity = str(data.count("1") % 2)
sent = data + parity
received = sent[:2] + "0" + sent[3:]
print(sent)
print(received)
print(received.count("1") % 2 != 0)

出力は次のとおりです。

10110010
10010010
True

例題4　チェックディジットを求めます

4桁の番号 4725 に、検査用の1桁を右端に付けます。規則は「検査用の桁を含めた各桁の和を10の倍数にする」です。検査用の桁には0から9の整数を使います。付ける値を求め、入力が 47269 に変わったときに検出できるか調べます。

元の各桁を足します。4 + 7 + 2 + 5 = 18 です。番号そのものを10で割るのではなく、各桁の和を計算するという規則を守ります。
次の10の倍数に届く不足分を求めます。20 − 18 = 2 なので、付ける値は2で、完成した番号は 47252 です。和がすでに10の倍数なら、付ける値は0です。
検査対象の各桁を足します。47269 は 4 + 7 + 2 + 6 + 9 = 28 で、10の倍数ではありません。元の番号を知らなくても、規則に合わない入力だと判断できます。

答え：チェックディジットは2、完成した番号は 47252 で、47269 の誤りは検出できます。

ここで検査に失敗しても、どの桁を直せばよいかは決まりません。複数の異なる番号が同じチェックディジットを持つため、確認用の1桁から元の4桁を逆算できるわけではないのです。番号を読み直すなど、検出した後の対応を別に考える必要があります。

つまずきやすいところと直し方

圧縮後の割合と削減した割合を取り違えます

誤った書き方は「96ビットから36ビットになったので、圧縮後は元の62.5％」です。どこが違うかというと、62.5％は減った60ビットを元の96ビットで割った割合です。残った36ビットの割合を問われているのに、減った量を分子にしています。

正しい書き方は「圧縮後は 36 ÷ 96 × 100 = 37.5％、削減した割合は 60 ÷ 96 × 100 = 62.5％」です。「圧縮率」という呼び方だけでは、資料によって比の取り方が異なる場合があります。問題に示された式や説明を優先し、答案では何を何で割ったかも示すと意味が明確になります。

可逆なら必ず小さくなると考えます

誤った書き方は「ランレングス法は可逆圧縮だから、どんな文字列でも容量を減らせる」です。どこが違うかというと、可逆は完全に復元できる性質であり、どの入力でも小さくなる性質ではありません。例題1と同じ保存条件で ABAB を扱えば、圧縮前は 4 × 8 = 32 ビット、圧縮後は 4 × 12 = 48 ビットになって増えます。

正しい書き方は「元の並びは完全に復元できるが、連続が短いと回数の保存分だけ増えることがある」です。すでに圧縮されたデータをもう一度圧縮しても、大きく減るとは限りません。また、非可逆圧縮の品質設定を高くして保存し直しても、失った細部が自動的に元へ戻るわけではありません。復元可能性、容量、見た目の品質を別の軸で考えます。

パリティが合えば正しいと断定します

誤った書き方は「受信した列の 1 が偶数個なので、誤りはない」です。どこが違うかというと、偶数個のビットが反転した場合には、1 の個数の偶奇が変わらないためです。図3のように、例題3の送信列で3番目と4番目を反転させると 10000010 になり、1 は2個のまま偶数です。内容は変わっていても、この検査では検出できません。

正しい書き方は「偶数パリティの条件を満たしているが、検出できない誤りが残る可能性がある」です。単純なパリティは、パリティビット自身を含む検査対象の列で奇数個のビットが反転すると検出でき、偶数個の反転は検出できません。図3の色付きの枠は反転した位置を示し、左の表示は誤りを検出できるかを示しています。

チェックディジットにも方式ごとの限界があります。例題4の単純な和の規則では、47252 の最初の2桁を交換した 74252 も和が20になるので検査を通ります。重みを付ける方式は桁の入れ替えへの検出能力を改善できますが、どの誤りを検出できるかは具体的な規則によります。誤り検出は誤り訂正とは異なり、暗号化や本人確認の代わりにもなりません。規則を知っている人がデータと検査値の両方を書き換えることも考えられるからです。

練習問題

練習1

文字列 AAAAAABB をランレングス法で表します。例題1と同じく、圧縮前は1文字8ビット、圧縮後は1組につき記号8ビットと回数4ビットとします。組の並び、圧縮前後の容量、圧縮後が圧縮前の何％かを求めてください。付加情報は考えません。

練習2

A = 0、B = 10、C = 110、D = 111 の符号を使います。文字列 ABACAD を符号化し、そのビット数を求めてください。また、得られた符号列を左から読み、元の文字列に戻ることを確認してください。対応表の容量は除きます。

練習3

データ 1100101 に偶数パリティビットを右端に付けてください。その送信列の左から1番目と2番目のビットが両方反転したとき、受信列を求め、単純な偶数パリティ検査で誤りを検出できるか説明してください。

練習4

4桁の番号 6381 に、各桁の和が検査用の桁を含めて10の倍数になるように1桁を付けてください。完成した番号の末尾の検査用の桁をそのままにして、元の4桁の部分を 6831 に入れ替えた場合、誤りを検出できるかも答えてください。

答えと解説

練習1の答えは、(A, 6)、(B, 2)、圧縮前64ビット、圧縮後24ビット、37.5％です。元は8文字なので 8 × 8 = 64、圧縮後は2組なので 2 × (8 + 4) = 24 です。割合は 24 ÷ 64 × 100 で求めます。記号の回数だけを足しても、圧縮後の容量にはなりません。

練習2の答えは 01001100111、11ビットです。0、10、0、110、0、111 とつなぐので、長さは 1 + 2 + 1 + 3 + 1 + 3 = 11 です。逆にこの順で区切ると ABACAD に戻ります。一律2ビットなら12ビットなので、ここではデータ本体が1ビット減っています。

練習3の答えは、付けるビットが0、送信列が 11001010、受信列が 00001010 で、検出できません。元の 1 は4個、受信列の 1 は2個で、どちらも偶数です。違う列なのに同じ検査結果になる具体例として、2本の列を並べて確かめてください。

練習4の答えは、チェックディジットが2、完成した番号が 63812 で、入れ替え後の 68312 の誤りは検出できません。6 + 3 + 8 + 1 = 18 なので2を加えます。足し算の順を変えても合計は変わらないため、この規則では桁の入れ替えを見つけられません。

次の単元へのつながりと家庭での確かめ方

圧縮は、画像や音を扱う情報デザインと、データを運ぶネットワークの両方につながります。送る量を減らした上で、通信のために確認用の情報を加えることは矛盾しません。必要な容量と確かめられる内容をそれぞれ考えることで、保存形式や通信の仕組みを理解しやすくなります。

家庭では、次の2つをそれぞれ5分ほどで試せます。1つ目は、紙に A と B だけで12文字の列を2本書き、よく連続する列と交互に並ぶ列でランの数を比べることです。例題1の保存条件で容量まで計算すれば、データの特徴と方式の相性を確かめられます。2つ目は、7ビットの列に偶数パリティを付け、別の紙に1か所変えた列と2か所変えた列を書いて、1 の個数を数え直すことです。

個別指導でこの計算が止まった場合は、割合の分母の選び方や、1ビットと1文字の違いまで戻って確かめます。計算が合っていても説明が曖昧なら、「検出できない誤りを1つ作れるか」を確かめると、規則の理解が見えます。保護者がお子さまと確認するときも、正解を急いで伝えるより、どの規則を使ったのかを言葉にしてもらうと途中の考えを追えます。