8.12
10 Huffman Codes
| (require binaryio/huffman) | package: binaryio-lib |
Added in version 1.3 of package binaryio-lib.
This module provides support for computing Huffman codes.
procedure
(make-huffman-code alphabet) → prefixcode-encode-table/c
alphabet :
(or/c (hash/c any/c rational?) (listof (cons/c any/c rational?)) (vectorof rational?))
Produces a prefix code encoder table (see prefixcode-encode) based on
alphabet, which contains the encodable elements and their relative
frequencies. Elements with zero or negative weights are included in the code
book; negative weights are clipped to zero.
If the alphabet consists only of exact integers, characters, and symbols, then a canonical Huffman code is constructed: alphabet elements having the same code length are sorted and assigned sequential, ascending code values.
If alphabet is a vector, the alphabet elements are the vector indexes, and the resulting encode table is also represented as a vector. Otherwise, the resulting encode table is represented as a hash table.
Examples:
> (define hc (make-huffman-code (vector 2 1 1 1 1)))
> (for ([code (in-vector hc)] [v (in-naturals)]) (printf "~v ~a\n" v (sbv->string code)))
0 0
1 100
2 101
3 110
4 111