BWT -> MTF -> RLE -> OUPTUT
This was the basic scheme of BWT by Burrows and Wheeler.
Sir, please have a look at the example I have taken to solve using this scheme….
STEP 1. X is the input.
Im taking input string as ABDACA
After applying BWT:
(arranging cyclic permutations) (lexicographic order)
A B D A C A A A B D A C
B D A C A A A B D A C A
D A C A A B A C A A B D
A C A A B D B D A C A A
C A A B D A C A A B D A
A A B D A C D A C A A B
So, the output string is CADAAB
STEP 2. APPLYING MTF
For that our input string will be CADAAB
On applying MTF….
Input string:
C A D A A B
2 1 3 1 0 3
0 1 2 3
A B C D
C A B D
A C B D
D A C B
A D C B
THEREFORE, for string CADAAB. We get output string as 213103
STEP3. The last step is to apply RLE, so , my question is how can we apply RLE on the string of integers. Because, RLE is applied on the alphabetic strings where we deal with repetition.
And here output of second stage should be taken as input for RLE.