Raul
-----Original Message-----
From: [email protected]
[mailto:[email protected]] On Behalf Of Henry Rich
Sent: Saturday, February 02, 2013 10:44 PM
To: [email protected]
Subject: Re: [Jprogramming] Burrows-Wheeler Transform
I don't know jack about the BWT, but from the Wikipedia entry this looks
like an implementation:
({~ <:@/:) 'aBANANAz'
BNNaAAzA
That works for their testcase, but it doesn't match yours. I think the
difference is that you sort on all characters rather than just the first.
Is this simpler version good enough?
Henry Rich
On 2/2/2013 10:08 PM, Raul Miller wrote:
> Here's a slightly flawed implementation of Burrows-Wheeler Transform
> (which is useful when compressing text, because the result tends to be
> easy to compress):
>
> bwt0=: (_1 {"1 [: /:~ (|."0 1~ i.@#)) :. ibwt0
> bwt0 'this is a test'
> ssa tt hiie ts
> ibwt0=: (_1 { ((,. /:~)^:(#@[) (#,0:) $ ''"_)) :. bwt0
> ibwt0 bwt0 'this is a test'
> stthis is a te
>
> As you can see, the inverse does not quite work right -- it has been
rotated.
>
> Here's a fixed implementation:
>
> bwt=: bwt0@,&EAV :.ibwt
> ibwt=: }.@(|.~ i.&EAV)@ibwt0 :.bwt
> ibwt bwt 'this is a test'
> this is a test
>
> This fixed implementation might fail if the original data contained EAV.
>
> It seems like we ought to be able to implement the transform without
> this flaw (perhaps using a boxed representation).
>
> Allowing arbitrary treatments of how the transformed result tracks the
> original location of the beginning/end of text, do we have a more
> efficient way of computing the inverse (or the transform)?
>
> Thanks,
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
