Burrows–Wheeler transform: Difference between revisions
Added FreeBASIC
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
(Added FreeBASIC) |
||
| (15 intermediate revisions by 8 users not shown) | |||
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’)
Line 70 ⟶ 69:
</pre>
=={{header|BQN}}==
<syntaxhighlight lang=
BWT ← { # Burrows-Wheeler Transform and its inverse as an invertible function
𝕊: "Input contained STX"!⊑stx¬∘∊𝕩 ⋄ (⍋↓𝕩) ⊏ stx∾𝕩;
Line 79 ⟶ 77:
</syntaxhighlight>
Example use:
<syntaxhighlight lang="text"> BWT "banana"
"annb␂aa"
BWT⁼ BWT "banana"
Line 107 ⟶ 105:
Error: Input contained STX
</syntaxhighlight>
=={{header|C}}==
{{trans|Python}}
<syntaxhighlight lang="c">#include <string.h>
#include <stdio.h>
#include <stdlib.h>
Line 236 ⟶ 233:
-->
</pre>
=={{header|C sharp|C#}}==
{{trans|D}}
<syntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.Linq;
Line 363 ⟶ 359:
--> ERROR: Input can't contain STX or ETX
--></pre>
=={{header|C++}}==
{{trans|C#}}
<syntaxhighlight lang="cpp">#include <algorithm>
#include <iostream>
#include <vector>
Line 489 ⟶ 484:
--> Error Input can't contain STX or ETX
--></pre>
=={{header|D}}==
{{trans|Kotlin}}
<syntaxhighlight lang="d">import std.algorithm.iteration;
import std.algorithm.mutation;
import std.algorithm.searching;
Line 590 ⟶ 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.
<syntaxhighlight lang="factor">USING: formatting io kernel math.transforms.bwt sequences ;
{
"banana" "dogwood" "TO BE OR NOT TO BE OR WANT TO BE OR NOT?"
Line 620 ⟶ 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}}
<syntaxhighlight lang="go">package main
import (
Line 725 ⟶ 928:
-->
</pre>
=={{header|Groovy}}==
{{trans|Java}}
<syntaxhighlight lang="groovy">class BWT {
private static final String STX = "\u0002"
private static final String ETX = "\u0003"
Line 826 ⟶ 1,028:
--> ERROR: String cannot contain STX or ETX
--> </pre>
=={{header|Haskell}}==
<syntaxhighlight lang="haskell">-- A straightforward, inefficient implementation of the Burrows–Wheeler
-- transform, based on the description in the Wikipedia article.
--
Line 895 ⟶ 1,096:
SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
</pre>
=={{header|J}}==
<pre>
Line 929 ⟶ 1,129:
</pre>
<syntaxhighlight lang="text">
NB. articulate definition
NB. local names (assignment =.) won't pollute the namespace
Line 969 ⟶ 1,169:
)
</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;
Line 1,073 ⟶ 1,284:
--> 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
Line 1,105 ⟶ 1,315:
</syntaxhighlight>
'''Tests'''
<syntaxhighlight lang="jq">
def tests:
(
Line 1,147 ⟶ 1,357:
--> ERROR: String can't contain STX or ETX
</pre>
=={{header|Julia}}==
<syntaxhighlight lang="julia">bwsort(vec) = sort(vec, lt = (a, b) -> string(a) < string(b))
function burrowswheeler_encode(s)
Line 1,196 ⟶ 1,405:
ERROR: LoadError: "String for Burrows-Wheeler input cannot contain STX or ETX"
</pre>
=={{header|Kotlin}}==
{{trans|Python}}
<syntaxhighlight lang="scala">// Version 1.2.60
const val STX = "\u0002"
Line 1,287 ⟶ 1,495:
-->
</pre>
=={{header|Ksh}}==
<syntaxhighlight lang="ksh">
#!/bin/ksh
Line 1,420 ⟶ 1,627:
|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))
Line 1,532 ⟶ 1,738:
--> ERROR: bwt.lua:6: String cannot contain STX
--></pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<syntaxhighlight lang=
BurrowWheeler[sin_String, {bdelim_, edelim_}] := Module[{s},
s = Characters[bdelim <> sin <> edelim];
Line 1,563 ⟶ 1,768:
|do^oodwg
dogwood</pre>
=={{header|Nim}}==
Translation of the Wikipedia Python algorithm. The program uses characters '¹' and '²' to display STX and ETX.
<syntaxhighlight lang=
from sequtils import repeat
import strutils except repeat
Line 1,656 ⟶ 1,860:
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;
Line 1,883 ⟶ 2,086:
---> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
</pre>
=={{header|Perl}}==
{{trans|Raku}}
<syntaxhighlight lang="perl">use utf8;
binmode STDOUT, ":utf8";
Line 1,938 ⟶ 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=
<span style="color: #000080;font-style:italic;">-- demo\rosetta\burrows_wheeler.exw
--/*
Line 2,100 ⟶ 2,301:
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.
Line 2,108 ⟶ 2,308:
Ref: [https://www.codespeedy.com/burrows-wheeler-transform-in-python/ Burrows Wheeler Transform in Python]
<syntaxhighlight lang=
def bwt(s):
"""Apply Burrows-Wheeler transform to input string."""
Line 2,126 ⟶ 2,326:
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" line># STX can be any character that doesn't appear in the text.
# Using a visible character here for ease of viewing.
Line 2,178 ⟶ 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.
<syntaxhighlight lang="rexx">/*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*/
Line 2,268 ⟶ 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"
Line 2,368 ⟶ 2,649:
=={{header|Rust}}==
<syntaxhighlight lang="rust">
use core::cmp::Ordering;
Line 2,479 ⟶ 2,760:
Inverse BWT: TO BE OR NOT TO BE OR WANT TO BE OR NOT?
</pre>
=={{header|Scala}}==
{{trans|Kotlin}}
<syntaxhighlight lang="scala">import scala.collection.mutable.ArrayBuffer
object BWT {
Line 2,571 ⟶ 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}}
<syntaxhighlight lang="ruby">class BurrowsWheelerTransform (String L = "\002") {
method encode(String s) {
Line 2,610 ⟶ 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 2,616 ⟶ 3,062:
{{trans|Kotlin}}
<syntaxhighlight lang="swift">import Foundation
private let stx = "\u{2}"
Line 2,680 ⟶ 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#}}
<syntaxhighlight lang="vbnet">Module Module1
ReadOnly STX As Char = Chr(&H2)
Line 2,811 ⟶ 3,286:
{{trans|Go}}
{{libheader|Wren-sort}}
<syntaxhighlight lang=
var stx = "\x02"
Line 2,898 ⟶ 3,373:
=={{header|zkl}}==
<syntaxhighlight lang="zkl">class BurrowsWheelerTransform{
fcn init(chr="$"){ var special=chr; }
fcn encode(str){
Line 2,915 ⟶ 3,390:
}
}</syntaxhighlight>
<syntaxhighlight lang="zkl">BWT:=BurrowsWheelerTransform();
//BWT.encode("$"); // --> assert(bbb.zkl:25): String cannot contain char "$"
| |||