高校情報I 可変長符号の復号—短い符号の割当てと区切りの一意性を表で確かめる｜武蔵野個別指導塾

展示記号の符号表を比べ、ビット数と復号を調べます。区切りの衝突を防ぐ鍵は接頭語です。

よくあるのは、高校生が展示の案内に使う記号の列を短く保存しようとし、よく出る記号に短い符号を与えれば区切りは考えなくてよいと思う場面です。符号を隙間なく並べると、どこまでが1個分かという情報も必要です。短さと読み戻せることを別々に調べ、記録した列から元の記号列に戻してみましょう。

問題で求められる判断

出方の1つは、与えられた符号表と記号列から、保存するビット列と総ビット数を求める問題です。記号ごとの符号を順番に連結し、長さを数えます。出現回数が示されている場合は、各記号の回数と符号長の積を足しても同じ長さになるはずです。ただし、回数だけでは元の並び順は決まりません。列そのものを求めるときは、順番を使います。

別の出方は、区切りを書かないビット列を表に従って復号する問題です。先頭からビットを読み、符号が確定する場所を探します。表に問題がある場合は、もっともらしい読み方を1つ出すだけでは足りません。同じ列を2通りに分けられる具体例があれば、一意に復号できないことを示せます。

さらに、2つの表の総ビット数を比べ、表の安全な区切りと長さの両方を説明する問題があります。どちらが短いかは出現回数に依存します。表そのものを記録する費用などが指定されていないときは、記号列を表したビット数に範囲を限って比べます。

先頭の重なりと復号木

符号は、記号と0・1の列を対応させたものです。記号によって符号の長さが異なれば可変長符号です。長さが同じ固定長符号では、決められた桁数ごとに切れます。可変長では、長さを固定して切ることができないため、表の作り方を確かめます。

ある符号が別の符号の先頭部分になることを、ここでは接頭語になると呼びます。例えば0と01を別の記号に割り当てると、01を読んだとき、0で区切る可能性と01まで読む可能性が生まれます。実際に残りも符号として読めるかどうかは表全体で調べます。先頭の重なりを見つけただけで、必ず複数の復号結果があると断定してはいけません。

どの符号も別の符号の接頭語にならない表なら、先頭から読んで初めて符号に一致した場所で区切れます。その符号を延長した別の符号は存在しないためです。区切った後は残りの先頭から同じ操作を繰り返します。これを接頭語を持たない符号と考えます。

図1のように、根から0と1の枝をたどり、記号の置かれた終点に着いたら記号を出して根に戻ると、区切りを視覚的に追えます。枝の途中に記号を置かず、終点にだけ記号を置いた木では、ある符号が別の符号の先頭になることを避けられます。

図1ではAが0、Bが10、Cが11です。例えば10はBに着きます。最初の1は途中の分岐なので、そこで記号を出さず次の0まで読みます。0を読んだ場合はすぐAが確定し、次のビットは新しい記号のために根から読みます。

接頭語を持たないことは、区切りなく左から確定できるための十分な条件です。逆に、接頭語がある表でも列全体を見れば一意に復号できる場合はあります。したがって「接頭語がある」と「必ず一意に復号できない」は同じ意味ではありません。ここで使う比較用の表は、確実に区切れるように接頭語を持たない形にします。

表と列が正しく届くことも前提です。未登録の枝へ進む列や途中で終わる列は、完成した記号列として扱えません。途中のビットが別の値に変わった場合、たまたま別の有効な列になってしまうこともあります。接頭語を持たないことだけでは、そのような誤りを必ず検出できません。

基本例題：展示記号を2つの表で表す

展示の順路を示す記号列をA、B、A、C、A、Bとします。次の表はこの問題のために作った対応です。区切り文字や表自体の保存分は数えず、符号を連結したビット列と総ビット数をそれぞれ答えてください。表Pと表Qは次のとおりです。

図2のように、表PではAを0、Bを10、Cを11に置き換えます。表Pも表Qも、1ビットの符号はほかの符号の先頭にならず、2ビット同士も異なります。そのため、どちらも先頭から区切れます。

