This is similar:
erase names ''
1 1 1
ibwt =: }:@:((4 :0)~ i.&EAV)
c=. +/\ 0,}: <: #/.~ a.,y
p=. <: (a.i.y) {"_1 +/\ a.=/~y
|. y{~ ({&p + c{~{&(a.i.y))^:(<#y) x
)
bwt 'this is a test'
|value error: bwt
Linda
-----Original Message-----
From: [email protected]
[mailto:[email protected]] On Behalf Of Marshall Lochbaum
Sent: Thursday, September 08, 2011 4:17 PM
To: Programming forum
Subject: Re: [Jprogramming] Burrows–Wheeler transform
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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
