http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform
The Burrows Wheeler transform is a reversible transform on text which
makes strings where some characters occur much more frequently than
others easier to compress. See the wikipedia url for more details.
Here's an inefficient but straightforward implementation, which
assumes that EAV is not contained in the string:
bwt=:{:"1@/:~@(|."0 1~ i.@-@#)@(,&EAV)
ibwt=: [: }.@(|.~ i.&EAV)@{. (,. /:~)^:(#@] - 1:)~
And, here is the wikipedia example:
bwt '^BANANA'
BNN^AA�A
ibwt bwt '^BANANA'
^BANANA
Note that a more robust implementation would have an index rather than
EAV to mark end-of-string location (which is necessary for reversal to
succeed), so the result should be a pair of boxes (containing an index
and an string).
Building more efficient implementations might interest some of you?
(I'll probably be trying this, myself, when I have some free time.)
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
