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

Published on 12 May 2024 09:40 PM
#J

How to resolve the algorithm Burrows–Wheeler transform step by step in the J 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 J programming language

Source code in the j programming language

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

3 :0'define Burrows-Wheeler transformations'
 Dyad=. [: :
 Monad=. :[:
 index=. i. Dyad
 Rank=. "
 sort=. /:~ Monad

 signal_error=. 13!:8
 VALUE_ERROR=.  21
 'STX ETX'=. 2 3 { a.
 verify=. ([ ('STX or ETX invalid in input' signal_error VALUE_ERROR + 0:))^:(1 e. (STX , ETX)&e.)
 rotations=. |."0 1~ -@:i.@:#
 tail=. {:
 mark=. STX , ,&ETX
 transform=. tail Rank 1 @: sort @: rotations @: mark @: verify
 EXPECT=. ETX , 'ANNB' , STX , 'AA'
 assert. EXPECT -: transform 'BANANA'

 unscramble=. (,Rank 0 1 sort)^:(#@[)&(i.0)
 find=. ETX index~ tail Rank 1
 from=. {
 behead=. }.
 curtail=. }:
 erase_mark =. behead @: curtail
 restore=.  erase_mark @: (from~ find) @: unscramble
 assert. 'BANANA' -: restore EXPECT

 obverse=. :.
 fixed=. f.
 bwt=: transform obverse restore fixed

 assert (-: ]&.:bwt)'same under transformation'

 EMPTY
)


bwt=:verb def '{:"1 /:~(|."0 1~i.@#) (8 u:y),{:a.'
ibwt=: 1 (}.{:) (/:~@,.^:(#@]) 0#"0])


   bwt'This is a test.'
ssat� tT hiies .
   ibwt bwt'This is a test.'
This is a test.

You may also check:How to resolve the algorithm Read entire file step by step in the AppleScript programming language
You may also check:How to resolve the algorithm Named parameters step by step in the Java programming language
You may also check:How to resolve the algorithm Metaprogramming step by step in the Lingo programming language
You may also check:How to resolve the algorithm Narcissistic decimal number step by step in the Java programming language
You may also check:How to resolve the algorithm Averages/Pythagorean means step by step in the Forth programming language