Visualizador de Codificação de Huffman

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.

A árvore cresce de baixo para cima: primeiro lista-se cada caractere pela sua frequência e depois unem-se repetidamente os dois elementos menos frequentes numa pequena subárvore, tratando-a como um único pacote. Repete-se até restar uma só árvore; então cada código é lido descendo a partir do topo — a esquerda é 0, a direita é 1. Esse hábito "guloso" de sempre juntar os dois menores parece míope, mas comprovadamente produz os códigos mais curtos possíveis.

David Huffman o concebeu em 1951, quando era estudante de pós-graduação no MIT, ao professor Robert Fano dar à turma a escolha entre um exame final e um trabalho sobre como encontrar o código mais eficiente. Fano e Claude Shannon já haviam tentado, construindo suas árvores de cima para baixo. Huffman quase desistiu, mas percebeu que construir de baixo para cima — fundindo primeiro os símbolos mais raros — era ótimo, superando o método de seu próprio professor.