Burrows-Wheeler (BWT) Algorithm in Python

[Michael J. Fromberger]

In article <1130919309.381711.305450 at f14g2000cwb.googlegroups.com>,
 "DENG" <polytechnique at gmail.com> wrote:

> 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.ht
> ml
> Python Bz2 module
> http://labix.org/python-bz2

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