情報圧縮の問題

質問

情報科学の問題なのですが、分からないのでどなたかお助けください。

各日の天気は，それまでの天気と無関係に晴れが 80%, 雨が 20% の確率で起きるものと仮定する。
晴れを1，雨を0 とした時の1年間の天気を示した365ビットの列を， 3日分づつを塊にすることにより，より短い文字列に表現する方法を考えよ。
またその方法での，圧縮率を求めよ。

１１１、１１０、１０１、１００…と３日分ずつだと８種類の文字列のどれかになりますよね。
それを例えば１１１＝１というふうに表現する事に決めたりすればいいのでしょうか？

いまいちよく分からないのでお助けください。

回答No.1

R_Earl · ベストアンサー

> １１１、１１０、１０１、１００…と３日分ずつだと８種類の文字列のどれかになりますよね。
> それを例えば１１１＝１というふうに表現する事に決めたりすればいいのでしょうか？

そうですね。そんな感じです。
ただし、あとでちゃんと復号化できるようにしないとだめです。
例えば111に「1」を割り当て、110に「10」、101に「01」と割り当てたとします。
ここで111101を圧縮すると「101」となりますが、
これを復号化すると、111101と110111の2通りの解釈ができてしまいます。
こんなことが起きないように工夫する必要があります。

参考URL：

http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%95%E3%83%9E%E3%83%B3%E7%AC%A6%E5%8F%B7

補足

回答いただきありがとうございます。
なるほど、復号化まで考えないといけないのですね。

それでちょっと割り当てを考えてみたのですが
１１１…０
０１１、１０１、１１０…１００，１０１，１１０
００１，０１０，１００…１１１００，１１１０１，１１１１０
０００…１１１１１
というふうに考えたのですが、もっと短く出来るような割りふりがあるのでしょうか？

回答No.3

JaritenCat

> というふうに考えたのですが、もっと短く出来るような割りふりがあるのでしょうか？

000～111の8種類だとそれが最適ですね。
8種類を2個組み合わせて64種類にすると、ちょっとだけ平均圧縮率がよくなりますが・・・手作業では難しいでしょう。

回答No.2

Tacosan

見た感じはそれで最適っぽいです.
まじめにがんばるなら Huffman 符号を作る... のかな?