Burrows–Wheeler transform

Burrows–Wheeler transform
You are encouraged to solve this task according to the task description, using any language you may know.

This page uses content from Wikipedia. The original article was at Burrows–Wheeler_transform. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)

The Burrows–Wheeler transform (BWT, also called block-sorting compression) rearranges a character string into runs of similar characters.

This is useful for compression, since it tends to be easy to compress a string that has runs of repeated characters by techniques such as move-to-front transform and run-length encoding.

More importantly, the transformation is reversible, without needing to store any additional data.

The BWT is thus a "free" method of improving the efficiency of text compression algorithms, costing only some extra computation.

Source: Burrows–Wheeler transform

11l

Translation of: Python

F bwt(String =s)
   ‘Apply Burrows-Wheeler transform to input string.’
   assert("\002" !C s & "\003" !C s, ‘Input string cannot contain STX and ETX characters’)
   s = "\002"s"\003"
   V table = sorted((0 .< s.len).map(i -> @s[i..]‘’@s[0 .< i]))
   V last_column = table.map(row -> row[(len)-1..])
   R last_column.join(‘’)

F ibwt(String r)
   ‘Apply inverse Burrows-Wheeler transform.’
   V table = [‘’] * r.len
   L 0 .< r.len
      table = sorted((0 .< r.len).map(i -> @r[i]‘’@table[i]))
   V s = table.filter(row -> row.ends_with("\003"))[0]
   R s.rtrim("\003").trim("\002")

L(text) [‘banana’,
         ‘appellee’,
         ‘dogwood’,
         ‘TO BE OR NOT TO BE OR WANT TO BE OR NOT?’,
         ‘SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES’]
   V transformed = bwt(text)
   V invTransformed = ibwt(transformed)

   print(‘Original text:                ’text)
   print(‘After transformation:         ’transformed.replace("\2", ‘^’).replace("\3", ‘|’))
   print(‘After inverse transformation: ’invTransformed)
   print()

Output:

Original text:                banana
After transformation:         |annb^aa
After inverse transformation: banana

Original text:                appellee
After transformation:         |e^elplepa
After inverse transformation: appellee

Original text:                dogwood
After transformation:         |do^oodwg
After inverse transformation: dogwood

Original text:                TO BE OR NOT TO BE OR WANT TO BE OR NOT?
After transformation:         |?OOORREEETTRTW   BBB  ATTT   NNOOONOO^   
After inverse transformation: TO BE OR NOT TO BE OR WANT TO BE OR NOT?

Original text:                SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
After transformation:         |STEXYDST.E.IXXIIXXSSMPPS.B..EE.^.USFXDIIOIIIT
After inverse transformation: SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

BQN

stx←@+2
BWT ← { # Burrows-Wheeler Transform and its inverse as an invertible function
  𝕊: "Input contained STX"!⊑stx¬∘∊𝕩 ⋄ (⍋↓𝕩) ⊏ stx∾𝕩;
  𝕊⁼: 1↓(⊑˜⍟(↕≠𝕩)⟜⊑ ⍋)⊸⊏ 𝕩
}

Example use:

    BWT "banana"
"annb␂aa"
    BWT⁼ BWT "banana"
"banana"

    BWT "appellee"
"e␂elplepa"
    BWT⁼ BWT "appellee"
"appellee"

    BWT "dogwood"
"do␂oodwg"
    BWT⁼ BWT "dogwood"
"dogwood"

    BWT "TO BE OR NOT TO BE OR WANT TO BE OR NOT?"
"?OOORREEETTRTW   BBB  ATTT   NNOOONOO␂   "
    BWT⁼ BWT "TO BE OR NOT TO BE OR WANT TO BE OR NOT?"
"TO BE OR NOT TO BE OR WANT TO BE OR NOT?"

    BWT "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES"
"STEXYDST.E.IXXIIXXSSMPPS.B..EE.␂.USFXDIIOIIIT"
    BWT⁼ BWT "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES"
"SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES"

    BWT "␂abc"
Error: Input contained STX

C

Translation of: Python

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

const char STX = '\002', ETX = '\003';

int compareStrings(const void *a, const void *b) {
    char *aa = *(char **)a;
    char *bb = *(char **)b;
    return strcmp(aa, bb);
}

int bwt(const char *s, char r[]) {
    int i, len = strlen(s) + 2;
    char *ss, *str;
    char **table;
    if (strchr(s, STX) || strchr(s, ETX)) return 1;
    ss = calloc(len + 1, sizeof(char));
    sprintf(ss, "%c%s%c", STX, s, ETX);
    table = malloc(len * sizeof(const char *));
    for (i = 0; i < len; ++i) {
        str = calloc(len + 1, sizeof(char));
        strcpy(str, ss + i);
        if (i > 0) strncat(str, ss, i);
        table[i] = str;
    }
    qsort(table, len, sizeof(const char *), compareStrings);
    for(i = 0; i < len; ++i) {
        r[i] = table[i][len - 1];
        free(table[i]);
    }
    free(table);
    free(ss);
    return 0;
}

void ibwt(const char *r, char s[]) {
    int i, j, len = strlen(r);
    char **table = malloc(len * sizeof(const char *));
    for (i = 0; i < len; ++i) table[i] = calloc(len + 1, sizeof(char));
    for (i = 0; i < len; ++i) {
        for (j = 0; j < len; ++j) {                        
            memmove(table[j] + 1, table[j], len);
            table[j][0] = r[j];
        }
        qsort(table, len, sizeof(const char *), compareStrings);
    }
    for (i = 0; i < len; ++i) {
        if (table[i][len - 1] == ETX) {
            strncpy(s, table[i] + 1, len - 2);
            break;
        }
    }
    for (i = 0; i < len; ++i) free(table[i]);
    free(table);
}

void makePrintable(const char *s, char t[]) {
    strcpy(t, s);
    for ( ; *t != '\0'; ++t) {
        if (*t == STX) *t = '^';
        else if (*t == ETX) *t = '|';
    }
}

int main() {
    int i, res, len;
    char *tests[6], *t, *r, *s;
    tests[0] = "banana";
    tests[1] = "appellee";
    tests[2] = "dogwood";
    tests[3] = "TO BE OR NOT TO BE OR WANT TO BE OR NOT?";
    tests[4] = "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
    tests[5] = "\002ABC\003";
    for (i = 0; i < 6; ++i) {
        len = strlen(tests[i]);
        t = calloc(len + 1, sizeof(char));
        makePrintable(tests[i], t);
        printf("%s\n", t);
        printf(" --> ");
        r = calloc(len + 3, sizeof(char));
        res = bwt(tests[i], r);
        if (res == 1) {
            printf("ERROR: String can't contain STX or ETX\n");
        }
        else {
            makePrintable(r, t);
            printf("%s\n", t);
        }
        s = calloc(len + 1, sizeof(char));
        ibwt(r, s);
        makePrintable(s, t);
        printf(" --> %s\n\n", t);
        free(t);
        free(r);
        free(s);
    }
    return 0;
}

Output:

banana
 --> |annb^aa
 --> banana

appellee
 --> |e^elplepa
 --> appellee

dogwood
 --> |do^oodwg
 --> dogwood

TO BE OR NOT TO BE OR WANT TO BE OR NOT?
 --> |?OOORREEETTRTW   BBB  ATTT   NNOOONOO^   
 --> TO BE OR NOT TO BE OR WANT TO BE OR NOT?

SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
 --> |STEXYDST.E.IXXIIXXSSMPPS.B..EE.^.USFXDIIOIIIT
 --> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

^ABC|
 --> ERROR: String can't contain STX or ETX
 --> 

C#

Translation of: D

using System;
using System.Collections.Generic;
using System.Linq;

namespace BurrowsWheeler {
    class Program {
        const char STX = (char)0x02;
        const char ETX = (char)0x03;

        private static void Rotate(ref char[] a) {
            char t = a.Last();
            for (int i = a.Length - 1; i > 0; --i) {
                a[i] = a[i - 1];
            }
            a[0] = t;
        }

        // For some reason, strings do not compare how whould be expected
        private static int Compare(string s1, string s2) {
            for (int i = 0; i < s1.Length && i < s2.Length; ++i) {
                if (s1[i] < s2[i]) {
                    return -1;
                }
                if (s2[i] < s1[i]) {
                    return 1;
                }
            }
            if (s1.Length < s2.Length) {
                return -1;
            }
            if (s2.Length < s1.Length) {
                return 1;
            }
            return 0;
        }

        static string Bwt(string s) {
            if (s.Any(a => a == STX || a == ETX)) {
                throw new ArgumentException("Input can't contain STX or ETX");
            }
            char[] ss = (STX + s + ETX).ToCharArray();
            List<string> table = new List<string>();
            for (int i = 0; i < ss.Length; ++i) {
                table.Add(new string(ss));
                Rotate(ref ss);
            }
            table.Sort(Compare);
            return new string(table.Select(a => a.Last()).ToArray());
        }

        static string Ibwt(string r) {
            int len = r.Length;
            List<string> table = new List<string>(new string[len]);
            for (int i = 0; i < len; ++i) {
                for (int j = 0; j < len; ++j) {
                    table[j] = r[j] + table[j];
                }
                table.Sort(Compare);
            }
            foreach (string row in table) {
                if (row.Last() == ETX) {
                    return row.Substring(1, len - 2);
                }
            }
            return "";
        }

        static string MakePrintable(string s) {
            return s.Replace(STX, '^').Replace(ETX, '|');
        }

        static void Main() {
            string[] tests = new string[] {
                "banana",
                "appellee",
                "dogwood",
                "TO BE OR NOT TO BE OR WANT TO BE OR NOT?",
                "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
                "\u0002ABC\u0003"
            };

            foreach (string test in tests) {
                Console.WriteLine(MakePrintable(test));
                Console.Write(" --> ");

                string t = "";
                try {
                    t = Bwt(test);
                    Console.WriteLine(MakePrintable(t));
                } catch (Exception e) {
                    Console.WriteLine("ERROR: {0}", e.Message);
                }

                string r = Ibwt(t);
                Console.WriteLine(" --> {0}", r);
                Console.WriteLine();
            }
        }
    }
}

Output:

banana
 --> |annb^aa
 --> banana

appellee
 --> |e^elplepa
 --> appellee

dogwood
 --> |do^oodwg
 --> dogwood

TO BE OR NOT TO BE OR WANT TO BE OR NOT?
 --> |?OOORREEETTRTW   BBB  ATTT   NNOOONOO^
 --> TO BE OR NOT TO BE OR WANT TO BE OR NOT?

SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
 --> |STEXYDST.E.IXXIIXXSSMPPS.B..EE.^.USFXDIIOIIIT
 --> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

^ABC|
 --> ERROR: Input can't contain STX or ETX
 -->

C++

Translation of: C#

#include <algorithm>
#include <iostream>
#include <vector>

const int STX = 0x02;
const int ETX = 0x03;

void rotate(std::string &a) {
    char t = a[a.length() - 1];
    for (int i = a.length() - 1; i > 0; i--) {
        a[i] = a[i - 1];
    }
    a[0] = t;
}

std::string bwt(const std::string &s) {
    for (char c : s) {
        if (c == STX || c == ETX) {
            throw std::runtime_error("Input can't contain STX or ETX");
        }
    }

    std::string ss;
    ss += STX;
    ss += s;
    ss += ETX;

    std::vector<std::string> table;
    for (size_t i = 0; i < ss.length(); i++) {
        table.push_back(ss);
        rotate(ss);
    }
    //table.sort();
    std::sort(table.begin(), table.end());

    std::string out;
    for (auto &s : table) {
        out += s[s.length() - 1];
    }
    return out;
}

std::string ibwt(const std::string &r) {
    int len = r.length();
    std::vector<std::string> table(len);
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len; j++) {
            table[j] = r[j] + table[j];
        }
        std::sort(table.begin(), table.end());
    }
    for (auto &row : table) {
        if (row[row.length() - 1] == ETX) {
            return row.substr(1, row.length() - 2);
        }
    }
    return {};
}

std::string makePrintable(const std::string &s) {
    auto ls = s;
    for (auto &c : ls) {
        if (c == STX) {
            c = '^';
        } else if (c == ETX) {
            c = '|';
        }
    }
    return ls;
}

int main() {
    auto tests = {
        "banana",
        "appellee",
        "dogwood",
        "TO BE OR NOT TO BE OR WANT TO BE OR NOT?",
        "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
        "\u0002ABC\u0003"
    };

    for (auto &test : tests) {
        std::cout << makePrintable(test) << "\n";
        std::cout << " --> ";

        std::string t;
        try {
            t = bwt(test);
            std::cout << makePrintable(t) << "\n";
        } catch (std::runtime_error &e) {
            std::cout << "Error " << e.what() << "\n";
        }

        std::string r = ibwt(t);
        std::cout << " --> " << r << "\n\n";
    }

    return 0;
}

Output:

