Burrows-Wheeler (BWT) Algorithm in Python

[DENG]

Hi, all

I've used Python Bz2 module for times and want to kown something about
Burrows-Wheeler (BWT) algorithm, the Bz2 module is wrriten in C, is
there a version in Python too?

BWT

http://gatekeeper.dec.com/pub/DEC/SRC/research-reports/abstracts/src-rr-124.html

Python Bz2 module

http://labix.org/python-bz2

thanks

[Michael J. Fromberger]

Re: Burrows-Wheeler (BWT) Algorithm in Python

In article <1130919309.381 711.305450@f14g 2000cwb.googleg roups.com>,
"DENG" <polytechnique@ gmail.com> wrote:
[color=blue]
> Hi, all
>
> I've used Python Bz2 module for times and want to kown something about
> Burrows-Wheeler (BWT) algorithm, the Bz2 module is wrriten in C, is
> there a version in Python too?
>
> BWT
> http://gatekeeper.dec.com/pub/DEC/SR.../src-rr-124.ht
> ml
> Python Bz2 module
> http://labix.org/python-bz2[/color]

It is perfectly possible to implement the BWT in Python. I can send you
a Python implementation I wrote, if you like; but if you're interested
in better understanding how the transform works, I would recommend you
try writing your own implementation. It's not very difficult to do,
though for large inputs you may find performance to be an issue.

Mark Nelson wrote a nice user-friendly article on the BWT for the Sep.
1996 issue of Dr. Dobbs, you might have a look:

http://www.dogma.net/markn/articles/bwt/bwt.htm

I hope this helps you get started.

-M

--
Michael J. Fromberger | Lecturer, Dept. of Computer Science
http://www.dartmouth.edu/~sting/ | Dartmouth College, Hanover, NH, USA

[bearophileHUGS@lycos.com]

Re: Burrows-Wheeler (BWT) Algorithm in Python

Michael J. Fromberger:[color=blue]
> I can send you
> a Python implementation I wrote, if you like; but if you're interested
> in better understanding how the transform works, I would recommend you
> try writing your own implementation.[/color]

I'd like to see it, if you want you can put it somewhere or send it
directly.

Bye and thank you,
bearophile

[Michael J. Fromberger]

Re: Burrows-Wheeler (BWT) Algorithm in Python

In article <1131048758.719 582.204090@g43g 2000cwa.googleg roups.com>,
bearophileHUGS@ lycos.com wrote:
[color=blue]
> Michael J. Fromberger:[color=green]
> > I can send you a Python implementation I wrote, if you like; but if
> > you're interested in better understanding how the transform works,
> > I would recommend you try writing your own implementation.[/color]
>
> I'd like to see it, if you want you can put it somewhere or send it
> directly.[/color]

You can grab a copy here:

http://www.cs.dartmouth.edu/~sting/sw/bwt.py

Cheers,
-M

--
Michael J. Fromberger | Lecturer, Dept. of Computer Science
http://www.dartmouth.edu/~sting/ | Dartmouth College, Hanover, NH, USA

[DENG]

Re: Burrows-Wheeler (BWT) Algorithm in Python

thanks very much Michael

i'll try your implementation, i hope i can improve it after i
understand all the theory:)

cheers