Burrows–Wheeler transform: Difference between revisions

Line 14:

Source: [[wp:Burrows–Wheeler_transform|Burrows–Wheeler transform]]

=={{header|11l}}==

<syntaxhighlight lang=11l>F bwt(String =s)

<syntaxhighlight 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 70:

Line 69:

</pre>

=={{header|BQN}}==

<syntaxhighlight lang=~~BQN~~>stx←@+2

<syntaxhighlight lang="bqn">stx←@+2

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

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

Line 79:

Line 77:

</syntaxhighlight>

Example use:

<syntaxhighlight lang=text> BWT "banana"

<syntaxhighlight lang="text"> BWT "banana"

"annb␂aa"

BWT⁼ BWT "banana"

Line 107:

Line 105:

Error: Input contained STX

</syntaxhighlight>

=={{header|C}}==

<syntaxhighlight lang=c>#include <string.h>

<syntaxhighlight lang="c">#include <string.h>

#include <stdio.h>

#include <stdlib.h>

Line 236:

Line 233:

-->

</pre>

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

<syntaxhighlight lang=csharp>using System;

<syntaxhighlight lang="csharp">using System;

using System.Collections.Generic;

using System.Linq;

Line 363:

Line 359:

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

--></pre>

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

<syntaxhighlight lang=cpp>#include <algorithm>

<syntaxhighlight lang="cpp">#include <algorithm>

#include <iostream>

#include <vector>

Line 489:

Line 484:

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

--></pre>

=={{header|D}}==

<syntaxhighlight lang=d>import std.algorithm.iteration;

<syntaxhighlight lang="d">import std.algorithm.iteration;

import std.algorithm.mutation;

import std.algorithm.searching;

Line 590:

Line 584:

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

<syntaxhighlight lang=factor>USING: formatting io kernel math.transforms.bwt sequences ;

<syntaxhighlight 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 620:

Line 613:

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

</pre>

=={{header|Go}}==

<syntaxhighlight lang=go>package main

<syntaxhighlight lang="go">package main

