# Borrows Wheeler coding principles

## 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

```