Burrows–Wheeler transform: Difference between revisions
Added FreeBASIC
(Add Swift) |
(Added FreeBASIC) |
||
| (43 intermediate revisions by 22 users not shown) | |||
Line 1:
{{
{{Wikipedia|Burrows–Wheeler_transform}}
Line 14:
Source: [[wp:Burrows–Wheeler_transform|Burrows–Wheeler transform]]
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">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()</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|BQN}}==
<syntaxhighlight lang="bqn">stx←@+2
BWT ← { # Burrows-Wheeler Transform and its inverse as an invertible function
𝕊: "Input contained STX"!⊑stx¬∘∊𝕩 ⋄ (⍋↓𝕩) ⊏ stx∾𝕩;
𝕊⁼: 1↓(⊑˜⍟(↕≠𝕩)⟜⊑ ⍋)⊸⊏ 𝕩
}
</syntaxhighlight>
Example use:
<syntaxhighlight lang="text"> 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
</syntaxhighlight>
=={{header|C}}==
{{trans|Python}}
<
#include <stdio.h>
#include <stdlib.h>
Line 115 ⟶ 205:
}
return 0;
}</
{{out}}
Line 143 ⟶ 233:
-->
</pre>
=={{header|C sharp|C#}}==
{{trans|D}}
<
using System.Collections.Generic;
using System.Linq;
Line 371 ⟶ 334:
}
}
}</
{{out}}
<pre>banana
Line 396 ⟶ 359:
--> ERROR: Input can't contain STX or ETX
--></pre>
=={{header|C++}}==
{{trans|C#}}
<syntaxhighlight lang="cpp">#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;
}</syntaxhighlight>
{{out}}
<pre>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
--></pre>
=={{header|D}}==
{{trans|Kotlin}}
<
import std.algorithm.mutation;
import std.algorithm.searching;
Line 472 ⟶ 559:
writeln;
}
}</
{{out}}
<pre>banana
Line 497 ⟶ 584:
--> ERROR: Input can't contain STX or ETX
--></pre>
=={{header|Dart}}==
{{trans|Java}}
<syntaxhighlight lang="Dart">
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, "|");
}
</syntaxhighlight>
{{out}}
<pre>
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
-->
</pre>
=={{header|Factor}}==
Factor has a Burrows-Wheeler transform implementation in its standard library. In addition to the transformed sequence, the <code>bwt</code> word also outputs an index for use with the inverse <code>ibwt</code> word.
<
{
"banana" "dogwood" "TO BE OR NOT TO BE OR WANT TO BE OR NOT?"
Line 508 ⟶ 696:
2dup " bwt-->%3d %u\n" printf
ibwt " ibwt-> %u\n" printf nl
] each</
{{out}}
<pre>
Line 527 ⟶ 715:
ibwt-> "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES"
</pre>
=={{header|FreeBASIC}}==
{{trans|C++}}
<syntaxhighlight lang="vbnet">#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</syntaxhighlight>
{{out}}
<pre>Same as C++ entry.</pre>
=={{header|Go}}==
{{trans|Python}}
<
import (
Line 604 ⟶ 900:
fmt.Println(" -->", r, "\n")
}
}</
{{out}}
Line 632 ⟶ 928:
-->
</pre>
=={{header|Groovy}}==
{{trans|Java}}
<syntaxhighlight lang="groovy">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)
}
}
}</syntaxhighlight>
{{out}}
<pre>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
--> </pre>
=={{header|Haskell}}==
<
-- transform, based on the description in the Wikipedia article.
--
Line 678 ⟶ 1,073:
prettyVal (In c) = c
prettyVal Pre = '^'
prettyVal Post = '|'</
{{out}}
Line 701 ⟶ 1,096:
SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
</pre>
=={{header|J}}==
<pre>
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
</pre>
<syntaxhighlight lang="text">
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
)
</syntaxhighlight>
=== concise implementation ===
<syntaxhighlight lang=J>bwt=:verb def '{:"1 /:~(|."0 1~i.@#) (8 u:y),{:a.'
ibwt=: 1 (}.{:) (/:~@,.^:(#@]) 0#"0])</syntaxhighlight>
Example use:
<syntaxhighlight lang=J> bwt'This is a test.'
ssat� tT hiies .
ibwt bwt'This is a test.'
This is a test.</syntaxhighlight>
=={{header|Java}}==
{{trans|Kotlin}}
<syntaxhighlight lang="java">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);
}
}
}</syntaxhighlight>
{{out}}
<pre>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
--> </pre>
=={{header|jq}}==
{{trans|Wren}}
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
<syntaxhighlight lang="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] ;
</syntaxhighlight>
'''Tests'''
<syntaxhighlight lang="jq">
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</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Julia}}==
<
function burrowswheeler_encode(s)
Line 730 ⟶ 1,385:
"\nInverse transformation: ", burrowswheeler_decode(burrowswheeler_encode(s)), "\n")
end
</
<pre>
Original: BANANA
Line 750 ⟶ 1,405:
ERROR: LoadError: "String for Burrows-Wheeler input cannot contain STX or ETX"
</pre>
=={{header|Kotlin}}==
{{trans|Python}}
<
const val STX = "\u0002"
Line 813 ⟶ 1,467:
println(" --> $r\n")
}
}</
{{output}}
Line 841 ⟶ 1,495:
-->
</pre>
=={{header|Ksh}}==
<syntaxhighlight lang="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
</syntaxhighlight>
{{out}}<pre>
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 |</pre>
=={{header|Lua}}==
{{trans|Java}}
<syntaxhighlight lang="lua">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()</syntaxhighlight>
{{out}}
<pre>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
--></pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">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[%, {"^", "|"}]</syntaxhighlight>
{{out}}
<pre>|ANNB^AA
BANANA
|e^elplepa
appellee
|do^oodwg
dogwood</pre>
=={{header|Nim}}==
Translation of the Wikipedia Python algorithm. The program uses characters '¹' and '²' to display STX and ETX.
<syntaxhighlight lang="nim">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</syntaxhighlight>
{{out}}
<pre>
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</pre>
=={{header|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.
<syntaxhighlight lang="pascal">
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.
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Perl}}==
{{trans|
<
binmode STDOUT, ":utf8";
Line 879 ⟶ 2,123:
}
print join "\n", @res;</
{{out}}
<pre>Original: BANANA
Line 896 ⟶ 2,140:
Transformed: OOORREEETTRTW BBB ATTT NNOOONOO👍 ?
Inverse transformed: TO BE OR NOT TO BE OR WANT TO BE OR NOT?</pre>
=={{header|Phix}}==
An efficient implementation, based mainly on http://spencer-carroll.com/an-easy-to-understand-explanation-of-the-burrows-wheeler-transform/ <br>
Takes around about ten seconds to transform and invert a 100K string. Note: requires 0.8.0+
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #000080;font-style:italic;">-- 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.
--*/</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">terminator</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'$'</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">rot_sort</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- 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.</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
<span style="color: #000000;">j</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">j</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">compare</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">c</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">burrows_wheeler_transform</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">terminator</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #008000;">"error"</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">terminator</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">custom_sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">routine_id</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"rot_sort"</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">),{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">})</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">l</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #000080;font-style:italic;">--/*
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.
--*/</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">inverse_burrows_wheeler</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'\0'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- (doable, but needs some +1s)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">c</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">f</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">q</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">256</span><span style="color: #0000FF;">),</span> <span style="color: #000080;font-style:italic;">-- queue heads (per char)</span>
<span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">),</span> <span style="color: #000080;font-style:italic;">-- queue links</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- reformed/pairing links
-- Step 1. discover/build queues (backwards)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">l</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">-- Step 2. reform/pop char queues into pairing links</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">l</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
<span style="color: #000000;">q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">-- Step 3. rebuild (backwards)</span>
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">terminator</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #008000;">"error"</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> <span style="color: #000080;font-style:italic;">-- (first time in, skip the end marker)</span>
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">src</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">enc</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">burrows_wheeler_transform</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">dec</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">inverse_burrows_wheeler</span><span style="color: #0000FF;">(</span><span style="color: #000000;">enc</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">src</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"characters"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">enc</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">enc</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"characters"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">dec</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dec</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"characters"</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"original: %s --> %s\n inverse: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">src</span><span style="color: #0000FF;">,</span><span style="color: #000000;">enc</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dec</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"banana"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"dogwood"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"TO BE OR NOT TO BE OR WANT TO BE OR NOT?"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES"</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
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
</pre>
=={{header|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: [https://www.codespeedy.com/burrows-wheeler-transform-in-python/ Burrows Wheeler Transform in Python]
<syntaxhighlight lang="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
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2018.06}}
<syntaxhighlight lang="raku"
# Using a visible character here for ease of viewing.
Line 927 ⟶ 2,357:
say 'Inverse transformed: ', ɯɹoɟsuɐɹʇ transform $phrase;
say '';
}</
{{out}}
<pre>Original: BANANA
Line 947 ⟶ 2,377:
Original: Oops👍
String can't contain STX character.</pre>
=={{header|REXX}}==
Programming note: a little bit of code was added to support more (legal) characters in the input string for the '''BWT'''
<br>function. The error recovery and error messages are rudimentary when an illegal character in the input is detected.
<
$.= /*the default text for (all) the inputs*/
parse arg $.1 /*obtain optional arguments from the CL*/
Line 1,157 ⟶ 2,404:
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
_= 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=
@.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)
end /*k*/ /* ··· the array's right─most character*/
return $ /*return the constructed answer. */
Line 1,191 ⟶ 2,437:
_= @.j; @.j= @.k; @.k= _; ok= 0 /*swap two elements; flag as not done.*/
end /*j*/
end /*m*/; return</
{{out|output|text= when using the default inputs:}}
<pre>
Line 1,220 ⟶ 2,466:
***error*** BWT: invalid input: bad─bad thingy²
***error*** BWT: The input string contains an invalid character at position 15.
</pre>
=={{header|RPL}}==
{{works with|HP|28}}
<code>SORT</code> is defined at [[Sorting_algorithms/Bubble_sort#RPL|Sorting algorithms/Bubble sort]]
{| class="wikitable" ≪
! RPL code
! Comment
|-
|
≪
{ } SWAP 1 OVER SIZE '''FOR''' j
SWAP OVER + SWAP
DUP 2 OVER SIZE SUB SWAP 1 1 SUB +
'''NEXT''' DROP
≫ ‘<span style="color:blue">→BWtable</span>’ STO
≪
DUP <span style="color:blue">→BWtable SORT </span> → 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
≫ ≫ '<span style="color:blue">→BWT</span>' STO
≪ DUP 142 CHR POS
'''IF''' DUP 2 < '''THEN''' ""
'''ELSE''' DUP2 1 SWAP OVER - SUB '''END'''
ROT 3 PICK 1 + OVER SIZE SUB +
≫ ‘<span style="color:blue">IdxStr</span>’ STO
≪
<span style="color:blue">IdxStr</span> → idx BWstr
≪ { } 1 BWstr SIZE '''START''' "" + '''NEXT''' '<span style="color:green">TBL</span>' STO
1 BWstr SIZE '''FOR''' j 1 BWstr SIZE '''FOR''' k
BWstr k DUP SUB
'<span style="color:green">TBL</span>' k GET + '<span style="color:green">TBL</span>' k ROT PUT
'''NEXT'''
<span style="color:green">TBL</span> <span style="color:blue">SORT</span> '<span style="color:green">TBL</span>' STO '''NEXT'''
'<span style="color:green">TBL</span>' idx GET '<span style="color:green">TBL</span>' PURGE
≫ ≫ ‘<span style="color:blue">BWT→</span>’ STO
|
<span style="color:blue">→BWtable</span> ''( "string" → { "string" "trings" ... "gstrin" )''
initialize stack and loop n=len(string) times
add string to table
string = string[2..n]+string[1}
clean stack
<span style="color:blue">→BWT</span> ''( "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
<span style="color:blue">IdxStr</span> ''( "str←ing" → index "string" )''
if ← not at string beginning
get chars before
get chars after and concatenate
<span style="color:blue">→BWT</span> ''( "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" <span style="color:blue">→BWT</span>
DUP <span style="color:blue">BWT→</span>
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.
{{out}}
<pre>
2: "nnb←aaa"
1: "banana"
</pre>
=={{header|Ruby}}==
{{trans|C#}}
<syntaxhighlight lang="ruby">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()</syntaxhighlight>
{{out}}
<pre>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
--></pre>
=={{header|Rust}}==
<syntaxhighlight lang="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);
}
}
</syntaxhighlight>
{{out}}
<pre>
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?
</pre>
=={{header|Scala}}==
{{trans|Kotlin}}
<
object BWT {
Line 1,289 ⟶ 2,827:
})
}
}</
{{out}}
<pre>banana
Line 1,313 ⟶ 2,851:
^ABC|
--> ERROR: String can't contain STX or ETX</pre>
=={{header|Seed7}}==
The example below was inspired by the [https://seed7.sourceforge.net/algorith/string.htm#burrowsWheelerTransformConcept Burrows-Wheeler transform] example from the [https://seed7.sourceforge.net/ Seed7 Homepage].
<syntaxhighlight lang="seed7">$ 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;</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Sidef}}==
{{trans|Python}}
<
method encode(String s) {
Line 1,344 ⟶ 2,975:
say "BWT(#{dec.dump}) = #{enc.dump}"
assert_eq(str, dec)
}</
{{out}}
<pre>
Line 1,352 ⟶ 2,983:
BWT("TOBEORNOTTOBEORTOBEORNOT") = "TOOOBBBRRTTTEEENNOOOOR$TO"
BWT("SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES") = "STEXYDST.E.IXXIIXXSSMPPS.B..EE.$.USFXDIIOIIIT"
</pre>
More efficient implementation, running in '''O(n*log(n))''' time, using '''O(n)''' space:
<syntaxhighlight lang="ruby">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)
}</syntaxhighlight>
{{out}}
<pre>
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)
</pre>
Line 1,358 ⟶ 3,062:
{{trans|Kotlin}}
<
private let stx = "\u{2}"
Line 1,412 ⟶ 3,116:
print("\(readableBwt(test)) -> \(readableBwt(b)) -> \(readableBwt(c))")
}</
{{out}}
Line 1,422 ⟶ 3,126:
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</pre>
=={{header|TXR}}==
We use the U+DC00 code point as the EOF sentinel. In TXR terminology, this code is called the <i>pseudo-null</i>. 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.
<syntaxhighlight lang="txrlisp">(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]))</syntaxhighlight>
At the REPL:
<pre>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"</pre>
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
ReadOnly STX As Char = Chr(&H2)
Line 1,524 ⟶ 3,257:
End Sub
End Module</
{{out}}
<pre>banana
Line 1,549 ⟶ 3,282:
--> ERROR: Input can't contain STX or ETX
--></pre>
=={{header|Wren}}==
{{trans|Go}}
{{libheader|Wren-sort}}
<syntaxhighlight lang="wren">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")
}</syntaxhighlight>
{{out}}
<pre>
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
-->
</pre>
=={{header|zkl}}==
<
fcn init(chr="$"){ var special=chr; }
fcn encode(str){
Line 1,567 ⟶ 3,389:
table.filter1("%s*".fmt(special).glob)[1,*]; // str[0]==$, often first element
}
}</
<
//BWT.encode("$"); // --> assert(bbb.zkl:25): String cannot contain char "$"
Line 1,577 ⟶ 3,399:
enc:=BWT.encode(test);
println("%s\n -->%s\n -->%s".fmt(test,enc,BWT.decode(enc)));
}</
{{out}}
<pre>
| |||