Burrows–Wheeler transform: Difference between revisions

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

 

=={{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}}

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

{{trans|D}}

using System.Collections.Generic;

using System.Linq;

}

}

{{out}}

<pre>banana

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

{{trans|C#}}

#include <iostream>

#include <vector>

 

return 0;

{{out}}

<pre>banana

=={{header|D}}==

{{trans|Kotlin}}

import std.algorithm.mutation;

import std.algorithm.searching;

writeln;

}

{{out}}

<pre>banana

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

=={{header|Go}}==

{{trans|Python}}

 

import (

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

}

 

{{out}}

=={{header|Groovy}}==

{{trans|Java}}

private static final String STX = "\u0002"

private static final String ETX = "\u0003"

}

}

{{out}}

<pre>banana

 

=={{header|Haskell}}==

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

--

prettyVal (In c) = c

prettyVal Pre = '^'

 

{{out}}

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

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

 

=={{header|Julia}}==

 

function burrowswheeler_encode(s)

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

end

<pre>

Original: BANANA

=={{header|Kotlin}}==

{{trans|Python}}

 

const val STX = "\u0002"

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

}

 

{{output}}

 

=={{header|Ksh}}==

#!/bin/ksh

 

echo

done

{{out}}<pre>

BANANA

=={{header|Lua}}==

{{trans|Java}}

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

 

end

 

{{out}}

<pre>banana

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

BurrowWheeler[sin_String, {bdelim_, edelim_}] := Module[{s},

s = Characters[bdelim <> sin <> edelim];

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

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

{{out}}

<pre>|ANNB^AA

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

 

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>

=={{header|Perl}}==

{{trans|Raku}}

binmode STDOUT, ":utf8";

 

}

 

{{out}}

<pre>Original: BANANA

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

--/*

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

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

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

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>

=={{header|Ruby}}==

{{trans|C#}}

ETX = "\u0003"

 

end

 

{{out}}

<pre>banana

 

=={{header|Rust}}==

use core::cmp::Ordering;

 

}

}

{{out}}

<pre>

=={{header|Scala}}==

{{trans|Kotlin}}

 

object BWT {

})

}

{{out}}

<pre>banana

=={{header|Sidef}}==

{{trans|Python}}

 

method encode(String s) {

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

assert_eq(str, dec)

{{out}}

<pre>

{{trans|Kotlin}}

 

 

private let stx = "\u{2}"

 

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

 

{{out}}

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