Editing Burrows–Wheeler transform (section)

===Example===

Given an input string <code>S = <span style="color:red;">^</span>BANANA<span style="color:red;">$</span></code> (step 1 in the table below), rotate it ''N'' times (step 2), where <code>N = 8</code> is the length of the <code>S</code> string considering also the red <code><span style="color:red;">^</span></code> character representing the start of the string and the red <code><span style="color:red;">$</span></code> character representing the '[[End-of-file|EOF]]' pointer; these rotations, or circular shifts, are then sorted lexicographically (step 3). The output of the encoding phase is the last column <code>L = BNN<span style="color:red;">^</span>AA<span style="color:red;">$</span>A</code> after step 3, and the index (0-based) <code>I</code> of the row containing the original string <code>S</code>, in this case <code>I = 6</code>.

It is not necessary to use both <code><span style="color:red;">$</span></code> and <code><span style="color:red;">^</span></code>, but at least one must be used, else we cannot invert the transform, since all circular permutations of a string have the same Burrows–Wheeler transform.

{| class="wikitable"
|-
!  colspan="5" | Transformation
|-
! 1. Input
! 2. All<br />rotations
! 3. Sort into<br />lexical order
! 4. Take the<br />last column
! 5. Output
|-
|  align=center |
 <span style="color:red;">^</span>BANANA<span style="color:red;">$</span>
|
 <span style="color:red;">^</span>BANANA<span style="color:red;">$</span>
 <span style="color:red;">$</span><span style="color:red;">^</span>BANANA
 A<span style="color:red;">$</span><span style="color:red;">^</span>BANAN
 NA<span style="color:red;">$</span><span style="color:red;">^</span>BANA
 ANA<span style="color:red;">$</span><span style="color:red;">^</span>BAN
 NANA<span style="color:red;">$</span><span style="color:red;">^</span>BA
 ANANA<span style="color:red;">$</span><span style="color:red;">^</span>B
 BANANA<span style="color:red;">$</span><span style="color:red;">^</span>
|
 '''A'''NANA<span style="color:red;">$</span><span style="color:red;">^</span>B
 '''A'''NA<span style="color:red;">$</span><span style="color:red;">^</span>BAN
 '''A'''<span style="color:red;">$</span><span style="color:red;">^</span>BANAN
 '''B'''ANANA<span style="color:red;">$</span><span style="color:red;">^</span>
 '''N'''ANA<span style="color:red;">$</span><span style="color:red;">^</span>BA
 '''N'''A<span style="color:red;">$</span><span style="color:red;">^</span>BANA
 <span style="color:red;">^</span>BANANA<span style="color:red;">$</span>
 <span style="color:red;">'''$^'''</span>BANANA

|
 ANANA<span style="color:red;">$</span><span style="color:red;">^</span>'''B'''
 ANA<span style="color:red;">$</span><span style="color:red;">^</span>BA'''N'''
 A<span style="color:red;">$</span><span style="color:red;">^</span>BANA'''N'''
 BANANA<span style="color:red;">$</span><span style="color:red;">'''^'''</span>
 NANA<span style="color:red;">$</span><span style="color:red;">^</span>B'''A'''
 NA<span style="color:red;">$</span><span style="color:red;">^</span>BAN'''A'''
 <span style="color:red;">^</span>BANANA<span style="color:red;">'''$'''</span>
 <span style="color:red;">$^</span>BANAN'''A'''
|
 BNN<span style="color:red;">^</span>AA<span style="color:red;">$</span>A
|}