Algoritmos e Estruturas de Dados III - AED3 10 04 Codificação de Huffman

Videoaula da disciplina Algoritmos e Estruturas de Dados III no curso de Ciência da Computação da PUC Minas - 2018 ---------------------- A codificação de Huffman é um método de compressão baseado na frequência de cada símbolo. Esse método usa uma árvore binária para determinar o código de cada símbolo da informação. ---------------------- A codificação de Huffman é uma das mais principais formas de compressão de dados da era moderna (ela é de 1952). A compressão é feita por meio de uma análise da frequência de cada símbolo em um determinado conjunto de dados. Aos símbolos mais frequentes atribuímos alguns poucos bits e aos símbolos mais raros atribuímos um conjunto maior de bits (geralmente maior que o conjunto de bits original para representar esse símbolo). A expectativa é que os símbolos mais frequentes ocorram tantas vezes que se tenha um ganho no conjunto total. Mas já sabíamos disso. O segredo aqui é a forma que David Huffman bolou para se definir os códigos de cada símbolo. A ideia dele foi criar uma árvore binária em que cada símbolo é uma folha. O código do símbolo é o caminho da raiz até esse símbolo. Bem, o vídeo mostra a coisa sob a perspectiva da implementação, isto é, usando uma pilha de árvores binárias. Existem, é claro, representações visuais mais simples que essa. No próximo vídeo, veremos como aplicar esses códigos gerados para cada símbolo em operações de compactação e descompactação das mensagens.