Skip to content

Instantly share code, notes, and snippets.

@kierendavies kierendavies/bwt.clj
Created Feb 24, 2015

Embed
What would you like to do?
; Burrows-Wheeler Transform (and inverse)
; http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform
(def string-start \u0098)
(defn bwt [s]
(map last
(sort-by vec
(take (inc (count s))
(iterate #(concat (rest %)
(list (first %)))
(cons string-start s))))))
(defn inv-bwt [s]
(rest
(first
(filter #(= (first %) string-start)
(nth (iterate #(map cons s (sort-by vec %))
(map list s))
(dec (count s)))))))
(let [s "'Twas brillig, and the slithy toves
Did gyre and gimble in the wabe:
All mimsy were the borogoves,
And the mome raths outgrabe."]
(println (apply str (bwt s)))
(println (apply str (inv-bwt (bwt s)))))
@theronic

This comment has been minimized.

Copy link

theronic commented Feb 25, 2015

My attempt:

(defn bwt[s]
  (let [s' (str "^" s "|")
        c (cycle s')
        l (count s')]
    (map last (sort (apply map str (take l (partition l 1 c)))))))

(prn (apply str (bwt "banana")))
=> "|bnn^aaa"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.