Transformation de Burrows-Wheeler

chaine de caractère originale :
"that's the way it is"

Permutations Originiales :

00 - that's the way it is
01 - hat's the way it ist
02 - at's the way it isth
03 - t's the way it istha
04 - 's the way it isthat
05 - s the way it isthat'
06 -  the way it isthat's
07 - the way it isthat's
08 - he way it isthat's t
09 - e way it isthat's th
10 -  way it isthat's the
11 - way it isthat's the
12 - ay it isthat's the w
13 - y it isthat's the wa
14 -  it isthat's the way
15 - it isthat's the way
16 - t isthat's the way i
17 -  isthat's the way it
18 - isthat's the way it
19 - sthat's the way it i

Chaines Triées :

02 - at's the way it isth
12 - ay it isthat's the w
09 - e way it isthat's th
01 - hat's the way it ist
08 - he way it isthat's t
18 - isthat's the way it
15 - it isthat's the way
19 - sthat's the way it i
05 - s the way it isthat'
00 - that's the way it is
07 - the way it isthat's
03 - t's the way it istha
16 - t isthat's the way i
11 - way it isthat's the
13 - y it isthat's the wa
04 - 's the way it isthat
17 -  isthat's the way it
14 -  it isthat's the way
06 -  the way it isthat's
10 -  way it isthat's the

Sortie de la transformation de Burrows-Wheeler : la dernière colonne.
"hwhtt  i's ai attyse"
index de début : 3 (position de la chaine 01 dans le tableau des chaines triées)

La transformation inverse : on a la chaîne "hwhtt  i's ai attyse"

00 - h              11 - a
01 - w              14 - a
02 - h              19 - e
03 - t              00 - h
04 - t              02 - h
05 -                07 - i
06 -                12 - i
07 - i  -> SORT ->  09 - s
08 - '              18 - s
09 - s              03 - t
10 -                04 - t
11 - a              15 - t
12 - i              16 - t
13 -                01 - w
14 - a              17 - y
15 - t              08 - '
16 - t              05 - 
17 - y              06 - 
18 - s              10 - 
19 - e              13 - 

Matrice de Transformation (TM)
exemple :
   TM[11] = 00 , TM[14] = 01 , TM[19] = 02

03, 13, 04, 09, 10, 16, 17, 05, 15, 07,
18, 00, 06, 19, 01, 11, 12, 14, 08, 02,

on reconstruit avec la chaine originale
index = primary index
index = 03 donc    BTWstring[03] = t
index = TM[index] = TM[03] = 09 donc BTWstring[09] =  s
TM[09] = 07 BTWstring[07] = i
TM[07] = 05 BTWstring[05] = 
TM[05] = 16 BTWstring[16] = t

TM[16] = 12 BTWstring[12] = i
TM[12] = 06 BTWstring[06] = 
TM[06] = 17 BTWstring[17] = y

TM[17] = 14 BTWstring[14] = a
TM[14] = 01 BTWstring[01] = w
TM[01] = 13 BTWstring[13] = 
TM[13] = 19 BTWstring[13] = e

TM[19] = 02 BTWstring[02] = h
TM[02] = 04 BTWstring[02] = t
TM[04] = 10 BTWstring[10] = 
TM[10] = 18 BTWstring[18] = s

TM[18] = 08 BTWstring[08] = '
TM[08] = 15 BTWstring[15] = t
TM[15] = 11 BTWstring[11] = a
TM[11] = 00 BTWstring[00] = h
TM[00] = 03 primary index !

Et on obtient donc la ligne 01 non transformee et a l'envers
Donc c'est une transformation reversible.