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