Huffmani kodeerimise visualiseerija

Huffman encoding optimizes data compression by dynamically constructing a binary tree based on the statistical frequency of input symbols. It assigns mathematically shorter bit sequences to highly probable characters, achieving the theoretical limit of Shannon entropy. The strict requirement of prefix-free codes guarantees unambiguous algorithmic decoding. This deterministic reallocation of binary weight mathematically minimizes the total file size without any loss of data.

Puu kasvab alt üles: kõigepealt loetletakse iga märk selle sageduse järgi, seejärel liidetakse korduvalt kaks kõige harvemat elementi väikeseks alampuuks ja käsitletakse seda ühe kimbuna. Seda korratakse, kuni jääb üksainus puu; koodid loetakse siis ülevalt alla — vasak on 0, parem on 1. See "ahne" komme alati kaks väikseimat ühendada tundub lühinägelik, kuid annab tõestatavalt lühimad võimalikud koodid.

David Huffman leiutas selle 1951. aastal MIT-i kraadiõppurina, kui professor Robert Fano pakkus klassile valida lõpueksami ja kõige tõhusamat koodi käsitleva töö vahel. Fano ja Claude Shannon olid seda juba proovinud, ehitades oma puid ülalt alla. Huffman peaaegu loobus, kuid taipas siis, et alt üles ehitamine — kõigepealt haruldasemate sümbolite liitmine — on optimaalne, edestades oma õpetaja meetodit.