import (

Line 725:

Line 717:

-->

</pre>

=={{header|Groovy}}==

<syntaxhighlight lang=groovy>class BWT {

<syntaxhighlight lang="groovy">class BWT {

private static final String STX = "\u0002"

private static final String ETX = "\u0003"

Line 826:

Line 817:

--> ERROR: String cannot contain STX or ETX

--> </pre>

=={{header|Haskell}}==

<syntaxhighlight lang=haskell>-- A straightforward, inefficient implementation of the Burrows–Wheeler

<syntaxhighlight lang="haskell">-- A straightforward, inefficient implementation of the Burrows–Wheeler

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

--

Line 895:

Line 885:

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

</pre>

=={{header|J}}==

<pre>

Line 929:

Line 918:

</pre>

NB. articulate definition

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

Line 969:

Line 958:

)

</syntaxhighlight>

=={{header|Java}}==

<syntaxhighlight lang=java>import java.util.ArrayList;

<syntaxhighlight lang="java">import java.util.ArrayList;

import java.util.List;

Line 1,073:

Line 1,061:

--> ERROR: String cannot contain STX or ETX

--> </pre>

=={{header|jq}}==

'''Works with gojq, the Go implementation of jq'''

<syntaxhighlight lang=jq># substitute ^ for STX and | for ETX

<syntaxhighlight lang="jq"># substitute ^ for STX and | for ETX

def makePrintable:

if . == null then null

Line 1,105:

Line 1,092:

</syntaxhighlight>

'''Tests'''

def tests:

(

Line 1,147:

Line 1,134:

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

</pre>

=={{header|Julia}}==

<syntaxhighlight lang=julia>bwsort(vec) = sort(vec, lt = (a, b) -> string(a) < string(b))

<syntaxhighlight lang="julia">bwsort(vec) = sort(vec, lt = (a, b) -> string(a) < string(b))

function burrowswheeler_encode(s)

Line 1,196:

Line 1,182:

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

</pre>

=={{header|Kotlin}}==

<syntaxhighlight lang=scala>// Version 1.2.60

<syntaxhighlight lang="scala">// Version 1.2.60

const val STX = "\u0002"

Line 1,287:

Line 1,272:

-->

</pre>

=={{header|Ksh}}==

#!/bin/ksh

Line 1,420:

Line 1,404:

|ABC^

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

=={{header|Lua}}==

<syntaxhighlight lang=lua>STX = string.char(tonumber(2,16))

<syntaxhighlight lang="lua">STX = string.char(tonumber(2,16))

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

Line 1,532:

Line 1,515:

--> ERROR: bwt.lua:6: String cannot contain STX

--></pre>

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

<syntaxhighlight lang=~~Mathematica~~>ClearAll[BurrowWheeler, InverseBurrowWheeler]

<syntaxhighlight lang="mathematica">ClearAll[BurrowWheeler, InverseBurrowWheeler]

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

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

Line 1,563:

Line 1,545:

|do^oodwg

dogwood</pre>

=={{header|Nim}}==

Translation of the Wikipedia Python algorithm. The program uses characters '¹' and '²' to display STX and ETX.

<syntaxhighlight lang=~~Nim~~>import algorithm

<syntaxhighlight lang="nim">import algorithm

from sequtils import repeat

import strutils except repeat

Line 1,656:

Line 1,637:

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,883:

Line 1,863:

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

</pre>

=={{header|Perl}}==

<syntaxhighlight lang=perl>use utf8;

<syntaxhighlight lang="perl">use utf8;

binmode STDOUT, ":utf8";

Line 1,938:

Line 1,917:

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/

Takes around about ten seconds to transform and invert a 100K string. Note: requires 0.8.0+

-- demo\rosetta\burrows_wheeler.exw

--/*

Line 2,100:

Line 2,078:

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:

Line 2,085:

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

Line 2,126:

Line 2,103:

return s.rstrip("\003").strip("\002") # Get rid of start and end markers

</syntaxhighlight>

=={{header|Raku}}==

(formerly Perl 6)

<syntaxhighlight lang=raku line># STX can be any character that doesn't appear in the text.

<syntaxhighlight lang="raku" line># STX can be any character that doesn't appear in the text.

# Using a visible character here for ease of viewing.

Line 2,178:

Line 2,154:

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

function.   The error recovery and error messages are rudimentary when an illegal character in the input is detected.

<syntaxhighlight lang=rexx>/*REXX program performs a Burrows─Wheeler transform (BWT) on a character string(s). */

<syntaxhighlight 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,269:

Line 2,244:

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

</pre>

=={{header|Ruby}}==

<syntaxhighlight lang=ruby>STX = "\u0002"

<syntaxhighlight lang="ruby">STX = "\u0002"

ETX = "\u0003"

Line 2,366:

Line 2,340:

--> Input can't contain STX or ETX

--></pre>

=={{header|Rust}}==

use core::cmp::Ordering;

Line 2,479:

Line 2,452:

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

</pre>

=={{header|Scala}}==

<syntaxhighlight lang=scala>import scala.collection.mutable.ArrayBuffer

<syntaxhighlight lang="scala">import scala.collection.mutable.ArrayBuffer

object BWT {

Line 2,571:

Line 2,543:

^ABC|

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

=={{header|Sidef}}==

<syntaxhighlight lang=ruby>class BurrowsWheelerTransform (String L = "\002") {

<syntaxhighlight lang="ruby">class BurrowsWheelerTransform (String L = "\002") {

method encode(String s) {

Line 2,611:

Line 2,582:

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

</pre>

=={{header|Swift}}==

<syntaxhighlight lang=swift>import Foundation

<syntaxhighlight lang="swift">import Foundation

private let stx = "\u{2}"

Line 2,680:

Line 2,650:

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

<syntaxhighlight lang=vbnet>Module Module1

<syntaxhighlight lang="vbnet">Module Module1

ReadOnly STX As Char = Chr(&H2)

Line 2,807:

Line 2,776:

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

--></pre>

=={{header|Wren}}==

<syntaxhighlight lang=ecmascript>import "/sort" for Sort

<syntaxhighlight lang="ecmascript">import "/sort" for Sort

var stx = "\x02"

Line 2,896:

Line 2,864:

-->

</pre>

=={{header|zkl}}==

<syntaxhighlight lang=zkl>class BurrowsWheelerTransform{

<syntaxhighlight lang="zkl">class BurrowsWheelerTransform{

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

fcn encode(str){

Line 2,915:

Line 2,882:

}

}</syntaxhighlight>

<syntaxhighlight lang=zkl>BWT:=BurrowsWheelerTransform();

<syntaxhighlight lang="zkl">BWT:=BurrowsWheelerTransform();

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