Rosetta Code

Burrows–Wheeler transform: Difference between revisions

Page Discussion

Burrows–Wheeler transform (view source)

Revision as of 20:00, 30 August 2022

39 bytes added ,  1 year ago
m
Automated syntax highlighting fixup (second round - minor fixes)
m (syntax highlighting fixup automation)
m (Automated syntax highlighting fixup (second round - minor fixes))
Line 14:
Source: [[wp:Burrows–Wheeler_transform|Burrows–Wheeler transform]]
<br><br>
 
=={{header|11l}}==
{{trans|Python}}
 
<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 ⟶ 69:
 
</pre>
 
=={{header|BQN}}==
<syntaxhighlight lang=BQN"bqn">stx←@+2
BWT ← { # Burrows-Wheeler Transform and its inverse as an invertible function
𝕊: "Input contained STX"!⊑stx¬∘∊𝕩 ⋄ (⍋↓𝕩) ⊏ stx∾𝕩;
Line 79 ⟶ 77:
</syntaxhighlight>
Example use:
<syntaxhighlight lang="text"> BWT "banana"
"annb␂aa"
BWT⁼ BWT "banana"
Line 107 ⟶ 105:
Error: Input contained STX
</syntaxhighlight>
 
=={{header|C}}==
{{trans|Python}}
<syntaxhighlight lang="c">#include <string.h>
#include <stdio.h>
#include <stdlib.h>
Line 236 ⟶ 233:
-->
</pre>
 
=={{header|C sharp|C#}}==
{{trans|D}}
<syntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.Linq;
Line 363 ⟶ 359:
--> ERROR: Input can't contain STX or ETX
--></pre>
 
=={{header|C++}}==
{{trans|C#}}
<syntaxhighlight lang="cpp">#include <algorithm>
#include <iostream>
#include <vector>
Line 489 ⟶ 484:
--> Error Input can't contain STX or ETX
--></pre>
 
=={{header|D}}==
{{trans|Kotlin}}
<syntaxhighlight lang="d">import std.algorithm.iteration;
import std.algorithm.mutation;
import std.algorithm.searching;
Line 590 ⟶ 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 ;
{
"banana" "dogwood" "TO BE OR NOT TO BE OR WANT TO BE OR NOT?"
Line 620 ⟶ 613:
ibwt-> "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES"
</pre>
 
=={{header|Go}}==
{{trans|Python}}
<syntaxhighlight lang="go">package main
 
import (
Line 725 ⟶ 717:
-->
</pre>
 
=={{header|Groovy}}==
{{trans|Java}}
<syntaxhighlight lang="groovy">class BWT {
private static final String STX = "\u0002"
private static final String ETX = "\u0003"
Line 826 ⟶ 817:
--> ERROR: String cannot contain STX or ETX
--> </pre>
 
=={{header|Haskell}}==
<syntaxhighlight lang="haskell">-- A straightforward, inefficient implementation of the Burrows–Wheeler
-- transform, based on the description in the Wikipedia article.
--
Line 895 ⟶ 885:
SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
</pre>
 
=={{header|J}}==
<pre>
Line 929 ⟶ 918:
</pre>
 
<syntaxhighlight lang="text">
NB. articulate definition
NB. local names (assignment =.) won't pollute the namespace
Line 969 ⟶ 958:
)
</syntaxhighlight>
 
=={{header|Java}}==
{{trans|Kotlin}}
<syntaxhighlight lang="java">import java.util.ArrayList;
import java.util.List;
 
Line 1,073 ⟶ 1,061:
--> ERROR: String cannot contain STX or ETX
--> </pre>
 
=={{header|jq}}==
{{trans|Wren}}
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
<syntaxhighlight lang="jq"># substitute ^ for STX and | for ETX
def makePrintable:
if . == null then null
Line 1,105 ⟶ 1,092:
</syntaxhighlight>
'''Tests'''
<syntaxhighlight lang="jq">
def tests:
(
Line 1,147 ⟶ 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))
 
function burrowswheeler_encode(s)
Line 1,196 ⟶ 1,182:
ERROR: LoadError: "String for Burrows-Wheeler input cannot contain STX or ETX"
</pre>
 
=={{header|Kotlin}}==
{{trans|Python}}
<syntaxhighlight lang="scala">// Version 1.2.60
 
const val STX = "\u0002"
Line 1,287 ⟶ 1,272:
-->
</pre>
 
=={{header|Ksh}}==
<syntaxhighlight lang="ksh">
#!/bin/ksh
 
Line 1,420 ⟶ 1,404:
|ABC^
ERROR: string cannot contain ^ or |</pre>
 
=={{header|Lua}}==
{{trans|Java}}
<syntaxhighlight lang="lua">STX = string.char(tonumber(2,16))
ETX = string.char(tonumber(3,16))
 
Line 1,532 ⟶ 1,515:
--> ERROR: bwt.lua:6: String cannot contain STX
--></pre>
 
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<syntaxhighlight lang=Mathematica"mathematica">ClearAll[BurrowWheeler, InverseBurrowWheeler]
BurrowWheeler[sin_String, {bdelim_, edelim_}] := Module[{s},
s = Characters[bdelim <> sin <> edelim];
Line 1,563 ⟶ 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"nim">import algorithm
from sequtils import repeat
import strutils except repeat
Line 1,656 ⟶ 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.
<syntaxhighlight lang="pascal">
program BurrowsWheeler;
 
Line 1,883 ⟶ 1,863:
---> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
</pre>
 
=={{header|Perl}}==
{{trans|Raku}}
<syntaxhighlight lang="perl">use utf8;
binmode STDOUT, ":utf8";
 
Line 1,938 ⟶ 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/ <br>
Takes around about ten seconds to transform and invert a 100K string. Note: requires 0.8.0+
<!--<syntaxhighlight lang=Phix"phix">(phixonline)-->
<span style="color: #000080;font-style:italic;">-- demo\rosetta\burrows_wheeler.exw
--/*
Line 2,100 ⟶ 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 ⟶ 2,085:
Ref: [https://www.codespeedy.com/burrows-wheeler-transform-in-python/ Burrows Wheeler Transform in Python]
 
<syntaxhighlight lang=Python"python">
def bwt(s):
"""Apply Burrows-Wheeler transform to input string."""
Line 2,126 ⟶ 2,103:
return s.rstrip("\003").strip("\002") # Get rid of start and end markers
</syntaxhighlight>
 
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2018.06}}
 
<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 ⟶ 2,154:
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.
<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 ⟶ 2,244:
***error*** BWT: The input string contains an invalid character at position 15.
</pre>
 
=={{header|Ruby}}==
{{trans|C#}}
<syntaxhighlight lang="ruby">STX = "\u0002"
ETX = "\u0003"
 
Line 2,366 ⟶ 2,340:
--> Input can't contain STX or ETX
--></pre>
 
=={{header|Rust}}==
<syntaxhighlight lang="rust">
use core::cmp::Ordering;
 
Line 2,479 ⟶ 2,452:
Inverse BWT: TO BE OR NOT TO BE OR WANT TO BE OR NOT?
</pre>
 
=={{header|Scala}}==
{{trans|Kotlin}}
<syntaxhighlight lang="scala">import scala.collection.mutable.ArrayBuffer
 
object BWT {
Line 2,571 ⟶ 2,543:
^ABC|
--> ERROR: String can't contain STX or ETX</pre>
 
=={{header|Sidef}}==
{{trans|Python}}
<syntaxhighlight lang="ruby">class BurrowsWheelerTransform (String L = "\002") {
 
method encode(String s) {
Line 2,611 ⟶ 2,582:
BWT("SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES") = "STEXYDST.E.IXXIIXXSSMPPS.B..EE.$.USFXDIIOIIIT"
</pre>
 
=={{header|Swift}}==
 
{{trans|Kotlin}}
 
<syntaxhighlight lang="swift">import Foundation
 
private let stx = "\u{2}"
Line 2,680 ⟶ 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}}==
{{trans|C#}}
<syntaxhighlight lang="vbnet">Module Module1
 
ReadOnly STX As Char = Chr(&H2)
Line 2,807 ⟶ 2,776:
--> ERROR: Input can't contain STX or ETX
--></pre>
 
=={{header|Wren}}==
{{trans|Go}}
{{libheader|Wren-sort}}
<syntaxhighlight lang="ecmascript">import "/sort" for Sort
 
var stx = "\x02"
Line 2,896 ⟶ 2,864:
-->
</pre>
 
=={{header|zkl}}==
<syntaxhighlight lang="zkl">class BurrowsWheelerTransform{
fcn init(chr="$"){ var special=chr; }
fcn encode(str){
Line 2,915 ⟶ 2,882:
}
}</syntaxhighlight>
<syntaxhighlight lang="zkl">BWT:=BurrowsWheelerTransform();
//BWT.encode("$"); // --> assert(bbb.zkl:25): String cannot contain char "$"
 
Thundergnat
10,333

edits

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