Added BWT naive implementation.

bhehir · Jun 20, 2011 · 583aae2 · 583aae2
1 parent e498a75
commit 583aae2
Show file tree

Hide file tree

Showing 2 changed files with 42 additions and 1 deletion.
diff --git a/transform/BWT/ref/memo.txt b/transform/BWT/ref/memo.txt
@@ -1 +1,13 @@
-http://marknelson.us/1996/09/01/bwt/
+
+Michael Burrows and David Wheele: ftp://gatekeeper.research.compaq.com/pub/DEC/SRC/research-reports/SRC-124.pdf
+
+Michael Dipperstein
+Burrows-Wheeler Transform Discussion and Implementation
+http://michael.dipperstein.com/bwt/
+
+Mark Nelson
+Data Compression with the Burrows-Wheeler Transform
+http://marknelson.us/1996/09/01/bwt/
+
+WIKI
+http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform
diff --git a/transform/BWT/src/bwt.py b/transform/BWT/src/bwt.py
@@ -0,0 +1,29 @@
+#! /usr/bin/python
+
+# Algorithm 1, Naive version from [1]
+
+# using \0 as the special EOF char
+def bwt(s):
+    s += "\0"
+    table = sorted(s[i:] + s[:i] for i in range(len(s)))
+    last_colum = [row[-1:] for row in table]
+    return "".join(last_colum)
+
+def ibwt(r):
+    table = [""] * len(r)
+    for i in range(len(r)):
+        table = sorted(r[i] + table[i] for i in range(len(r)))
+    s = [row for row in table if row.endswith("\0")][0]
+    return s.rstrip("\0")
+
+def test():
+    s = "this is the demo program of bwt transform in the real programming code"
+    r = bwt(s)
+    print "bwt(", s, ") ==>", r
+    print "ibwt(", r, ") ==>", ibwt(r)
+
+if __name__ == "__main__":
+    test()
+
+# reference
+# [1] WIKI. http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform