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.

4 comments:

Adi said...

Oes Tsetnoc one of the ways in which we can learn seo besides Mengembalikan Jati Diri Bangsa. By participating in the Oes Tsetnoc or Mengembalikan Jati Diri Bangsa we can improve our seo skills. To find more information about Oest Tsetnoc please visit my Oes Tsetnoc pages. And to find more information about Mengembalikan Jati Diri Bangsa please visit my Mengembalikan Jati Diri Bangsa pages. Thank you So much.
Oes Tsetnoc | Semangat Mengembalikan Jati Diri Bangsa

zhengbin 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.

Dakuro 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

رضا رمضان said...




خدمات نقل الاثاث متعددة لدينا حيث يوجد لدينا خبرة في كيفية التعامل مع العملاء في تنفيذ اعمال فلدينا مدينة مكة افضل شركة نقل اثاث بمكة التي تتميز بالدقة في تنفيذ اعمال وتوصيل الاثاث من الباب لاننا نمتلك عمال متميزون في شركة نقل عفش بمكة فعليكم التواصل معنا من اجل الاستفادة من الخدمات التي نقدمها كل هذا ايضا تلاقه في مدينة الدمام من خلال التواصل مع شركة نقل اثاث بالدمام التي تمتلك فنين متميزين في اعمال الفك والتركيب كما لديها اسطول سيارات مجهز يساعدها علي الوصول الي منزلك الجديد فكل شئ يكون جاهز مع شركة نقل عفش بالدمام التي اثبتت انها نقل شركة لديها خبرة كبيرة في مجال نقل الاثاث
كما يوجد لدينا خبرة في خدمات نقل الاثاث بجدة من خلال
شركة نقل اثاث بجدة
شركة نقل عفش بجدة