How to resolve the algorithm Burrows–Wheeler transform step by step in the Perl programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Burrows–Wheeler transform step by step in the Perl programming language

Table of Contents

Problem Statement

The Burrows–Wheeler transform (BWT, also called block-sorting compression) rearranges a character string into runs of similar characters. This is useful for compression, since it tends to be easy to compress a string that has runs of repeated characters by techniques such as move-to-front transform and run-length encoding. More importantly, the transformation is reversible, without needing to store any additional data. The BWT is thus a "free" method of improving the efficiency of text compression algorithms, costing only some extra computation.

Source: Burrows–Wheeler transform

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Burrows–Wheeler transform step by step in the Perl programming language

Source code in the perl programming language

use utf8;
binmode STDOUT, ":utf8";

use constant STX => '👍 ';

sub transform {
    my($s) = @_;
    my($t);
    warn "String can't contain STX character." and exit if $s =~ /STX/;
    $s = STX . $s;
    $t .= substr($_,-1,1) for sort map { rotate($s,$_) } 1..length($s);
    return $t;
}

sub rotate { my($s,$n) = @_; join '', (split '', $s)[$n..length($s)-1, 0..$n-1] }

sub ɯɹoɟsuɐɹʇ {
    my($s) = @_;
    my @s = split '', $s;
    my @t = sort @s;
    map { @t = sort map { $s[$_] . $t[$_] } 0..length($s)-1 } 1..length($s)-1;
    for (@t) {
        next unless /${\(STX)}$/;  # interpolate the constant
        chop $_ and return $_
    }
}

for $phrase (qw<BANANA dogwood SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES>,
    'TO BE OR NOT TO BE OR WANT TO BE OR NOT?') {
    push @res, 'Original:            '. $phrase;
    push @res, 'Transformed:         '. transform $phrase;
    push @res, 'Inverse transformed: '. ɯɹoɟsuɐɹʇ transform $phrase;
    push @res, '';
}

print join "\n", @res;


  

You may also check:How to resolve the algorithm Call a foreign-language function step by step in the Arturo programming language
You may also check:How to resolve the algorithm Inverted syntax step by step in the ARM Assembly programming language
You may also check:How to resolve the algorithm Factors of a Mersenne number step by step in the Swift programming language
You may also check:How to resolve the algorithm Take notes on the command line step by step in the Scala programming language
You may also check:How to resolve the algorithm HTTP step by step in the Erlang programming language