From: Trans <transfire@...>
Date: 2007-03-20T12:12:38+09:00
Subject: Re: Just for fun...



On Mar 19, 4:20 pm, David Kastrup <d...@gnu.org> wrote:
> "Trans" <transf...@gmail.com> writes:
> > On Mar 15, 2:33 pm, "Matthew Moss" <matthew.moss.co...@gmail.com>
> > wrote:
> >> On 3/15/07, Stephen Lewis <step...@sock.org.uk> wrote:
>
> >> > Matthew Moss wrote:
> >> > > +5 pts if you know what algorithm is being used here...
>
> >> > I'm not going to try to golf it right now, but it looks like an inverse
> >> > Burrows-Wheeler Transform.
>
> >> +5 for Stephen.  =)
>
> > Looks interesting. Care to elaborate on "inverse Burrows-Wheeler
> > Transform"?
>
> The Burrows-Wheeler transform takes some arbitrary string, say,
> gigantomania and sorts the permutations: we start with
>
> gigantomania
> igantomaniag
> gantomaniagi
> antomaniagig
> ntomaniagiga
> tomaniagigan
> omaniagigant
> maniagiganto
> aniagigantom
> niagigantoma
> iagigantoman
> agigantomani
>
> and then sort the lines:
>
> agigantomani
> aniagigantom
> antomaniagig
> gantomaniagi
> gigantomania
> iagigantoman
> igantomaniag
> maniagiganto
> niagigantoma
> ntomaniagiga
> omaniagigant
> tomaniagigan
>
> Then we take the last column and assign numbers to it:
>
> imgiangoaatn
> 0123456789AB
>
> Now we sort the letters with the numbers alongside.
>
> aaaggiimnnot
> 489260315B7A
>
> And now we walk off a linked list starting at 4 (we need to remember
> that starting position since all cyclic strings have the same BWT
> transform otherwise).
>
> That puts out the original sequence.

That's nuts.

T.