banana
 --> |annb^aa
 --> banana

appellee
 --> |e^elplepa
 --> appellee

dogwood
 --> |do^oodwg
 --> dogwood

TO BE OR NOT TO BE OR WANT TO BE OR NOT?
 --> |?OOORREEETTRTW   BBB  ATTT   NNOOONOO^
 --> TO BE OR NOT TO BE OR WANT TO BE OR NOT?

SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
 --> |STEXYDST.E.IXXIIXXSSMPPS.B..EE.^.USFXDIIOIIIT
 --> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

^ABC|
 --> Error Input can't contain STX or ETX
 -->

D

Translation of: Kotlin

import std.algorithm.iteration;
import std.algorithm.mutation;
import std.algorithm.searching;
import std.algorithm.sorting;
import std.array;
import std.stdio;
import std.string;

immutable STX = 0x02;
immutable ETX = 0x03;

string bwt(string s) {
    if (s.any!"a==0x02 || a==0x03") {
        throw new Exception("Input can't contain STX or ETX");
    }
    char[] ss = (STX ~ s ~ ETX).dup;
    string[] table;
    foreach (i; 0..ss.length) {
        table ~= ss.idup;
        bringToFront(ss[0..$-1], ss[$-1..$]);
    }
    table.sort();
    return table.map!"a[$-1]".array;
}

string ibwt(string r) {
    const len = r.length;
    string[] table;
    table.length = len;
    foreach (_; 0..len) {
        foreach (i; 0..len) {
            table[i] = r[i] ~ table[i];
        }
        table.sort();
    }
    foreach (row; table) {
        if (row[$-1] == ETX) {
            return row[1..len-1];
        }
    }
    return "";
}

string makePrintable(string s) {
    return tr(s, "\u0002\u0003", "^|");
}

void main() {
    immutable tests = [
        "banana",
        "appellee",
        "dogwood",
        "TO BE OR NOT TO BE OR WANT TO BE OR NOT?",
        "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
        "\u0002ABC\u0003"
    ];

    foreach (test; tests) {
        writeln(test.makePrintable);
        write(" --> ");

        string t;
        try {
            t = bwt(test);
            writeln(t.makePrintable);
        } catch (Exception e) {
            writeln("ERROR: ", e.message);
        }

        auto r = ibwt(t);
        writeln(" --> ", r);
        writeln;
    }
}

Output:

banana
 --> |annb^aa
 --> banana

appellee
 --> |e^elplepa
 --> appellee

dogwood
 --> |do^oodwg
 --> dogwood

TO BE OR NOT TO BE OR WANT TO BE OR NOT?
 --> |?OOORREEETTRTW   BBB  ATTT   NNOOONOO^
 --> TO BE OR NOT TO BE OR WANT TO BE OR NOT?

SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
 --> |STEXYDST.E.IXXIIXXSSMPPS.B..EE.^.USFXDIIOIIIT
 --> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

^ABC|
 --> ERROR: Input can't contain STX or ETX
 -->

Dart

Translation of: Java

import "dart:io";

void main() {
  List<String> tests = [
    "banana",
    "appellee",
    "dogwood",
    "TO BE OR NOT TO BE OR WANT TO BE OR NOT?",
    "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
    "\u0002ABC\u0003"
  ];
  for (String test in tests) {
    print(makePrintable(test));
    stdout.write(" --> ");
    String t = "";
    try {
      t = bwt(test);
      print(makePrintable(t));
    } catch (e) {
      print("ERROR: ${e.toString()}");
    }
    String r = ibwt(t);
    print(" --> $r\n");
  }
}

const String STX = "\u0002";
const String ETX = "\u0003";

String bwt(String s) {
  if (s.contains(STX) || s.contains(ETX)) {
    throw FormatException("String cannot contain STX or ETX");
  }

  String ss = STX + s + ETX;
  List<String> table = [];
  for (int i = 0; i < ss.length; i++) {
    String before = ss.substring(i);
    String after = ss.substring(0, i);
    table.add(before + after);
  }
  table.sort();

  return table.map((str) => str[str.length - 1]).join();
}

String ibwt(String r) {
  int len = r.length;
  List<String> table = List.filled(len, "");
  for (int j = 0; j < len; ++j) {
    for (int i = 0; i < len; ++i) {
      table[i] = r[i] + table[i];
    }
    table.sort();
  }
  for (String row in table) {
    if (row.endsWith(ETX)) {
      return row.substring(1, len - 1);
    }
  }
  return "";
}

String makePrintable(String s) {
  // substitute ^ for STX and | for ETX to print results
  return s.replaceAll(STX, "^").replaceAll(ETX, "|");
}

Output:

banana
 --> |annb^aa
 --> banana

appellee
 --> |e^elplepa
 --> appellee

dogwood
 --> |do^oodwg
 --> dogwood

TO BE OR NOT TO BE OR WANT TO BE OR NOT?
 --> |?OOORREEETTRTW   BBB  ATTT   NNOOONOO^   
 --> TO BE OR NOT TO BE OR WANT TO BE OR NOT?

SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
 --> |STEXYDST.E.IXXIIXXSSMPPS.B..EE.^.USFXDIIOIIIT
 --> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

^ABC|
 --> ERROR: FormatException: String cannot contain STX or ETX
 --> 

EasyLang

Translation of: Lua

# stx$ = strchar 2
# etx$ = strchar 3
stx$ = "¹"
etx$ = "²"
# 
proc sort . d$[] .
   for i = 2 to len d$[]
      h$ = d$[i]
      j = i - 1
      while j >= 1 and strcmp h$ d$[j] < 1
         d$[j + 1] = d$[j]
         j -= 1
      .
      d$[j + 1] = h$
   .
.
func$ bwt s$ .
   ss$ = stx$ & s$ & etx$
   for i to len ss$
      a$ = substr ss$ 1 i
      b$ = substr ss$ (i + 1) 9999
      tbl$[] &= b$ & a$
   .
   sort tbl$[]
   for s$ in tbl$[]
      r$ &= substr s$ len s$ 1
   .
   return r$
.
func$ ibwt r$ .
   le = len r$
   for i to le
      tbl$[] &= ""
   .
   for j to le
      for i to le
         tbl$[i] = substr r$ i 1 & tbl$[i]
      .
      sort tbl$[]
   .
   for row$ in tbl$[]
      if substr row$ le 1 = etx$
         return substr row$ 2 (le - 2)
      .
   .
.
for s$ in [ "banana" "appellee" "dogwood" "TO BE OR NOT TO BE OR WANT TO BE OR NOT?" "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES" ]
   print s$
   h$ = bwt s$
   print h$
   print ibwt h$
   print ""
.

Output:

banana
bnn¹aaa²
banana

appellee
¹lpelepae²
appellee

dogwood
¹ooodwgd²
dogwood

TO BE OR NOT TO BE OR WANT TO BE OR NOT?
OOORREEETTRTW   BBB  ATTT   NNOOONOO¹   ?²
TO BE OR NOT TO BE OR WANT TO BE OR NOT?

SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
TEXYDST.E.IXIXIXXSSMPPS.B..E.¹.UESFXDIIOIIITS²
SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

Factor

Factor has a Burrows-Wheeler transform implementation in its standard library. In addition to the transformed sequence, the bwt word also outputs an index for use with the inverse ibwt word.

USING: formatting io kernel math.transforms.bwt sequences ;
{
    "banana" "dogwood" "TO BE OR NOT TO BE OR WANT TO BE OR NOT?"
    "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES"
} [
    [ print ] [ bwt ] bi
    2dup "  bwt-->%3d %u\n" printf
    ibwt "  ibwt->    %u\n" printf nl
] each

Output:

banana
  bwt-->  3 "nnbaaa"
  ibwt->    "banana"

dogwood
  bwt-->  1 "odoodwg"
  ibwt->    "dogwood"

TO BE OR NOT TO BE OR WANT TO BE OR NOT?
  bwt--> 36 "OOORREEETTRTW   BBB  ATTT   NNOOONOO?   "
  ibwt->    "TO BE OR NOT TO BE OR WANT TO BE OR NOT?"

SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
  bwt--> 29 "TEXYDST.E.IXIXIXXSSMPPS.B..E.S.EUSFXDIIOIIIT"
  ibwt->    "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES"

FreeBASIC

Translation of: C++

#define STX  Chr(&H2)
#define ETX  Chr(&H3)

Sub Sort(arr() As String)
    Dim As Integer i, j, n    
    n = Ubound(arr) + 1
    For i = 0 To n - 1
        For j = i + 1 To n - 1
            If arr(i) > arr(j) Then Swap arr(i), arr(j)
        Next j
    Next i
End Sub

Function Replace(Byval cadena As String, Byval subcadena As String, Byval reemplazaCon As String) As String
    Dim As Integer posic = Instr(cadena, subcadena)
    While posic <> 0
        cadena = Left(cadena, posic - 1) & reemplazaCon & Mid(cadena, posic + Len(subcadena))
        posic = Instr(posic + Len(reemplazaCon), cadena, subcadena)
    Wend
    Return cadena
End Function

Sub Rotate(s As String)
    Dim As Integer longi = Len(s)
    Dim As String t = Right(s, 1)
    s = t & Left(s, longi - 1)
End Sub

Function BWT(s As String) As String
    Dim As Integer i
    For i = 1 To Len(s)
        If Mid(s, i, 1) = STX Orelse Mid(s, i, 1) = ETX Then
            Print "ERROR: String can't contain STX or ETX";
            Exit Function
        End If
    Next i
    
    Dim As String ss = STX & s & ETX   
    Dim As Integer longi = Len(ss)
    Dim As String tabla(longi)
    
    For i = 1 To longi
        tabla(i) = ss
        Rotate(ss)
    Next i
    
    Sort tabla()
    
    Dim As String salida
    For i = 1 To longi
        salida &= Right(tabla(i), 1)
    Next i
    
    Return salida
End Function

Function Ibwt(r As String) As String
    Dim As Integer i, j
    Dim As Integer longi = Len(r)
    Dim As String sa(1 To longi)
    Dim As String tabla(Lbound(sa) To Ubound(sa))
    
    For i = 1 To longi
        For j = 1 To longi
            tabla(j) = Mid(r, j, 1) & tabla(j)
        Next j
        Sort tabla()
    Next i
    
    For i = Lbound(tabla) To Ubound(tabla)
        If Right(tabla(i), 1) = ETX Then Return Mid(tabla(i), 2, longi - 2)
    Next i
    
    Return ""
End Function

Function makePrintable(s As String) As String
    Dim As String ls = s
    
    For i As Integer = 1 To Len(ls)
        Select Case Mid(ls, i, 1)
        Case STX : Mid(ls, i, 1) = "^"
        Case ETX : Mid(ls, i, 1) = "|"
        End Select
    Next i
    
    Return ls
End Function

Dim As String tests(5) = { _
"banana", "appellee", "dogwood", "TO BE OR NOT TO BE OR WANT TO BE OR NOT?", _
"SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES", STX & "ABC" & ETX }

For i As Integer = Lbound(tests) To Ubound(tests)
    Print makePrintable(tests(i))
    Print " --> ";
    Dim As String t = BWT(tests(i))
    Print makePrintable(t)
    Dim As String r = iBWT(t)
    Print " --> "; r; Chr(10); Chr(10);
Next i

Sleep

Output:

Same as C++ entry.

Go

Translation of: Python

package main

import (
    "fmt"
    "sort"
    "strings"
)

const stx = "\002"
const etx = "\003"

func bwt(s string) (string, error) {
    if strings.Index(s, stx) >= 0 || strings.Index(s, etx) >= 0 {
        return "", fmt.Errorf("String can't contain STX or ETX")
    }
    s = stx + s + etx
    le := len(s)
    table := make([]string, le)
    table[0] = s
    for i := 1; i < le; i++ {
        table[i] = s[i:] + s[:i]
    }
    sort.Strings(table)
    lastBytes := make([]byte, le)
    for i := 0; i < le; i++ {
        lastBytes[i] = table[i][le-1]
    }
    return string(lastBytes), nil
}

func ibwt(r string) string {
    le := len(r)
    table := make([]string, le)
    for range table {
        for i := 0; i < le; i++ {
            table[i] = r[i:i+1] + table[i]
        }
        sort.Strings(table)
    }
    for _, row := range table {
        if strings.HasSuffix(row, etx) {
            return row[1 : le-1]
        }
    }
    return ""
}

func makePrintable(s string) string {
    // substitute ^ for STX and | for ETX to print results
    t := strings.Replace(s, stx, "^", 1)
    return strings.Replace(t, etx, "|", 1)
}

func main() {
    tests := []string{
        "banana",
        "appellee",
        "dogwood",
        "TO BE OR NOT TO BE OR WANT TO BE OR NOT?",
        "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
        "\002ABC\003",
    }
    for _, test := range tests {
        fmt.Println(makePrintable(test))
        fmt.Print(" --> ")
        t, err := bwt(test)
        if err != nil {
            fmt.Println("ERROR:", err)
        } else {
            fmt.Println(makePrintable(t))
        }
        r := ibwt(t)
        fmt.Println(" -->", r, "\n")
    }
}

