HSPポータル
サイトマップ お問い合わせ


HSPTV!掲示板


未解決 解決 停止 削除要請

2014
1229
FunnyMakerHuffman符号化2解決


FunnyMaker

リンク

2014/12/29(Mon) 17:44:57|NO.66705

今年もそろそろ終わりますねー。
年を越す前にちょっとcrasyなことをやってみました。標準命令だけを使ってのHuffman符号化です。
どうにか出来上がりましたが案の定、恐ろしく遅くなりました。
数百kbのファイルを符号化するのが関の山です。
セーブデータの圧縮くらいならなんとか...。(一旦符号化してヘッダを暗号化すれば簡単な「暗号化」に使えるかも?)
(当たり前ですがいつも圧縮できるとは限りません。偏りのないデータを符号化してもヘッダの分だけ膨らむだけです。)

http://www.mediafire.com/download/m3x9vb3rx3z9aw5/Huffman4hsp.zip

もはや殆どネタですが、興味のある方はどうぞ。エンコード/デコードのサンプルを付けています。(「EncDec.exe」)



この記事に返信する


kanahiron

リンク

2014/12/29(Mon) 20:47:39|NO.66707

2005年にMizki_Fさんがese-packという圧縮/解凍ソフトを作っていますね
その中に外部DLL不要でハフマン符号化できるモジュールが入っています
http://www.onionsoft.net/hsp/contest2005/list_n4.html

考えることは同じようですねw
2つの速度を比較するソースを書いてみました

#uselib "winmm.dll" #cfunc msec "timeGetTime" #include "mod_bitio.hsp" #include "mod_huffman.hsp" #include "Huffman4hsp.as" filename = "Huffman4hsp.as" s_time = 0 e_time = 0 encsize = 0 exist filename filesize = strsize sdim filedata,filesize+1 sdim encdata,filesize*2 sdim decdata,filesize+1 bload filename,filedata mes "入力ファイルサイズ " +filesize+"B" mes mes "mod_huffmanで符号化開始" init_huffman s_time = msec() h_encode encdata,filedata,filesize encsize = stat e_time = msec() mes " 出力ファイルサイズ " +encsize+"B" mes " 圧縮率 "+((1.0*encsize)/(1.0*filesize)*100)+"%" mes " 符号化にかかった時間 "+(e_time-s_time)+"ms" mes "mod_huffmanで復号開始" s_time = msec() h_decode decdata,encdata,filesize,encsize e_time = msec() mes " 復号にかかった時間 "+(e_time-s_time)+"ms" //初期化 sdim encdata,filesize*2 sdim decdata,filesize+1 s_time = 0 e_time = 0 encsize = 0 plabel = *label mes mes "Huffman4hspで符号化開始" s_time = msec() hfmn4hsp_enc filedata, filesize, encdata, plabel, 0x7FFFFFFF encsize = stat e_time = msec() mes " 出力ファイルサイズ " +encsize+"B" mes " 圧縮率 "+((1.0*encsize)/(1.0*filesize)*100)+"%" mes " 符号にかかった時間 "+(e_time-s_time)+"ms" mes "Huffman4hspで復号開始" s_time = msec() hfmn4hsp_dec encdata, decdata, plabel, 0x7FFFFFFF e_time = msec() mes " 復号にかかった時間 "+(e_time-s_time)+"ms" stop *label return
mod_huffman.hspは進捗をtitleで表示する機能がありますが計算部分を含めてコメントアウトしています

結果として、Huffman4hspがmod_huffmanと比較して符号化は2倍ほど早く、復号化が4倍ほど遅いようです
しかしそれは数百KBのデータの話で、数MBあるデータをHuffman4hspで復号化すると符号化に比べ10倍以上遅くなります
なんででしょう…



FunnyMaker

リンク

2014/12/29(Mon) 22:01:06|NO.66709

比較実験までして下さってありがとうございます。
符号化モジュールが9年前に作られていたとは...! いや〜、作る前に一度探してみるものですね。

全体的にMizki_Fさん圧勝ですねこれは。コード読みながらそう思いました。
ちゃんと文献読んで作ってたみたいですし...流石です。
(コード読んだだけじゃロジックがよく分からないなぁ..。符号化後データに可変長符号-固定長符号の対応テーブルが無いみたいだけど
どうやって元のコードを特定してるんだろ? 私は何か根本の理解が足りていないな。勉強せねば...。)

拙作モジュールの方で復号化が異様に遅い件ですが、1bit読む度に「可変長符号-8bit固定長符号対応テーブル」に検索をかけているのが原因だと考えています。(1bit読む度に最悪で256回の比較が発生しますから。)
多分この仕組み自体がマズいのだと思っています。
何というか...、状態遷移機械のようにジリジリと元符号を特定していく仕組が必要なのだろうなと考えています。(Mizki_Fさんの復号化処理を読んでいてそんな気がしました。)



ONION software Copyright 1997-2021(c) All rights reserved.