表Pでは順に0、10、0、11、0、10です。これをつなぐと010011010で、9ビットです。先頭から0、10、0、11、0、10と切り直すと、A、B、A、C、A、Bに戻ります。区切りを紙に書いて確認しましたが、記録する列には区切り文字を含めていません。

表Qでは順に10、0、10、11、10、0です。つなぐと1001011100で、10ビットです。10、0、10、11、10、0と復号すれば同じ記号列に戻ります。短くなったのは表Pで、差は1ビットです。

回数からも確かめます。Aは3回、Bは2回、Cは1回です。表Pは3×1 + 2×2 + 1×2で9ビット、表Qは3×2 + 2×1 + 1×2で10ビットです。よく出るAが表Pでは短いので、この列では差が生じます。一方、Bがもっと多い別の列では、Bに短い符号を与えた表Qのほうが短くなることもあります。

符号を連結して数える方法と回数から求める方法は、互いの確認になります。ただし両方で同じ符号表を読み違えることはあります。最後に連結した列を元の記号へ戻し、順番と個数まで確かめると、区切りの取り違えも見つけやすくなります。

標準例題：出現回数を変える

同じ表Pと表Qを使い、別の展示列ではAが2回、Bが5回、Cが3回現れるとします。順序は指定されていません。区切り文字と表の保存分を除き、それぞれの総ビット数と短い表を答えてください。

表Pは2×1 + 5×2 + 3×2で18ビットです。表Qは2×2 + 5×1 + 3×2で15ビットです。今回は表Qが3ビット短くなります。AとBの回数の大小が基本例題と逆になったため、短い符号を多く使う表も変わりました。

順序は何通りもあるので、連結された列を1つに決めることはできません。検算として、条件を満たす列をA、A、B、B、B、B、B、C、C、Cと置きます。表Pでは0を2個、10を5個、11を3個連結し、表Qでは10を2個、0を5個、11を3個連結します。いずれも各部分を逆にたどれば、指定した10個の記号と各回数に戻ります。総ビット数は順序を入れ替えても変わりません。

表の読み取りで大切なのは、記号の種類数だけで長さを比べないことです。表Pと表Qにはそれぞれ長さ1の符号が1個、長さ2の符号が2個あります。それでも、短い符号に対応する記号の回数が違えば、記録全体の長さは違います。符号長の一覧と出現回数の一覧を記号名で結んでから掛け算をします。

発展例題：区切りを保証できる表へ直す

自作の表RをAに0、Bに01、Cに1とします。区切りを含めずに記録した01を、この表で記号列に戻してください。また、3記号の表を、Aの符号0を残したまま接頭語を持たない表へ直し、01という列の扱いも答えてください。

表Rでは01をBと読む方法と、0と1に分けてA、Cと読む方法があります。どちらも同じビット列を作るため、元の記号列を1つに決められません。出現回数や記号数が別途与えられていないという条件の下では、Bと決め打ちすることはできません。

修正例はAを0、Bを10、Cを11にする表Pです。0は10や11の先頭ではなく、10と11も互いに先頭ではありません。01は0をAとして読んだ後、残る1が枝の途中です。この列は表Pで完成した記号列にはならず、途中で途切れた列として扱います。無理にBやCを付け足してはいけません。

この修正では表Rで記録したデータを、そのまま新しい表Pで読めるとは限りません。符号の対応を変えたからです。旧表で元の列を一意に戻せない記録は、新表への変換も元の列を別途確認しなければ決まりません。新たに記録する際には、同じ表を読む側と共有してから符号化します。

誤答を原因まで戻す

図3の表Rで、01をBとだけ読んで終える誤答を考えます。01がBの符号であること自体は正しいものの、0と1に分けたA、Cという読み方を調べていません。短い符号を先に見つける方法と、長い符号を優先する方法は、表に接頭語の重なりがあると同じ答えを保証しません。

図3のように2つの読み方をそれぞれ符号化し、どちらも01へ戻ることを示せば、区切りの衝突が具体的に確認できます。読み方を1つ見つけることと、ほかの読み方がないと示すことは別の作業です。

