【2ch】圧縮アルゴリズム【オリジナル】
■ このスレッドは過去ログ倉庫に格納されています
0001１
NGNG中途半端に圧縮されて拡張子が.2ch
0031デフォルトの名無しさん
NGNGピクセル単位で命懸けてるAA職人に失礼かと。
0033デフォルトの名無しさん
NGNG>>32
うん。俺職人じゃないけど、モナ板住人なんで。
0034デフォルトの名無しさん
NGNG0035デフォルトの名無しさん
NGNGそれは圧縮とは言わない。
0036デフォルトの名無しさん
NGNGお馬 さん
0037デフォルトの名無しさん
NGNGhttp://pc3.2ch.net/test/read.cgi/tech/1028570486
0038デフォルトの名無しさん
NGNGまで圧縮できないか？
0039デフォルトの名無しさん
NGNGtech/1028570486までは逝ける。
1028570486はlong intで表現できるからtech(4byte)。
tech等はテーブルを持ってindexは1byteで表現しちまおう。
よって、このスレは5byteで表現できる。
0040デフォルトの名無しさん
NGNG0041デフォルトの名無しさん
NGNG0042デフォルトの名無しさん
NGNGこれで、少なくとも 2ch に存在するAAなら7byteで表現化農家
0043デフォルトの名無しさん
NGNG0044デフォルトの名無しさん
NGNG0045デフォルトの名無しさん
NGNGオススメあったら教えて。
馬鹿でもなんとなくわかる本希望で
0046デフォルトの名無しさん
NGNGCマガの先月（7月）号
0047デフォルトの名無しさん
NGNG素直にデータ圧縮ハンドブック読んでおくのがいいかと。
0048デフォルトの名無しさん
NGNG英語でも良いなら
Kluwer Academic Publishers "Compression and coding algorithms"
がおすすめ。
日本語は参考になる本が少ないからな〜
データ圧縮ハンドブック と C MAGAZINE 以外には、
文書データ圧縮アルゴリズム入門くらいしかないが、絶版だし。
そもそも、圧縮自体が研究が進みすぎて下火になっているという罠。
画像圧縮の方は盛んだけどな。
何か画期的な圧縮法を>>45が発明することを期待する。
0049デフォルトの名無しさん
NGNG0050デフォルトの名無しさん
NGNG0051デフォルトの名無しさん
NGNGその方が、圧縮率が悪くなりそうだよ。
基本パターンやカッコなどの対応をあらかじめ学習しておくのがAA向きか。
0052デフォルトの名無しさん
NGNG0053デフォルトの名無しさん
NGNG小さいサイズのAAなら職人技が光るけど、
大きいサイズだとツールを使ったものも多いよね。
0054開発者 ◆GODLHAg2
NGNG0055デフォルトの名無しさん
NGNG0056デフォルトの名無しさん
NGNGああ特許の件で何も影響力が無かったカスか、まあいらっしゃい
0057デフォルトの名無しさん
NGNGいっそのことマイナーな圧縮アルゴリズム使ってみないか？
おれはBPEぐらいしか知らんが。
0058デフォルトの名無しさん
NGNG0059デフォルトの名無しさん
NGNG0060デフォルトの名無しさん
NGNGかなり圧縮できそう。
006158
NGNGJPEG圧縮ﾌﾟﾙグラムを作ろうとしたがやはり無理か。
006458
NGNG鬱出汁脳。
0065デフォルトの名無しさん
NGNG([ISOと圧縮対象ファイル]の[同じデータ]を探してISOのデータアドレスをアーカイブに書く)
回答時はネットに接続して、ISO参照の部分だけISOから抜き取って解凍。
DQNだと思われなら無視なされて結構です。
0066デフォルトの名無しさん
NGNGなに言ってんだかさっぱりだけど
恒常性の無いデータなんか
使いモンにならんぞなモシ
0067デフォルトの名無しさん
NGNGDQN
どうせなら辞書鯖用意して巨大共通辞書ファイル置くってのはどうか。
0068デフォルトの名無しさん
NGNGそのISOファイルへのポインタが消費するバイト数 ＞
ISOファイルを利用することによって節約できるバイト数
になる予感。
006967
NGNG･巨大鯖
･クライアント
･高速回線
ユーザがファイル圧縮を選択するとファイル内容が巨大鯖に転送されます。
……書いてて面倒くさくなってきたので続きはTHComp参照。
案外実現できそうな気がしない？
0070デフォルトの名無しさん
NGNG昔導き出された結論はこうだ・・・
「インデックスのサイズが圧縮元のサイズと同じになる」
0071デフォルトの名無しさん
NGNG１８GBに収まるってのがあった
この辞書を各クライアントが持つってのはどうかな？
当時は夢の容量だったから、だからどうしたレベルだったけど今ならいけそうだね
0072デフォルトの名無しさん
NGNG0073デフォルトの名無しさん
NGNGBPEって特許からむのかな。
Cマガの記事は読んでないのでよく知らないけど、
セクションサイズを可変にするのはダメ？
255種類のByteが出現するまで読み込んで、
その中で最も多いペアを出現していない残りの１種類のByteに置き換える。
セクションのデリミタとしてもう1Byte予約しておかないとダメか。
007457
NGNG俺もCマガの記事は読んだこと無いけどBPEの作者は特許取らない
ような事を言ってたらしいよ。
たしかBPEでは200種のByteが出てくるまで読みこんで(これを１ブロックとする)
その中から最多頻度のペアから順次残りの56種に割り当てて
圧縮していって圧縮が効かなくなるか256種使いきるまでやって
ペア表(軽く圧縮)・ブロックサイズ・圧縮データの組を順次出力してたと思う。
BPEが実際に使われた例は1しか知らないな。(除自作プログラム)
0075デフォルトの名無しさん
NGNGなるほど。そもそもブロックサイズは固定じゃなかったのか。
適当に前処理すれば圧縮率上がりそうな感じするね。
007657
NGNGブロックソーティング→ランレングス圧縮→BPE(Byte Pair Encoding)
※ランレングス圧縮を間にはさむのは、ブロックソートすると同値の連続が多くなり、
それをそのままBPEするとその連続の個所で無駄にペアが消費されるから。
でも本当に圧縮率が上がるかどうかは不明(汗
0077デフォルトの名無しさん
NGNGそれをやるなら普通に BWT→MTF→BPE なのかな。
BPEってもっと効率の良いブロックサイズを決定する方法がある気がする。
007857
NGNG>RLE→BPE は太るよね。
あ、RLEでビット単位の操作が入るようなのだとBPEは効きにくくなるな。
テキスト専用の圧縮にするなら0x00を長さ表示の開始コードに割り当てれば
実際の圧縮の場合は問題無いかも。
#それとも、まだ勘違いしてる？
>それをやるなら普通に BWT→MTF→BPE なのかな。
あと、ここ↓の2.14.15をみるとBWT→MTFよりMTF→BWTの方がいいみたい。
http://www.ingnet.or.jp/~kojif/mu/comp/bwt.htm
>BPEってもっと効率の良いブロックサイズを決定する方法がある気がする。
このへんは良い方法思いつかないな。
以前自分で作った(拾ったコードを改変した)やつではデフォルトのパラメータ使ってたし。
0079デフォルトの名無しさん
NGNGBWT→RLEの時点で、前後のByte同士の関連は無くなってると思っただけです。
> あと、ここ↓の2.14.15をみるとBWT→MTFよりMTF→BWTの方がいいみたい。
「２．１４．５ メモ」のこと？
そこに書いてある“MWT”ってのは何なのかわかんないけど、
BWT→MTFよりMTF→BWTの方がいいという意味では無いと思いますよ。
そこに書いてあるのは、BWT後のデータを効率よく圧縮する方法として、
まずMTFで0（ゼロ）を増やしてからZero-Runをかけると良いってな意味かと。
0080デフォルトの名無しさん
NGNG0081デフォルトの名無しさん
NGNG現在、世界中のサーバに格納されているテキスト文書を
URIの形をインデックスの表現とすると考える。
このURIリストを圧縮することで、世界中の文書を圧縮できたと仮定する
これは、実際は間違いだが、下限値を記述することにはなる。
4億のサーバがあると仮定。各サーバが10文書持つと仮定。
URIの長さがIPアドレスの長さ4byteの2倍程度に圧縮できると仮定。
4億×10×8 = 29.8 GByte
結論： 18GBではとても無理だ！
0082デフォルトの名無しさん
NGNGまあ10年前なら18GBを楽に割りそう
ネット環境の発達が文書量のインフレを加速してますな
0083デフォルトの名無しさん
NGNGMTFかけただけならサイズは増えないだろ。
0084デフォルトの名無しさん
NGNGBWT->MTF->... よりも MTF->BWT->... の方が大きくなる場合が多いってことでは？
008557
NGNGおれはMWTってのをBWTの誤植って解釈してた。
多分MTFのMとBWTのWTが混ざったんじゃないかな。
>84
Cで簡単なコード書いて試してみた。
Cのコード自身にそれぞれの変換をした結果をLZH(lh5)で圧縮して圧縮率を見たら
無変換 41.1%
BWT->MTF 14.1%
MTF->BWT 19.2%
になった。
使い方
a.exe option input output
option
b BWT->MTF
m MTF->BWT
制限
入力ファイルは65536Byte以下
動作確認
CYGWIN_98-4.10 名無し 1.3.12(0.54/3/2) 2002-07-06 02:16 i686 unknown
gcc version 2.95.3-5 (cygwin special)
コンパイル
gcc bwt_mtf.c -o bwt_mtf -Wall -O6
※30分で書いたコードだから間違いあるかも。
↓ソースをLZH圧縮＆uuencodeしたもの。
begin-base64 644 bwt_mtf.lzh
RQAtbGg1LU4CAACbBQAA1hRpPSAC4ApNCwABQnd0TXRmLmMbAEGgjeqRXkzC
AQBPDntdTMIBAJhjFUhMwgEFAAALyAAAAe5ju9Gmo75yQ9/7tJtbThwBMeDB
SR8CyMi+dkITS23rjql7ht6hlYfG7//u60AIrFY+Bi5gNG0271oTJrrlPmqX
KhXp1Z7tzr4IqUJ8vsjl1ojYju3DproD63bgB7/V8IQyd/fjyGu3N+UliErB
Evn41I+lvePcvxko2PSKTUsNqkShBEYOXaN9ojSdddKQoPQTgLJGawOfEP3k
JSaoqYCFHi4hBULEJKLEdwK1O8hMp/PQMSaSe3Jo65iRQYtLEbIvZFIMNdnz
eFhBnxgEaYLZei68xLzXEwTKpeRDgygjMxOPC9edCRFJQajTCHYUBoaf72vT
pjha7kh+VSqVtkI1hcP6qZk6wPmsqt0PQ/h9Uw6sgTQTBfDDzgR1fKulaKFz
f6tC4o9Z9GLvycaomCfhXKT8xCLf0iBoMyJOUKf+VpIWSzlb1JsnY2TuIZ+L
WMNzPNJp9MMISPhHSeL4ufN/KlE7kguM/oERfK/1Ctp3uxoDg0mB3LCPKd/L
ykbAIFJ/atlSWiJCXi4RU+UhnZawD02ujL2e33esIEJ2GCBVa/vmJwrg7DZ2
JkzxCOYMb9hvhdYIQuEaS7DpJi26MQx11Ux9TY9IFFcNE5SzmMGExbxlfbY1
hmk1qqO87uxz3IXJqeZGw0JswYiqOHbR2+AdzMQb+ccrQg7m0jLFJg/w1cBm
6H4SW2faIxtERa7+cQW0R/T5+ya0RlPNFXrX4NTiKyqBKl6h8ftovxp9bcob
E86h4yqHusqHNupQs9tPm7ci5c6fu78cGMFmDAAA
====
0086デフォルトの名無しさん
NGNG> おれはMWTってのをBWTの誤植って解釈してた。
大丈夫、大抵の奴はそう思うから。
MTF->BWTの逆にするとサイズが大きくなるのは有名な話だとおもてた。
少なくとも圧縮に関する研究や職業ならMTFがどういうものか知てるので。
0087デフォルトの名無しさん
NGNG有名な話だと思ってたってことはどっかに解説でもある？
検索してもBWT->MTFしかでてこない。
むしろ↑これが有効なことの方が有名な気がする。
MTFがどういうものかってのは…まんまの認識じゃあまいってことなのか
MTF程度にどうもこうもないと思うんだが（煽りとちゃいますよ）
0088デフォルトの名無しさん
NGNGttp://www.hn.is.uec.ac.jp/~arimura/compression_papers.html
にリストアップされてるような論文が理解できないとだめだよね。
ttp://www.ingnet.or.jp/~kojif/mu/comp/bwt.htm
あたりの入門用の解説を読んでもたいしたことは書いてない。
0089デフォルトの名無しさん
NGNG本体はでかくなるが。
0090デフォルトの名無しさん
NGNG0091デフォルトの名無しさん
NGNG0092デフォルトの名無しさん
NGNG0093デフォルトの名無しさん
NGNG登録すれば宜しいか｡
0094デフォルトの名無しさん
NGNGそれが本当なら今すぐ特許を取れ。
0095デフォルトの名無しさん
NGNG実際そんなに使われていない罠
009657
NGNGそれを初期状態とした動的ハフマン使ったら結構圧縮きくかも。
# 眠い頭で考えたからツッコミ歓迎。
0097デフォルトの名無しさん
NGNG全てのファイルを1バイト以下にできるということだな？
0098デフォルトの名無しさん
NGNGすべてのファイルを1ビット未満にできると！？
0099デフォルトの名無しさん
NGNG1ビット未満ってことは0だな？
それはさておき，少し前にランダムデータに対して圧縮できるって話出てたけど
あれはどうなったんだろう。
0100デフォルトの名無しさん
NGNG1ビット未満は即0ではないのだが・・・まぁいいや。
再帰的に繰り返せば同じことだから。
＞それはさておき，少し前にランダムデータに対して圧縮できるって話出てたけど
消えたのではなかろうか。
http://www.zeosync.com/ が404エラーになる。
0101デフォルトの名無しさん
NGNG無知で申し訳無いんだが，今のコンピュータでビットより高い分解能の単位は表現できるの？
（日本語おかしいかも知れんが許してくれ）
0102デフォルトの名無しさん
NGNG0103デフォルトの名無しさん
NGNGあ，要するに
7ビット中に10個のファイルの内容を格納する
という意味でつね？納得しますた。
0104デフォルトの名無しさん
NGNGまぁ算術符号なんかは実直にその概念を実装したものなわけだ。小数ビットの。
一方、ZLなんかも見た目は違うけど、実態は同じ。
0105デフォルトの名無しさん
NGNG誤解してるのかもしれないが、何故動的ハフマンを使う必要が・・。
別にストリームで圧縮するわけじゃないでしょ？
0106デフォルトの名無しさん
NGNGもの凄く処理時間がかかって現段階では実用にならない
アルゴリズムってあるの？
0107デフォルトの名無しさん
NGNG全てのファイルが1〜十数バイトになるってのが昔あったよ（ｗ
0108デフォルトの名無しさん
NGNG円周率圧縮
0110デフォルトの名無しさん
NGNGこの宇宙で存在しうる全てのデータにインデックスを付けるとしても、せいぜい256bitもあれば十分です
は真でも、全てのデータを256bitに圧縮出来るというのは別の話です。
よく勘違いする人がいるので気をつけましょう
0111デフォルトの名無しさん
NGNG円周率の数列から目的のデータを検索して
その出現位置でデータを表すってこと？
0112デフォルトの名無しさん
NGNGそれとの差分のみを圧縮すればいいだろ？
シャノンの情報理論に基づきデータの偏りを均一化するんだ。
0113105
NGNG0114デフォルトの名無しさん
NGNG初期状態のハフマンコード表を作るって言ってるんで、それは違うんじゃない？
あくまで推測ですが、動的ハフマンなら出現頻度の偏りの変化に追従できるから
高圧縮になると考えているのではないかと思われ。
0115デフォルトの名無しさん
NGNGMTF程度にどうもこうもないと思うんだが（煽りとちゃいますよ）
0116デフォルトの名無しさん
NGNGあと復号方法も考慮に入れてません(アカシックレコードが必要)
0117デフォルトの名無しさん
NGNGMTFは情報源の特性（無記憶とか定常とか）によって左右されるから気をつける。
最近、EffrosらによってBWTの冗長度が理論的に証明されたけど、
そこではMTFについてかなり細かく（実はそうでもないが）分析がされてたよ。
0118デフォルトの名無しさん
NGNG0119デフォルトの名無しさん
NGNG0120デフォルトの名無しさん
NGNG0121デフォルトの名無しさん
NGNGif (assyukuPattern == 0) {
int i;
while(searchPI(i++))
;
} else {
int j;
long sosuu;
while((long = getSosuu(j++)) != 0)
int i;
while(searchExp(i++, Sosuu)
;
}
put("ok");
}
private: getSosuu() {
//preaseWrite
}
private: searchPI() {
//preaseWrite
}
private: searchExp() {
//preaseWrite
}
0122デフォルトの名無しさん
NGNG圧縮可能だったら、圧縮するんだよ。無理ならやらなければいい。
それにたとえ確立が低くても、LZHやZIPが圧縮できたら神だろ？
0123デフォルトの名無しさん
NGNG素数は http://pc3.2ch.net/test/read.cgi/tech/1018657457/ に頼め
0124デフォルトの名無しさん
NGNGlong searchBit(bit* data, long assyukuPattern)
//とにかく探す
int i;
if (assyukuPattern == 0) {
searchPI(i++);
} else {
searchExpSosuu(&data, i++, assyukuPattern)
}
return i;
}
long searchPI(bit* data, long offset) {
//PIを検索する
}
long searchExpSosuu(bit* data, long offset, long sosuuno) {
//expSosuuを検索する
}
long expSosuu(long n) {
//getSosuuで取得した素数を(1/2)乗し、PIと同じく無限小数化する
}
long getSosuu(long n) {
//n番目の素数を返す(もちろんテーブルを引く)
}
0125デフォルトの名無しさん
NGNG0126デフォルトの名無しさん
NGNG> それにたとえ確率が低くても、LZHやZIPが圧縮できたら神だろ？
限りなく低いので却下
0127デフォルトの名無しさん
NGNGいや、だから初期状態のテーブルはプログラム側でもって、圧縮したファイルには
入れないんでしょう。
0128デフォルトの名無しさん
NGNG0129デフォルトの名無しさん
NGNGPPMZとかで再圧縮した方がはるかに縮みそうだ。
>>128
URR って「万能数値表現法」のこと？
ちょっと資料読んでみたけど、算術符号や、（二分）木による数値圧縮法、
などが近い考えなのではないかとふとおもた。
■ このスレッドは過去ログ倉庫に格納されています