Rosetta Code

Burrows–Wheeler transform: Difference between revisions

Page Discussion

Burrows–Wheeler transform (view source)

Revision as of 21:21, 28 March 2024

14,567 bytes added ,  1 month ago
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}}
 
<langsyntaxhighlight 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 45 ⟶ 44:
print(‘After transformation: ’transformed.replace("\2", ‘^’).replace("\3", ‘|’))
print(‘After inverse transformation: ’invTransformed)
print()</langsyntaxhighlight>
 
{{out}}
Line 70 ⟶ 69:
 
</pre>
 
=={{header|BQN}}==
<langsyntaxhighlight BQNlang="bqn">stx←@+2
BWT ← { # Burrows-Wheeler Transform and its inverse as an invertible function
𝕊: "Input contained STX"!⊑stx¬∘∊𝕩 ⋄ (⍋↓𝕩) ⊏ stx∾𝕩;
𝕊⁼: 1↓(⊑˜⍟(↕≠𝕩)⟜⊑ ⍋)⊸⊏ 𝕩
}
</syntaxhighlight>
</lang>
Example use:
<syntaxhighlight lang="text"> BWT "banana"
"annb␂aa"
BWT⁼ BWT "banana"
Line 106 ⟶ 104:
BWT "␂abc"
Error: Input contained STX
</syntaxhighlight>
</lang>
 
=={{header|C}}==
{{trans|Python}}
<langsyntaxhighlight lang="c">#include <string.h>
#include <stdio.h>
#include <stdlib.h>
Line 208 ⟶ 205:
}
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 236 ⟶ 233:
-->
</pre>
 
