Burrows-Wheeler Transform

b-w-t.clj

;; simple implementation of the Burrows-Wheeler transform (used in bzip2)
;; https://en.wikipedia.org/wiki/Burrows-Wheeler_transform

(defn rotations
  "All rotations (cyclic permutations) of a string s."
  [s]
  (let [n (count s)] 
    (reduce (fn [rotations i]
              (conj rotations
                    (apply str
                           (take n (drop i (cycle s))))))
            [] 
            (range (count s)))))

(defn b-w-t
  "The Burrows-Wheeler transform of a string s. It produces a single
  permuted string."
  [s]
  (apply str (map last (sort (rotations s)))))

(defn reverse-b-w-t
  "Reverse transformation of the Burrows-Wheeler Transform. Returns all
  rotations of the original string."
  [s]
  (reduce (fn [ss _]
            (sort
              (map (comp (partial apply str) cons)
                   s
                   ss)))
          (sort (map str s))
          (range (dec (count s)))))

(defn r-b-w-t
  "If the string s was encoded with start character ^ and end
  character |, then this function finds the original string."
  [s]
  (filter #(= \^ (first %))
          (reverse-b-w-t s)))

(b-w-t "^banana|")

(r-b-w-t "|bnn^aaa")