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

スポンサードリンク

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

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

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

スポンサードリンク

1. 符号化とは

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

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

2進数置き換えルールと呼ぶことにしますか

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

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

符号化の例

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

復号化の例

例題

アルファベットのA~Dを次のように符号化する。

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

このとき、(1), (2)の問いに答えなさい。

(1) 文字列「BDCA」を符号化しなさい。
(2) 「11001111010」を復号化しなさい。

[解説]

符号化ルール

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

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

(1)

BDCA101111100

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

(2)

11001111010CADBB

より、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

一意復号可能な符号と瞬時復号可能な符号

[一意復号可能な符号の判定]

基本的に瞬時に見分ける方法はない。地道に試して2通り以上の復号パターンが得られるか確認するしかない。

(1つでも2通り以上復号パターンが得られる場合は、一意復号不可能)

[瞬時復号可能な符号の判定法]

符号化ルール内にあるどの文字(情報)を符号化しても、頭部分に自分以外の符号語が出てこなければOK。

(符号語を確認する際には、各符号化ルールの中から符号語の文字数が少ない順に行うことをおすすめします。また、自身の符号の文字数以下のものは確認を省略できます。)

瞬時復号可能な符号は必ず一意復号可能な符号となるため、 瞬時復号可能な符号を満たすことを確認できれば一意復号可能な符号かどうかは確認しなくても一意復号可能であることを確認できる

スポンサードリンク

3. 練習問題

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

練習問題

次の(1)~(3)の符号のうち、瞬時可能な符号は(1), (2), (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進数に変換して記載している)は下のようになります。

f:id:momoyama1192:20190731112523g:plain

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

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

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

文字化けの例

注釈

注釈
1 "001" を復号すると「」or「」のどちらがわからなくなるということですね。
2 例えば「0の頭部分は10ですか?」と聞かれても絶対違うじゃん、となりますよね。また、同じ文字数の場合は完全一致していない場合は100%頭部分は異なるため、こちらもチェックしなくてOK。

関連広告・スポンサードリンク

おすすめの記事