Skip to content

Instantly share code, notes, and snippets.

@ssboisen ssboisen/huffman.clj
Last active Oct 12, 2015

What would you like to do?
Hoffman encoding in Clojure
(defn branch? [node]
(= (:type node) :branch))
(defn get-chars [node]
(if (branch? node)
(:chars node)
[(:char node)]))
(defn leaf [char weight]
{:char char :weight weight :type :leaf})
(defn branch [left right]
{:left left :right right
:chars (sort (into (get-chars left) (get-chars right)))
:weight (+ (:weight left) (:weight right))
:type :branch})
(defn create-code-tree [text]
(letfn [(combine-trees [trees]
(let [[fst snd & r] trees]
(if (nil? snd)
(recur (sort-by :weight (cons (branch fst snd) r))))))]
(first (combine-trees
(->> (frequencies text)
(sort-by second)
(map #(leaf (first %) (second %))))))))
(defn decode [tree bits]
(loop [_tree tree
bits bits
chars []]
(if (branch? _tree)
(let [bit (first bits)
v (if (= bit 0) :left :right)]
(recur (v _tree) (rest bits) chars))
(let [chars (into chars (get-chars _tree) )]
(if (empty? bits)
(recur tree bits chars))))))
(defn encode [tree text]
(letfn [(has-char? [tree c]
(some #(= c %) (get-chars tree)))]
(loop [_tree tree
chars text
bits []]
(if (empty? chars)
(if (branch? _tree)
(let [v (if (has-char? (:left _tree) (first chars)) :left :right)
bits (conj bits (if (= v :left) 0 1))]
(recur (v _tree) chars bits))
(recur tree (rest chars) bits))))))
(defn fast-encode [tree]
(let [code-map (into {} (map #(hash-map % (encode tree (str %))) (get-chars tree)))]
(fn [text] (reduce (fn [s c] (into s (get code-map c))) [] text))))

This comment has been minimized.

Copy link

mookid8000 commented Nov 5, 2012


teach me!

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.