Erlangとハフマン符号 (2)

前回の続きです。

decodeを改良しようとして失敗した記録です。特に使うあてがあるわけではありませんが、もうちょっと高速化するあてはないもんかと思いました。

なんとなく1ビットずつマッチさせてるのが非効率な感じがしました。ビット列→1バイトの変換表はハフマン木が決まれば作れるわけで、それを元に、たとえば下記のような関数を作れば一度に複数ビットをマッチングできるのでいいのではないかと思いました。

fun
    (<<0:1, Rem/bitstring>>) -> {<<65:8>>, Rem};
    (<<2:2, Rem/bitstring>>) -> {<<67:8>>, Rem};
    (<<3:2, Rem/bitstring>>) -> {<<66:8>>, Rem}
end.

まず、文字列で上記のような関数を組み立てて、それをevalして無名関数にしたてあげてみることにします。

make_fun(Tree) ->
    List = get_encodelist(Tree),
    Expression = 
	lists:map(
	  fun({X, Bits}) ->
		  Exp = string:strip(
			  string:strip(
			    lists:flatten(io_lib:format("~p", [Bits])),
			    left, $<), right, $>),
		  io_lib:format("(<<~s, Rem/bitstring>>) -> {<<~p:8>>, Rem}",
			    [Exp, X])
	  end, List),
    Source = 
	lists:flatten(
	  io_lib:format("fun~n~s~nend.", [string:join(Expression, ";\n")])),
    {ok, Tokens, _} = erl_scan:string(Source),
    {ok, [Expr]} = erl_parse:parse_exprs(Tokens),
    {value, F, _} = erl_eval:expr(Expr, erl_eval:bindings(erl_eval:new_bindings())),
    F.

get_encodelist/1 は、encodeの時に作った関数です。それを元に各ビット列→バイトをマッチさせる関数を作成し、evalさせます。

あとはdecodeを少しいじって順次呼ぶようにすれば完成です。

decode2({Tree, Bin}) -> decode2(Tree, Bin).
decode2(Tree, Bin) ->
    decode2(make_fun(Tree), Bin, <<>>).

decode2(_F, <<>>, Res) -> Res;
decode2(F, Bin, Res) -> 
    {B, Rem} = F(Bin),
    decode2(F, Rem, <<Res/binary, B/binary>>).

では早速動かしてみましょう。

Input = <<"ABCABA">>.
<<"ABCABA">>
63> {Tree, Compressed} = huffman:encode(Input).
{{[{65,3},{[{67,1},{66,2}],3}],6},<<115,0:1>>}
64> D = huffman:decode(Tree, Compressed).
<<"ABCABA">>
65> D = huffman:decode2(Tree, Compressed).
<<"ABCABA">>
66> 

いけてるようです。もうちょっとでかいファイルを圧縮してみます。

68> {ok, Input} = file:read_file("huffman.erl").
{ok,<<"-module(huffman).\r\n-compile(export_all).\r\n\r\nmake_frqtbl(Bin) ->\r\n    Tmp =\r\n\tlists:foldl(\r\n\t  fun(B, Ary) ->"...>>}
69> {Tree, Compressed} = huffman:encode(Input).
{{[{[{[{[{[{62,62},{108,62}],124},{44,126}],250},
       {[{[{[{125,31},{123,31}],62},
(中略)
  2727},
 <<52,180,173,216,113,165,14,213,84,185,38,195,55,177,186,
   36,183,84,14,55,28,29,38,17,214,64,133,...>>}
70> D = huffman:decode(Tree, Compressed).
<<"-module(huffman).\r\n-compile(export_all).\r\n\r\nmake_frqtbl(Bin) ->\r\n    Tmp =\r\n\tlists:foldl(\r\n\t  fun(B, Ary) ->\r\n\t\t  ar"...>>
71> D = huffman:decode2(Tree, Compressed).
<<"-module(huffman).\r\n-compile(export_all).\r\n\r\nmake_frqtbl(Bin) ->\r\n    Tmp =\r\n\tlists:foldl(\r\n\t  fun(B, Ary) ->\r\n\t\t  ar"...>>
72> 

大丈夫そうです。が、目で見て分かるほど今回作ったバージョンの方が遅いです。計測してみると...

72> timer:tc(huffman, decode, [Tree, Compressed]).
{3000,
 <<"-module(huffman).\r\n-compile(export_all).\r\n\r\nmake_frqtbl(Bin) ->\r\n    Tmp =\r\n\tlists:foldl(\r\n\t  fun(B, Ary) ->"...>>}
73> timer:tc(huffman, decode2, [Tree, Compressed]).
{477000,
 <<"-module(huffman).\r\n-compile(export_all).\r\n\r\nmake_frqtbl(Bin) ->\r\n    Tmp =\r\n\tlists:foldl(\r\n\t  fun(B, Ary) ->"...>>}
74> 

100倍以上遅いです。これはひどいですね。