Burrows–Wheeler transform: Difference between revisions
Added FreeBASIC
Thundergnat (talk | contribs) m (Automated syntax highlighting fixup (second round - minor fixes)) |
(Added FreeBASIC) |
||
| (14 intermediate revisions by 7 users not shown) | |||
Line 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.
Line 613 ⟶ 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}}
Line 958 ⟶ 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}}
Line 2,244 ⟶ 2,467:
***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#}}
Line 2,340 ⟶ 2,647:
--> Input can't contain STX or ETX
--></pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">
Line 2,543 ⟶ 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}}
Line 2,582 ⟶ 2,984:
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>
=={{header|Swift}}==
Line 2,650 ⟶ 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#}}
Line 2,776 ⟶ 3,282:
--> ERROR: Input can't contain STX or ETX
--></pre>
=={{header|Wren}}==
{{trans|Go}}
{{libheader|Wren-sort}}
<syntaxhighlight lang="
var stx = "\x02"
Line 2,864 ⟶ 3,371:
-->
</pre>
=={{header|zkl}}==
<syntaxhighlight lang="zkl">class BurrowsWheelerTransform{
| |||