HSPTV!掲示板

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

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

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

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

考えることは同じようですねｗ
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倍以上遅くなります
なんででしょう…

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

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

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