Burrows–Wheeler transform: Difference between revisions

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’)

print(‘After transformation: ’transformed.replace("\2", ‘^’).replace("\3", ‘|’))

print(‘After inverse transformation: ’invTransformed)

 

{{out}}

 

</pre>

=={{header|BQN}}==

BWT ← { # Burrows-Wheeler Transform and its inverse as an invertible function

𝕊: "Input contained STX"!⊑stx¬∘∊𝕩 ⋄ (⍋↓𝕩) ⊏ stx∾𝕩;

𝕊⁼: 1↓(⊑˜⍟(↕≠𝕩)⟜⊑ ⍋)⊸⊏ 𝕩

}

Example use:

"annb␂aa"

BWT⁼ BWT "banana"

BWT "␂abc"

Error: Input contained STX

=={{header|C}}==

{{trans|Python}}

#include <stdio.h>

#include <stdlib.h>

}

return 0;

 

{{out}}

-->

</pre>

=={{header|C sharp|C#}}==

{{trans|D}}

using System.Collections.Generic;

using System.Linq;

}

}

{{out}}

<pre>banana

--> ERROR: Input can't contain STX or ETX

--></pre>

=={{header|C++}}==

{{trans|C#}}

#include <iostream>

#include <vector>

 

return 0;

{{out}}

<pre>banana

--> Error Input can't contain STX or ETX

--></pre>

=={{header|D}}==

{{trans|Kotlin}}

import std.algorithm.mutation;

import std.algorithm.searching;

writeln;

}

{{out}}

<pre>banana

--> ERROR: Input can't 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?"

2dup " bwt-->%3d %u\n" printf

ibwt " ibwt-> %u\n" printf nl

{{out}}

<pre>

ibwt-> "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES"

</pre>

 

=={{header|Go}}==

{{trans|Python}}

 

import (

fmt.Println(" -->", r, "\n")

}

 

{{out}}

-->

</pre>

=={{header|Groovy}}==

{{trans|Java}}

private static final String STX = "\u0002"

private static final String ETX = "\u0003"

}

}

{{out}}

<pre>banana

--> ERROR: String cannot contain STX or ETX

--> </pre>

=={{header|Haskell}}==

-- transform, based on the description in the Wikipedia article.

--

prettyVal (In c) = c

prettyVal Pre = '^'

 

{{out}}

SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

</pre>

=={{header|J}}==

<pre>

</pre>

 

NB. articulate definition

NB. local names (assignment =.) won't pollute the namespace

EMPTY

)

 

=={{header|Java}}==

{{trans|Kotlin}}

import java.util.List;

 

}

}

{{out}}

<pre>banana

--> 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

| first( .[] | select(endswith("\u0003")))

| .[1:-1] ;

'''Tests'''

def tests:

(

(if $t then " --> \($t | ibwt)\n" else "" end) ;

 

{{out}}

<pre>

--> ERROR: String can't contain STX or ETX

</pre>

=={{header|Julia}}==

 

function burrowswheeler_encode(s)

"\nInverse transformation: ", burrowswheeler_decode(burrowswheeler_encode(s)), "\n")

end

<pre>

Original: BANANA

ERROR: LoadError: "String for Burrows-Wheeler input cannot contain STX or ETX"

</pre>

=={{header|Kotlin}}==

{{trans|Python}}

 

const val STX = "\u0002"

println(" --> $r\n")

}

 

{{output}}

-->

</pre>

=={{header|Ksh}}==

#!/bin/ksh

 

echo

done

{{out}}<pre>

BANANA

|ABC^

ERROR: string cannot contain ^ or |</pre>

=={{header|Lua}}==

{{trans|Java}}

ETX = string.char(tonumber(3,16))

 

end

 

{{out}}

<pre>banana

--> 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];

InverseBurrowWheeler[%, {"^", "|"}]

BurrowWheeler["dogwood", {"^", "|"}]

{{out}}

<pre>|ANNB^AA

|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

echo "Original text: ", text

echo "After transformation: ", transformed.displaybleString()

 

{{out}}

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;

 

Test( 'SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES');

end.

{{out}}

<pre>

---> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES

</pre>

=={{header|Perl}}==

{{trans|Raku}}

binmode STDOUT, ":utf8";

 

}

 

{{out}}

<pre>Original: BANANA

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+

{{out}}

<pre>

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.

Ref: [https://www.codespeedy.com/burrows-wheeler-transform-in-python/ Burrows Wheeler Transform in Python]

 

def bwt(s):

"""Apply Burrows-Wheeler transform to input string."""

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

=={{header|Raku}}==

(formerly Perl 6)

{{works with|Rakudo|2018.06}}

 

# Using a visible character here for ease of viewing.

say 'Inverse transformed: ', ɯɹoɟsuɐɹʇ transform $phrase;

say '';

{{out}}

<pre>Original: BANANA

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.

$.= /*the default text for (all) the inputs*/

parse arg $.1 /*obtain optional arguments from the CL*/

_= @.j; @.j= @.k; @.k= _; ok= 0 /*swap two elements; flag as not done.*/

end /*j*/

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

***error*** BWT: invalid input: bad─bad thingy²

***error*** BWT: The input string contains an invalid character at position 15.

</pre>

 

=={{header|Ruby}}==

{{trans|C#}}

ETX = "\u0003"

 

end

 

{{out}}

<pre>banana

 

=={{header|Rust}}==

use core::cmp::Ordering;

 

}

}

{{out}}

<pre>

Inverse BWT: TO BE OR NOT TO BE OR WANT TO BE OR NOT?

</pre>

=={{header|Scala}}==

{{trans|Kotlin}}

 

object BWT {

})

}

{{out}}

<pre>banana

^ABC|

--> ERROR: String can't contain STX or ETX</pre>

 

=={{header|Sidef}}==

{{trans|Python}}

 

method encode(String s) {

say "BWT(#{dec.dump}) = #{enc.dump}"

assert_eq(str, dec)

{{out}}

<pre>

BWT("TOBEORNOTTOBEORTOBEORNOT") = "TOOOBBBRRTTTEEENNOOOOR$TO"

BWT("SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES") = "STEXYDST.E.IXXIIXXSSMPPS.B..EE.$.USFXDIIOIIIT"

</pre>

 

{{trans|Kotlin}}

 

 

private let stx = "\u{2}"

 

print("\(readableBwt(test)) -> \(readableBwt(b)) -> \(readableBwt(c))")

 

{{out}}

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|Visual Basic .NET}}==

{{trans|C#}}

 

ReadOnly STX As Char = Chr(&H2)

End Sub

 

{{out}}

<pre>banana

{{trans|Go}}

{{libheader|Wren-sort}}

 

var stx = "\x02"

var r = ibwt.call(t)

System.print(" --> %(r)\n")

 

{{out}}

 

=={{header|zkl}}==

fcn init(chr="$"){ var special=chr; }

fcn encode(str){

table.filter1("%s*".fmt(special).glob)[1,*]; // str[0]==$, often first element

}

//BWT.encode("$"); // --> assert(bbb.zkl:25): String cannot contain char "$"

 

enc:=BWT.encode(test);

println("%s\n -->%s\n -->%s".fmt(test,enc,BWT.decode(enc)));

{{out}}

<pre>