Tuesday, April 03, 2007

Burrows-Wheeler transform in Python

def bwt(s):
s = s + '\0'
return ''.join([x[-1] for x in
sorted([s[i:] + s[:i] for i in range(len(s))])])

def ibwt(s):
L = [''] * len(s)
for i in range(len(s)):
L = sorted([s[i] + L[i] for i in range(len(s))])
return [x for x in L if x.endswith('\0')][0][:-1]
The Burrows-Wheeler transform [1] is an invertible mathematical transformation which tends to clump related sequences of data together; hence it is useful as a pre-pass for some compression algorithms. The BWT domain in the above code excludes the null character; to include the null character, modify the transformation to also output the row of sorted([s[i:] + s[:i]...]) on which s occurs, then in IBWT simply return this row after the for loop. The Python code above is not particularly fast.

2 comments:

tpjewelry said...

Kauf und Verkauf von Gold in den thomas sabo Goldmarkt hat viel an Popularität gewonnen, sind thomas sabo shop Gold-Nuggets und Goldmünzen im Handel erhältlich herkömmlichen thomas sabo jewellery Wege der Kauf und Verkauf bei niedrigen wenn thomas sabo schmuck high.Tips Gold und Silver.Have eine thomassabo online shop klare Vorstellung davon, warum die Schmuck thomas sabo onlineshop verkaufen muss, um verkauft werden und Scout für die sabo schmuck entsprechende buyer.Volume aus Gold oder thomas sabo shop online Silber zu einem Zeitpunkt verkauft werden bestimmen den Verkaufspreis und die Verhandlungsmacht thomas sabo charm club der seller.Purity bestimmt auch den Endpreis der verkauften Artikel.

Anonymous said...

There's a proagrammer that know a lot about this, this friend of my use to hack web pages and forums for incressing something realted with the traffic I don't know but the think it's that I understand the algoritms, and many times I realize when someone it's trying to do something.

________________________________________
Viagra Online