別の誤りは、記号ごとの符号長を足す際に、出現回数を掛けないことです。例えば基本例題の表Pで1 + 2 + 2とすると、各種類を1回ずつ数えた5ビットにしかなりません。実際の列は6記号です。表の横に回数を書き、回数の合計が列の記号数に合うことも確かめます。

また、復号の途中で列が終わっているのに、最後の分岐を勝手に補う誤りもあります。表Pで末尾が1だけなら、次が0か1かでBとCが変わります。列の途中までに確定した記号と、未完成の末尾を分けて報告します。記録途中で止まったのか、入力時に削れたのかは列だけでは判定できません。

表の一部にない記号が入力された場合も、既存の符号を代用してはいけません。新しい表を定めるか、表を共有している相手に確認する必要があります。表を変更すると過去の記録の読み方にも影響するため、どの表を使った記録か区別して管理します。

練習問題

以下の表Sと表Tは、この練習のために作ったものです。各符号は0と1からなり、区切り文字は保存しません。問題ごとに指示した形で答えてください。

1. 表SでX、Z、Y、X、Zを符号化し、区切りのないビット列と総ビット数を答えてください。答えから元の列にも戻してください。
2. 表Tで011100を復号し、記号を順に答えてください。復号後に再び符号化し、元のビット列と照合してください。
3. Xが4回、Yが3回、Zが2回の列について、表Sと表Tそれぞれの総ビット数と差を答えてください。表と区切りの保存分は含めません。
4. 別の表UをXが0、Yが01、Zが1とします。ビット列010を2通りの記号列に復号し、両方を符号化し直してください。記号数の事前指定はありません。
5. 表Sを使って列101を受け取りました。確定できる記号と未完成の部分を答え、完成した記号列にするために末尾へ1ビットを補う場合の候補をそれぞれ示してください。補う前の列を勝手に完成扱いしないでください。

練習の答えと道筋

1. 表Sでは0、11、10、0、11なので、連結した列は01110011、8ビットです。0、11、10、0、11と読み直すとX、Z、Y、X、Zに戻ります。長さも1 + 2 + 2 + 1 + 2で8です。

2. 表Tで0、11、10、0と切るため、Y、X、Z、Yです。各記号を0、11、10、0へ戻すと011100となり、与えられた6ビットと一致します。最初の0を読んだ時点でYが確定し、次の1から新たに読み始める点が区切りの要です。

3. 表Sは4×1 + 3×2 + 2×2で14ビットです。表Tは4×2 + 3×1 + 2×2で15ビットです。表Sが1ビット短くなります。例えばXを4個、Yを3個、Zを2個並べた列を作れば、どちらの表でも復号後にXが4個、Yが3個、Zが2個に戻ります。順序は指定されていないので、特定のビット列は答えに必要ありません。

4. 01、0と切ればY、Xです。0、1、0と切ればX、Z、Xです。前者を符号化すると01と0で010、後者も0と1と0で010です。異なる2つの記号列が同じ列に対応するので、表Uではこの入力の元の列を一意に決められません。

5. はじめの10はYで、残る1は未完成です。末尾に0を補うと10、10となりY、Yです。1を補うと10、11となりY、Zです。元の101はどちらとも確定できず、追加したビットが何だったかを受け取った列だけで決めることもできません。再符号化するとそれぞれ1010、1011となり、どちらも元の101を先頭に含みます。

覚えておくこと

• 接頭語を持たない表なら、先頭から符号に一致するたびに区切れます。
• 総ビット数は各記号の出現回数と符号長の積の合計です。
• 比較後は実際に復号し、元の記号の順序と個数を確かめます。
• 曖昧な区切りや途中で終わる列は、根拠なく補いません。

どこで迷ったかを見分ける

答えの長さが合わないときは、まず記号ごとの回数の合計と、列にある記号の数を比べます。長さは合うのに復号結果が違う場合は、置換の順序と根に戻る位置を紙に書き込むと、最初にずれた箇所が見えます。個別指導では、本人が符号表のどの行を使い、どのビットで1記号が確定したと判断したかを確かめます。短さの比較と区切りの確認を別々に説明できれば、条件が変わった問題にも判断を移せます。