Borrows Wheeler coding principles

Contents

The Burrows-Wheeler transformation ("encoding" algorithm)

N=11;
input_str='mississippi'
inp=double(input_str(:));
% Here it is the Burrows-Wheeler "direct" transform
T=gallery('circul',inp); % This performs the circular shifts of inp
P=flipud(T); % The matrix P is reversed up-down
base = max(P(:))+1;
keyP=P*[base.^(0:(N-2))'; 0];
[skeyP,indP]=sort(keyP);
Pe=P(indP,:);
ind_first=find(indP==1)
%char([P(:,1:(N-1)), P(:,N), Pe(:,1:(N-1)), Pe(:,N) ])
CC=[];
for i = 1:N
CC = [CC; char(P(i,1:(N-1))), '    ',  char(P(i,N)),  '    ',char(Pe(i,1:(N-1))), '    ' char(Pe(i,N)) ];
end
CC
input_str =

mississippi


ind_first =

     2


CC =

ississippi    m    sissippimi    s
ssissippim    i    ississippi    m
sissippimi    s    sippimissi    s
issippimis    s    pimississi    p
ssippimiss    i    ssissippim    i
sippimissi    s    imississip    p
ippimissis    s    mississipp    i
ppimississ    i    issippimis    s
pimississi    p    ippimissis    s
imississip    p    ssippimiss    i
mississipp    i    ppimississ    i

The message to send is: first the column Pd=Pe(:,N) and then ind_first

Pd=Pe(:,N); p=ind_first;

The Inverse Burrows-Wheeler transformation ("decoding" algorithm)

Inspect the message for existing symbols, and initialize the vector M for each symbol

Pd=Pe(:,N); p=ind_first;
Ms=1;
for ii=1:max(Pd)
K(ii)=sum(Pd==ii);
if(K(ii)~=0), M(ii)=Ms; Ms=Ms+K(ii); char(ii), end
end
ans =

i


ans =

m


ans =

p


ans =

s

Initialize the array L

for i=1:N
s=Pd(i);
L(i)=M(s);
M(s)=M(s)+1;
end

start from position p and continue decoding

i=p;
for k=1:N
Dec(k)=Pd(i);
i=L(i);
end
char(Dec)
ans =

mississippi