Here's a fast version of the inverse transform, using the algorithm outlined
in section 4.2 of
http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.pdf:
ibwt =: }:@:((4 :0)~ i.&EAV)
c=. +/\ 0,}: <: #/.~ a.,y
p=. <: (a.i.y) {"_1 +/\ a.=/~y
|. y{~ ({&p + c{~{&(a.i.y))^:(<#y) x
)
ibwt bwt '^BANANA'
^BANANA
f=. a.{~ 97+1e6 ?@$ 26
6!:2 'ff=. bwt f'
3.89258
6!:2 'ibwt ff'
4.61294
Note that the inner function in ibwt (i.e. the (4 :0) part) takes left
argument the index of the last character, and right argument the encoded
string. Therefore only the inside part can be used if you have an output
formatted with an index.
Marshall
On Thu, Sep 8, 2011 at 3:07 PM, Marshall Lochbaum <[email protected]>wrote:
> And here it is! Certifiably faster than the naive version.
>
> sortbox =: </. /: ~.@[
> bwt =: 3 :'y{~ (([: ; $:^:(1<#)&.>)@:sortbox~ y{~(#y)&|)&.:>: i.@
> #y=.y,EAV'
>
> bwt 'aba'
> �baa
> f=. a.{~ 97+20000?@$26
> 6!:2 'bwt f'
> 0.0843269
> bwt0=:{:"1@/:~@(|."0 1~ i.@-@#)@(,&EAV)
> 6!:2 'bwt0 f'
> 0.976645
>
> Marshall
>
> On Thu, Sep 8, 2011 at 2:59 PM, Marshall Lochbaum <[email protected]>wrote:
>
>> I just realized this. I'm working on a radix-sort-ish method that actually
>> performs the correct transform now.
>>
>> Marshall
>>
>>
>> On Thu, Sep 8, 2011 at 2:57 PM, Raul Miller <[email protected]>wrote:
>>
>>> On Thu, Sep 8, 2011 at 2:41 PM, Marshall Lochbaum <[email protected]>
>>> wrote:
>>> > The forward transform can be implemented as:
>>> >
>>> > bwt =: (/: 1&|.)@:(,&EAV)
>>>
>>> bwt=: (/: 1&|.)@:(,&EAV)
>>> bwt0=:{:"1@/:~@(|."0 1~ i.@-@#)@(,&EAV)
>>> (bwt -: bwt0) 'aba'
>>> 0
>>> bwt 'aba'
>>> b�aa
>>> bwt0 'aba'
>>> �baa
>>>
>>> --
>>> Raul
>>> ----------------------------------------------------------------------
>>> For information about J forums see http://www.jsoftware.com/forums.htm
>>>
>>
>>
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
