implement huffman libraries lisp prolog
imht-decode bits huffman-tree message
ht-encode message huffman-tree bits
ht-encode-file filename huffman-tree bits
ht-generate-huffman-tree symbols-n-weights huffman-tree
ht-generate-symbol-bits-table huffman-tree symbol-bits-table
ht-pprint-huffman-tree huffman-tree &optional (indent-level 0)
huffman-tree is a Huffman tree (its root);
symbols-n-weigths is a list of pairs of symbol-weight (<symbol>. <weight>);
symbol-bits-table is a list of pairs (<symbol>. <bits>).
The ht-encode-file function reads a text from a file and then invokes ht-encode on the read.
Functions must generate errors (with the function error) if encoding and / or decoding are not
The ht-print-huffman-tree function prints a Huffman Tree terminal and serves essentially
for debugging. No perticular format is required, but printed information has to be fine
represent the tree structure of Huffman
You must implement the following predicates:
ht_decode / 3 Bits HuffmanTree Message
ht_encode / 3 Message HuffmanTree Bits
ht_encode_file / 3 Filename HuffmanTree Bits
ht_generate_huffman_tree / 2 SymbolsAndWeights HuffmanTree
ht_generate_symbol_bits_table / 2 HuffmanTree SymbolBitsTable
ht_pprint_huffman_tree / 1 HuffmanTree
The constraints are the same as above (obviously remodeled in Prolog). In particular, Symbolic pairs
and bits symbol are represented as pairs lists of two elements (i.e., (<symbol>,
<weight>) and (<symbol>, <bits>)). Predicates must fail if there are errors or if they encode and / or
decoding can not be completed.
The predicate ht_print_huffman_tree prints a Huffman Tree terminal.
The most important example to keep in mind (the specification, according to a more correct terminology) is the
In Common Lisp:
cl-prompt> (defparameter ht
cl-prompt> (defparameter message '<some-message>)
cl-prompt> (equal message (ht-decode (ht-encode message ht ht))
? - assert (symbols_n_weights (<symbols-n-weights>)).
? - assert (message (<some-message>)).
| ht_generate_huffman_tree(SWs, HT),
| ht_encode(M, HT, Bits),
| ht_decode(Bits, HT, M).
As you may have noticed, the structure of the implementation of a tree has not been specified
A problem you will have will be in managing ordered sets of elements (leaves and tree nodes in
construction); you will need to implement a structure and / or functions that keep them together
The implementation of the various functions and predicates is relatively simple once it is exploited
the sorting of knots and leaves. If you find yourself writing features or long predicates
or complex then you are probably on the wrong track..