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.