【2ch】圧縮アルゴリズム【オリジナル】
■ このスレッドは過去ログ倉庫に格納されています
0001１
NGNG中途半端に圧縮されて拡張子が.2ch
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うわー、おっかなーい。藁
0153デフォルトの名無しさん
NGNGはいはい。怖い怖い。
ぶるぶる〜
藁
0154
NGNG0155デフォルトの名無しさん
NGNG0156デフォルトの名無しさん
NGNG151と152と153を同一フレーズに圧縮したら非可逆になっちまうだろうが。
まあ展開結果は「クソレス3件」だけでも構わんがな。
0157デフォルトの名無しさん
NGNG真面目に考えんなＹＯ。
つーか思いついた。
２ｃｈ語を特定の数字に置き換えんの。
1,オマエモナー 2,ＹＯ 3,逝ってよし 4,１よ 5,藁・・・・・（２ｃｈ語続く）
だれか作ってくださいお願いします。,5,
0158デフォルトの名無しさん
NGNG>>95
0159デフォルトの名無しさん
NGNG特定の文字を数字にしたら
今度は数字を符号化しないといけなくなるじゃん。
0160不マジレス
NGNGそれ以外は原文字のままで１バイトずつ。
で、それら８個集めて別のフラグバイトにどっちかを示すビットを立てていく。
0161デフォルトの名無しさん
NGNG全部 9bits にするぐらいなら予約語を escape した方が縮むんじゃ…
よっぽど頻繁に出てくればともかく、平文が 9/8 に膨らむと大きそう。
0162デフォルトの名無しさん
NGNGお前は自作自演を見破れないのか？
0163がいしゅつだったらｽﾏｿ
NGNGただし、ファイルの先頭より前の部分に2chで頻出する文脈を詰めておき、
そこを初期のスライド窓の位置とする。
圧縮・展開ソフトが固定データを持ってなきゃいけないのが重大な欠点か。
0164デフォルトの名無しさん
NGNG0165デフォルトの名無しさん
NGNG. |（･∀･）|
. |￣￣￣ ｼﾞｻｸｼﾞｴﾝ共和国
△
△ｌ |
＿＿△|_.田 |△＿＿＿＿＿
|__|__門_|__|＿＿＿＿＿|＿＿＿＿＿
0166デフォルトの名無しさん
NGNG0167デフォルトの名無しさん
NGNG圧縮時はその時点での 2ch から頻度表作って詰めて、
展開時には初期の辞書で置き換えられた部分は無視するの。
…無視するなら、圧縮前に削除しちゃった方がいいか…
0168デフォルトの名無しさん
NGNG0169デフォルトの名無しさん
NGNG圧縮アルゴリズムを発見（発明）した時、
特許とかの申請はどういう風になるんですか？
0170デフォルトの名無しさん
NGNG0171デフォルトの名無しさん
NGNG0173デフォルトの名無しさん
NGNG「情報処理」にソフトウェアやアルゴリズムの特許についての話が連載中。読め。
0174デフォルトの名無しさん
NGNG0175
NGNGそんなことも知らない奴には発明なんて無理
0176デフォルトの名無しさん
NGNG0177デフォルトの名無しさん
NGNGとりあえず2chにアルゴリズムをＵＰ汁。そして各所からリンクを張られろ。
どこかの香具師が勝手に特許とっても申請前に既に一般に知られていれば
特許を無効にできると思われ。
0178デフォルトの名無しさん
NGNG. |（･∀･）|
. |￣￣￣ ｼﾞｻｸｼﾞｴﾝ民主主義人民共和国
△
△ｌ |
＿＿△|_.田 |△＿＿＿＿＿
|__|__門_|__|＿＿＿＿＿|＿＿＿＿＿
0179デフォルトの名無しさん
NGNG>>とりあえず2chにアルゴリズムをＵＰ汁。
これが一番危険と思うんですよね
２ｃｈに書き込んだのはすべて２ｃｈのものってことになってますから。
まずどっかのサーバーにウプした時点で著作権だけは保持できるはずなんですので
そのあとここに書き込むかもしれません。（まぁ無理かな、いちをおテスト中です）
0180177
NGNG＞２ｃｈに書き込んだのはすべて２ｃｈのものってことになってますから。
そうなのか、知らなかったよ。
じゃあジオとかを避けて適当にＵＰしてそのＵＲＬを2chに晒すのがいい鴨な。
以前、会社でＰＧやってる香具師が、退職時に自分の作ったコードを
自由に使えるようにする為に、会社で使う前に自分のＨＰにＵＰしてた
という話を聞いたことがあるよ。
0181デフォルトの名無しさん
NGNGんなわけねーだろ。というわけで晒しあげ。
0182デフォルトの名無しさん
NGNG0183デフォルトの名無しさん
NGNG■ このスレッドは過去ログ倉庫に格納されています