Anonymous user
Burrows–Wheeler transform: Difference between revisions
→{{header|J}}
Thundergnat (talk | contribs) m (Promote to task, lots of examples, little controversy) |
|||
Line 906:
--> ERROR: String cannot contain STX or ETX
--> </pre>
=={{header|J}}==
Working in integer space, all ASCII characters are allowed. Less useful for compression this way.
<pre>
NB. transform and inverse
bwt=: {:"1@:(/:~)@:(|."0 1~ -@:i.@:#)@:(256 , ,&257)@:(a.&([: :i.)) :.(a. {~ }.@:}:@:({~ (257 [: :i.~ {:"1))@:((,"0 1 /:~)^:(#@[)&(0$00)))
NB. demonstrate the transform
,. A=: <@bwt ;._2 ] 0 :0
tests[0] = "banana";
tests[1] = "appellee";
tests[2] = "dogwood";
tests[3] = "TO BE OR NOT TO BE OR WANT TO BE OR NOT?";
tests[4] = "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
)
┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│256 32 32 61 93 32 97 32 91 34 32 115 48 110 110 98 34 116 97 97 116 101 32 115 257 59 │
├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│256 32 32 61 93 32 101 32 91 34 32 115 49 34 101 108 112 116 108 101 112 97 116 101 32 115 257 59 │
├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│256 32 32 61 93 32 100 32 91 34 32 115 50 111 34 116 111 111 100 119 116 101 32 115 103 257 59 │
├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│256 32 32 61 93 79 79 79 82 82 69 69 69 84 84 82 32 63 32 91 34 32 84 87 32 32 32 66 66 66 32 32 65 84 84 84 32 32 32 78 78 79 79 79 78 79 79 34 32 32 32 115 51 116 116 101 32 115 257 59 │
├──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤
│256 32 32 61 93 32 83 32 34 84 69 88 89 68 83 84 91 32 46 69 46 73 88 88 73 73 88 88 83 83 77 80 80 83 46 66 46 46 69 69 46 34 46 85 83 70 88 68 73 73 79 73 73 73 84 115 52 116 116 101 32 115 257 44│
└──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘
NB. show the inverse transform
bwt inv &> A
tests[0] = "banana";
tests[1] = "appellee";
tests[2] = "dogwood";
tests[3] = "TO BE OR NOT TO BE OR WANT TO BE OR NOT?";
tests[4] = "SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
NB. the final test pattern
bwt a. {~ 2 , (a. i. 'ABC') , 3
256 67 2 65 66 257 3
bwt inv 256 67 2 65 66 257 3
�ABC�
</pre>
<lang>
NB. transform articulately defined
NB. local names (assignment =.) won't pollute the namespace
3 :0'define Burrows-Wheeler transformations'
Dyad=. [: :
index=. i. Dyad
Rank=. "
sort=. /:~
rotations=. |."0 1~ -@:i.@:#
tail=. {:
mark=. 256 , ,&257
integer=. a.&index
forward=. tail Rank 1 @: sort @: rotations @: mark @: integer
assert. 66 78 78 256 65 65 257 65 -: forward 'BANANA'
unscramble=. (,Rank 0 1 sort)^:(#@[)&(i.0)
find=. 257 index~ tail Rank 1
from=. {
behead=. }.
curtail=. }:
erase_mark =. behead @: curtail
inverse=. (a. from~ erase_mark @: (from~ find) @: unscramble)
assert. 'BANANA' -: inverse 66 78 78 256 65 65 257 65
obverse=. :.
fixed=. f.
bwt=: forward obverse inverse fixed
assert (-: ]&.:bwt)'same under transformation'
EMPTY
)
</lang>
=={{header|Julia}}==
| |||