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