アカウント名:
パスワード:
情報量的にはM77,232,917で表せちゃうものをZIPだと11.2MBも必要とするのか。最悪に近い圧縮率ですね。
#10進数の23,249,425桁の圧縮と考えればがんばってるのは承知の上で
しかしながら、それは10進数での話。2進数(バイナリ)ならばZIPで11,496バイト!更に、bzip2ではわずか47バイト!!(中身はほぼ0xFFなので(^^;))
むむ、これはメルセンヌ数だ!パラメタM77,232,917と圧縮できるぞ!はい、圧縮しました。というスーパー圧縮エンジンがそのうち出来ますよ!
そういう問題はチューリング完全じゃないかな?
チューリング完全という言葉が使いたかっただけなのはよくわかった。
すべてのプログラムを短い順に順次実行していって、M77,232,917を出力するプログラムだったらそれを出力して停止、とやればいいから、「そのうち」なんて言わずもうできたも同然。
# ただし速度は考えないものとする# 停止問題があるにも関わらず、この場合はちょっと工夫すれば問題ない(なぜかは考えてみよう)
もちろんアスキーコード表記でのテキストファイルだということは分かってますが、素数なのに圧縮できるってことが不思議な感覚です。
バイナリで考えると2の77,232,917乗-1ってことは77,232,917ビット。つまり10MiB未満。アスキーにして圧縮して11MBってのは割と納得できる感じじゃない?
2進表記のテキストを圧縮するとすごく圧縮できますよね。
数学詳しくないから素数の性質わかってないだけかも知れないけど、素数って絶対に圧縮不可なんだっけ?辞書圧縮とかでも?
素数は n までの自然数の中に確率 1/ln n で存在する「ありふれてない数」で低エントロピーだから圧縮率高いだろう。
メルセンヌ数の50番目という記述でいいので辞書圧縮だとヘッダ含めて数バイトで済むレベル。それにメリットがあるのかどうかは分かりません。
まれに圧縮率が高くなるが、ほとんどの場合圧縮できず、圧縮するにも素数判定しなきゃならず時間がかかる、そんな圧縮アルゴリズムになります。そんなのでよければ。
「n番目の素数」と記述すれば、常に圧縮できそうだが。
# ただし速度は考えないものとする。元コメも速度については何も言っていないし計算機科学者でない数学者は通常計算可能かどうか以上のことをあまり気にしないし
「素数の圧縮率」じゃ主語が大きすぎる上に定義も曖昧でほとんど何も言えない。たとえばメルセンヌ素数の2進数表記は明らかに圧縮率が極めて高いわけだが、一般の素数の任意n進数表記で言える話ではない。
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)に設定を変更する必要があります。
あつくて寝られない時はhackしろ! 386BSD(98)はそうやってつくられましたよ? -- あるハッカー
圧縮率 (スコア:1)
情報量的には
M77,232,917
で表せちゃうものをZIPだと11.2MBも必要とするのか。
最悪に近い圧縮率ですね。
#10進数の23,249,425桁の圧縮と考えればがんばってるのは承知の上で
Re:圧縮率 (スコア:1)
しかしながら、それは10進数での話。
2進数(バイナリ)ならばZIPで11,496バイト!
更に、bzip2ではわずか47バイト!!
(中身はほぼ0xFFなので(^^;))
Re: (スコア:0)
むむ、これはメルセンヌ数だ!
パラメタM77,232,917と圧縮できるぞ!
はい、圧縮しました。
というスーパー圧縮エンジンがそのうち出来ますよ!
Re: (スコア:0)
そういう問題はチューリング完全じゃないかな?
意味不明にもほどがある (スコア:0)
チューリング完全という言葉が使いたかっただけなのはよくわかった。
Re: (スコア:0)
Re: (スコア:0)
すべてのプログラムを短い順に順次実行していって、M77,232,917を出力するプログラムだったらそれを出力して停止、とやればいいから、「そのうち」なんて言わずもうできたも同然。
# ただし速度は考えないものとする
# 停止問題があるにも関わらず、この場合はちょっと工夫すれば問題ない(なぜかは考えてみよう)
Re: (スコア:0)
もちろんアスキーコード表記でのテキストファイルだということは分かってますが、
素数なのに圧縮できるってことが不思議な感覚です。
Re:圧縮率 (スコア:2, 興味深い)
バイナリで考えると2の77,232,917乗-1ってことは77,232,917ビット。
つまり10MiB未満。
アスキーにして圧縮して11MBってのは割と納得できる感じじゃない?
Re: (スコア:0)
2進表記のテキストを圧縮するとすごく圧縮できますよね。
Re: (スコア:0)
数学詳しくないから素数の性質わかってないだけかも知れないけど、素数って絶対に圧縮不可なんだっけ?
辞書圧縮とかでも?
Re: (スコア:0)
素数は n までの自然数の中に確率 1/ln n で存在する「ありふれてない数」で低エントロピーだから圧縮率高いだろう。
Re: (スコア:0)
メルセンヌ数の50番目という記述でいいので辞書圧縮だとヘッダ含めて数バイトで済むレベル。それにメリットがあるのかどうかは分かりません。
Re: (スコア:0)
まれに圧縮率が高くなるが、ほとんどの場合圧縮できず、圧縮するにも素数判定しなきゃならず時間がかかる、そんな圧縮アルゴリズムになります。そんなのでよければ。
Re: (スコア:0)
「n番目の素数」と記述すれば、常に圧縮できそうだが。
# ただし速度は考えないものとする。元コメも速度については何も言っていないし計算機科学者でない数学者は通常計算可能かどうか以上のことをあまり気にしないし
Re: (スコア:0)
「素数の圧縮率」じゃ主語が大きすぎる上に定義も曖昧でほとんど何も言えない。
たとえばメルセンヌ素数の2進数表記は明らかに圧縮率が極めて高いわけだが、一般の素数の任意n進数表記で言える話ではない。
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)
うーん、ハフマン符号も算術符号も基本的な考え方は「出現頻度によって符号長(算術符号の場合は区間の大きさ)を変えることにあって、使っている文字が少なければ短く表現できるのは結果論みたいなものですよね。
そのため出現頻度の偏りがほとんどない場合は事前に固定コードを割り振るのと同等にしかならないのにわざわざコード長を決めるための集計処理をするって無駄だなぁと思ってしまいます。
算術符号でも「ハフマンより多少はまし」なだけで、符号とは別に辞書データを持つ分サイズが増えるので非圧縮のバイナリ整数に勝てる見込みはまずないでしょう。
うじゃうじゃ