Output:

banana
 --> |annb^aa
 --> banana 

appellee
 --> |e^elplepa
 --> appellee 

dogwood
 --> |do^oodwg
 --> dogwood 

TO BE OR NOT TO BE OR WANT TO BE OR NOT?
 --> |?OOORREEETTRTW   BBB  ATTT   NNOOONOO^   
 --> TO BE OR NOT TO BE OR WANT TO BE OR NOT? 

SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
 --> |STEXYDST.E.IXXIIXXSSMPPS.B..EE.^.USFXDIIOIIIT
 --> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES 

^ABC|
 --> ERROR: String can't contain STX or ETX
 -->  

Groovy

Translation of: Java

class BWT {
    private static final String STX = "\u0002"
    private static final String ETX = "\u0003"

    private static String bwt(String s) {
        if (s.contains(STX) || s.contains(ETX)) {
            throw new IllegalArgumentException("String cannot contain STX or ETX")
        }

        String ss = STX + s + ETX
        List<String> table = new ArrayList<>()
        for (int i = 0; i < ss.length(); i++) {
            String before = ss.substring(i)
            String after = ss.substring(0, i)
            table.add(before + after)
        }
        Collections.sort(table)

        StringBuilder sb = new StringBuilder()
        for (String str : table) {
            sb.append(str[str.length() - 1])
        }
        return sb.toString()
    }

    private static String ibwt(String r) {
        int len = r.length()
        List<String> table = new ArrayList<>()
        for (int i = 0; i < len; ++i) {
            table.add("")
        }
        for (int j = 0; j < len; ++j) {
            for (int i = 0; i < len; ++i) {
                table[i] = r[i] + table[i]
            }
            Collections.sort(table)
        }
        for (String row : table) {
            if (row.endsWith(ETX)) {
                return row.substring(1, len - 1)
            }
        }
        return ""
    }

    private static String makePrintable(String s) {
        // substitute ^ for STX and | for ETX to print results
        return s.replace(STX, "^").replace(ETX, "|")
    }

    static void main(String[] args) {
        List<String> tests = new ArrayList<>()
        tests.add("banana")
        tests.add("appellee")
        tests.add("dogwood")
        tests.add("TO BE OR NOT TO BE OR WANT TO BE OR NOT?")
        tests.add("SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES")
        tests.add("\u0002ABC\u0003")

        for (String test : tests) {
            println(makePrintable(test))
            print(" --> ")
            String t = ""
            try {
                t = bwt(test)
                println(makePrintable(t))
            } catch (IllegalArgumentException e) {
                println("ERROR: " + e.getMessage())
            }
            String r = ibwt(t)
            printf(" --> %s\n\n", r)
        }
    }
}

Output:

banana
 --> |annb^aa
 --> banana

appellee
 --> |e^elplepa
 --> appellee

dogwood
 --> |do^oodwg
 --> dogwood

TO BE OR NOT TO BE OR WANT TO BE OR NOT?
 --> |?OOORREEETTRTW   BBB  ATTT   NNOOONOO^   
 --> TO BE OR NOT TO BE OR WANT TO BE OR NOT?

SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
 --> |STEXYDST.E.IXXIIXXSSMPPS.B..EE.^.USFXDIIOIIIT
 --> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

^ABC|
 --> ERROR: String cannot contain STX or ETX
 --> 

Haskell

-- A straightforward, inefficient implementation of the Burrows–Wheeler
-- transform, based on the description in the Wikipedia article.
--
-- Special characters are *not* used to indicate the start or end of sequences,
-- so all strings can be represented.

import Data.List ((!!), find, sort, tails, transpose)
import Data.Maybe (fromJust)
import Text.Printf (printf)

newtype BWT a = BWT [Val a]

bwt :: Ord a => [a] -> BWT a
bwt xs = let n  = length xs + 2
             ys = transpose $ sort $ take n $ tails $ cycle $ pos xs
         in BWT $ ys !! (n-1)

invBwt :: Ord a => BWT a -> [a]
invBwt (BWT xs) = let ys = iterate step (map (const []) xs) !! length xs
                  in unpos $ fromJust $ find ((== Post) . last) ys
  where step = sort . zipWith (:) xs


data Val a = In a | Pre | Post deriving (Eq, Ord)

pos :: [a] -> [Val a]
pos xs = Pre : map In xs ++ [Post]

unpos :: [Val a] -> [a]
unpos xs = [x | In x <- xs]


main :: IO ()
main = mapM_ testBWT [ "", "a", "BANANA", "dogwood",
                       "TO BE OR NOT TO BE OR WANT TO BE OR NOT?",
                       "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES" ]

testBWT :: String -> IO ()
testBWT xs = let fwd = bwt xs
                 inv = invBwt fwd
             in printf "%s\n\t%s\n\t%s\n" xs (pretty fwd) inv
  where pretty (BWT ps) = map prettyVal ps
        prettyVal (In c) = c
        prettyVal Pre    = '^'
        prettyVal Post   = '|'

Output:

        |^
        
a
        ^|a
        a
BANANA
        BNN^AA|A
        BANANA
dogwood
        ^ooodwg|d
        dogwood
TO BE OR NOT TO BE OR WANT TO BE OR NOT?
        OOORREEETTRTW   BBB  ATTT   NNOOONOO^   |?
        TO BE OR NOT TO BE OR WANT TO BE OR NOT?
SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
        TEXYDST.E.IXIXIXXSSMPPS.B..E.^.UESFXDIIOIIIT|S
        SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

