August 19, 2024
P52 - Huffman code (2)
First of all, consult a good book on discrete mathematics or algorithms for a detailed description of Huffman codes!We suppose a set of symbols with their frequencies, given as a list of (S F) elements.
Example: ( (a 45) (b 13) (c 12) (d 16) (e 9) (f 5) ). Our objective is to construct a list of (S C) elements, where C is the Huffman code word for symbol S. In our example, the result could be ( (A "0") (B "101") (C "100") (D "111") (E "1101") (F "1100") ). The task shall be performed by a function huffman defined as follows:
(huffman F) returns the Huffman code table for the frequency table F
lisp
(load "p49.lisp")
(defun huffman (f)
(huf-codes (huf-tree (huf-encode f)))
)
(defun huf-encode (f)
(mapcar #'huf-enc-car f)
)
(defun huf-enc-car (p)
(list (first p) (second p) nil nil)
)
(defun huf-tree (l)
(cond
((null l) ())
((null (cdr l)) (car l))
(t (let* ((a (huf-min l))
(l1 (remove a l))
(b (huf-min l1))
(l2 (remove b l1)))
(huf-tree (cons (list nil (+ (second a) (second b)) a b) l2))
))
)
)
(defun huf-min (hl)
(if (null (cdr hl))
(car hl)
(let ((a (car hl))
(b (huf-min (cdr hl))))
(if (<= (second a) (second b))
a
b
)
)
)
)
(defun huf-codes (ht)
(if (null ht)
()
(huf-codes-prefix () ht)
)
)
(defun huf-codes-prefix (prefix ht)
(if (null (third ht))
(list (list (first ht) (list-to-string (reverse prefix))))
(append (huf-codes-prefix (cons #\0 prefix) (third ht))
(huf-codes-prefix (cons #\1 prefix) (fourth ht))
)
)
)
Be first to comment