うさぎでもわかる情報理論　第2羽　符号化と一意復号可能・瞬時復号可能な符号

皆さんはパソコンやスマホなどのコンピュータ上で何事もなく、「日本語」や「アルファベット」などの文字を使ってやり取りしていますね。

しかし、コンピュータ上では0, 1の2進数のみで情報を記録されているのでしたね。言い換えると、「日本語」や「アルファベット」などの情報はそのままコンピュータ上で保存されているわけではなく、2進数に変換されて保存されています。

そこで今回は、コンピュータ上で情報を読み出したり書きだしたりする際に使われる符号化についてみていきましょう。

スポンサードリンク

1. 符号化とは

文字などの情報を2進数（0と1だけで表す）に置き換え、コンピュータ上で扱えるデータに変換することを符号化と言います。

例えば、「あ」・「い」・「う」・「え」の文字列を、下の2進数で置き換える（＝符号化する）ことにします。

ここで、置き換えた2進数（今回の場合は "00", "01", "10", "11"）のことを符号語と呼びます。

すると、文字列「あいうえ」は「00011011」と変換されます。

また、符号化された文字列を元の情報 (文字など) に戻すことを復号化と呼びます。

[解説]

符号化ルール

• A → 0
• B → 10
• C → 110
• D → 111

に従って、符号化・復号化をしていきましょう。

(1)

BDCA → 101111100

より、101111100と符号化できる。

(2)

11001111010 → CADBB

より、CADBBと復号化できる。

スポンサードリンク

2. 符号化のための条件

やみくもに符号化のルールを決めると、復号する際に

• 復号ができない
• 復号ができたとしても復号に時間がかかる

といった問題が発生します。

そこで、符号化の際には、下のルールを守って符号化をする必要があります。

[必須条件]

• 符号化した文字列を一意に復号できること
  → 一意復号可能な符号であること

[推奨条件] (満たしてなくてもいいけど満たして)

• 符号化した文字列を後戻りせず（かつ一意）に復号できること → 瞬時復号可能な符号
• 出来る限り短い符号 (0, 1) で符号化すること

(1) 一意復号可能な符号 [必須条件]

(i) 一意復号可能とは

一意復号可能な符号とは、符号化した文字列を復号した際にその結果が1通りだけになる符号のことを表します。言い換えて、「元の情報を符号化し、それを復号すると100%元の情報に戻るような符号」と思っていただいてもOKです。

符号化は、一意復号可能な符号で行うことが必須です。「符号化された情報を復号したら、元の情報と違うものが出てきた」なんてことがあったら困りますよね。

(ii) 一意復号可能な符号の条件

ある符号が一意復号可能であるかを瞬時に見分ける方法は基本的にはありません。
（ただし、元の文字列への戻し方が2パターン以上存在する符号列を1つでも見つけることができれば、一意復号不可能であることは確認できます。）

(ii) 一意復号不可能な符号の例

下の例の符号を考えてみましょう。

• あ → 0
• い → 01
• う → 001

この場合、出てくる符号語は "0", "01", "001" の3つですね。ここで、"0", "01" をそれぞれ復号化すると、

• 0 → あ
• 01 → い

の1通りだけ得られます。一方、"001" は復号化すると、下のように2つの復号結果が出てきてしまいます^[1]"001" を復号すると「あい」or「う」のどちらがわからなくなるということですね。。そのため、例1の符号は一意復号不可能です。

(2) 瞬時復号可能な符号 [推奨条件]

瞬時復号可能な符号とは、符号化した文字列を復号していく際に、後戻りせずに復号ができる符号のことを表します。言い換えて、「先頭から順番に見ていくだけで、復号ができる符号」と考えてもOKです。

(ii) 瞬時復号可能な符号の条件

一意復号のときと異なり、瞬時復号可能な符号は見分ける方法があります。

ある符号が瞬時復号可能であるかは、符号化した文字列を左から読んでいくだけで、後戻りせずに各符号語を判別できるような符号化ルールをつかって符号化をする必要がありますね。

ここで、後戻りしないと各符号語を判別できない（＝瞬時復号不可能な）符号を見ていきましょう。

例えば下の符号化ルールの場合、「0」が出てきたときは、次の文字を先読みしないと「あ → 0」か「い → 01」のどちらかが確定できません。

もう少し詳しく符号化ルールを見ていくと、 01の頭部分には、「あ → 0」の0が含まれていますね。そのため、「い → 01」を復号する際に冒頭の1文字目0を読んだだけでは、「あ → 0」なのか、「い → 01」に出てくる0なのかがわかりません。

これを言い換えると、瞬時復号可能かどうかは符号化ルールに出てくるどの符号語に対しても、頭部分に自身以外の符号語が出てこないかどうかで判定ができますね。

(iii) 例で確認

例1) 瞬時復号不可能な符号

「い」の符号化ルールにおいて、「い → 01」のように、頭部分に「あ → 0」の0が含まれているため、瞬時復号不可能。

例2) 瞬時復号可能な符号

「あ → 0」：他の符号化ルールに出てくる符号 10, 11 の頭部分に0は出てこないのでOK
「い → 10」：「あ → 0」の符号は1文字、「う → 11」の符号は2文字と、自身の符号の文字数(2文字) 以下なのでOK。

より瞬時復号可能。

※ 各符号を確認する際は、自身の符号の文字数以下のものは「頭文字に来ることがないことが明らか」なため、確認を省略できます^[2] … Continue reading。

スポンサードリンク

3. 練習問題

それでは、実際に「一意復号可能な符号」、「瞬時復号可能な符号」の判定法が理解できているかを練習問題で確認しましょう。

[略解]

(1)

[解説]

(1): 瞬時復号可能

まずは、瞬時復号可能な符号かどうかの判定。

「あ → 00」、「い → 01」、「う → 10」、「え → 00」いずれも2文字の符号語である。

よって、完全一致しない限り自身以外の符号語の接頭語となる符号は存在しない。

よって、瞬時復号可能である。

(2): 瞬時復号可能ではない

「あ → 0」については、他の符号語 10, 11, 101 の接頭語になっていないためOK。

しかし、「い → 10」については、「え → 101」の符号 101 の接頭語になってしまっているため、瞬時復号可能な符号ではない。

(3): 瞬時復号可能ではない

「あ → 0」については、「え → 010」の符号語 010 の接頭語になっていないためNG。よって、瞬時復号可能な符号ではない。

4. さいごに

今回は、コンピュータ上で文字などの情報を扱う際に使われる符号化について学んでいきました。

最後に、一意復号可能な符号と瞬時復号可能な符号の関係を図にて、確認しておきましょう。

次回からは、実際に符号化する際に使われるハフマン符号やシャノンファノ符号についてみていきたいと思います。

[余談1] 符号化と文字コード

コンピュータをよく使う人や、情報系の人なら文字コード（ASCIIコード、Unicode、Shift-JISなど）というのを聞いたことがあると思います。この文字コードというのは、「どの符号化のルールが適用されているか」というのを表しています。

例えば、ASCIIコードであれば、各種文字とその符号（16進数に変換して記載している）は下のようになります。

[余談2] 符号化と文字化け

実際にWebサイトやドキュメントなどを見ていて、「文字化け」に出会ったことはありませんか？

実は、文字化けというのは「Webサイトやドキュメントを作成する際のコード設定」と「閲覧時の文字コード設定」がそろっていないために発生する現象なのです。