Hello,
I posted on this topic back in February. I can't find a way to post a
reply to that message, but here's a link to the thread...
http://groups.google.com/groups?dq=&hl=en&lr=&ie=UTF-8&threadm=m6r8abnlmg.fsf%40pc156.maths.bris.ac.uk&rnum=1&prev=/groups%3Fdq%3D%26hl%3Den%26lr%3D%26ie%3DUTF-8%26selm%3Dm6r8abnlmg.fsf%2540pc156.maths.bris.ac.uk
I've now submitted a LISP program which performed Huffman encoding and
decoding as described in that posting. Unfortunately, though, the
program is horribly inefficient because I had to Kludge the tree data
structure. I can't change my grade now, but I would like to learn
what the problem was. I was stymied in building an ordered binary
tree. I wound up having to settle for a kludged solution. In the
interest of learning, can anyone tell me why the RecursiveMerge
function in my program is building an inside-out tree? The entire
program is posted at
http://home.ccil.org/~remlaps/PL/HuffMan.lisp.txt.
This excerpt from the header block describes the problem I think I'm
having...
;;; The intended tree structure would look like:
;;; (Root ( Left Sub-Tree ) (Right Sub-Tree ))
;;; Each subtree would be triplets of the same form.
;;;
;;; The ugly structure I wound up with and can't seem to get away
from
;;; looks like this....
;;; ((...(Root Left_Sub-Tree Right_Sub-Tree)
;;; Left_Sub_of_Right_Sub Right_Sub_of_Right_Sub)
;;; Left_Sub_of_Left_Sub Right_Sub_of_Left_Sub)...)
;;; The parents alternate to the bottom of the list with the
;;; left parents being 2 levels deeper than their children and
;;; the right parents being 1 level deeper. If there is no right
;;; parent, the left parent is off by 1 level instead of two.
I think this is the section causing me problems. It's found in (defun
Recursive-Merge)...
; Merge 1st two and recurse through remaining items.
(t (cons (Recursive-Merge (SortBranches
(cons (MergeBranches (first HuffTree) (second
HuffTree))
(rest (rest HuffTree)))))
Thanks in advance for any assists, -Steve-
·······@despammed.com writes:
> http://home.ccil.org/~remlaps/PL/HuffMan.lisp.txt.
Various comments:
* make-leaves reads message directly. It should be given as a
parameter instead.
* make-set can be replaced with the standard function
REMOVE-DUPLICATES.
* countword can be replaced with the standard function COUNT.
* Functions should signal errors in the "should never happen"
cases.
* In SortBranches, you can easily get the effect of a
non-destructive sort by copying the list before sorting. You
could also use the :KEY argument and get rid of TreeNodeLess:
(sort (copy-seq SortTree) #'< :key #'Weight)
* ListAtoms is usually not necessary. APPEND or CONS could be
used instead.
> In the interest of learning, can anyone tell me why the
> RecursiveMerge function in my program is building an inside-out
> tree?
Well, I didn't quite figure out what the code was doing, but I
think I got it working. First, MergeBranches should construct a
whole triplet, rather than just a leaf structure:
(defun MergeBranches (HTree1 HTree2)
"Makes a new node with symbols and weights from HTree1 and HTree2"
;; Make a node and put it in a list.
(list
(make-leaf :symbols (ListAtoms
(list (symbol-leaf (CurrentNode HTree1))
(symbol-leaf (CurrentNode HTree2))))
:weight (+ (weight-leaf (CurrentNode HTree1))
(weight-leaf (CurrentNode HTree2))))
HTree1
HTree2))
Then, Recursive-Merge need not worry about the subtrees:
(defun Recursive-Merge (HuffTree)
"Merges leaves and nodes into a complete Huffman tree"
(cond ((null (first HuffTree)) nil) ; Should never happen
((null (second HuffTree)) nil) ; Should never happen
((null (third HuffTree)) ; Merge 1st two and stop
(MergeBranches (first HuffTree)
(second HuffTree)))
(t
(Recursive-Merge
(SortBranches (cons (MergeBranches (first HuffTree)
(second HuffTree))
(rest (rest HuffTree))))))))
I would simplify it to this, though:
(defun Recursive-Merge (branches)
"Merge a sorted list of branches into a complete Huffman tree."
(assert (not (null branches)))
(if (null (rest branches))
;; There is only one branch, so it's our tree.
(first branches)
;; There are multiple branches. Merge the first two, sort the
;; resulting tree to the right place among the rest and recurse.
(Recursive-Merge (SortBranches
(cons (MergeBranches (first branches)
(second branches))
(rest (rest branches)))))))
Or even an iterative version that does not assume that its input
has already been sorted:
(defun Iterative-Merge (branches)
"Merge a list of branches into a complete Huffman tree."
(loop while (rest branches)
finally (return (first branches))
do (setq branches (SortBranches branches))
(push (MergeBranches (pop branches)
(pop branches))
branches)))
Kalle Olavi Niemitalo <···@iki.fi> wrote in message news:<··············@Astalo.kon.iki.fi>...
> ·······@despammed.com writes:
>
> > http://home.ccil.org/~remlaps/PL/HuffMan.lisp.txt.
>
> Various comments:
>
Thank you for all your comments. They are quite helpful. I tested
with MergeBranches and Recursive-Merge modified as you suggested. As
you stated, it built a tree like the one I was looking for. Now I'll
have to find some time after the semester to rewrite Encode and
Decode.
Thanks,
-Steve-