Burrows–Wheeler transform: Difference between revisions
Added FreeBASIC
m (→{{header|Phix}}: added syntax colouring, marked p2js compatible) |
(Added FreeBASIC) |
||
(16 intermediate revisions by 8 users not shown) | |||
Line 14:
Source: [[wp:Burrows–Wheeler_transform|Burrows–Wheeler transform]]
<br><br>
=={{header|11l}}==
{{trans|Python}}
<
‘Apply Burrows-Wheeler transform to input string.’
assert("\002" !C s & "\003" !C s, ‘Input string cannot contain STX and ETX characters’)
Line 45 ⟶ 44:
print(‘After transformation: ’transformed.replace("\2", ‘^’).replace("\3", ‘|’))
print(‘After inverse transformation: ’invTransformed)
print()</
{{out}}
Line 70 ⟶ 69:
</pre>
=={{header|BQN}}==
<
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"
Line 106 ⟶ 104:
BWT "␂abc"
Error: Input contained STX
</syntaxhighlight>
=={{header|C}}==
{{trans|Python}}
<
#include <stdio.h>
#include <stdlib.h>
Line 208 ⟶ 205:
}
return 0;
}</
{{out}}
Line 236 ⟶ 233:
-->
</pre>
=={{header|C sharp|C#}}==
{{trans|D}}
<
using System.Collections.Generic;
using System.Linq;
Line 338 ⟶ 334:
}
}
}</
{{out}}
<pre>banana
Line 363 ⟶ 359:
--> ERROR: Input can't contain STX or ETX
--></pre>
=={{header|C++}}==
{{trans|C#}}
<
#include <iostream>
#include <vector>
Line 464 ⟶ 459:
return 0;
}</
{{out}}
<pre>banana
Line 489 ⟶ 484:
--> Error Input can't contain STX or ETX
--></pre>
=={{header|D}}==
{{trans|Kotlin}}
<
import std.algorithm.mutation;
import std.algorithm.searching;
Line 565 ⟶ 559:
writeln;
}
}</
{{out}}
<pre>banana
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.
<
{
"banana" "dogwood" "TO BE OR NOT TO BE OR WANT TO BE OR NOT?"
Line 601 ⟶ 696:
2dup " bwt-->%3d %u\n" printf
ibwt " ibwt-> %u\n" printf nl
] each</
{{out}}
<pre>
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}}
<
import (
Line 697 ⟶ 900:
fmt.Println(" -->", r, "\n")
}
}</
{{out}}
Line 725 ⟶ 928:
-->
</pre>
=={{header|Groovy}}==
{{trans|Java}}
<
private static final String STX = "\u0002"
private static final String ETX = "\u0003"
Line 801 ⟶ 1,003:
}
}
}</
{{out}}
<pre>banana
Line 826 ⟶ 1,028:
--> ERROR: String cannot contain STX or ETX
--> </pre>
=={{header|Haskell}}==
<
-- transform, based on the description in the Wikipedia article.
--
Line 872 ⟶ 1,073:
prettyVal (In c) = c
prettyVal Pre = '^'
prettyVal Post = '|'</
{{out}}
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 968 ⟶ 1,168:
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}}
<
import java.util.List;
Line 1,048 ⟶ 1,259:
}
}
}</
{{out}}
<pre>banana
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'''
<
def makePrintable:
if . == null then null
Line 1,103 ⟶ 1,313:
| first( .[] | select(endswith("\u0003")))
| .[1:-1] ;
</syntaxhighlight>
'''Tests'''
<syntaxhighlight lang="jq">
def tests:
(
Line 1,121 ⟶ 1,331:
(if $t then " --> \($t | ibwt)\n" else "" end) ;
tests</
{{out}}
<pre>
Line 1,147 ⟶ 1,357:
--> ERROR: String can't contain STX or ETX
</pre>
=={{header|Julia}}==
<
function burrowswheeler_encode(s)
Line 1,176 ⟶ 1,385:
"\nInverse transformation: ", burrowswheeler_decode(burrowswheeler_encode(s)), "\n")
end
</
<pre>
Original: BANANA
Line 1,196 ⟶ 1,405:
ERROR: LoadError: "String for Burrows-Wheeler input cannot contain STX or ETX"
</pre>
=={{header|Kotlin}}==
{{trans|Python}}
<
const val STX = "\u0002"
Line 1,259 ⟶ 1,467:
println(" --> $r\n")
}
}</
{{output}}
Line 1,287 ⟶ 1,495:
-->
</pre>
=={{header|Ksh}}==
<
#!/bin/ksh
Line 1,396 ⟶ 1,603:
echo
done
</syntaxhighlight>
{{out}}<pre>
BANANA
Line 1,420 ⟶ 1,627:
|ABC^
ERROR: string cannot contain ^ or |</pre>
=={{header|Lua}}==
{{trans|Java}}
<
ETX = string.char(tonumber(3,16))
Line 1,507 ⟶ 1,713:
end
main()</
{{out}}
<pre>banana
Line 1,532 ⟶ 1,738:
--> ERROR: bwt.lua:6: String cannot contain STX
--></pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
BurrowWheeler[sin_String, {bdelim_, edelim_}] := Module[{s},
s = Characters[bdelim <> sin <> edelim];
Line 1,555 ⟶ 1,760:
InverseBurrowWheeler[%, {"^", "|"}]
BurrowWheeler["dogwood", {"^", "|"}]
InverseBurrowWheeler[%, {"^", "|"}]</
{{out}}
<pre>|ANNB^AA
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.
<
from sequtils import repeat
import strutils except repeat
Line 1,633 ⟶ 1,837:
echo "Original text: ", text
echo "After transformation: ", transformed.displaybleString()
echo "After inverse transformation: ", invTransformed</
{{out}}
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.
<
program BurrowsWheeler;
Line 1,845 ⟶ 2,048:
Test( 'SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES');
end.
</syntaxhighlight>
{{out}}
<pre>
Line 1,883 ⟶ 2,086:
---> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
</pre>
=={{header|Perl}}==
{{trans|Raku}}
<
binmode STDOUT, ":utf8";
Line 1,921 ⟶ 2,123:
}
print join "\n", @res;</
{{out}}
<pre>Original: BANANA
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+
<!--<
<span style="color: #000080;font-style:italic;">-- demo\rosetta\burrows_wheeler.exw
--/*
Line 2,088 ⟶ 2,289:
<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>
<!--</
{{out}}
<pre>
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="python">
def bwt(s):
"""Apply Burrows-Wheeler transform to input string."""
Line 2,125 ⟶ 2,325:
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 2,158 ⟶ 2,357:
say 'Inverse transformed: ', ɯɹoɟsuɐɹʇ transform $phrase;
say '';
}</
{{out}}
<pre>Original: BANANA
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.
<
$.= /*the default text for (all) the inputs*/
parse arg $.1 /*obtain optional arguments from the CL*/
Line 2,239 ⟶ 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 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#}}
<
ETX = "\u0003"
Line 2,341 ⟶ 2,622:
end
main()</
{{out}}
<pre>banana
Line 2,368 ⟶ 2,649:
=={{header|Rust}}==
<
use core::cmp::Ordering;
Line 2,466 ⟶ 2,747:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 2,479 ⟶ 2,760:
Inverse BWT: TO BE OR NOT TO BE OR WANT TO BE OR NOT?
</pre>
=={{header|Scala}}==
{{trans|Kotlin}}
<
object BWT {
Line 2,547 ⟶ 2,827:
})
}
}</
{{out}}
<pre>banana
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}}
<
method encode(String s) {
Line 2,602 ⟶ 2,975:
say "BWT(#{dec.dump}) = #{enc.dump}"
assert_eq(str, dec)
}</
{{out}}
<pre>
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}}
<
private let stx = "\u{2}"
Line 2,670 ⟶ 3,116:
print("\(readableBwt(test)) -> \(readableBwt(b)) -> \(readableBwt(c))")
}</
{{out}}
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#}}
<
ReadOnly STX As Char = Chr(&H2)
Line 2,782 ⟶ 3,257:
End Sub
End Module</
{{out}}
<pre>banana
Line 2,811 ⟶ 3,286:
{{trans|Go}}
{{libheader|Wren-sort}}
<
var stx = "\x02"
Line 2,868 ⟶ 3,343:
var r = ibwt.call(t)
System.print(" --> %(r)\n")
}</
{{out}}
Line 2,898 ⟶ 3,373:
=={{header|zkl}}==
<
fcn init(chr="$"){ var special=chr; }
fcn encode(str){
Line 2,914 ⟶ 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 2,924 ⟶ 3,399:
enc:=BWT.encode(test);
println("%s\n -->%s\n -->%s".fmt(test,enc,BWT.decode(enc)));
}</
{{out}}
<pre>
|