Home > voicebox > huffman.m

huffman

PURPOSE

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

SYNOPSIS

function [cc,ll,l]=huffman(p,a)

DESCRIPTION

```HUFFMAN calculates a D-ary 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```

CROSS-REFERENCE INFORMATION

This function calls:
This function is called by:

SOURCE CODE

```0001 function [cc,ll,l]=huffman(p,a)
0002 %HUFFMAN calculates a D-ary 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: huffman.m 713 2011-10-16 14:45:43Z dmb \$
0014 %
0015 %   VOICEBOX is a MATLAB toolbox for speech processing.
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```

Generated on Mon 06-Aug-2018 14:48:32 by m2html © 2003