=={{header|C sharp|C#}}==
{{trans|D}}
<langsyntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.Linq;
Line 338 ⟶ 334:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>banana
Line 363 ⟶ 359:
--> ERROR: Input can't contain STX or ETX
--></pre>
 
=={{header|C++}}==
{{trans|C#}}
<langsyntaxhighlight lang="cpp">#include <algorithm>
#include <iostream>
#include <vector>
Line 464 ⟶ 459:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>banana
Line 489 ⟶ 484:
--> Error Input can't contain STX or ETX
--></pre>
 
=={{header|D}}==
{{trans|Kotlin}}
<langsyntaxhighlight lang="d">import std.algorithm.iteration;
import std.algorithm.mutation;
import std.algorithm.searching;
Line 565 ⟶ 559:
writeln;
}
}</langsyntaxhighlight>
{{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.
<langsyntaxhighlight 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 601 ⟶ 696:
2dup " bwt-->%3d %u\n" printf
ibwt " ibwt-> %u\n" printf nl
] each</langsyntaxhighlight>
{{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}}
<langsyntaxhighlight lang="go">package main
 
import (
Line 697 ⟶ 900:
fmt.Println(" -->", r, "\n")
}
}</langsyntaxhighlight>
 
{{out}}
Line 725 ⟶ 928:
-->
</pre>
 
=={{header|Groovy}}==
{{trans|Java}}
<langsyntaxhighlight lang="groovy">class BWT {
private static final String STX = "\u0002"
private static final String ETX = "\u0003"
Line 801 ⟶ 1,003:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>banana
Line 826 ⟶ 1,028:
--> ERROR: String cannot contain STX or ETX
--> </pre>
 
=={{header|Haskell}}==
<langsyntaxhighlight lang="haskell">-- A straightforward, inefficient implementation of the Burrows–Wheeler
-- transform, based on the description in the Wikipedia article.
--
Line 872 ⟶ 1,073:
prettyVal (In c) = c
prettyVal Pre = '^'
prettyVal Post = '|'</langsyntaxhighlight>
 
{{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>
</lang>
 
=== 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}}
<langsyntaxhighlight lang="java">import java.util.ArrayList;
import java.util.List;
 
Line 1,048 ⟶ 1,259:
}
}
}</langsyntaxhighlight>
{{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'''
<langsyntaxhighlight lang="jq"># substitute ^ for STX and | for ETX
def makePrintable:
if . == null then null
Line 1,103 ⟶ 1,313:
| first( .[] | select(endswith("\u0003")))
| .[1:-1] ;
</syntaxhighlight>
</lang>
'''Tests'''
<syntaxhighlight lang="jq">
<lang jq>
def tests:
(
Line 1,121 ⟶ 1,331:
(if $t then " --> \($t | ibwt)\n" else "" end) ;
 
tests</langsyntaxhighlight>
{{out}}
<pre>
Line 1,147 ⟶ 1,357:
--> ERROR: String can't contain STX or ETX
</pre>
 
=={{header|Julia}}==
<langsyntaxhighlight lang="julia">bwsort(vec) = sort(vec, lt = (a, b) -> string(a) < string(b))
 
function burrowswheeler_encode(s)
Line 1,176 ⟶ 1,385:
"\nInverse transformation: ", burrowswheeler_decode(burrowswheeler_encode(s)), "\n")
end
</langsyntaxhighlight>{{out}}
<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}}
<langsyntaxhighlight lang="scala">// Version 1.2.60
 
const val STX = "\u0002"
Line 1,259 ⟶ 1,467:
println(" --> $r\n")
}
}</langsyntaxhighlight>
 
{{output}}
Line 1,287 ⟶ 1,495:
-->
</pre>
 
=={{header|Ksh}}==
<langsyntaxhighlight lang="ksh">
#!/bin/ksh
 
Line 1,396 ⟶ 1,603:
echo
done
</syntaxhighlight>
</lang>
{{out}}<pre>
BANANA
Line 1,420 ⟶ 1,627:
|ABC^
ERROR: string cannot contain ^ or |</pre>
 
=={{header|Lua}}==
{{trans|Java}}
<langsyntaxhighlight lang="lua">STX = string.char(tonumber(2,16))
ETX = string.char(tonumber(3,16))
 
Line 1,507 ⟶ 1,713:
end
 
main()</langsyntaxhighlight>
{{out}}
<pre>banana
Line 1,532 ⟶ 1,738:
--> ERROR: bwt.lua:6: String cannot contain STX
--></pre>
 
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<langsyntaxhighlight Mathematicalang="mathematica">ClearAll[BurrowWheeler, InverseBurrowWheeler]
BurrowWheeler[sin_String, {bdelim_, edelim_}] := Module[{s},
s = Characters[bdelim <> sin <> edelim];
Line 1,555 ⟶ 1,760:
InverseBurrowWheeler[%, {"^", "|"}]
BurrowWheeler["dogwood", {"^", "|"}]
InverseBurrowWheeler[%, {"^", "|"}]</langsyntaxhighlight>
{{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.
 
<langsyntaxhighlight Nimlang="nim">import algorithm
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</langsyntaxhighlight>
 
{{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.
<langsyntaxhighlight lang="pascal">
program BurrowsWheeler;
 
Line 1,845 ⟶ 2,048:
Test( 'SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES');
end.
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 1,883 ⟶ 2,086:
---> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
</pre>
 
=={{header|Perl}}==
{{trans|Raku}}
<langsyntaxhighlight lang="perl">use utf8;
binmode STDOUT, ":utf8";
 
Line 1,921 ⟶ 2,123:
}
 
print join "\n", @res;</langsyntaxhighlight>
{{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+
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<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>
<!--</langsyntaxhighlight>-->
{{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">
<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>
</lang>
 
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2018.06}}
 
<syntaxhighlight lang="raku" perl6line># STX can be any character that doesn't appear in the text.
# Using a visible character here for ease of viewing.
Line 2,158 ⟶ 2,357:
say 'Inverse transformed: ', ɯɹoɟsuɐɹʇ transform $phrase;
say '';
}</langsyntaxhighlight>
{{out}}
<pre>Original: BANANA
Line 2,178 ⟶ 2,377:
Original: Oops👍
String can't contain STX character.</pre>
 
=={{header|REXX}}==
Programming note: &nbsp; a little bit of code was added to support more (legal) characters in the input string for the '''BWT'''
<br>function. &nbsp; The error recovery and error messages are rudimentary when an illegal character in the input is detected.
<langsyntaxhighlight 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,239 ⟶ 2,437:
_= @.j; @.j= @.k; @.k= _; ok= 0 /*swap two elements; flag as not done.*/
end /*j*/
end /*m*/; return</langsyntaxhighlight>
{{out|output|text=&nbsp; 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#}}
<langsyntaxhighlight lang="ruby">STX = "\u0002"
ETX = "\u0003"
 
Line 2,341 ⟶ 2,622:
end
 
main()</langsyntaxhighlight>
{{out}}
<pre>banana
Line 2,368 ⟶ 2,649:
 
=={{header|Rust}}==
<langsyntaxhighlight lang="rust">
use core::cmp::Ordering;
 
Line 2,466 ⟶ 2,747:
}
}
</syntaxhighlight>
</lang>
{{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}}
<langsyntaxhighlight lang="scala">import scala.collection.mutable.ArrayBuffer
 
object BWT {
Line 2,547 ⟶ 2,827:
})
}
}</langsyntaxhighlight>
{{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}}
<langsyntaxhighlight lang="ruby">class BurrowsWheelerTransform (String L = "\002") {
 
method encode(String s) {
Line 2,602 ⟶ 2,975:
say "BWT(#{dec.dump}) = #{enc.dump}"
assert_eq(str, dec)
}</langsyntaxhighlight>
{{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}}
 
<langsyntaxhighlight lang="swift">import Foundation
 
private let stx = "\u{2}"
Line 2,670 ⟶ 3,116:
 
print("\(readableBwt(test)) -> \(readableBwt(b)) -> \(readableBwt(c))")
}</langsyntaxhighlight>
 
{{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#}}
<langsyntaxhighlight lang="vbnet">Module Module1
 
ReadOnly STX As Char = Chr(&H2)
Line 2,782 ⟶ 3,257:
End Sub
 
End Module</langsyntaxhighlight>
{{out}}
<pre>banana
Line 2,811 ⟶ 3,286:
{{trans|Go}}
{{libheader|Wren-sort}}
<langsyntaxhighlight ecmascriptlang="wren">import "./sort" for Sort
 
var stx = "\x02"
Line 2,868 ⟶ 3,343:
var r = ibwt.call(t)
System.print(" --> %(r)\n")
}</langsyntaxhighlight>
 
{{out}}
Line 2,898 ⟶ 3,373:
 
=={{header|zkl}}==
<langsyntaxhighlight lang="zkl">class BurrowsWheelerTransform{
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
}
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">BWT:=BurrowsWheelerTransform();
//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)));
}</langsyntaxhighlight>
{{out}}
<pre>
Jjuanhdez
2,123

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/283610...363000"