v_huffman

V_HUFFMAN calculates a D-ary v_huffman code [CC,LL]=(P,A)

  Inputs:  P        is a vector or matrix of probabilities
           A(D)     is a vector of alphabet characters either integers of chars [default: '01']
                    the length of A determines the order of the code

 Outputs:  CC       is a cell array containing the code for each symbol with the sme shape as P
           LL       is a vector or matrix of code lengths with the sme shape as P
           L        is the average code length

0001 function [cc,ll,l]=v_huffman(p,a)
0002 %V_HUFFMAN calculates a D-ary v_huffman code [CC,LL]=(P,A)
0003 %
0004 %  Inputs:  P        is a vector or matrix of probabilities
0005 %           A(D)     is a vector of alphabet characters either integers of chars [default: '01']
0006 %                    the length of A determines the order of the code
0007 %
0008 % Outputs:  CC       is a cell array containing the code for each symbol with the sme shape as P
0009 %           LL       is a vector or matrix of code lengths with the sme shape as P
0010 %           L        is the average code length
0011 
0012 %       Copyright (C) Mike Brookes 1995
0013 %      Version: $Id: v_huffman.m 10865 2018-09-21 17:22:45Z dmb $
0014 %
0015 %   VOICEBOX is a MATLAB toolbox for speech processing.
0016 %   Home page: http://www.ee.ic.ac.uk/hp/staff/dmb/voicebox/voicebox.html
0017 %
0018 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
0019 %   This program is free software; you can redistribute it and/or modify
0020 %   it under the terms of the GNU General Public License as published by
0021 %   the Free Software Foundation; either version 2 of the License, or
0022 %   (at your option) any later version.
0023 %
0024 %   This program is distributed in the hope that it will be useful,
0025 %   but WITHOUT ANY WARRANTY; without even the implied warranty of
0026 %   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
0027 %   GNU General Public License for more details.
0028 %
0029 %   You can obtain a copy of the GNU General Public License from
0030 %   http://www.gnu.org/copyleft/gpl.html or by writing to
0031 %   Free Software Foundation, Inc.,675 Mass Ave, Cambridge, MA 02139, USA.
0032 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
0033 
0034 np=length(p(:));
0035 if nargin <2
0036     a='01';
0037 end
0038 d=length(a);
0039 
0040 % first append additional zeros-probability symbols to ensure a full code tree
0041 
0042 nx=np+mod(1-np,d-1);
0043 px=zeros(nx,1);
0044 px(1:np)=p(:);
0045 
0046 cl=(nx-1)/(d-1);        % max potential code length
0047 cd=zeros(nx,cl);        % code array
0048 qx=px;
0049 ix=(1:nx)';
0050 dd=(d:-1:1)';
0051 kx=zeros(nx,1);
0052 for i=cl:-1:1
0053     nc=1+i*(d-1);
0054     [rx,jx]=sort(qx);   % find the D smallest probabilities
0055     kx(jx)=(1:nc)';          % create a reverse index
0056     cd(:,i)=kx(ix);     
0057     ix=max(kx(ix)-d+1,1);
0058     rx(d)=sum(rx(1:d));
0059     qx=rx(d:end);
0060 end
0061 cc=cell(size(p));
0062 ll=zeros(size(p));
0063 for i=1:np
0064     ci=cd(i,cd(i,:)<=d);
0065     ll(i) = length(ci);
0066     cc{i}=a(ci);
0067 end
0068 l=p(:)'*ll(:)/sum(p(:));      % calculate average length