[Jprogramming] Burrows-Wheeler Transform

[Mike Müller]

Sorry for dragging up such an old thread, but I just read this and wanted to remark, that it's essential for the BWT to sort on all characters.
There's a variant called Sort Transform (or sometimes Schindler Transform) that only sorts the cyclic shifts according to the first k characters.
See, for instance: http://arxiv.org/abs/0908.0239
Inverting this one is more complicated though…

Mike

Am 03.02.2013 um 04:43 schrieb Henry Rich <HenryHRich at nc.rr.com>:

> 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