/prog/ - Huffman Tree in LISP

Name: Anonymous 2010-12-30 1:10



huff xs -> xs.sort.{[x@xs ys:_:@{l=>l.lhd!=x}]=>[[x@xs] @ys.rec]}

           |> map x~>[x.len x.lhd] |> sort by={a b => a|0 < b|0}

           |> {[x]=>x|1;[a b @xs]=>nins a|0+b|0 [a|1 b|1] xs |> rec}

           |> {bs x=>[[x bs]]; bs [a b]=>conc rec,[@bs 0],a rec,[@bs 1],b} []

usage example:



(repl "huff \"The algorithm for generating a Huffman tree is very simple.\"")

((\y (0 0 0 0 0))   (\h (0 0 0 0 1))   (\m (0 0 0 1))    

 (\n (0 0 1 0))     (\t (0 0 1 1))     (\f (0 1 0 0))    

 (\g (0 1 0 1))     (\e (0 1 1))       (\u (1 0 0 0 0 0))

 (\v (1 0 0 0 0 1)) (\. (1 0 0 0 1 0)) (\H (1 0 0 0 1 1))

 (\T (1 0 0 1 0 0)) (\p (1 0 0 1 0 1)) (\l (1 0 0 1 1))  

 (\o (1 0 1 0 0))   (\s (1 0 1 0 1))   (\a (1 0 1 1))    

 (\i (1 1 0 0))     (\r (1 1 0 1))     (\Space (1 1 1))  )

Name: Anonymous 2010-12-30 20:28

Huffman Tree in C++



function huff(str) {

    var f = {}, cs = str.split(''), h = new MinHeap(), r = [];

    cs.forEach(function (c) {f[c] |= 0; f[c]++});

    for (c in f) h.push([f[c], c]);

    while (h.length > 1)

        h.push((function (x, y) [x[0] + y[0], [x, y]])(h.pop(), h.pop()));

    (function (e, p) {var [f, c] = e; if (c instanceof Array) { let s = arguments.callee; s(c[0], p + '0'); s(c[1], p + '1') } else r.push([c, p]);})(h.pop(), '');

    return r;

}

usage example:
huff("The algorithm for generating a Huffman tree is very simple.");



[["y","00000"],  [".","000010"], ["H","000011"],

 ["f","0001"],   ["g","0010"],   ["m","0011"],

 ["n","0100"],   ["t","0101"],   ["e","011"],

 ["T","100000"], ["p","100001"], ["u","100010"],

 ["v","100011"], ["h","10010"],  ["l","10011"],

 ["o","10100"],  ["s","10101"],  ["a","1011"],

 [" ","110"],    ["i","1110"],   ["r","1111"]]

Huffman Tree in LISP

1 Name: Anonymous 2010-12-30 1:10

21 Name: Anonymous 2010-12-30 20:28

Name: Anonymous 2010-12-30 1:10

Name: Anonymous 2010-12-30 20:28