はじめに

情報理論における最大のテーマは圧縮と誤り訂正でした。
それでは、符号理論の基礎である語頭符号について学んでいきましょう。

符号についての概要

符号化とは送りたい文字列を0と1で表現することでした。例えば、

a	b	c
0	10	11

を使って「abc」を符号化すると「01011」になります。これを復号化すると「abc」に戻りますね。では、次の場合はどうでしょうか？

a	b	c
0	1	01

「abc」の符号は「0101」になりますね。これを復号化してみてください。結果は「abc」と「abab」と「cab」と「cc」になってしまうんです。このように符号空間の設計によっては復号化で失敗してしまうことがあります。これを解決するために語頭符号を学んでいきましょう。

語頭符号とは

記号の符号の先頭が他の符号語と同じでない符号空間のことを指します。例えば上の2つ目の符号空間では aの0 が cの01 の先頭となっているので、語頭符号でないです。他にも「0101」と「010110」のような場合でも語頭符号でない例です。
一方、上の1つ目の符号空間は語頭符号です。

メリット

語頭符号のメリットは必ず復号結果が一つに定まるということです。せっかく送ったデータの復号結果が複数あったら困りますよね。

例えば、上の1つ目の符号空間は語頭符号です。

一方、上の2つ目の符号空間では aの0 が cの01 の先頭となっているので、語頭符号でないです。
他にも「0101」と「010110」のような場合でも語頭符号でない例です。

演習問題

1. 次の関数を作りなさい。

任意の符号空間で文字列を符号化する関数

入力: 符号化する文字列, 記号列, 符号列
出力: 符号化した文字列

例

入力: 'abc', ['a','b','c'], ['0','10','11']
出力: '01011'

2. 次の関数を作りなさい。

語頭符号な任意の符号空間で文字列を復号化する関数

入力: 復号化する文字列, 記号列, 符号列
出力: 復号化した文字列

例

入力: '01011', ['a','b','c'], ['0','10','11']
出力: 'abc'

3. 次の関数を作りなさい。(めっちゃむずい)

任意の符号空間で文字列を復号化する関数

入力: 復号化する文字列, 記号列, 符号列
出力: 復号化した文字列の配列

例

入力: '0101', ['a','b','c'], ['0','1','01']
出力: ['abab','abc','cab','cc']

解説

1, 2

おそらく簡単な問題だったと思います。基本的に左から文字を置き換えていくだけでできる問題でした。また、復号化に関しても語頭符号を条件としているので複雑な処理は不要でした。それでは答えを見ていきましょう。

次のコードではstartとendの範囲にある文字列がsymbolsの入っている時、対応する符号語に置き換えています。その後startの位置を更新して同じことを繰り返していきます。

encode.py

def encode(text, symbols, signs):
   result = ''
   start = 0
   end = 0
   length = len(text)
   while end <= length:
      if (text[start:end + 1] in symbols): 
         result += signs[symbols.index(text[start:end + 1])]
         start = end + 1
         end = start
      else:
         end += 1
   return result

decode.py

def decode(text, symbols, signs):
   result = ''
   start = 0
   end = 0
   length = len(text)
   while end <= length:
      if (text[start:end + 1] in signs):
         result += symbols[signs.index(text[start:end + 1])]
         start = end + 1
         end = start
      else:
         end += 1
   return result

3

この問題の難しさは結果が複数存在してしまうことです。語頭符号の良さがわかると思います。それでは答えを見ていきましょう。

次のコードは再帰処理を用いて、もし一致する文字列があればそれ以降の文字列を同じ関数に実行し、また、そうであってもそうでなかったとしても文字の長さを一文字増やして同じことをしていくという構想です。もし、最後の処理で一致するものがなければそのまま破棄されます。

decode_super.py

def decode_super(text, symbols, signs, instance = '' ,stack=[]):
    end = 0
    length = len(text)
    if length <= 0:
        stack.append(instance)
    while end < length:
        if (text[0:end+1] in signs):
            decode_super(text[end+1:], symbols, signs, instance + symbols[signs.index(text[0:end+1])], stack)
        end += 1
    return stack

次のステップ

次の講義では符号の木を使っていきましょう。とてもとても超超めちゃめちゃ大事な手法なので、是非トライしてみてください。