Menu
▾
▴
[Octave-cvsupdate] SF.net SVN: octave:[9304] trunk/octave-forge/main/comm/inst
|
From: <car...@us...> - 2011-12-07 18:08:05
|
Revision: 9304
http://octave.svn.sourceforge.net/octave/?rev=9304&view=rev
Author: carandraug
Date: 2011-12-07 18:07:57 +0000 (Wed, 07 Dec 2011)
Log Message:
-----------
huffmandict/huffmandeco/huffmanenco:
* almost complete rewrite of huffmandeco by Ferran Mesas <fer...@gm...> to use binary tree instead of a brute-force O(n^3) or O(n^4)
* improved help text
* more test cases for huffmandeco
* better input checking and default setting
* updated licenses to GPLv3+
Modified Paths:
--------------
trunk/octave-forge/main/comm/inst/huffmandeco.m
trunk/octave-forge/main/comm/inst/huffmandict.m
trunk/octave-forge/main/comm/inst/huffmanenco.m
Modified: trunk/octave-forge/main/comm/inst/huffmandeco.m
===================================================================
--- trunk/octave-forge/main/comm/inst/huffmandeco.m 2011-12-07 16:05:56 UTC (rev 9303)
+++ trunk/octave-forge/main/comm/inst/huffmandeco.m 2011-12-07 18:07:57 UTC (rev 9304)
@@ -1,8 +1,9 @@
## Copyright (C) 2006 Muthiah Annamalai <mut...@ut...>
+## Copyright (C) 2011 Ferran Mesas Garcia <fer...@gm...>
##
## This program is free software; you can redistribute it and/or modify
## it under the terms of the GNU General Public License as published by
-## the Free Software Foundation; either version 2 of the License, or
+## the Free Software Foundation; either version 3 of the License, or
## (at your option) any later version.
##
## This program is distributed in the hope that it will be useful,
@@ -12,130 +13,90 @@
##
## You should have received a copy of the GNU General Public License
## along with this program; If not, see <http://www.gnu.org/licenses/>.
-##
## -*- texinfo -*-
-## @deftypefn {Function File} {@var{sig} = } huffmandeco (@var{hcode}, @var{dict})
+## @deftypefn {Function File} {@var{sig} =} huffmandeco (@var{hcode}, @var{dict})
+## Decode signal encoded by @code{huffmanenco}.
##
-## Returns the original signal that was Huffman encoded signal using
-## @code{huffmanenco}. This function uses a dict built from the
+## This function uses a dict built from the
## @code{huffmandict} and uses it to decode a signal list into a huffman
## list. A restriction is that @var{hcode} is expected to be a binary code
-## The returned signal set that strictly belongs in the range @code{[1,N]}
+##
+## The returned @var{sig} set that strictly belongs in the range @code{[1,N]}
## with @code{N = length(@var{dict})}. Also @var{dict} can only be from the
## @code{huffmandict} routine. Whenever decoding fails, those signal values a
-## re indicated by @code{-1}, and we successively try to restart decoding
-## from the next bit that hasn't failed in decoding, ad-infinitum. An exmaple
-## of the use of @code{huffmandeco} is
+## re indicated by @code{-1}, and we successively try to restart decoding
+## from the next bit that hasn't failed in decoding, ad-infinitum. An example
+## of the use of @code{huffmandeco} is:
##
## @example
## @group
-## hd = huffmandict(1:4,[0.5 0.25 0.15 0.10])
-## hcode = huffmanenco(1:4,hd) # [ 1 0 1 0 0 0 0 0 1 ]
-## huffmandeco(hcode,h d) # [1 2 3 4]
+## hd = huffmandict (1:4, [0.5 0.25 0.15 0.10]);
+## hcode = huffmanenco (1:4, hd);
+## back = huffmandeco (hcode, hd)
+## @result{} [1 2 3 4]
## @end group
## @end example
-## @end deftypefn
## @seealso{huffmandict, huffmanenco}
+## @end deftypefn
-function sig=huffmandeco(hcode,dict)
- if ( nargin < 2 || strcmp(class(dict),"cell")~=1 )
- error('usage: huffmanenco(sig,dict)');
- end
- if (max(hcode) > 1 || min(hcode) < 0)
- error("hcode has elements that are outside alphabet set ...
- Cannot decode.");
- end
-
-# TODO:
-# O(log(N)) algorithms exist, but we need some effort to implement those
-# Maybe sometime later, it would be a nice 1-day project
-# Ref: A memory efficient Huffman Decoding Algorithm, AINA 2005, IEEE
-#
+function symbols = huffmandeco (hcode, dict)
-# TODO: Somebody can implement a 'faster' algorithm than O(N^3) at present
-# Decoding Algorithm O(N+k*log(N)) which is approximately O(N+Nlog(N))
-#
-# 1. Separate the dictionary by the lengths
-# and knows symbol correspondence.
-#
-# 2. Find the symbol in the dict of lengths l,h where
-# l = smallest cw length ignoring 0 length CW, and
-# h = largest cw length , with k=h-l+1;
-#
-# 3. Match the k codewords to the dict using binary
-# search, and then you can declare decision.
-#
-# 4. In case of non-decodable words skip the start-bit
-# used in the previous case, and then restart the same
-# procedure from the next bit.
-#
- L=length(dict);
- lenL=length(dict{1});
- lenH=0;
-
-#
-# Know the ranges of operation
-#
- for itr=1:L
- t=length(dict{itr});
- if(t < lenL)
- lenL=t;
- end
- if(t > lenH)
- lenH=t;
- end
+ if (nargin != 2)
+ print_usage();
+ elseif (!all((hcode == 1) + (hcode == 0)) || !isvector(hcode))
+ error ("first argument must be a binary array");
+ elseif (!strcmp (class (dict), "cell"))
+ error ("second argument must be of the class dict (from `huffmandict')");
end
-#
-# Now do a O(N^4) algorithm
-#
- itr=0; #offset into the hcode
- sig=[]; #output
- CL=length(hcode);
+ ## Convert the Huffman Dictionary to a Huffman Tree represented by
+ ## an array.
+ tree = dict2tree(dict);
- %whole decoding loop.
- while ( itr < CL )
- %decode one element (or just try to).
- for itr_y=lenL:lenH
- %look for word in dictionary.
- %with flag to indicate found
- %or not found. Detect end of buffer.
-
- if ( (itr+itr_y) > CL )
- break;
- end
+ ## Traverse the tree and store the symbols.
+ symbols = [];
+ pointer = 1; # a pointer to a node of the tree.
+ for i = 1:length (hcode);
+ if (tree(pointer) != -1)
+ symbols = [symbols, tree(pointer)];
+ pointer = 1;
+ endif
+ pointer = 2 * pointer + hcode(i);
+ endfor
- word=hcode(itr+1:itr+itr_y);
- flag=0;
-
- %word
+ ## Check if decodification was successful
+ if (tree(pointer) == -1)
+ warning ("could not decode last symbol.")
+ endif
+ symbols = [symbols, tree(pointer)];
+endfunction
- %search loop.
- for itr_z=1:L
- if(isequal(dict{itr_z},word))
- itr=itr+itr_y;
- sig=[sig itr_z];
- flag=1;
- break;
- end
- end %for_ loop breaker
+function tree = dict2tree (dict)
+ L = length(dict);
+ lengths = zeros(1,L);
- if( flag == 1 )
- break; %also need to break_ above then.
- end
+ ## the depth of the tree is limited by the maximum word length.
+ for i = 1:L
+ lengths(i) = length (dict{i});
+ endfor
+ m = max (lengths);
- end %for_ loop
+ tree = zeros(1,2^(m+1)-1)-1;
+ for i = 1:L
+ pointer = 1;
+ word = dict{i};
+ for bit = word
+ pointer = 2 * pointer + bit;
+ endfor
+ tree(pointer) = i;
+ endfor
+endfunction
- #could not decode
- if( flag == 0 )
- itr=itr+1;
- sig=[sig -1];
- end
-
- end %while_ loop
-end
-%!
-%! assert(huffmandeco(huffmanenco(1:4, huffmandict(1:4,[0.5 0.25 0.15 0.10])), huffmandict(1:4,[0.5 0.25 0.15 0.10])), [1:4],0)
-%!
+%!assert(huffmandeco(huffmanenco(1:4, huffmandict(1:4,[0.5 0.25 0.15 0.10])), huffmandict(1:4,[0.5 0.25 0.15 0.10])), [1:4],0)
+%!assert(huffmandeco(huffmanenco([1:100 100:-1:1], huffmandict(1:100,ones(1,100)/100)), huffmandict(1:100,ones(1,100)/100)), [1:100 100:-1:1],0)
+%!assert(huffmandeco([huffmanenco(1:4, huffmandict(1:4,[0.5 0.25 0.15 0.10])) 0], huffmandict(1:4,[0.5 0.25 0.15 0.10])), [1:4 -1],0)
+%!fail('huffmandeco([huffmanenco(1:4, huffmandict(1:4,[0.5 0.25 0.15 0.10])) 0], huffmandict(1:4,[0.5 0.25 0.15 0.10]))','warning')
+%!fail('huffmandeco(''this is not a code'',huffmandict(1:4,[0.5 0.25 0.15 0.10]))')
+%!fail('huffmandeco([1 0 1 0],''this is not a dictionary'')')
Modified: trunk/octave-forge/main/comm/inst/huffmandict.m
===================================================================
--- trunk/octave-forge/main/comm/inst/huffmandict.m 2011-12-07 16:05:56 UTC (rev 9303)
+++ trunk/octave-forge/main/comm/inst/huffmandict.m 2011-12-07 18:07:57 UTC (rev 9304)
@@ -2,7 +2,7 @@
##
## This program is free software; you can redistribute it and/or modify
## it under the terms of the GNU General Public License as published by
-## the Free Software Foundation; either version 2 of the License, or
+## the Free Software Foundation; either version 3 of the License, or
## (at your option) any later version.
##
## This program is distributed in the hope that it will be useful,
@@ -49,8 +49,8 @@
## @end example
##
## Reference: Dr.Rao's course EE5351 Digital Video Coding, at UT-Arlington.
-## @end deftypefn
## @seealso{huffmandeco, huffmanenco}
+## @end deftypefn
## Huffman code algorithm.
## while (uncombined_symbols_remain)
@@ -69,18 +69,11 @@
## reverse each symbol, and dump it out.
##
-function cw_list=huffmandict(sym,source_prob,togglecode,minvar)
+function cw_list = huffmandict (sym, source_prob, togglecode = 0, minvar = 0)
if nargin < 2
- error("Usage: huffman_dict(source_prob,{togglecode 1-0 in code});")
- elseif nargin < 3
- togglecode=0;
- minvar=0;
- elseif nargin < 4
- minvar=0;
- end
-
- %need to compare to 1
- if((sum(source_prob)-1.0) > 1e-7 )
+ print_usage;
+ ## need to compare to 1
+ elseif((sum(source_prob)-1.0) > 1e-7 )
error("source probabilities must add up to 1.0");
end
@@ -103,19 +96,19 @@
for itr1=1:L
for itr2=itr1:L
if(source_prob(itr1) < source_prob(itr2))
- t=source_prob(itr1);
- source_prob(itr1)=source_prob(itr2);
- source_prob(itr2)=t;
+ t=source_prob(itr1);
+ source_prob(itr1)=source_prob(itr2);
+ source_prob(itr2)=t;
- t=index(itr1);
- index(itr1)=index(itr2);
- index(itr2)=t;
+ t=index(itr1);
+ index(itr1)=index(itr2);
+ index(itr2)=t;
end
end
end
- stage_list={};
- cw_list{1:L}=[];
+ stage_list = {};
+ cw_list = cell(1,L);
stage_curr={};
stage_curr.prob_list=source_prob;
@@ -145,8 +138,8 @@
%
for i=1:(L-2)
if((minvar && stage_curr.prob_list(i)<=nprob) || \
- stage_curr.prob_list(i) < nprob)
- break;
+ stage_curr.prob_list(i) < nprob)
+ break;
end
end
@@ -202,7 +195,7 @@
%disp('Before resorting')
%cw_list
- nw_list{1:L}=[];
+ nw_list = cell(1,L);
%
% Re-sort the indices according to the probability list.
%
@@ -224,8 +217,7 @@
return
end
-%!
+
%!assert(huffmandict(1:4,[0.5 0.25 0.15 0.1],1), {[0],[1 0],[1 1 1],[1 1 0]},0)
%!assert(huffmandict(1:4,0.25*ones(1,4),1),{[1 1],[1 0],[0 1],[0 0]},0)
%!assert(huffmandict(1:4,[1 0 0 0 ]),{[1],[0 1],[0 0 0],[0 0 1]},0)
-%!
Modified: trunk/octave-forge/main/comm/inst/huffmanenco.m
===================================================================
--- trunk/octave-forge/main/comm/inst/huffmanenco.m 2011-12-07 16:05:56 UTC (rev 9303)
+++ trunk/octave-forge/main/comm/inst/huffmanenco.m 2011-12-07 18:07:57 UTC (rev 9304)
@@ -2,7 +2,7 @@
##
## This program is free software; you can redistribute it and/or modify
## it under the terms of the GNU General Public License as published by
-## the Free Software Foundation; either version 2 of the License, or
+## the Free Software Foundation; either version 3 of the License, or
## (at your option) any later version.
##
## This program is distributed in the hope that it will be useful,
@@ -26,24 +26,22 @@
##
## @example
## @group
-## hd = huffmandict(1:4,[0.5 0.25 0.15 0.10])
-## huffmanenco(1:4,hd) # [ 1 0 1 0 0 0 0 0 1 ]
+## hd = huffmandict (1:4, [0.5 0.25 0.15 0.10]);
+## huffmanenco (1:4, hd);
+## @result{} [1 0 1 0 0 0 0 0 1]
## @end group
## @end example
-## @end deftypefn
## @seealso{huffmandict, huffmandeco}
+## @end deftypefn
-function hcode=huffmanenco(sig,dict)
- if ( nargin < 2 || strcmp(class(dict),"cell")~=1 )
- error('usage: huffmanenco(sig,dict)');
- end
- if (max(sig) > length(dict)) || ( min(sig) < 1)
- error("signal has elements that are outside alphabet set ...
- Cannot encode.");
- end
- hcode=[dict{sig}];
+function hcode = huffmanenco (sig, dict)
+ if (nargin != 2 || strcmp (class (dict),"cell") != 1)
+ print_usage;
+ elseif (max (sig) > length (dict) || min (sig) < 1)
+ error("signal has elements that are outside alphabet set. Cannot encode.");
+ endif
+ hcode = [dict{sig}];
return
end
-%!
-%! assert(huffmanenco(1:4, huffmandict(1:4,[0.5 0.25 0.15 0.10])), [ 1 0 1 0 0 0 0 0 1 ],0)
-%!
+
+%!assert(huffmanenco(1:4, huffmandict(1:4,[0.5 0.25 0.15 0.10])), [ 1 0 1 0 0 0 0 0 1 ],0)
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
