File Huffman.h

↰ Parent directory (ADS/string)

The code of Huffman (reality check of section 14.4): a prefix code, no code being a prefix of another one, so that a text can be decoded, of least length for the frequencies of the characters.

Definition (ADS/string/Huffman.h)

Detailed Description

The characters go into a min-heap by frequency; the two least frequent ones, c_1 and c_2, are replaced by a new virtual character of frequency f_1 + f_2, whose children in a binary tree are c_1 and c_2; after n - 1 steps the root is left, and the code of a character is the path from the root to its leaf, 0 to the left and 1 to the right; O( n log n ) time. The least frequent characters get the longest codes.

The contracts [see File Contract.h]: huffman() needs at least one character and no negative frequency, and gives a prefix-free code of each character (checked at level 3); encode() needs a code for each character of the text, and decode() bits that are a concatenation of codes. The operations are defined in Huffman.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 14.4, https://algoritmicamente.it/materiali/libro/capitoli/cap14.pdf

    1. Huffman, A method for the construction of minimum-redundancy codes, Proceedings of the IRE 40(9), 1098-1101, 1952, doi:10.1109/JRPROC.1952.273898

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Functions