BWT: Added a better inverse BWT algorithm in Python, Haskell naive ve…

…rsion is finished.
bhehir · Jun 22, 2011 · fa8c0f6 · fa8c0f6
1 parent 91b974b
commit fa8c0f6
Show file tree

Hide file tree

Showing 4 changed files with 57 additions and 3 deletions.
diff --git a/common-en.tex b/common-en.tex
@@ -30,6 +30,8 @@
 \usepackage{graphicx, color}
 \usepackage{subfig}
 
+\usepackage{amsmath, amsthm, amssymb} % for math
+
 %
 % for programming 
 %
@@ -70,8 +72,6 @@
 \def\BibTeX{{\rm B\kern-.05em{\sc i\kern-.025em b}\kern-.08em
     T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}}
 
-\newtheorem{theorem}{Theorem}
-
 %
 % mathematics
 %
@@ -89,4 +89,7 @@
 \newcommand{\bean}{\begin{eqnarray*}}
 \newcommand{\eean}{\end{eqnarray*}}
 
-
+\newtheorem{theorem}{Theorem}[section]
+\newtheorem{lemma}[theorem]{Lemma}
+\newtheorem{proposition}[theorem]{Proposition}
+\newtheorem{corollary}[theorem]{Corollary}
diff --git a/others/problems/majority-elem/Occurrence.hs b/others/problems/majority-elem/Occurrence.hs
@@ -20,3 +20,5 @@ find (x:xs) = Just $ maximumBy (compare `on` snd) $ (x, l):catMaybes
                 [find [ a| a<-xs, a < x], find [ a| a<-xs, a > x]]
   where
     l = length (x:[ a| a<-xs, a == x])
+
+-- Boyer-Moore linear time majority vote algorithm
diff --git a/transform/BWT/src/BWT.hs b/transform/BWT/src/BWT.hs
@@ -0,0 +1,18 @@
+module BWT where
+
+import Data.List
+
+-- Algorithm 1, Naive version
+
+bwt :: (Ord a)=>[a]->([a], Int)
+bwt s = (map last m, i) where
+    m = sort [ drop i s ++ take i s | i<-[1..length s]]
+    (Just i) = elemIndex s m
+
+ibwt :: (Ord a)=> ([a], Int) -> [a]
+ibwt (r, i) = m !! i where
+    m = iterate f (replicate n []) !! n
+    f = sort . zipWith (:) r
+    n = length r
+
+-- Algorithm 2, 
diff --git a/transform/BWT/src/bwt.py b/transform/BWT/src/bwt.py
@@ -100,6 +100,34 @@ def ibwt2(t):
         i = trans[i]
     return s
 
+# Algorithm 4,
+#   Same as algorithm 3, but we sort on rots index
+#   The main improvement is in inverse BWT, the transform
+#   vector can be calculated as the following
+#
+#   T = snd $ sortBy (compare `on` fst) (zip(r, [1..])
+#
+def bwt3(s):
+    n = len(s)
+    ids = sorted(range(n), lambda x, y: rcmp(s, x, y))
+    last_colum = [s[(i-1)%n] for i in ids]
+    return ("".join(last_colum), ids.index(0))
+
+def rcmp(s, i, j):
+    x = s[i:]+s[:i]
+    y = s[j:]+s[:j]
+    return cmp(x, y)
+
+def ibwt3(p):
+    (r, i) = p
+    n = len(r)
+    trans = [ x for (c, x) in sorted(zip(r, range(n)))]
+    s = ""
+    for _ in range(n):
+        i = trans[i]
+        s = s + r[i]
+    return s
+
 def test():
     s = "this is the demo program of bwt transform in the real programming code"
     r = bwt(s)
@@ -111,6 +139,9 @@ def test():
     t = bwt2(s)
     print "bwt2(s) ==>", t
     print "ibwt2(r) ==>", ibwt2(t)
+    p = bwt3(s)
+    print "bwt3(s) ==>", p
+    print "ibwt3(r) ==>", ibwt3(p)
 
 if __name__ == "__main__":
     test()