アカウント名:
パスワード:
情報量的にはM77,232,917で表せちゃうものをZIPだと11.2MBも必要とするのか。最悪に近い圧縮率ですね。
＃10進数の23,249,425桁の圧縮と考えればがんばってるのは承知の上で
ZIPファイルは 10.6MiB で、これを展開すると 22.6MiB くらい。（1KiB = 1024Bytes として）だから半分くらいには圧縮できたって感じ。
ZIPってハフマンコード＋ランレングス圧縮だったけ。多分、ハフマンコードの時点で1文字あたり平均4bit未満に圧縮されただろうから（数字0～9しか使われてないし）だとするとランレングスではほぼ圧縮できてない、って事でいいのかな。
乱数列として面白く使えたりするんだろうか。検定のやり方とかさっぱり知らんけど。でも「あ、この数列はM77232917だな」とバレちゃうとアカンから、セキュアでは無い。。。
ZIPはハフマン＋スライド辞書です。この場合は似たようなものですが。ハフマンの方も「一文字あたり8ビットだけど実際には10種類しか使ってない」ことによるもので、出現頻度にはあまり偏りがないと思われるのでコード長は3ビットか4ビット。
別コメントにあるように「これは素数である」という前提を使える方法でないと、整数を単純にバイナリ表現したものより小さく圧縮することは難しそう。
100桁毎に改行(CR+LF)が入ってますので、使用文字は12種類ですね。全部で23,714,413Bytesで、CRとLFはそれぞれ232,494個ハフマン符号化で数字5個に3bit、数字5個に4bit、CR+LF(辞書に100バイト前から2バイトマッチ)に5bit割り当てると、全部で82.5Mbit=9.84MiByteぐらいですので、ZIP圧縮におけるスライド辞書はほとんど役に立たず、シンボル数の少なさによるハフマン圧縮だけが効いてる感じですかね。
「スライド辞書が役に立たない」=「シンボル間の相関が見つからない」以上、これ以上はどうしようもなさそう。算術符号などのシンボルに対して小数ビットを割り当てることができる方法をつかえばもうちょい減らすことはできるでしょうけで、まー誤差レベルですかね。
うーん、ハフマン符号も算術符号も基本的な考え方は「出現頻度によって符号長(算術符号の場合は区間の大きさ)を変えることにあって、使っている文字が少なければ短く表現できるのは結果論みたいなものですよね。そのため出現頻度の偏りがほとんどない場合は事前に固定コードを割り振るのと同等にしかならないのにわざわざコード長を決めるための集計処理をするって無駄だなぁと思ってしまいます。
算術符号でも「ハフマンより多少はまし」なだけで、符号とは別に辞書データを持つ分サイズが増えるので非圧縮のバイナリ整数に勝てる見込みはまずないでしょう。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
皆さんもソースを読むときに、行と行の間を読むような気持ちで見てほしい -- あるハッカー
圧縮率 (スコア:1)
情報量的には
M77,232,917
で表せちゃうものをZIPだと11.2MBも必要とするのか。
最悪に近い圧縮率ですね。
＃10進数の23,249,425桁の圧縮と考えればがんばってるのは承知の上で
Re: (スコア:0)
ZIPファイルは 10.6MiB で、これを展開すると 22.6MiB くらい。（1KiB = 1024Bytes として）
だから半分くらいには圧縮できたって感じ。
ZIPってハフマンコード＋ランレングス圧縮だったけ。
多分、ハフマンコードの時点で1文字あたり平均4bit未満に圧縮されただろうから（数字0～9しか使われてないし）
だとするとランレングスではほぼ圧縮できてない、って事でいいのかな。
乱数列として面白く使えたりするんだろうか。検定のやり方とかさっぱり知らんけど。
でも「あ、この数列はM77232917だな」とバレちゃうとアカンから、セキュアでは無い。。。
Re:圧縮率 (スコア:1)
ZIPはハフマン＋スライド辞書です。この場合は似たようなものですが。
ハフマンの方も「一文字あたり8ビットだけど実際には10種類しか使ってない」ことによるもので、出現頻度にはあまり偏りがないと思われるのでコード長は3ビットか4ビット。
別コメントにあるように「これは素数である」という前提を使える方法でないと、整数を単純にバイナリ表現したものより小さく圧縮することは難しそう。
うじゃうじゃ
Re:圧縮率 (スコア:1)
100桁毎に改行(CR+LF)が入ってますので、使用文字は12種類ですね。
全部で23,714,413Bytesで、CRとLFはそれぞれ232,494個
ハフマン符号化で数字5個に3bit、数字5個に4bit、CR+LF(辞書に100バイト前から2バイトマッチ)に5bit割り当てると、
全部で82.5Mbit=9.84MiByteぐらいですので、
ZIP圧縮におけるスライド辞書はほとんど役に立たず、シンボル数の少なさによるハフマン圧縮だけが効いてる感じですかね。
「スライド辞書が役に立たない」=「シンボル間の相関が見つからない」以上、これ以上はどうしようもなさそう。算術符号などのシンボルに対して小数ビットを割り当てることができる方法をつかえばもうちょい減らすことはできるでしょうけで、まー誤差レベルですかね。
Re:圧縮率 (スコア:1)
うーん、ハフマン符号も算術符号も基本的な考え方は「出現頻度によって符号長(算術符号の場合は区間の大きさ)を変えることにあって、使っている文字が少なければ短く表現できるのは結果論みたいなものですよね。
そのため出現頻度の偏りがほとんどない場合は事前に固定コードを割り振るのと同等にしかならないのにわざわざコード長を決めるための集計処理をするって無駄だなぁと思ってしまいます。
算術符号でも「ハフマンより多少はまし」なだけで、符号とは別に辞書データを持つ分サイズが増えるので非圧縮のバイナリ整数に勝てる見込みはまずないでしょう。
うじゃうじゃ