Também conhecido como codificação Huffman, um algoritmo para compactação sem perdas de arquivos com base na frequência de ocorrência de um símbolo no arquivo que está sendo compactado. O algoritmo de Huffman é baseado em codificação estatística, o que significa que a probabilidade de um símbolo tem uma relação direta com o comprimento de sua representação. Quanto mais provável for a ocorrência de um símbolo, menor será sua representação em bit. Em qualquer arquivo, certos caracteres são usados mais do que outros. Usando a representação binária, o número de bits necessários para representar cada caractere depende do número de caracteres que devem ser representados. Usando um bit, podemos representar dois caracteres, ou seja, 0 representa o primeiro caractere e 1 representa o segundo caractere. Usando dois bits, podemos representar quatro caracteres e assim por diante.
Ao contrário do código ASCII, que é um código de comprimento fixo usando sete bits por caractere, a compressão Huffman é um sistema de codificação de comprimento variável que atribui códigos menores para caracteres usados com mais frequência e códigos maiores para caracteres usados com menos frequência, a fim de reduzir o tamanho de arquivos sendo compactados e transferidos.
Por exemplo, em um arquivo com os seguintes dados:
XXXXXXYYYYZZ
a frequência de “X” é 6, a frequência de “Y” é 4 e a frequência de “Z” é 2. Se cada caractere for representado usando um código de comprimento fixo de dois bits, então o número de bits necessários para armazenar este arquivo seria 24, ou seja, (2 x 6) + (2x 4) + (2x 2) = 24.
Se os dados acima fossem compactados usando a compactação Huffman, os números de ocorrência mais frequente seriam representados por bits menores, como:
X pelo código 0 (1 bit)
Y pelo código 10 (2 bits)
Z pelo código 11 (2 bits)
portanto, o tamanho do arquivo passa a ser 18, ou seja, (1x 6) + (2 x 4) + (2 x 2) = 18.
No exemplo acima, os caracteres de ocorrência mais frequente recebem códigos menores, resultando em um número menor de bits no arquivo compactado final.
A compressão Huffman recebeu o nome de seu descobridor, David Huffman.