【2ch】圧縮アルゴリズム【オリジナル】
■ このスレッドは過去ログ倉庫に格納されています
0001１
NGNG中途半端に圧縮されて拡張子が.2ch
0053デフォルトの名無しさん
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 って「万能数値表現法」のこと？
ちょっと資料読んでみたけど、算術符号や、（二分）木による数値圧縮法、
などが近い考えなのではないかとふとおもた。
0130デフォルトの名無しさん
NGNG0131デフォルトの名無しさん
NGNG圧縮可能ならと言ってるが、その情報を付加するんだから情報量は基本的に増える
ことになるんだよ。円周率やら素数やら増やせば増やすほどな
それらのパターンを増やし、全ての情報パターンを表せるようになったときに
圧縮前のデータとおなじビット数が必要になることに気がつくんだよ（藁
くだらんこと言ってないで確率統計でもやってろ痴呆
0132デフォルトの名無しさん
NGNG0133デフォルトの名無しさん
NGNG0134デフォルトの名無しさん
NGNGネタにマジレスするなよ…
0135デフォルトの名無しさん
NGNGオマエモナー
0136デフォルトの名無しさん
NGNGあとがんばっても５％も減らないだろ
0137デフォルトの名無しさん
NGNGでも、BWTはアレを無視した手法強引にエントロピーを低下させてるんでしょ？
0138デフォルトの名無しさん
NGNG圧縮くわしくないけどさ
とくに2chのログなんてかなり省略できると思う
↑を圧縮
非可逆圧縮でよくない？
圧縮ｼﾗﾈｰﾖ
特に2chのログﾅﾝﾃｶﾅﾘ省略ﾃﾞｷﾙｻ
0139デフォルトの名無しさん
NGNG下のやつを展開するとどうなるんですか？
0140デフォルトの名無しさん
NGNG人工無能を搭載してありがちな反応を数パターン予測して、
その中から一致するパターンがあればそのパターン番号を出力、
失敗したら通常の圧縮って手もあるな。
つまり、擬似コードで書くとこんな感じな。
void 圧縮(前ﾚｽ, レス) {
array= 人工無能(前レス);
for(i=0; i< array.size; i++) {
if(レス== array[i]) {
出力(i);
(・∀・)ｶｴﾚ!;
}
}
出力(予測ｼﾊﾟｰｲ);
出力(通常圧縮(レス));
(・∀・)ｶｴﾚ!;
}
0141デフォルトの名無しさん
NGNGこの場合，圧縮率の高いスレは内容の少ない糞スレである確率が高い．
0142デフォルトの名無しさん
NGNG原文と一緒に圧縮して何%圧縮出来たかで 作者が同一か判定するというのがあったけど
圧縮率でクソスレ率を出すのも面白いかもね。
0143デフォルトの名無しさん
NGNGﾜﾗﾀ。むちゃくちゃ言うなよ。
エントロピーとエントロピーレートは似て非なるもの。
0144思いつきおとこ
NGNGを
「とてつちたそせすしさこけくきかおえういあ」
の反対と見るようなロジックってありました？
0145デフォルトの名無しさん
NGNGつーかlzhでいいです。
0146デフォルトの名無しさん
NGNGよくないです・・・・・lzhが拡張子だと、デフォルトではunlhaの方に渡されちゃうよ。
0147デフォルトの名無しさん
NGNGそりゃ環境依存だ。うちではlzhには何の関連付けもしていない。
unixだと関係ないしな〜
0148デフォルトの名無しさん
NGNGまぁ結局そうなんですが、やはり.lzhは避けた方がいいのでは。
負荷がかかりまくるでしょうが。
単純にhttp://をEsc文字 <a href= を \
アラーム文字 とかでいいと思うんだけどなー
0150デフォルトの名無しさん
NGNGあふぉだな
そんなくだらんことしないでgzipしたほうが圧縮率あがるんだよヴォケ
殆どgzipで転送してんだからくだらん加工してサーバーに余計な負荷かけるな史ね
0151デフォルトの名無しさん
NGNG0152デフォルトの名無しさん
NGNGうわー、おっかなーい。藁
■ このスレッドは過去ログ倉庫に格納されています