J

   NB. transform and inverse
   bwt=: {:"1@:(/:~ :[:)@:(|."0 1~ -@:i.@:#)@:((2{a.) , ,&(3{a.))@:(([ ('STX or ETX invalid in input' (13!:8) 21 + 0:))^:(1 e. (2 3{a.)&e.)) :.(}.@:}:@:({~ ((3{a.) [: :i.~ {:"1))@:((,"0 1 /:~ :[:)^:(#@[)&(0$00)))

   NB. demonstrate the transform
   A=: <@bwt ;._2 ] 0 :0
    tests[0] = "banana";
    tests[1] = "appellee";
    tests[2] = "dogwood";
    tests[3] = "TO BE OR NOT TO BE OR WANT TO BE OR NOT?";
    tests[4] = "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
)
�;�  =] a [" s0nnb"taate s                                      
�;�  =] e [" s1"elptlepate s                                    
�;�  =] d [" s2o"toodwte sg                                     
�;�  =]OOORREEETTR ? [" TW   BBB  ATTT   NNOOONOO"   s3tte s    
�,�  =] S "TEXYDST[ .E.IXXIIXXSSMPPS.B..EE.".USFXDIIOIIITs4tte s

   NB. and the restoring transformation
   bwt inv&> A
    tests[0] = "banana";                                      
    tests[1] = "appellee";                                    
    tests[2] = "dogwood";                                     
    tests[3] = "TO BE OR NOT TO BE OR WANT TO BE OR NOT?";    
    tests[4] = "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
   
   NB. the final test pattern
   bwt  a. {~ 2 , (a. i. 'ABC') , 3
|STX or ETX invalid in input: bwt
|       bwt a.{~2,(a.i.'ABC'),3

   
NB. articulate definition
NB. local names (assignment =.) won't pollute the namespace

3 :0'define Burrows-Wheeler transformations'
 Dyad=. [: :
 Monad=. :[:
 index=. i. Dyad
 Rank=. "
 sort=. /:~ Monad

 signal_error=. 13!:8
 VALUE_ERROR=.  21
 'STX ETX'=. 2 3 { a.
 verify=. ([ ('STX or ETX invalid in input' signal_error VALUE_ERROR + 0:))^:(1 e. (STX , ETX)&e.)
 rotations=. |."0 1~ -@:i.@:#
 tail=. {:
 mark=. STX , ,&ETX
 transform=. tail Rank 1 @: sort @: rotations @: mark @: verify
 EXPECT=. ETX , 'ANNB' , STX , 'AA'
 assert. EXPECT -: transform 'BANANA'

 unscramble=. (,Rank 0 1 sort)^:(#@[)&(i.0)
 find=. ETX index~ tail Rank 1
 from=. {
 behead=. }.
 curtail=. }:
 erase_mark =. behead @: curtail
 restore=.  erase_mark @: (from~ find) @: unscramble
 assert. 'BANANA' -: restore EXPECT

 obverse=. :.
 fixed=. f.
 bwt=: transform obverse restore fixed

 assert (-: ]&.:bwt)'same under transformation'

 EMPTY
)

concise implementation

bwt=:verb def '{:"1 /:~(|."0 1~i.@#) (8 u:y),{:a.'
ibwt=: 1 (}.{:) (/:~@,.^:(#@]) 0#"0])

Example use:

   bwt'This is a test.'
ssat� tT hiies .
   ibwt bwt'This is a test.'
This is a test.

Java

Translation of: Kotlin

import java.util.ArrayList;
import java.util.List;

public class BWT {
    private static final String STX = "\u0002";
    private static final String ETX = "\u0003";

    private static String bwt(String s) {
        if (s.contains(STX) || s.contains(ETX)) {
            throw new IllegalArgumentException("String cannot contain STX or ETX");
        }

        String ss = STX + s + ETX;
        List<String> table = new ArrayList<>();
        for (int i = 0; i < ss.length(); i++) {
            String before = ss.substring(i);
            String after = ss.substring(0, i);
            table.add(before + after);
        }
        table.sort(String::compareTo);

        StringBuilder sb = new StringBuilder();
        for (String str : table) {
            sb.append(str.charAt(str.length() - 1));
        }
        return sb.toString();
    }

    private static String ibwt(String r) {
        int len = r.length();
        List<String> table = new ArrayList<>();
        for (int i = 0; i < len; ++i) {
            table.add("");
        }
        for (int j = 0; j < len; ++j) {
            for (int i = 0; i < len; ++i) {
                table.set(i, r.charAt(i) + table.get(i));
            }
            table.sort(String::compareTo);
        }
        for (String row : table) {
            if (row.endsWith(ETX)) {
                return row.substring(1, len - 1);
            }
        }
        return "";
    }

    private static String makePrintable(String s) {
        // substitute ^ for STX and | for ETX to print results
        return s.replace(STX, "^").replace(ETX, "|");
    }

    public static void main(String[] args) {
        List<String> tests = List.of(
            "banana",
            "appellee",
            "dogwood",
            "TO BE OR NOT TO BE OR WANT TO BE OR NOT?",
            "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
            "\u0002ABC\u0003"
        );
        for (String test : tests) {
            System.out.println(makePrintable(test));
            System.out.print(" --> ");
            String t = "";
            try {
                t = bwt(test);
                System.out.println(makePrintable(t));
            } catch (IllegalArgumentException e) {
                System.out.println("ERROR: " + e.getMessage());
            }
            String r = ibwt(t);
            System.out.printf(" --> %s\n\n", r);
        }
    }
}

Output:

banana
 --> |annb^aa
 --> banana

appellee
 --> |e^elplepa
 --> appellee

dogwood
 --> |do^oodwg
 --> dogwood

TO BE OR NOT TO BE OR WANT TO BE OR NOT?
 --> |?OOORREEETTRTW   BBB  ATTT   NNOOONOO^   
 --> TO BE OR NOT TO BE OR WANT TO BE OR NOT?

SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
 --> |STEXYDST.E.IXXIIXXSSMPPS.B..EE.^.USFXDIIOIIIT
 --> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

^ABC|
 --> ERROR: String cannot contain STX or ETX
 --> 

jq

Translation of: Wren

Works with: jq

Works with gojq, the Go implementation of jq

# substitute ^ for STX and | for ETX
def makePrintable:
  if . == null then null
  else sub("\u0002"; "^") | sub("\u0003"; "|")
  end;
 
def bwt:
  {stx: "\u0002", etx: "\u0003"} as $x
  | if index($x.stx) >= 0 or index($x.etx) >= 0 then null
    else $x.stx + . + $x.etx
    | . as $s
    | (reduce range(0; length) as $i ([];
         .[$i] = $s[$i:] + $s[:$i]) | sort) as $table
    | reduce range(0; length) as $i ("";
         . + $table[$i][-1:])
    end;

def ibwt:
  . as $r
  | length as $len
  | reduce range(0;$len) as $i ([]; 
        reduce range(0; $len) as $j (.;
	.[$j] = $r[$j:$j+1] + .[$j]) | sort)
  | first( .[] | select(endswith("\u0003")))
  | .[1:-1] ;

Tests

def tests:
  (
    "banana",
    "appellee",
    "dogwood",
    "TO BE OR NOT TO BE OR WANT TO BE OR NOT?",
    "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
    "\u0002ABC\u0003"
  )
  | . as $test
  | bwt as $t
  | "\(makePrintable)\n --> \($t | makePrintable
      // "ERROR: String can't contain STX or ETX" )",
    (if $t then " --> \($t | ibwt)\n" else "" end) ;

tests

Output:

banana
 --> |annb^aa
 --> banana

appellee
 --> |e^elplepa
 --> appellee

dogwood
 --> |do^oodwg
 --> dogwood

TO BE OR NOT TO BE OR WANT TO BE OR NOT?
 --> |?OOORREEETTRTW   BBB  ATTT   NNOOONOO^   
 --> TO BE OR NOT TO BE OR WANT TO BE OR NOT?

SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
 --> |STEXYDST.E.IXXIIXXSSMPPS.B..EE.^.USFXDIIOIIIT
 --> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

^ABC|
 --> ERROR: String can't contain STX or ETX

Julia

bwsort(vec) = sort(vec, lt = (a, b) -> string(a) < string(b))

function burrowswheeler_encode(s)
    if match(r"\x02|\x03", s) != nothing
        throw("String for Burrows-Wheeler input cannot contain STX or ETX")
    end
    s = "\x02" * s * "\x03"
    String([t[end] for t in bwsort([circshift([c for c in s], n) for n in 0:length(s)-1])])
end
 
function burrowswheeler_decode(s)
    len, v = length(s), [c for c in s]
    m = fill(' ', len, len)
    for col in len:-1:1
        m[:, col] .= v
        for (i, row) in enumerate(bwsort([collect(r) for r in eachrow(m)]))
            m[i, :] .= row
        end
    end
    String(m[findfirst(row -> m[row, end] == '\x03', 1:len), 2:end-1])
end

for s in ["BANANA", "dogwood", "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
    "TO BE OR NOT TO BE OR WANT TO BE OR NOT?", "Oops\x02"]
    println("Original: ", s, "\nTransformation: ", burrowswheeler_encode(s),
        "\nInverse transformation: ", burrowswheeler_decode(burrowswheeler_encode(s)), "\n")
end

Output:

Original: BANANA
Transformation: BNN�AA�A
Inverse transformation: BANANA

Original: dogwood
Transformation: �do�oodwg
Inverse transformation: dogwood

Original: SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
Transformation: TEXYDST.E.IXIXIXXSSMPPS.B..E.�.UESFXDIIOIIIT�S
Inverse transformation: SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

Original: TO BE OR NOT TO BE OR WANT TO BE OR NOT?
Transformation: OOORREEETTRTW   BBB  ATTT   NNOOONOO�   �?
Inverse transformation: TO BE OR NOT TO BE OR WANT TO BE OR NOT?

ERROR: LoadError: "String for Burrows-Wheeler input cannot contain STX or ETX"

Kotlin

Translation of: Python

// Version 1.2.60

const val STX = "\u0002"
const val ETX = "\u0003"

fun bwt(s: String): String {
    if (s.contains(STX) || s.contains(ETX)) {
        throw RuntimeException("String can't contain STX or ETX")
    }
    val ss = STX + s + ETX
    val table = Array<String>(ss.length) { ss.substring(it) + ss.substring(0, it) }
    table.sort()
    return String(table.map { it[it.lastIndex] }.toCharArray())
}

fun ibwt(r: String): String {
    val len = r.length
    val table = Array<String>(len) { "" }
    repeat(len) {
        for (i in 0 until len) {
            table[i] = r[i].toString() + table[i]
        }
        table.sort()
    }
    for (row in table) {
        if (row.endsWith(ETX)) {
            return row.substring(1, len - 1)
        }
    }
    return ""
}

fun makePrintable(s: String): String {
    // substitute ^ for STX and | for ETX to print results
    return s.replace(STX, "^").replace(ETX, "|")
}

fun main(args: Array<String>) {
    val tests = listOf(
        "banana",
        "appellee",
        "dogwood",
        "TO BE OR NOT TO BE OR WANT TO BE OR NOT?",
        "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
        "\u0002ABC\u0003"
    )
    for (test in tests) {
        println(makePrintable(test))
        print(" --> ")
        var t = ""
        try {
            t = bwt(test)
            println(makePrintable(t))
        }
        catch (ex: RuntimeException) {
            println("ERROR: " + ex.message)
        }
        val r = ibwt(t)
        println(" --> $r\n")
    }
}

Output:

banana
 --> |annb^aa
 --> banana

appellee
 --> |e^elplepa
 --> appellee

dogwood
 --> |do^oodwg
 --> dogwood

TO BE OR NOT TO BE OR WANT TO BE OR NOT?
 --> |?OOORREEETTRTW   BBB  ATTT   NNOOONOO^   
 --> TO BE OR NOT TO BE OR WANT TO BE OR NOT?

SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
 --> |STEXYDST.E.IXXIIXXSSMPPS.B..EE.^.USFXDIIOIIIT
 --> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

^ABC|
 --> ERROR: String can't contain STX or ETX
 --> 

Ksh

#!/bin/ksh

# Burrows–Wheeler transform

#	# Variables:
#
export LC_COLLATE=POSIX

STX=\^		# start marker
ETX=\|		# end marker

typeset -a str
str[0]='BANANA'
str[1]='appellee'
str[2]='dogwood'
str[3]='TO BE OR NOT TO BE OR WANT TO BE OR NOT?'
str[4]='SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES'
str[5]='|ABC^'

#	# Functions:
#

#	# Function _bwt(str, arr, lc) - sort all circular shifts of arr, return last col
#
function _bwt {
	typeset _str ; _str="$1"
	typeset _arr ; nameref _arr="$2"
	typeset _lastcol ; nameref _lastcol="$3"
	typeset _i _j _newstr ; integer _i _j

	[[ ${_str} == *+("$STX"|"$ETX")* ]] && return 1
	
	_str="$STX${_str}$ETX"
	for ((_i=0; _i<${#_str}; _i++)); do
		_newstr=${_str:${#_str}-1:1}
		for ((_j=0; _j<${#_str}-1; _j++)); do
			_newstr+=${_str:${_j}:1}
		done
		_arr+=( "${_newstr}" )
		_str="${_newstr}"
	done

	set -sA arr		# Sort arr

	for ((_i=0; _i<${#_arr[*]}; _i++)); do
		_lastcol+=${_arr[_i]:${#_arr[_i]}-1:1}
	done
}

#	# Function _ibwt(str) - inverse bwt
#
function _ibwt {
	typeset _str ; _str="$1"
	typeset _arr _vec _ret _i ; typeset -a _arr _vec ; integer _i

	_intovec "${_str}" _vec
	for ((_i=1; _i<${#_str}; _i++)); do
		_intoarr _vec _arr
		set -sA _arr
	done

	for ((_i=0; _i<${#arr[*]}; _i++)); do
		[[ "${arr[_i]}" == ${STX}*${ETX} ]] && echo "${arr[_i]}" && return
	done
}

#	# Function _intovec(str, vec) - trans str into vec[]
#
function _intovec {
	typeset _str ; _str="$1"
	typeset _vec ; nameref _vec="$2"
	typeset _i ; integer _i

	for ((_i=0; _i<${#_str}; _i++)); do
		_vec+=( "${_str:${_i}:1}" )
	done
}

#	# Function _intoarr(i, vec, arr) - insert vec into arr
#
function _intoarr {
	typeset _vec ; nameref _vec="$1"
	typeset _arr ; nameref _arr="$2"
	typeset _j ; integer _j

	for ((_j=0; _j<${#_vec[*]}; _j++)); do
		_arr="${_vec[_j]}${_arr[_j]}"
	done
}

 ######
# main #
 ######

for ((i=0; i<${#str[*]}; i++)); do
	unset arr lastcol result ; typeset -a arr

	print -- "${str[i]}"
	_bwt "${str[i]}" arr lastcol
	(( $? )) && print "ERROR: string cannot contain $STX or $ETX" && continue

	print -- "${lastcol}"
	result=$(_ibwt "${lastcol}")
	print -- "${result}"
	echo
done

Output:

BANANA
BNN^AA|A
^BANANA|
appellee
|^lpelepae
^appellee|
dogwood
|^ooodwgd
^dogwood|
TO BE OR NOT TO BE OR WANT TO BE OR NOT?
OOORREEETTRTW   BBB  ATTT   NNOOONOO^   |?
^TO BE OR NOT TO BE OR WANT TO BE OR NOT?|
SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
TEXYDST.E.IXIXIXXSSMPPS.B..E.^.UESFXDIIOIIIT|S
^SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES|
|ABC^

ERROR: string cannot contain ^ or |

Lua

Translation of: Java

STX = string.char(tonumber(2,16))
ETX = string.char(tonumber(3,16))

function bwt(s)
    if s:find(STX, 1, true) then
        error("String cannot contain STX")
    end
    if s:find(ETX, 1, true) then
        error("String cannot contain ETX")
    end

    local ss = STX .. s .. ETX
    local tbl = {}
    for i=1,#ss do
        local before = ss:sub(i + 1)
        local after = ss:sub(1, i)
        table.insert(tbl, before .. after)
    end

    table.sort(tbl)

    local sb = ""
    for _,v in pairs(tbl) do
        sb = sb .. string.sub(v, #v, #v)
    end

    return sb
end

function ibwt(r)
    local le = #r
    local tbl = {}

    for i=1,le do
        table.insert(tbl, "")
    end
    for j=1,le do
        for i=1,le do
            tbl[i] = r:sub(i,i) .. tbl[i]
        end
        table.sort(tbl)
    end

    for _,row in pairs(tbl) do
        if row:sub(le,le) == ETX then
            return row:sub(2, le - 1)
        end
    end

    return ""
end

function makePrintable(s)
    local a = s:gsub(STX, '^')
    local b = a:gsub(ETX, '|')
    return b
end

function main()
    local tests = {
        "banana",
        "appellee",
        "dogwood",
        "TO BE OR NOT TO BE OR WANT TO BE OR NOT?",
        "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
        STX .. "ABC" .. ETX
    }

    for _,test in pairs(tests) do
        print(makePrintable(test))
        io.write(" --> ")
        local t = ""
        if xpcall(
            function () t = bwt(test) end,
            function (err) print("ERROR: " .. err) end
        ) then
            print(makePrintable(t))
        end
        local r = ibwt(t)
        print(" --> " .. r)
        print()
    end
end

main()

Output:

banana
 --> |annb^aa
 --> banana

appellee
 --> |e^elplepa
 --> appellee

dogwood
 --> |do^oodwg
 --> dogwood

TO BE OR NOT TO BE OR WANT TO BE OR NOT?
 --> |?OOORREEETTRTW   BBB  ATTT   NNOOONOO^
 --> TO BE OR NOT TO BE OR WANT TO BE OR NOT?

SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
 --> |STEXYDST.E.IXXIIXXSSMPPS.B..EE.^.USFXDIIOIIIT
 --> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

^ABC|
 --> ERROR: bwt.lua:6: String cannot contain STX
 -->

Mathematica / Wolfram Language

ClearAll[BurrowWheeler, InverseBurrowWheeler]
BurrowWheeler[sin_String, {bdelim_, edelim_}] := Module[{s},
  s = Characters[bdelim <> sin <> edelim];
  s = RotateLeft[s, #] & /@ Range[Length[s]];
  StringJoin[LexicographicSort[s][[All, -1]]]
  ]
InverseBurrowWheeler[sin_String, {bdelim_, edelim_}] := Module[{s, chars},
  chars = Characters[sin];
  s = ConstantArray[{}, Length[chars]];
  Do[
   s = LexicographicSort[MapThread[Prepend, {s, chars}]];
   ,
   {Length[chars]}
   ];
  StringTake[StringJoin[SelectFirst[s, Last /* EqualTo[edelim]]], {2, -2}]
  ]
BurrowWheeler["BANANA", {"^", "|"}]
InverseBurrowWheeler[%, {"^", "|"}]
BurrowWheeler["appellee", {"^", "|"}]
InverseBurrowWheeler[%, {"^", "|"}]
BurrowWheeler["dogwood", {"^", "|"}]
InverseBurrowWheeler[%, {"^", "|"}]

Output:

|ANNB^AA
BANANA
|e^elplepa
appellee
|do^oodwg
dogwood

Nim

Translation of the Wikipedia Python algorithm. The program uses characters '¹' and '²' to display STX and ETX.

import algorithm
from sequtils import repeat
import strutils except repeat

const
  Stx = '\2'
  Etx = '\3'

#---------------------------------------------------------------------------------------------------

func bwTransform*(s: string): string =
  ## Apply Burrows–Wheeler transform to input string.

  doAssert(Stx notin s and Etx notin s, "Input string cannot contain STX and ETX characters")

  let s = Stx & s & Etx  # Add start and end of text marker.

  # Build the table of rotated strings and sort it.
  var table = newSeqOfCap[string](s.len)
  for i in 0..s.high:
    table.add(s[i + 1..^1] & s[0..i])
  table.sort()

  # Extract last column of the table.
  for item in table:
    result.add(item[^1])

#---------------------------------------------------------------------------------------------------

func invBwTransform*(r: string): string =
  ## Apply inverse Burrows–Wheeler transform.

  # Build table.
  var table = repeat("", r.len)
  for _ in 1..r.len:
    for i in 0..<r.len:
      table[i] = r[i] & table[i]
    table.sort()

  # Find the correct row (ending in ETX).
  var idx = 0
  while not table[idx].endsWith(Etx):
    inc idx
  result = table[idx][1..^2]


#———————————————————————————————————————————————————————————————————————————————————————————————————

when isMainModule:

  proc displaybleString(s: string): string =
    ## Build a displayable string from a string containing STX and ETX characters.

    s.multiReplace(("\2", "¹"), ("\3", "²"))

  for text in ["banana",
               "appellee",
               "dogwood",
               "TO BE OR NOT TO BE OR WANT TO BE OR NOT?",
               "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES"]:
    let transformed = text.bwTransform()
    let invTransformed = transformed.invBwTransform()

    echo ""
    echo "Original text:                ", text
    echo "After transformation:         ", transformed.displaybleString()
    echo "After inverse transformation: ", invTransformed

Output:

Original text:                banana
After transformation:         ²annb¹aa
After inverse transformation: banana

Original text:                appellee
After transformation:         ²e¹elplepa
After inverse transformation: appellee

Original text:                dogwood
After transformation:         ²do¹oodwg
After inverse transformation: dogwood

Original text:                TO BE OR NOT TO BE OR WANT TO BE OR NOT?
After transformation:         ²?OOORREEETTRTW   BBB  ATTT   NNOOONOO¹   
After inverse transformation: TO BE OR NOT TO BE OR WANT TO BE OR NOT?

Original text:                SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
After transformation:         ²STEXYDST.E.IXXIIXXSSMPPS.B..EE.¹.USFXDIIOIIIT
After inverse transformation: SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

Pascal

A console program in Free Pascal, created with the Lazarus IDE. It doesn't use special characters, but records the encoded string along with an index to enable decoding (as in the original paper by Burrows and Wheeler).

The first character in a Pascal string has index 1, but it's more convenient to describe the algorithm in terms of zero-based indices. The constant STR_BASE = 1 is used to make it clear where Pascal usage has been taken into account.

program BurrowsWheeler;

{$mode objfpc}{$H+}  // Lazarus default mode; long strings
uses SysUtils;       // only for console output
const STR_BASE = 1;  // first character in a Pascal string has index [1].
type TComparison = -1..1;

procedure Encode( const input : string;
                  out encoded : string;
                  out index : integer);
var
  n : integer;
  perm : array of integer;
  i, j, k : integer;
  incr, v : integer;

        // Subroutine to compare rotations whose *last* letters have zero-based
        //  indices a, b. Returns 1, 0, -1 according as the rotation ending at a
        //  is >, =, < the rotation ending at b.
        function CompareRotations( a, b : integer) : TComparison;
        var
          p, q, nrNotTested : integer;
        begin
          result := 0;
          p := a;
          q := b;
          nrNotTested := n;
          repeat
            inc(p); if (p = n) then p := 0;
            inc(q); if (q = n) then q := 0;
            if (input[p + STR_BASE] = input[q + STR_BASE]) then dec( nrNotTested)
            else if (input[p + STR_BASE] > input[q + STR_BASE]) then result := 1
            else result := -1
          until (result <> 0) or (nrNotTested = 0);
        end;
begin
  n := Length( input);
  SetLength( perm, n);
  for j := 0 to n - 1 do perm[j] := j;

  // Sort string indices by comparing the associated rotations, as above.
  // This is a Shell sort from Press et al., Numerical Recipes, 3rd edn, pp 422-3.
  // Other sorting algorithms might be used.
  incr := 1;
  repeat
    incr := 3*incr + 1
  until (incr >= n);
  repeat
    incr := incr div 3;
    for i := incr to n - 1 do begin
      v := perm[i];
      j := i;
      while (j >= incr) and (CompareRotations( perm[j - incr], v) = 1) do begin
        perm[j] := perm[j - incr];
        dec( j, incr);
      end;
      perm[j] := v;
    end; // for
  until (incr = 1);

  // Apply the sorted array to create the output.
  SetLength( encoded, n);
  for j := 0 to n - 1 do begin
    k := perm[j];
    encoded[j + STR_BASE] := input[k + STR_BASE];
    if (k = n - 1) then index := j;
  end;
end;

{------------------------------------------------------------------------------
Given an encoded string and the associated index, one way to rebuild
the original string is to do the following, or its equivalent:

Given        Make an array     Sort the array    Rebuild the original string
'NNBAAA'     [0] = ('N', 0)    [0] = ('A', 3)    Start with given index 3
index = 3    [1] = ('N', 1)    [1] = ('A', 4)    [3] gives 'B', next index = 2
             [2] = ('B', 2)    [2] = ('A', 5)    [2] gives 'A', next index = 5
             [3] = ('A', 3)    [3] = ('B', 2)    [5] gives 'N', next index = 1
             [4] = ('A', 4)    [4] = ('N', 0)    [1] gives 'A', next index = 4
             [5] = ('A', 5)    [5] = ('N', 1)    [4] gives 'N', next index = 0
                                                 [0] gives 'A', next index = 3
                                                 3 = start index, so stop
                                                 Result = 'BANANA'

If the original string consists of two or more repetitions of a substring,
  the above method will stop when that substring has been built, e.g.
  'CANCAN' will stop at 'CAN'.
We therefore need to test for the rebuilt string being too short, and if so
  make enough copies of the decoded part to fill the required length.

It's possible to take the above description literally, and write a decoding
  routine that uses a record type consisting of a character and an integer.
A more efficient way is to create an integer array containing only the indices,
  in the above example (3, 4, 5, 2, 0, 1). A first pass counts the occurrences
  of each character in the encoded string. If the character set is ['A'..'Z']
  then the indices associated with 'A' are stored from [0]. If 'A' occurs a times,
  the indices associated with 'B' are stored from [a]; if 'B' occurs b times,
  the indices associated with 'C' are stored from [a + b]; and so on.
}
function Decode( encoded : string;
                 index : integer) : string;
var
  charInfo : array [char] of integer;
  perm : array of integer;
  n, j, k : integer;
  c : char;
  total, prev : integer;

begin
  n := Length( encoded);
  // An empty encoded string will crash the code below, so trap it here.
  if (n = 0) then begin
    result := '';
    exit;
  end;

  // Count the occurrences of each possible character.
  for c := Low(char) to High(char) do charInfo[c] := 0;
  for j := 0 to n - 1 do begin
    c := encoded[j + STR_BASE];
    inc( charInfo[c]);
  end;

  // Cumulate, i.e. charInfo[k] := sum of old charInfo from 0 to k - 1
  total := 0;
  prev := 0;
  for c := Low(char) to High(char) do begin
    inc( total, prev);
    prev := CharInfo[c];
    charInfo[c] := total;
  end;

  // Make the array "perm"
  SetLength( perm, n);
  for j := 0 to n - 1 do begin
    c := encoded[j + STR_BASE];
    k := charInfo[c];
    perm[k] := j;
    inc( charInfo[c]);
  end;

  // Apply the array "perm" to re-create the original string.
  SetLength( result, n);
  k := 0; // index into result
  j := index;
  repeat
    j := perm[j];
    result[k + STR_BASE] := encoded[j + STR_BASE];
    inc(k);
  until (j = index);

  // If the original consisted of M repetitions of the same string, then
  //   at this point exactly 1/M of the result has been filled in.
  // For M > 1 (shown by k < n), complete the result by copying the first part.
  if (k < n) then begin
    Assert( n mod k = 0); // we should have n = M*k
    for j := k to n - 1 do result[j + STR_BASE] := result[j - k + STR_BASE];
  end;
end;

procedure Test( const s : string);
var
  encoded, decoded : string;
  index : integer;
begin
  WriteLn( '');
  WriteLn( '     ' + s);
  Encode( s, {out} encoded, index);
  WriteLn( '---> ' + encoded);
  WriteLn( '       index = ' + SysUtils.IntToStr( index));
  decoded := Decode( encoded, index);
  WriteLn( '---> ' + decoded);
end;

begin
  Test( 'BANANA');
  Test( 'CANAAN');
  Test( 'CANCAN');
  Test( 'appellee');
  Test( 'dogwood');
  Test( 'TO BE OR NOT TO BE OR WANT TO BE OR NOT?');
  Test( 'SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES');
end.

Output:

     BANANA
---> NNBAAA
       index = 3
---> BANANA

     CANAAN
---> NCANAA
       index = 3
---> CANAAN

     CANCAN
---> CCNNAA
       index = 2
---> CANCAN

     appellee
---> eelplepa
       index = 0
---> appellee

     dogwood
---> odoodwg
       index = 1
---> dogwood

     TO BE OR NOT TO BE OR WANT TO BE OR NOT?
---> OOORREEETTRTW   BBB  ATTT   NNOOONOO?
       index = 36
---> TO BE OR NOT TO BE OR WANT TO BE OR NOT?

     SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
---> TEXYDST.E.IXIXIXXSSMPPS.B..E.S.EUSFXDIIOIIIT
       index = 29
---> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

Perl

Translation of: Raku

use utf8;
binmode STDOUT, ":utf8";

use constant STX => '👍 ';

sub transform {
    my($s) = @_;
    my($t);
    warn "String can't contain STX character." and exit if $s =~ /STX/;
    $s = STX . $s;
    $t .= substr($_,-1,1) for sort map { rotate($s,$_) } 1..length($s);
    return $t;
}

sub rotate { my($s,$n) = @_; join '', (split '', $s)[$n..length($s)-1, 0..$n-1] }

sub ɯɹoɟsuɐɹʇ {
    my($s) = @_;
    my @s = split '', $s;
    my @t = sort @s;
    map { @t = sort map { $s[$_] . $t[$_] } 0..length($s)-1 } 1..length($s)-1;
    for (@t) {
        next unless /${\(STX)}$/;  # interpolate the constant
        chop $_ and return $_
    }
}

for $phrase (qw<BANANA dogwood SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES>,
    'TO BE OR NOT TO BE OR WANT TO BE OR NOT?') {
    push @res, 'Original:            '. $phrase;
    push @res, 'Transformed:         '. transform $phrase;
    push @res, 'Inverse transformed: '. ɯɹoɟsuɐɹʇ transform $phrase;
    push @res, '';
}

print join "\n", @res;

Output:

Original:            BANANA
Transformed:         BNN👍 AAA
Inverse transformed: BANANA

Original:            dogwood
Transformed:         👍 ooodwgd
Inverse transformed: dogwood

Original:            SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
Transformed:         TEXYDST.E.IXIXIXXSSMPPS.B..E.👍 .UESFXDIIOIIITS
Inverse transformed: SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

Original:            TO BE OR NOT TO BE OR WANT TO BE OR NOT?
Transformed:         OOORREEETTRTW   BBB  ATTT   NNOOONOO👍    ?
Inverse transformed: TO BE OR NOT TO BE OR WANT TO BE OR NOT?

Phix

An efficient implementation, based mainly on http://spencer-carroll.com/an-easy-to-understand-explanation-of-the-burrows-wheeler-transform/
Takes around about ten seconds to transform and invert a 100K string. Note: requires 0.8.0+

-- demo\rosetta\burrows_wheeler.exw
--/*
The traditional method:

    7 banana$           $banana 6
    6 $banana   ===>    a$banan 5
    5 a$banan           ana$ban 3
    4 na$bana   sort    anana$b 1
    3 ana$ban           banana$ 7
    2 nana$ba   ===>    na$bana 4
    1 anana$b           nana$ba 2
                              ^ desired answer == "annb$aa"

First ignore the numbers: the desired answer is found by creating a table of all
rotations of "banana$", sorting it, and then extracting the right-hand column. 

However, there is no need to actually create such a table, which could be very
expensive for long strings, instead just number them logically (admittedly that
was somewhat arbitrarily chosen to get the indexes to work out nicely, I picked
the original index of the last character), and perform a custom sort on those.

The latter effectively just recreates the rotations one character at a time until 
there is a mismatch (which there always will be since there is only one $). 
The left hand column is my arbitrary numbering scheme and the right hand column 
is those sorted into order, which is also the indexes to the original string of
the characters that we want.

The code below uses $ as the terminator, but eg 1 (== '\#01') should be fine,
except of course for the display of that on a console.
--*/
with javascript_semantics
constant terminator = '$'

function rot_sort(integer i,j, sequence s)
-- i,j are indexes of the last character, so bump before first compare.
-- eg/ie rot_sort(i,j,s) should yield compare(rotate(s,i),rotate(s,j)), 
--       as in rot_sort(7,6,"banana$") == compare("banana$","$banana")
--       - but one character at a time rather than constructing both.
    integer l = length(s)
    while true do
        i = mod(i,l)+1
        j = mod(j,l)+1
        integer c = compare(s[i],s[j])
        if c!=0 then return c end if
    end while
end function

function burrows_wheeler_transform(string s)
    if find(terminator,s) then return "error" end if
    s &= terminator
    integer l = length(s)
    sequence t = custom_sort(routine_id("rot_sort"),tagset(l),{s})
    string res = repeat(' ',l)
    for i=1 to l do
        res[i] = s[t[i]]
    end for
    return res
end function

--/*
Inversion. The traditional method is add column and sort, seven times,
to reconstruct the table above, then pick the entry that ends with the
marker. Showing that technique in full detail here is not helpful, and
like above that would be hideously inefficient for large strings.

                $banana         1  $ (1 ) a  2
                a$banan         2  a ( 1) n  6
                ana$ban         3  a ( 2) n  7
                anana$b         4  a ( 3) b  5
                banana$         5  b      $  1
                na$bana         6  n (2 ) a  3
                nana$ba         7  n (3 ) a  4
                ^     ^            ^      ^  ^
                f     l            f      l  t

However, we already have the last column, and the first is just that 
sorted alphabetically, and with just those two, we have all possible
character pairings of the original message. The trick is in figuring 
out how to stitch them together in the right order. If you carefully
study the three that end in a, and the three that start in a, notice
the $banan,na$ban,nana$b parts are sorted in the same order, whether 
they are prefixed with a or not. That is, the middle (parenthesised)
matching numbers are both 123, not 123 and say 231. It is quite hard
to see that being useful, but eventually the penny should drop. The
right-hand 1 with an a rotated right gives the left-hand 1, and the
same goes for 2 and 3: they are in fact links to the prior pairing.

In other words the first a in l always corresponds to the first in f,
the second to the second, and so on, and that (amazingly) forms the
order in which the pairings need to be daisy-chained together.

Try following (1->)2a->6n->3a->7n->4a->5b->$, == reverse("banana"),
in the above f and t tables.

The code below builds a queue of 'a' ({1,6,7}, built backwards) then
we pop {2,3,4} into those slots in t as we find 'a' in f, likewise
for all other letters, forming the links for each pairing as shown.
See the trivial step 3 scan below, then go back and stare at f and
t as shown above, and once again, eventually the penny should drop.
I will admit I had to read ten or so explanations before I got it.
--*/

function inverse_burrows_wheeler(string s)
    if find('\0',s) then ?9/0 end if -- (doable, but needs some +1s)
    integer l = length(s), c
    string f = sort(s)
    sequence q = repeat(0,256), -- queue heads (per char)
             x = repeat(0,l),   -- queue links
             t = repeat(0,l)    -- reformed/pairing links
    -- Step 1. discover/build queues (backwards)
    for i=l to 1 by -1 do
        c = s[i]
        x[i] = q[c]
        q[c] = i
    end for     
    -- Step 2. reform/pop char queues into pairing links
    for i=1 to l do
        c = f[i]
        t[q[c]] = i
        q[c] = x[q[c]]
    end for
    -- Step 3. rebuild (backwards)
    c = find(terminator,f)
    if c=0 then return "error" end if
    string res = repeat(' ',l-1)
    for i=l-1 to 1 by -1 do
        c = t[c]        -- (first time in, skip the end marker)
        res[i] = f[c]
    end for
    return res
end function

procedure test(string src)
string enc = burrows_wheeler_transform(src),
       dec = inverse_burrows_wheeler(enc)
    src = shorten(src,"characters")
    enc = shorten(enc,"characters")
    dec = shorten(dec,"characters")
    printf(1,"original: %s --> %s\n inverse: %s\n",{src,enc,dec})
end procedure

test("banana")
test("dogwood")
test("TO BE OR NOT TO BE OR WANT TO BE OR NOT?")
test("SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES")

Output:

original: banana --> annb$aa
 inverse: banana
original: dogwood --> do$oodwg
 inverse: dogwood
original: TO BE OR NOT TO BE OR WANT TO BE OR NOT? --> OOORREEETTR?TW   BBB  ATTT   NNOOONOO$
 inverse: TO BE OR NOT TO BE OR WANT TO BE OR NOT?
original: SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES --> STEXYDST.E.IXXIIXXSSMPPS.B..EE.$.USFXDIIOIIIT
 inverse: SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

Python

This Python implementation sacrifices speed for simplicity: the program is short, but takes more than the linear time that would be desired in a practical implementation.

Using the STX/ETX control codes to mark the start and end of the text, and using s[i:] + s[:i] to construct the ith rotation of s, the forward transform takes the last character of each of the sorted rows. The inverse transform repeatedly inserts r as the left column of the table and sorts the table. After the whole table is built, it returns the row that ends with ETX, minus the STX and ETX. Ref: Burrows Wheeler Transform in Python

def bwt(s):
    """Apply Burrows-Wheeler transform to input string."""
    assert "\002" not in s and "\003" not in s, "Input string cannot contain STX and ETX characters"
    s = "\002" + s + "\003"  # Add start and end of text marker
    table = sorted(s[i:] + s[:i] for i in range(len(s)))  # Table of rotations of string
    last_column = [row[-1:] for row in table]  # Last characters of each row
    return "".join(last_column)  # Convert list of characters into string


def ibwt(r):
    """Apply inverse Burrows-Wheeler transform."""
    table = [""] * len(r)  # Make empty table
    for i in range(len(r)):
        table = sorted(r[i] + table[i] for i in range(len(r)))  # Add a column of r
    s = [row for row in table if row.endswith("\003")][0]  # Find the correct row (ending in ETX)
    return s.rstrip("\003").strip("\002")  # Get rid of start and end markers

Raku

(formerly Perl 6)

Works with: Rakudo version 2018.06

# STX can be any character that doesn't appear in the text.
# Using a visible character here for ease of viewing. 
 
constant \STX = '👍';

# Burrows-Wheeler transform
sub transform (Str $s is copy) {
    note "String can't contain STX character." and exit if $s.contains: STX;
    $s = STX ~ $s;
    (^$s.chars).map({ $s.comb.list.rotate: $_ }).sort[*;*-1].join
}
 
# Burrows-Wheeler inverse transform
sub ɯɹoɟsuɐɹʇ (Str $s) {
    my @t = $s.comb.sort;
    @t = ($s.comb Z~ @t).sort for 1..^$s.chars;
    @t.first( *.ends-with: STX ).chop
}
 
# TESTING
for |<BANANA dogwood SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES>,
    'TO BE OR NOT TO BE OR WANT TO BE OR NOT?', "Oops{STX}"
    -> $phrase {
    say 'Original:            ', $phrase;
    say 'Transformed:         ', transform $phrase;
    say 'Inverse transformed: ', ɯɹoɟsuɐɹʇ transform $phrase;
    say '';
}

Output:

Original:            BANANA
Transformed:         BNN👍AAA
Inverse transformed: BANANA

Original:            dogwood
Transformed:         👍ooodwgd
Inverse transformed: dogwood

Original:            SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
Transformed:         TEXYDST.E.IXIXIXXSSMPPS.B..E.👍.UESFXDIIOIIITS
Inverse transformed: SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

Original:            TO BE OR NOT TO BE OR WANT TO BE OR NOT?
Transformed:         OOORREEETTRTW   BBB  ATTT   NNOOONOO👍   ?
Inverse transformed: TO BE OR NOT TO BE OR WANT TO BE OR NOT?

Original:            Oops👍
String can't contain STX character.

REXX

Programming note:   a little bit of code was added to support more (legal) characters in the input string for the BWT
function.   The error recovery and error messages are rudimentary when an illegal character in the input is detected.

/*REXX program performs a  Burrows─Wheeler transform  (BWT)  on a character string(s).  */
$.=                                              /*the default text for (all) the inputs*/
parse arg $.1                                    /*obtain optional arguments from the CL*/
if $.1=''  then do;  $.1= "banana"               /*Not specified?  Then use the defaults*/
                     $.2= "BANANA"
                     $.3= "appellee"
                     $.4= "dogwood"
                     $.5= "TO BE OR NOT TO BE OR WANT TO BE OR NOT?"
                     $.6= "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES"
                     $.7= "^ABC|"
                     $.7= "bad─bad thingy"'fd'x  /* ◄─── this string can't be processed.*/
                end
                                                 /* [↑]  show blank line between outputs*/
       do t=1  while $.t\='';  if t\==1 then say /*process each of the inputs (or input)*/
       out=  BWT($.t)                            /*invoke the  BWT  function, get result*/
       ori= iBWT(out)                            /*   "    "  iBWT      "      "     "  */
       say '   input ───► '   $.t                /*display    input      string to term.*/
       say '  output ───► '   out                /*   "       output        "    "   "  */
       say 'original ───► '   ori                /*   "    reconstituted    "    "   "  */
       end    /*t*/
exit                                             /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
BWT:   procedure expose ?.; parse arg y,,$       /*obtain the input;  nullify $ string. */
       ?.1= 'fd'x;          ?.2= "fc"x           /*assign the  STX  and  ETX  strings.  */
          do i=1  for 2                          /* [↓]  check for invalid input string.*/
          _= verify(y, ?.i, 'M');  if _==0  then iterate;        er= '***error***  BWT: '
          say er "invalid input: "    y
          say er 'The input string contains an invalid character at position' _"."; exit _
          end   /*i*/                            /* [↑]  if error,  perform a hard exit.*/
       y= ?.1 || y || ?.2;      L= length(y)     /*get the input & add a fence; gel len.*/
       @.1= y;                  m= L - 1         /*define the first element of the table*/
                    do j=2  for m;        _= j-1 /*now, define the rest of the elements.*/
                    @.j= right(@._,1)left(@._,m) /*construct a table from the  Y  input.*/
                    end   /*j*/                  /* [↑]  each element: left & right part*/
       call cSort L                              /*invoke lexicographical sort for array*/
                    do k=1  for L                /* [↓]  construct the answer from array*/
                    $= $  ||  right(@.k, 1)      /*build the answer from each of  ···   */
                    end   /*k*/                  /* ··· the array's right─most character*/
       return $                                  /*return the constructed answer.       */
/*──────────────────────────────────────────────────────────────────────────────────────*/
iBWT:  procedure expose ?.; parse arg y,,@.      /*obtain the input;  nullify @. string.*/
       L= length(y)                              /*compute the length of the input str. */
                   do   j=1  for L               /* [↓]  step through each input letters*/
                     do k=1  for L               /* [↓]  step through each row of table.*/
                     @.k= substr(y, k, 1) || @.k /*construct a row of the table of chars*/
                     end   /*k*/                 /* [↑]  order of table row is inverted.*/
                   call cSort L                  /*invoke lexicographical sort for array*/
                   end    /*j*/                  /* [↑]  answer is the penultimate entry*/
         do #=1
         if right(@.#, 1)==?.2  then return substr(@.#, 2, L-2)  /*return correct result*/
         end   /*#*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
cSort: procedure expose @.;  parse arg n;  m=n-1 /*N: is the number of @ array elements.*/
           do m=m  for m  by -1  until ok;  ok=1 /*keep sorting the  @ array until done.*/
             do j=1  for m;  k= j+1;   if @.j<<=@.k  then iterate   /*elements in order?*/
             _= @.j;  @.j= @.k;  @.k= _;   ok= 0 /*swap two elements;  flag as not done.*/
             end   /*j*/
           end     /*m*/;       return

output   when using the default inputs:

   input ───►  banana
  output ───►  bnn²aaaⁿ
original ───►  banana

   input ───►  BANANA
  output ───►  BNN²AAAⁿ
original ───►  BANANA

   input ───►  appellee
  output ───►  ²lpelepaeⁿ
original ───►  appellee

   input ───►  dogwood
  output ───►  ²ooodwgdⁿ
original ───►  dogwood

   input ───►  TO BE OR NOT TO BE OR WANT TO BE OR NOT?
  output ───►  OOORREEETTRTW   BBB  ATTT   NNOOONOO²   ?ⁿ
original ───►  TO BE OR NOT TO BE OR WANT TO BE OR NOT?

   input ───►  SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
  output ───►  TEXYDST.E.IXIXIXXSSMPPS.B..E.².UESFXDIIOIIITSⁿ
original ───►  SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

***error***  BWT:  invalid input:  bad─bad thingy²
***error***  BWT:  The input string contains an invalid character at position 15.

RPL

Works with: HP version 28

SORT is defined at Sorting algorithms/Bubble sort

RPL code

Comment

≪ { } SWAP 1 OVER SIZE FOR j SWAP OVER + SWAP DUP 2 OVER SIZE SUB SWAP 1 1 SUB + NEXT DROP ≫ ‘→BWtable’ STO ≪ DUP →BWtable SORT → string table ≪ table string POS "" 1 string SIZE FOR j IF OVER j == THEN 142 CHR + END table j GET DUP SIZE DUP SUB + NEXT SWAP DROP ≫ ≫ '→BWT' STO ≪ DUP 142 CHR POS IF DUP 2 < THEN "" ELSE DUP2 1 SWAP OVER - SUB END ROT 3 PICK 1 + OVER SIZE SUB + ≫ ‘IdxStr’ STO ≪ IdxStr → idx BWstr ≪ { } 1 BWstr SIZE START "" + NEXT 'TBL' STO 1 BWstr SIZE FOR j 1 BWstr SIZE FOR k BWstr k DUP SUB 'TBL' k GET + 'TBL' k ROT PUT NEXT TBL SORT 'TBL' STO NEXT 'TBL' idx GET 'TBL' PURGE ≫ ≫ ‘BWT→’ STO

→BWtable ( "string" → { "string" "trings" ... "gstrin" ) initialize stack and loop n=len(string) times add string to table string = string[2..n]+string[1} clean stack →BWT ( "string" → "transformed" ) store input string and table to speed up execution get position of string in table loop to create transformed string: if table[j]=string then add index to output string add last character of table[j] clean stack IdxStr ( "str←ing" → index "string" ) if ← not at string beginning get chars before get chars after and concatenate →BWT ( "str←ing" → "transformed" ) get index and store initialize table as a global variable loop len(string) times add kth char of string to kth table item sort table clean RAM return appropriate string

"banana" →BWT
DUP BWT→

Transforming "banana" takes 1.5 seconds on a basic HP-28S, but almost 15 for the inverse transform. The wikipedia example ("SIX MIXED...BOXES") takes resp. 41 seconds to transform and... 47 minutes to inverse.

Output:

2: "nnb←aaa"
1: "banana"

Ruby

Translation of: C#

STX = "\u0002"
ETX = "\u0003"

def bwt(s)
    for c in s.split('')
        if c == STX or c == ETX then
            raise ArgumentError.new("Input can't contain STX or ETX")
        end
    end

    ss = ("%s%s%s" % [STX, s, ETX]).split('')
    table = []
    for i in 0 .. ss.length - 1
        table.append(ss.join)
        ss = ss.rotate(-1)
    end

    table = table.sort
    return table.map{ |e| e[-1] }.join
end

def ibwt(r)
    len = r.length
    table = [""] * len
    for i in 0 .. len - 1
        for j in 0 .. len - 1
            table[j] = r[j] + table[j]
        end
        table = table.sort
    end
    for row in table
        if row[-1] == ETX then
            return row[1 .. -2]
        end
    end
    return ""
end

def makePrintable(s)
    s = s.gsub(STX, "^")
    return s.gsub(ETX, "|")
end

def main
    tests = [
        "banana",
        "appellee",
        "dogwood",
        "TO BE OR NOT TO BE OR WANT TO BE OR NOT?",
        "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
        "\u0002ABC\u0003"
    ]
    for test in tests
        print makePrintable(test), "\n"
        print " --> "

        begin
            t = bwt(test)
            print makePrintable(t), "\n"

            r = ibwt(t)
            print " --> ", r, "\n\n"
        rescue ArgumentError => e
            print e.message, "\n"
            print " -->\n\n"
        end
    end
end

main()

Output:

banana
 --> |annb^aa
 --> banana

appellee
 --> |e^elplepa
 --> appellee

dogwood
 --> |do^oodwg
 --> dogwood

TO BE OR NOT TO BE OR WANT TO BE OR NOT?
 --> |?OOORREEETTRTW   BBB  ATTT   NNOOONOO^
 --> TO BE OR NOT TO BE OR WANT TO BE OR NOT?

SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
 --> |STEXYDST.E.IXXIIXXSSMPPS.B..EE.^.USFXDIIOIIIT
 --> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

^ABC|
 --> Input can't contain STX or ETX
 -->

Rust

use core::cmp::Ordering;

const STX: char = '\u{0002}';
const ETX: char = '\u{0003}';

// this compare uses simple alphabetical sort, but for the special characters (ETX, STX)
// it sorts them later than alphanumeric characters
pub fn special_cmp(lhs: &str, rhs: &str) -> Ordering {
    let mut iter1 = lhs.chars();
    let mut iter2 = rhs.chars();

    loop {
        match (iter1.next(), iter2.next()) {
            (Some(lhs), Some(rhs)) => {
                if lhs != rhs {
                    let is_lhs_special = lhs == ETX || lhs == STX;
                    let is_rhs_special = rhs == ETX || rhs == STX;

                    let result = if is_lhs_special == is_rhs_special {
                        lhs.cmp(&rhs)
                    } else if is_lhs_special {
                        Ordering::Greater
                    } else {
                        Ordering::Less
                    };

                    return result;
                }
            }
            (Some(_), None) => return Ordering::Greater,
            (None, Some(_)) => return Ordering::Less,
            (None, None) => return lhs.cmp(&rhs),
        }
    }
}

fn burrows_wheeler_transform(input: &str) -> String {
    let mut table: Vec<String> = vec![];

    // add markers for the start and end
    let input_string = format!("{}{}{}", STX, input, ETX);

    // create all possible rotations
    for (i, _) in input_string.char_indices() {
        table.push(format!(
            "{}{}",
            &input_string[input_string.len() - 1 - i..],
            &input_string[0..input_string.len() - 1 - i]
        ));
    }

    // sort rows alphabetically
    table.sort_unstable_by(|lhs, rhs| special_cmp(&lhs, &rhs));

    // return the last column
    table
        .iter()
        .map(|s| s.chars().nth_back(0).unwrap())
        .collect::<String>()
}

fn inverse_burrows_wheeler_transform(input: &str) -> String {
    let mut table: Vec<String> = vec![String::new(); input.len()];
    for _ in 0..input.len() {
        // insert the charatcers of the encoded input as a first column for each row
        for (j, s) in table.iter_mut().enumerate() {
            *s = format!("{}{}", input.chars().nth(j).unwrap(), s);
        }

        // sort rows alphabetically
        table.sort_unstable_by(|lhs, rhs| special_cmp(&lhs, &rhs));
    }

    // return the row which has the end marker at the last position
    table
        .into_iter()
        .filter(|s| s.ends_with(ETX))
        .collect::<String>()
        // remove start and markers
        .replace(STX, "")
        .replace(ETX, "")
}

fn main() {
    let input = [
        "banana",
        "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
        "TO BE OR NOT TO BE OR WANT TO BE OR NOT?",
    ];
    for s in input.iter() {
        let bwt = burrows_wheeler_transform(s);
        let ibwt = inverse_burrows_wheeler_transform(&bwt);
        println!("Input: {}", s);
        println!("\tBWT: {}", bwt.replace(STX, "^").replace(ETX, "|"));
        println!("\tInverse BWT: {}", ibwt);
    }
}

Output:

Input: banana
        BWT: bnn^aa|a
        Inverse BWT: banana
Input: SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
        BWT: TEXYDST.E.IXIXIXXSSMPPS.B..E.^.UESFXDIIOIIIT|S
        Inverse BWT: SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
Input: TO BE OR NOT TO BE OR WANT TO BE OR NOT?
        BWT: OOORREEETTRTW   BBB  ATTT   NNOOONOO^   |?
        Inverse BWT: TO BE OR NOT TO BE OR WANT TO BE OR NOT?

Scala

Translation of: Kotlin

import scala.collection.mutable.ArrayBuffer

object BWT {
  val STX = '\u0002'
  val ETX = '\u0003'

  def bwt(s: String): String = {
    if (s.contains(STX) || s.contains(ETX)) {
      throw new RuntimeException("String can't contain STX or ETX")
    }
    var ss = STX + s + ETX
    var table = new ArrayBuffer[String]()
    (0 until ss.length).foreach(_ => {
      table += ss
      ss = ss.substring(1) + ss.charAt(0)
    })
    table.sorted.map(a => a.last).mkString
  }

  def ibwt(r: String): String = {
    var table = Array.fill(r.length)("")
    (0 until r.length).foreach(_ => {
      (0 until r.length).foreach(i => {
        table(i) = r.charAt(i) + table(i)
      })
      table = table.sorted
    })
    table.indices.foreach(i => {
      val row = table(i)
      if (row.last == ETX) {
        return row.substring(1, row.length - 1)
      }
    })
    ""
  }

  def makePrintable(s: String): String = {
    s.replace(STX, '^').replace(ETX, '|')
  }

  def main(args: Array[String]): Unit = {
    val tests = Array("banana",
      "appellee",
      "dogwood",
      "TO BE OR NOT TO BE OR WANT TO BE OR NOT?",
      "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
      "\u0002ABC\u0003"
    )

    tests.foreach(test => {
      println(makePrintable(test))
      print(" --> ")

      try {
        val t = bwt(test)
        println(makePrintable(t))
        val r = ibwt(t)
        printf(" --> %s\n", r)
      } catch {
        case e: Exception => printf("ERROR: %s\n", e.getMessage)
      }

      println()
    })
  }
}

Output:

banana
 --> |annb^aa
 --> banana

appellee
 --> |e^elplepa
 --> appellee

dogwood
 --> |do^oodwg
 --> dogwood

TO BE OR NOT TO BE OR WANT TO BE OR NOT?
 --> |?OOORREEETTRTW   BBB  ATTT   NNOOONOO^   
 --> TO BE OR NOT TO BE OR WANT TO BE OR NOT?

SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
 --> |STEXYDST.E.IXXIIXXSSMPPS.B..EE.^.USFXDIIOIIIT
 --> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

^ABC|
 --> ERROR: String can't contain STX or ETX

Seed7

The example below was inspired by the Burrows-Wheeler transform example from the Seed7 Homepage.

$ include "seed7_05.s7i";

const func string: burrowsWheelerTransform (in string: stri) is func
  result
    var string: encoded is "";
  local
    var integer: length is 0;
    var integer: index is 0;
    var array string: rotations is 0 times "";
  begin
    length := succ(length(stri));
    rotations := length times "";
    for index range 1 to length do
      rotations[index] := stri[index ..] & "\256;" & stri[.. pred(index)];
    end for;
    rotations := sort(rotations);
    for index range 1 to length do
      encoded &:= rotations[index][length];
    end for;
  end func;

const func string: inverseBurrowsWheelerTransform (in string: stri) is func
  result
    var string: decoded is "";
  local
    var integer: length is 0;
    var integer: count is 0;
    var integer: index is 0;
    var array string: rotations is 0 times "";
  begin
    length := length(stri);
    rotations := length times "";
    for count range 1 to length do
      for index range 1 to length do
        rotations[index] := str(stri[index]) & rotations[index];
      end for;
      rotations := sort(rotations);
    end for;
    decoded := rotations[1];
    index := pos(decoded, "\256;");
    decoded := decoded[succ(index) ..] & decoded[.. pred(index)];
  end func;

const proc: test(in string: stri) is func
  local
    var string: encoded is "";
    var string: decoded is "";
  begin
    writeln;
    writeln("     " <& stri);
    encoded := burrowsWheelerTransform(stri);
    writeln("---> " <& literal(encoded));
    decoded := inverseBurrowsWheelerTransform(encoded);
    writeln("---> " <& decoded);
  end func;

const proc: main is func
  begin
    test("banana");
    test("appellee");
    test("dogwood");
    test("TO BE OR NOT TO BE OR WANT TO BE OR NOT?");
    test("SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES");
  end func;

Output:

     banana
---> "bnn\256;aaa"
---> banana

     appellee
---> "\256;lpelepae"
---> appellee

     dogwood
---> "\256;ooodwgd"
---> dogwood

     TO BE OR NOT TO BE OR WANT TO BE OR NOT?
---> "OOORREEETTRTW   BBB  ATTT   NNOOONOO\256;   ?"
---> TO BE OR NOT TO BE OR WANT TO BE OR NOT?

     SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
---> "TEXYDST.E.IXIXIXXSSMPPS.B..E.\256;.UESFXDIIOIIITS"
---> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

     SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
---> "TEXYDST.E.IXIXIXXSSMPPS.B..E.\256;.UESFXDIIOIIIT\257;S"
---> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

Sidef

Translation of: Python

class BurrowsWheelerTransform (String L = "\002") {

    method encode(String s) {
        assert(!s.contains(L), "String cannot contain `#{L.dump}`")
        s = (L + s)
        s.len.of{|i| s.substr(i) + s.substr(0, i) }.sort.map{.last}.join
    }

    method decode(String s) {
        var t = s.len.of("")
        var c = s.chars
        { t = (c »+« t).sort } * s.len
        t.first { .begins_with(L) }.substr(L.len)
    }
}

var tests = [
    "banana", "appellee", "dogwood", "TOBEORNOTTOBEORTOBEORNOT"
    "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
]

var bwt = BurrowsWheelerTransform(L: '$')

tests.each { |str|
    var enc = bwt.encode(str)
    var dec = bwt.decode(enc)
    say "BWT(#{dec.dump}) = #{enc.dump}"
    assert_eq(str, dec)
}

Output:

BWT("banana") = "annb$aa"
BWT("appellee") = "e$elplepa"
BWT("dogwood") = "do$oodwg"
BWT("TOBEORNOTTOBEORTOBEORNOT") = "TOOOBBBRRTTTEEENNOOOOR$TO"
BWT("SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES") = "STEXYDST.E.IXXIIXXSSMPPS.B..EE.$.USFXDIIOIIIT"

More efficient implementation, running in O(n*log(n)) time, using O(n) space:

define LOOKAHEAD_LEN = 128

func bwt_sort (String s) {    # O(n * LOOKAHEAD_LEN) space (fast)
    ^s.len -> map {|i|
        var t = s.slice(i, LOOKAHEAD_LEN)

        if (t.len < LOOKAHEAD_LEN) {
            t += s.slice(0, min(i, LOOKAHEAD_LEN - t.len))
        }

        [t, i]
    }.sort {|a,b|
        (a[0] <=> b[0]) || (s.rotate(a[1]) <=> s.rotate(b[1]))
    }.map { .[1] }
}

func bwt_encode(String s) {

    var bwt = bwt_sort(s)
    var ret = bwt.map {|i| s.slice(i-1, 1) }.join
    var idx = bwt.first_index_by { .is_zero }

    return (ret, idx)
}

func bwt_decode(String bwt, Number idx) {    # fast inversion

    var tail = bwt.chars
    var head = tail.sort

    var indices = Hash()
    tail.each_kv {|i,v|
        indices{v} := [] << i
    }

    var table = []
    head.each_kv {|i,v|
        table[i] = indices{v}.shift
    }

    var dec = ''
    var i = idx

    head.len.times {
        dec += head[i]
        i = table[i]
    }

    return dec
}

var tests = [
    "banana", "appellee", "dogwood", "TOBEORNOTTOBEORTOBEORNOT"
    "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
]

tests.each { |str|
    var (enc, idx) = bwt_encode(str)
    var dec = bwt_decode(enc, idx)
    say "BWT(#{dec.dump}) = (#{enc.dump}, #{idx})"
    assert_eq(str, dec)
}

Output:

BWT("banana") = ("nnbaaa", 3)
BWT("appellee") = ("eelplepa", 0)
BWT("dogwood") = ("odoodwg", 1)
BWT("TOBEORNOTTOBEORTOBEORNOT") = ("OOOBBBRRTTTEEENNOOORTTOO", 20)
BWT("SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES") = ("TEXYDST.E.IXIXIXXSSMPPS.B..E.S.EUSFXDIIOIIIT", 29)

Swift

Translation of: Kotlin

import Foundation

private let stx = "\u{2}"
private let etx = "\u{3}"

func bwt(_ str: String) -> String? {
  guard !str.contains(stx), !str.contains(etx) else {
    return nil
  }

  let ss = stx + str + etx
  let table = ss.indices.map({i in ss[i...] + ss[ss.startIndex..<i] }).sorted()

  return String(table.map({str in str.last!}))
}

func ibwt(_ str: String) -> String? {
  let len = str.count
  var table = Array(repeating: "", count: len)

  for _ in 0..<len {
    for i in 0..<len {
      table[i] = String(str[str.index(str.startIndex, offsetBy: i)]) + table[i]
    }

    table.sort()
  }

  for row in table where row.hasSuffix(etx) {
    return String(row.dropFirst().dropLast())
  }

  return nil
}


func readableBwt(_ str: String) -> String {
  return str.replacingOccurrences(of: "\u{2}", with: "^").replacingOccurrences(of: "\u{3}", with: "|")
}

let testCases = [
  "banana",
  "appellee",
  "dogwood",
  "TO BE OR NOT TO BE OR WANT TO BE OR NOT?",
  "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
  "\u{2}ABC\u{3}"
]

for test in testCases {
  let b = bwt(test) ?? "error"
  let c = ibwt(b) ?? "error"

  print("\(readableBwt(test)) -> \(readableBwt(b)) -> \(readableBwt(c))")
}

Output:

banana -> |annb^aa -> banana
appellee -> |e^elplepa -> appellee
dogwood -> |do^oodwg -> dogwood
TO BE OR NOT TO BE OR WANT TO BE OR NOT? -> |?OOORREEETTRTW   BBB  ATTT   NNOOONOO^    -> TO BE OR NOT TO BE OR WANT TO BE OR NOT?
SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES -> |STEXYDST.E.IXXIIXXSSMPPS.B..EE.^.USFXDIIOIIIT -> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
^ABC| -> error -> error

TXR

We use the U+DC00 code point as the EOF sentinel. In TXR terminology, this code is called the pseudo-null. It plays a special significance in that when a NUL byte occurs in UTF-8 external data, TXR's decoder maps it the U+DC00 point. When a string containing U+DC00 is converted to UTF-8, that code becomes a NUL again.

(defvarl eof "\xDC00")

(defun bwt (str)
  (if (contains eof str)
    (error "~s: input may not contain ~a" %fun% eof))
  (let ((seof `@str@eof`))
    (flow 0..(len seof) (mapcar (op rot seof)) sort (mappend last))))

(defun ibwt (str)
  (let* ((ch (tuples 1 str))
         (row (sort ch)))
    (dotimes (i (pred (len str)))
      (upd row (mapcar append ch) nsort))
    [(find-if (op ends-with eof) row) 0..-1]))

At the REPL:

1> (bwt "^BANANA")
"BNN^AA\xDC00;A"
2> (ibwt *1)
"^BANANA"
3> (bwt "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES")
"TEXYDST.E.IXIXIXXSSMPPS.B..E.\xDC00.UESFXDIIOIIITS"
4> (ibwt *3)
"SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES"

Visual Basic .NET

Translation of: C#

Module Module1

    ReadOnly STX As Char = Chr(&H2)
    ReadOnly ETX As Char = Chr(&H3)

    Sub Rotate(Of T)(a As T())
        Dim o = a.Last
        For i = a.Length - 1 To 1 Step -1
            a(i) = a(i - 1)
        Next
        a(0) = o
    End Sub

    Private Function Compare(s1 As String, s2 As String) As Integer
        Dim i = 0
        While i < s1.Length AndAlso i < s2.Length
            Dim a = s1(i)
            Dim b = s2(i)
            If a < b Then
                Return -1
            End If
            If b < a Then
                Return 1
            End If
            i += 1
        End While
        If s1.Length < s2.Length Then
            Return -1
        End If
        If s2.Length < s1.Length Then
            Return 1
        End If
        Return 0
    End Function

    Function Bwt(s As String) As String
        If s.Any(Function(c) c = STX OrElse c = ETX) Then
            Throw New ArgumentException("Input can't contain STX or ETX")
        End If
        Dim ss = (STX + s + ETX).ToCharArray
        Dim table As New List(Of String)
        For i = 0 To ss.Length - 1
            table.Add(New String(ss))
            Rotate(ss)
        Next
        table.Sort(Function(a As String, b As String) Compare(a, b))
        Return New String(table.Select(Function(a) a.Last).ToArray)
    End Function

    Function Ibwt(r As String) As String
        Dim len = r.Length
        Dim sa(len - 1) As String
        Dim table As New List(Of String)(sa)
        For i = 0 To len - 1
            For j = 0 To len - 1
                table(j) = r(j) + table(j)
            Next
            table.Sort(Function(a As String, b As String) Compare(a, b))
        Next
        For Each row In table
            If row.Last = ETX Then
                Return row.Substring(1, len - 2)
            End If
        Next
        Return ""
    End Function

    Function MakePrintable(s As String) As String
        Return s.Replace(STX, "^").Replace(ETX, "|")
    End Function

    Sub Main()
        Dim tests As String() = {
            "banana",
            "appellee",
            "dogwood",
            "TO BE OR NOT TO BE OR WANT TO BE OR NOT?",
            "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
            STX + "ABC" + ETX
        }

        For Each test In tests
            Console.WriteLine(MakePrintable(test))
            Console.Write(" --> ")

            Dim t = ""
            Try
                t = Bwt(test)
                Console.WriteLine(MakePrintable(t))
            Catch ex As Exception
                Console.WriteLine("ERROR: {0}", ex.Message)
            End Try

            Dim r = Ibwt(t)
            Console.WriteLine(" --> {0}", r)
            Console.WriteLine()
        Next
    End Sub

End Module

Output:

banana
 --> |annb^aa
 --> banana

appellee
 --> |e^elplepa
 --> appellee

dogwood
 --> |do^oodwg
 --> dogwood

TO BE OR NOT TO BE OR WANT TO BE OR NOT?
 --> |?OOORREEETTRTW   BBB  ATTT   NNOOONOO^
 --> TO BE OR NOT TO BE OR WANT TO BE OR NOT?

SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
 --> |STEXYDST.E.IXXIIXXSSMPPS.B..EE.^.USFXDIIOIIIT
 --> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

^ABC|
 --> ERROR: Input can't contain STX or ETX
 -->

Wren

Translation of: Go

Library: Wren-sort

import "./sort" for Sort

var stx = "\x02"
var etx = "\x03"
 
var bwt = Fn.new { |s|
    if (s.indexOf(stx) >= 0 || s.indexOf(etx) >= 0) return null
    s = stx + s + etx
    var len = s.count
    var table = [""] * len
    table[0] = s
    for (i in 1...len) table[i] = s[i..-1] + s[0...i]
    Sort.quick(table)
    var lastChars = [""] * len
    for (i in 0...len) lastChars[i] = table[i][len-1]
    return lastChars.join()
}
 
var ibwt = Fn.new { |r|
    var len = r.count
    var table = [""] * len
    for (i in 0...len) { 
        for (j in 0...len) table[j] = r[j] + table[j]
        Sort.quick(table)
    }
    for (row in table) {
        if (row.endsWith(etx)) return row[1...len-1]
    }
    return ""
}
 
var makePrintable = Fn.new { |s|   
    // substitute ^ for STX and | for ETX to print results
    s = s.replace(stx, "^")
    return s.replace(etx, "|")
}
 
var tests = [
    "banana",
    "appellee",
    "dogwood",
    "TO BE OR NOT TO BE OR WANT TO BE OR NOT?",
    "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
    "\x02ABC\x03"
]
for (test in tests) {
    System.print(makePrintable.call(test))
    System.write(" --> ")
    var t = bwt.call(test)
    if (t == null) {
        System.print("ERROR: String can't contain STX or ETX")
        t = ""
    } else {
        System.print(makePrintable.call(t))
    }
    var r = ibwt.call(t)
    System.print(" --> %(r)\n")
}

Output:

banana
 --> |annb^aa
 --> banana

appellee
 --> |e^elplepa
 --> appellee

dogwood
 --> |do^oodwg
 --> dogwood

TO BE OR NOT TO BE OR WANT TO BE OR NOT?
 --> |?OOORREEETTRTW   BBB  ATTT   NNOOONOO^   
 --> TO BE OR NOT TO BE OR WANT TO BE OR NOT?

SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
 --> |STEXYDST.E.IXXIIXXSSMPPS.B..EE.^.USFXDIIOIIIT
 --> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

^ABC|
 --> ERROR: String can't contain STX or ETX
 --> 

zkl

class BurrowsWheelerTransform{
   fcn init(chr="$"){ var special=chr; }
   fcn encode(str){
      _assert_(not str.holds(special), "String cannot contain char \"%s\"".fmt(special) );
      str=str.append(special);
      str.len().pump(List().merge,'wrap(n){ String(str[n,*],str[0,n]) })
      .pump(String,T("get",-1));	// last char of each "permutation"
   }
   fcn decode(str){      
      table:=List.createLong(str.len(),"");	// ("",""..), mutable
      do(str.len()){
	 foreach n in (str.len()){ table[n]=str[n] + table[n] }
	 table.sort();
      }   // --> ("$dogwood","d$dogwoo","dogwood$",...)
      table.filter1("%s*".fmt(special).glob)[1,*];  // str[0]==$, often first element
   }
}

BWT:=BurrowsWheelerTransform();
//BWT.encode("$"); // --> assert(bbb.zkl:25): String cannot contain char "$"

tests:=T(
    "banana", "appellee", "dogwood", "TO BE OR NOT TO BE OR WANT TO BE OR NOT?",
    "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",);
foreach test in (tests){
   enc:=BWT.encode(test);
   println("%s\n  -->%s\n  -->%s".fmt(test,enc,BWT.decode(enc)));
}

Output:

banana
  -->annb$aa
  -->banana
appellee
  -->e$elplepa
  -->appellee
dogwood
  -->do$oodwg
  -->dogwood
TO BE OR NOT TO BE OR WANT TO BE OR NOT?
  -->OOORREEETTR?TW   BBB  ATTT   NNOOONOO$   
  -->TO BE OR NOT TO BE OR WANT TO BE OR NOT?
SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
  -->STEXYDST.E.IXXIIXXSSMPPS.B..EE.$.USFXDIIOIIIT
  -->SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES