次のデータを効率的に圧縮したい

質問

次のデータを効率的に圧縮したい

いま、1000bitのデータが与えられていて、その内どこが１でどこが０か分かっている。
例えば、2bit目、5bit目、12bit目、21bit目、23bit目、25bit目、50bit目、200bit目が１で、
それ以外が０であるとわかっている。
このようなデータを効率的に可逆圧縮したいと考えています。

いま考えている方法として、
2bit目、5bit目、12bit目、21bit目、23bit目、25bit目、50bit目、200bit目が１なので、
横に並べて、251221232550200。

251221232550200
　↓（下表に従う）
001 1110 1000 1110 000001 1110 001000 1110 001010 1110 0011000 1110 10001101 1110 00111011101

こうして、1000bitが79bitに圧縮でき、復元も可能です。

しかし、問題は、
　☆１となるビットが多い場合、全然圧縮できないということ。
　☆元のデータが50bitくらいだと、あまり圧縮できない。
ということです。

もっと効率的な圧縮の方法や他に良い方法はないでしょうか？
知恵をお貸し下さい。
よろしくお願いします。

―――　表　―――――――――
1 ⇔ 000
2 ⇔ 001
3 ⇔ 010
4 ⇔ 011
5 ⇔ 1000
6 ⇔ 1010
7 ⇔ 1001
8 ⇔ 1011
9 ⇔ 1100
0 ⇔ 1101
& ⇔ 1110
（&は区切り文字）
――――――――――――――

回答No.3

kentarou2333 · ベストアンサー

ほとんどが 0 って事であれば、No2 さんのおっしゃるように 0 の続く個数を
エンコードするのがよいかと思います。

自分だったら、次のどちらかですかね。

0～7: 1XXX
8～39: 01XXXXX
40～167: 001XXXXXXX
168～679: 0001XXXXXXXXX
以下同様に、0 が一つ増えたら、その後の桁が 2 つ増える

0～3: 1XX
4～19: 01XXXX
20～83: 001XXXXXX
84～339: 0001XXXXXXXX
以下同様に、0 が一つ増えたら、その後の桁が 2 つ増える

先ほどのデータだと、No2 さんのように、1,2,6,8,1,1,24,149 を圧縮すればいいので

上だと
1-001 1-010 1-110 01-00000 1-001 1-001 01-10000 001-1101101
で、34bit

下だと、
1-01 1-10 01-0010 01-0100 1-01 1-01 001-000100 0001-01000001
で、33bit

になります。

1となるビットが多い場合があるんだったら、下の方がいいでしょうね。
下の方だったら全体の 1/4 ぐらいまでだったらなんとか圧縮できそうです。

結局は、No1 さんのおっしゃるように、元データの特性に合わせて、
圧縮する方式を考えるのが一番という事になるかとは思います。

補足

ご回答ありがとうございます。

３０bit前後に圧縮できるなら十分利用できそうですね。
とても参考になりました。ありがとうございます。

また、別の方法として、以下の記事のフィボナッチ数列を利用した符号化は
どうかと考えています。
（フィボナッチ数の性質で「すべての自然数は、隣接しないフィボナッチ数の
和の形で一意的にかける」というのがあるそうなので。）

フィボナッチ符号
http://ameblo.jp/316228/entry-10476109850.html

つまり、
2bit目、5bit目、12bit目、21bit目、23bit目、25bit目、50bit目、200bit目が１
⇒1,2,6,8,1,1,24,149
⇒12681124149（これをフィボナッチ符号で表す）
　※フィボナッチ数列はあらかじめ表として作っておく

しかし、フィボナッチ符号で表せても、数字の区切りをどう表したらよいかで悩んでいます。
また、桁数が大きすぎてオーバーフローするのではというのも問題です。

この方法で補足頂けるアイデアがございましたらご教示ください。
よろしくお願いします。

回答No.7

Mr_Holland

＞　対象とするデータは、時間によって変化する時系列のデータで、ある時間帯では、
＞　1 が多くなり、ある時間帯では、1 は数ビットのみとなるようなデータとなります。
＞　そのため、偏りが小さい平均的に圧縮率が大きい符号復号の方法を検討しています。

　時間帯によってデータの特徴が大きく異なるのであれば　次の方法が考えられます。

（Ａ）　最も長い時間現れるデータの特徴に適した圧縮方法をとる。
（Ｂ）　データの特徴によって圧縮方法を適宜変更する。（圧縮方法はデータに符号化して付加する。）

　また、これまでのところ時間帯別のデータを個別に圧縮することを考えておられるようですが、各ビットの時系列上の変化はどうなっているでしょうか。
　もし各ビットでの変化が少ないようでしたら、１つ前の時間帯のデータに対して変化したビットだけｆごうかするという方法もあります。

　可能でしたら　実際のデータの例を出してみませんか？
　ここの回答者さんたちでしたら　そのほうがより的確なアドバイスが得られるように思いますよ。
　いかがですか？

回答No.6

alice_44

＞ どんな符号化が効率的かは、
＞ どんなデータが、どんな頻度で現れるか次第です。

と書きましたが、御理解いただけなかったよですね。

＞ ある時間帯では、1 が多くなり、ある時間帯では、1 は数ビットのみとなるようなデータ

・ 1 が多い時間帯での 1 の多さは、最大どのくらいか。
・ 1 が多い時間帯と 0 が多い時間帯は、それぞれどのくらいの長さ続くのか。
・ 1 が多い時間帯と 0 が多い時間帯の、切り替わり方に何かパターンは無いか。
などなど…

もう少し具体化してゆかないと、何が効率的かは検討できません。
可逆符号による圧縮とは、要するに、予測しやすいデータに短い符号を割り当てる
ということなんですから。

回答No.5

alice_44

No.1 には、応答を頂けなかったようです。
書いておいたのですが、可逆圧縮で
どんな符号化が効率的かは、
どんなデータが、どんな頻度で現れるか次第です。
そこの補足がないとね。

0 の多いデータを想定した回答がありますが、
質問には、1 が多くなると圧縮率が落ちる
ことに悩んでいる件りがあるし…

実のところ、質問氏は何がしたいんでしょう？

補足

＞どんな符号化が効率的かは、どんなデータが、どんな頻度で現れるか次第です。
　対象とするデータは、時間によって変化する時系列のデータで、ある時間帯では、
　1 が多くなり、ある時間帯では、1 は数ビットのみとなるようなデータとなります。
　そのため、偏りが小さい平均的に圧縮率が大きい符号復号の方法を検討しています。

　そのような方法が難しいのは重々承知していますが、それでも何かよい方法がないか
　と考えている次第です。

回答No.4

kentarou2333

フィボナッチ符号の符号化の仕方は、数字の区切り方も含めて、
いただいた HP にありますので、詳しくはそちらを参照して
いただくとして。

フィボナッチ符号は、符号化が面倒なうえ、バイトの使用効率が
よくないです。

理想的な圧縮列は、0 と 1 がほぼ半々になりますが、
フィボナッチ符号は 0 が多いため、情報に偏りがあります。

ちなみに、先ほどの数列だと 50bit になりました。

って、さすがにそこまで差がつかないだろうと思ってみてみたら、
さっきの書き込みで、自分の圧縮列のビット数を数え間違えてますね、、、
さすがに、そこまで差はつきませんよね。
ちなみに、44bit と 45bit ですね。

補足

フィボナッチ符号は符号復号の計算時間、圧縮率からしてもあまりよくないですね。
また別の方法も考えてみます。

回答No.2

Mr_Holland

扱うデータの特徴によりけりです。
　ですので、小手先ですが質問者さんの方法を改善する案を提示します。

【改善案】「１」のあるビット目をそのまま１０進数で並べていますが、次の「１」までの「０」の個数を並べます。
　　　この方が１０進数の数値を小さくさせられるため　２進数に暗号化したときビット長は短くなります。
　　　質問者さんが提示されたデータの場合　次のようになります。
＞　　　2bit目、5bit目、12bit目、21bit目、23bit目、25bit目、50bit目、200bit目が１
　　　⇒1,2,6,8,1,1,24,149
　　　⇒000 1110 001 1110 1010 1110 1011 1110 000 1110 000 1110 001011 1110 0010111100　（６４ビット）

　　利点：「１」の個数が増えるほど次の「１」までの「０」の個数は減少し、１０進数の数値が小さくなるため　暗号化の効率が向上します。

補足

ご回答ありがとうございます。

次の「１」までの「０」の個数を並べる符号法もありですね。

新たにできないかと思う方法として、以下の記事のフィボナッチ数列を
利用した符号化はどうかと考えています。
（フィボナッチ数の性質で「すべての自然数は、隣接しないフィボナッチ数の
和の形で一意的にかける」というのがあるそうなので。）

フィボナッチ符号
http://ameblo.jp/316228/entry-10476109850.html

つまり、
2bit目、5bit目、12bit目、21bit目、23bit目、25bit目、50bit目、200bit目が１
⇒1,2,6,8,1,1,24,149
⇒12681124149（これをフィボナッチ符号で表す）
　※フィボナッチ数列はあらかじめ表として作っておく

しかし、フィボナッチ符号で表せても、数字の区切りをどう表したらよいかで悩んでいます。
また、桁数が大きすぎてオーバーフローするのではというのも問題です。

この方法で補足頂けるアイデアがございましたらご教示ください。
よろしくお願いします。

回答No.1

alice_44

可逆圧縮では、全ての場合にデータを小さくすることはできません。
全ての場合にデータが小さくなったら、それは情報量が減っている
ということですから、もと通りに復元できない場合が生じてしまいます。
ある場合にはデータが圧縮され、別の場合にはデーターが膨張するのが、
可逆圧縮の特徴です。
生データが表現し得る全てのデータを考えるのではなく、
出現頻度が高いデータに対して圧縮率が高くなるように、
圧縮方法をデザインしておくのです。
どんなデータの頻度が高いか、考察することから設計が始まります。