Exercícios e Árvore de Huffman

HUFFMAN O algoritmo de Huffman recebe um fluxo de bits e devolve um fluxo de bits comprimido que representa o fluxo original Em geral o fluxo comprimido é mais curto que o original O fluxo de bits original é lido de 8 em 8 bits como se fosse um fluxo de caracteres 010000010100001001010010010000010100001101000001100010000100000101000010010100100100000100100001 A B R A C A D A B R A Tudo se passa como se o algoritmo transformasse uma string em uma cadeia de bits Exemplo transforma ABRACADABRA em 010011110010100010101010011110010001 A B R A C A D A B R A 010 011 110 010 100 010 101 010 011 110 010 001 Cada caractere da string original é convertido em uma pequena cadeia de bits que é o seu código Por exemplo C 100 Ideia do algoritmo de Huffman usar códigos curtos para os caracteres que ocorrem com frequência e deixar os códigos mais longos para os caracteres mais raros Os códigos são portanto de comprimento variável Dois exemplos um com códigos de comprimento fixo e outro com códigos de comprimento variável Expansão decodificação Na decodificação cada código de caractere deve ser convertido no correspondente caractere A tabela de códigos deve ser injetiva caracteres diferentes devem ter códigos diferentes Mas isso não basta Exemplo A tabela de códigos ao lado transforma ABRACADABRA em 01000010100100011 Mas essa cadeia de bits também representa CRRDDCRCB Isso contraria a regra do jogo A tabela deve ser livre de prefixos Uma tabela de códigos é livre de prefixos prefixfree se nenhum código é prefixo de outro Exemplo A tabela ao lado é livre de prefixos Assim ABRACADABRA é a única decodificação possível de 011111110011001000111111100101 ATIVIDADES HUFFMAN 1 Qual a diferença entre código de comprimento fixo e código de comprimento variável Por que código de comprimento variável precisa ser livre de prefixos 2 Quais das tabelas de códigos abaixo são livres de prefixos Tabela Código A 0 100 10 11 B 0 1 00 11 C 1 01 001 0001 D 1 01 001 000 3 Escreva a cadeia de bits que codifica a string ABRACADABRA usando o código de Huffman Quantos bits tem a cadeia Insira espaços para facilitar a leitura 4 Unicidade Mostre que a árvore de Huffman não é unica Use a string ABRACADABRA como exemplo Faça um exemplo mais interessante que a mera troca de 0 por 1 e viceversa 11 A 0 B 1 C 01 D 10 R 00 001 1010 A 010 A 0 B 011 B 111 C 100 C 1011 D 101 D 100 R 110 R 110 101 A 0 B 1111 C 110 D 100 R 1110 5 Dado um alfabeto A com as seguintes letras a1 a2 a3 a4 a5 com a distribuição de probabilidade mostrada na tabela desenhe a árvore de Huffman 6 Construa o código de Huffman para esta fonte Calcule a eficiência do código 7 Uma palavra foi codificada usando o código de Huffman tendose obtido a sequência binária 01000100101100110001010 O alfabeto original era constituído pelas letras A B C D E I L R e T e a letra R foi codificada como 11 Supondo que estas letras ocorriam com as probabilidades PA 026 PD 002 PL 001 PB 009 PE 007 PR 019 PC 008 PI 025 PT 003 Qual terá sido a palavra codificada Calcule o número médio de bits por caractere obtido pelo uso da codificação de Huffman e compare com a utilização de um código binário de tamanho fixo otimizado para representação do mesmo alfabeto 8 Dado um alfabeto A com as seguintes letras L M N O P Q com a distribuição de probabilidade 009 021 025015 019 e 011 respectivamente desenhe a árvore de Huffman Calcule a eficiência da codificação 9 Imagine um dado de sete faces D7 com as seguintes probabilidades de ocorrência de cada face pA 002 pB 004 pC 044 pD 003 pE 005 pF 017 pG025 Construa a codificação de Huffman e responda a quantos bits seriam necessários para esta representação se a codificação fosse fixa Justifique sua resposta b Qual a eficiência da codificação 10 Uma fonte tem um alfabeto com A 8 e PA 025 020 015 012 010 008 005 005 Encontre a eficiência de informação desta fonte Utilize método de Huffman 11Uma fonte discreta sem memória tem um alfabeto A a b c d com probabilidades dos símbolos 025 04 015 02 respectivamente Encontre a entropia da fonte Construa o código de Huffman para esta fonte Calcule a eficiência do código 12Uma fonte discreta sem memória tem um alfabeto K a b c d e f g com probabilidades dos símbolos 009 025 016 015 021 008 006 respectivamente Encontre a entropia da fonte Construa o código de Huffman para esta fonte Calcule a eficiência do código 13Construa o código de Huffman para esta fonte Calcule a eficiência do código 14 Uma palavra foi codificada usando o código de Huffman tendose obtido a sequência binária 1001101000110001101110010 O alfabeto original era constituído pelas letras M O I U C H T E e B A letra M foi codificada como 10 Supondo que estas letras ocorriam com as probabilidades PM 024 PU 012 PT 007 PO 016 PC 009 PE 006 PI 013 PH 008 PB 005 G1 Qual foi a MENSAGEM codificada G2 Calcule o número médio de bits por caractere obtido pelo uso da codificação de Huffman e compare com a utilização de um código binário de tamanho fixo otimizado para representação do mesmo alfabeto G3 Calcule e compare as eficiências de ambas as codificações 15 Imagine um dado de sete faces D7 com as seguintes probabilidades de ocorrência de cada face pA 12 pB 14 pC 14 pD 18 pE 18 pF 116 pG 116 Construa a codificação de Huffman e utilizando esta codificação responda quantos bits seriam necessários para esta representação Qual a eficiência da codificação CODIFICAÇÃO DE FONTE HUFFMAN PROFª DRª DENISE FUKUMI TSUNODA 29042024 CODIFICAÇÃO DE FONTE As técnicas de codificação de fonte têm o objetivo de reduzir tanto quanto possível a redundância existente nos dados antes que estes sejam transmitidos A codificação de fonte é a base teórica dos algoritmos de compressão de voz dados imagens existentes nos sistemas de comunicação e armazenamento digital Fonte httpwwwdvprppgufcbrppgeticharlesPDFitCodificacaofontepdf COMPRESSÃO DE DADOS Objetivos Reduzir espaço de armazenagem Reduzir tempo de transmissão Justificativa Informação e dados tende a crescer de forma exponencial Exemplos Compressão de arquivos em geral ZIP GZIP BZIPARJ Sistemas de arquivos NTFS Multimídia Imagens GIF JPEG Som MP3 Vídeo MPEG DivX CODIFICAÇÃO DE FONTE descrição de acontecimentos produzidos por determinada fonte procurase minimizar o comprimento médio do código cada símbolo é representado por um código CODIFICAÇÃO LIVRE DE PREFIXO Qual o valor da mensagem 010010001100 em cada um dos códigos Letra SÍMBOLO Codificação Fixa Codificação LIVRE DE PREFIXO Codificação NÃO livre de prefixo A 00 0 0 B 01 10 1 C 10 110 01 N 11 111 10 Codificação Fixa Codificação livre de prefixo Codificação NÃO livre de prefixo 010010001100 010010001100 010010001100 BACANA ABABAACA ABAABAAABBAA QUAL O COMPRIMENTO DA MENSAGEM CODIFICADA NA CODIFICAÇÃO FIXA Resposta 12 bits Codificação Fixa 010010001100 BACANA CODIFICAÇÃO LIVRE DE PREFIXO Como ficaria BACANA na codificação LIVRE DE PREFIXO Letra SÍMBOLO Codificação Fixa Codificação LIVRE DE PREFIXO Codificação NÃO livre de prefixo A 00 0 0 B 01 10 1 C 10 110 01 N 11 111 10 Codificação Fixa Codificação livre de prefixo Codificação NÃO livre de prefixo 010010001100 10011001110 BACANA BACANA QUAL O COMPRIMENTO DA MENSAGEM CODIFICADA NA CODIFICAÇÃO LIVRE DE PREFIXO Resposta 11 bits Por que isto ocorreu Qual a mágica Codificação livre de prefixo 10011001110 BACANA CODIFICAÇÃO NÃO LIVRE DE PREFIXO Como ficaria BACANA na codificação NÃO LIVRE DE PREFIXO Letra SÍMBOLO Codificação Fixa Codificação LIVRE DE PREFIXO Codificação NÃO livre de prefixo A 00 0 0 B 01 10 1 C 10 110 01 N 11 111 10 Codificação Fixa Codificação livre de prefixo Codificação NÃO livre de prefixo 010010001100 10011001110 BACANA ABABAACA TEOREMA DA CODIFICAÇÃO DA FONTE Também conhecido como 1º Teorema de Shannon noiseless coding theorem É possível codificar sem distorção uma fonte de entropia H bitsímbolo usando em média NHe bits por símbolo em que e é uma quantidade arbitrariamente pequena EFICIÊNCIA DA CODIFICAÇÃO A eficiência da codificação é dada por em que N é o comprimento médio das palavras de código e HX é a entropia da fonte COMPRIMENTO MÉDIO O comprimento médio das palavras de um código definese como em que lxi é o comprimento da palavra de código que representa o símbolo xi Representa o número médio de dígitos utilizado para representar cada símbolo da fonte ANÁLISE DO COMPRIMENTO MÉDIO Supondo as duas codificações Qual a codificação mais eficiente RESOLVENDO PASSOAPASSO PARA O PRIMEIRO CÓDIGO COMPRIMENTO MÉDIO RESOLVENDO PASSOAPASSO PARA O PRIMEIRO CÓDIGO ENTROPIA RESOLVENDO PASSOAPASSO PARA O PRIMEIRO CÓDIGO EFICIÊNCIA DA CODIFICAÇÃO RESOLVENDO PASSOAPASSO PARA O SEGUNDO CÓDIGO COMPRIMENTO MÉDIO RESOLVENDO PASSOAPASSO PARA O SEGUNDO CÓDIGO ENTROPIA RESOLVENDO PASSOAPASSO PARA O SEGUNDO CÓDIGO EFICIÊNCIA DA CODIFICAÇÃO Código 1 Código 2 COMPARAÇÃO RESPOSTA O código 1 é mais eficiente quando comparado ao código 2 Huffman Ideia é usar caracteres símbolos com número variável de bits Caracteres mais comuns menos bits Caracteres menos comuns mais bits Árvore de Prefixos de Huffman Dada uma mensagem encontrar a melhor menor codificação para os caracteres Usos MP3 a técnica de Huffman garante em média uma redução de até 20 no código final ZIP PKZIP winzip etc e BZIP2 JPEG e PNG ALGORITMO DE CODIFICAÇÃO DE HUFFMAN Ordenar os símbolos por probabilidade decrescente e considerá los como nós de uma árvore Enquanto houver mais do que um nó Agrupar os dois nós de menor probabilidade e formar um novo nó com probabilidade igual à soma dos dois nós que se agruparam Arbitrariamente atribuir os códigos 0 e 1 a cada ramo dos nós que se juntaram O código de cada símbolo é obtido pela leitura sequencial da raiz até ao nó final a que pertence o símbolo em questão CÓDIGO ÓTIMO O código de Huffman é muito utilizado porque garante que HX N HX1 No caso em que NHX o código é dito ideal Exemplo de código de Huffman CALCULAR A EFICIÊNCIA PARA A CODIFICAÇÃO DE HUFFMAN Resposta e 98 EXEMPLO DE CODIFICAÇÃO DE HUFFMAN Frequências dos caracteres 125 Freq 93 80 76 72 71 61 55 41 40 E Char T A O I N R H L D 31 27 C U 65 S EXEMPLO DE CODIFICAÇÃO DE HUFFMAN R S N I E H C U 31 27 55 71 73 61 65 125 40 T D L 41 93 A O 80 76 R S N I E H C U 58 D L A O T 31 27 55 71 73 61 65 125 40 41 93 80 76 EXEMPLO DE CODIFICAÇÃO DE HUFFMAN R S N I E H C U 58 D L 81 A O T 31 27 55 71 73 61 65 125 40 41 93 80 76 EXEMPLO DE CODIFICAÇÃO DE HUFFMAN R S N I E H C U 58 113 D L 81 A O T 31 27 55 71 73 61 65 125 40 41 93 80 76 EXEMPLO DE CODIFICAÇÃO DE HUFFMAN R S N I E H C U 58 113 126 D L 81 A O T 31 27 55 71 73 61 65 125 40 41 93 80 76 EXEMPLO DE CODIFICAÇÃO DE HUFFMAN R S N I E H C U 58 113 144 126 D L 81 A O T 31 27 55 71 73 61 65 125 40 41 93 80 76 EXEMPLO DE CODIFICAÇÃO DE HUFFMAN R S N I E H C U 58 113 144 126 D L 81 156 A O T 31 27 55 71 73 61 65 125 40 41 93 80 76 EXEMPLO DE CODIFICAÇÃO DE HUFFMAN R S N I E H C U 58 113 144 126 D L 81 156 174 A O T 31 27 55 71 73 61 65 125 40 41 93 80 76 EXEMPLO DE CODIFICAÇÃO DE HUFFMAN R S N I E H C U 58 113 144 126 238 T D L 81 156 174 A O 31 27 55 71 73 61 65 40 41 80 76 125 93 EXEMPLO DE CODIFICAÇÃO DE HUFFMAN R S N I E H C U 58 113 144 126 238 270 T D L 81 156 174 A O 31 27 55 71 73 61 65 125 40 41 93 80 76 EXEMPLO DE CODIFICAÇÃO DE HUFFMAN R S N I E H C U 58 113 144 126 238 270 330 T D L 81 156 174 A O 31 27 55 71 73 61 65 125 40 41 93 80 76 EXEMPLO DE CODIFICAÇÃO DE HUFFMAN R S N I E H C U 58 113 144 126 238 270 330 508 T D L 81 156 174 A O 31 27 55 71 73 61 65 125 40 41 93 80 76 EXEMPLO DE CODIFICAÇÃO DE HUFFMAN R S N I E H C U 58 113 144 126 238 270 330 508 838 T D L 81 156 174 A O 31 27 55 71 73 61 65 125 40 41 93 80 76 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 EXEMPLO DE CODIFICAÇÃO DE HUFFMAN 125 Freq 93 80 76 73 71 61 55 41 40 E Char T A O I N R H L D 31 27 C U 65 S 0000 Fixo 0001 0010 0011 0100 0101 0111 1000 1001 1010 1011 1100 0110 110 Huff 011 000 001 1011 1010 1000 1111 0101 0100 11100 11101 1001 838 Total 400 362 EXEMPLO DE CODIFICAÇÃO DE HUFFMAN COMPARAÇÃO COM CODIFICAÇÃO FIXA ABORDAGEM ALTERNATIVA 1 Disponha as letrasfonte em ordem decrescente de probabilidade p1p2pk 2 Atribua 0 ao último dígito de Xk e 1 ao último dígito de Xk1 3 Uma pk e pk1 para formar um novo conjunto de probabilidades p1 p2 p3 Pk2 pk1pk 4 Se faltou apenas uma única letra então está terminado Caso contrário retorne ao passo 1 e repita o procedimento EXEMPLO DE CODIFICAÇÃO DE HUFFMAN e 2185522 9934 EXEMPLO 1 SUPONDO UM DADO COM 4 FACES COM AS SEGUINTES PROBABILIDADES A 042 B 028 C 024 D 006 Proponha a codificação de HUFFMAN e codificação FIXA OTIMIZADA e calcule a A entropia do conjunto b Para Huffman número médio de bits e eficiência da codificação c Para codificação fixa número médio de bits e eficiência da codificação d Compare a e b Criação da árvore A042 B028 C024 D006 030 Ordene do maior para o menor e reúna os dois menores Em seguida reordene do maior para o menor Criação da árvore A042 B028 C024 D006 030 Reúna os dois menores Em seguida reordene do maior para o menor 058 Criação da árvore A042 B028 C024 D006 030 Reúna os dois menores Em seguida distribua os 0s e 1s NÓS vamos padronizar esquerda 0 direta 1 058 1 0 0 1 1 0 1 Codificação A042 B028 C024 D006 030 Caminhe da raiz até a letra para saber o código Por exemplo para o código de A você sai do 1 caminha pelo 1 e já chega no A Logo o código é 1 Para o código de D você sai do 1 passa pelo 058 passa pelo 030 e chega no D No caminho você passou por 001 e este é o código de D 058 1 0 0 1 1 0 1 Codificação de Huffman A042 B028 C024 D006 030 058 1 0 0 1 1 0 1 Letra HUFFMAN BITS A 1 1 B 01 2 C 000 3 D 001 3 Nesta coluna está apresentado o número de bits do código Por exemplo 001 3 bits Codificação fixa Letra Código Fixo Bits A 00 2 B 01 2 C 10 2 D 11 2 Na codificação de 4 elementos A B C e D precisamos de 2 bits na codificação fixa otimizada Como sabemos disto Número de códigos 2n onde n é o número de bits Ou seja 2 bits suportam 22 4 códigos 3 bits suportam 23 8 códigos E assim sucessivamente Agora já temos os elementos para realizar os demais cálculos ENTROPIA CÓDIGO HUFFMAN CÓDIGO FIXO Letra Dados P 100 HM COD BITS NHUF FIXO BITS2 NFIXO A 042 042 42 05256 1 1 042 00 2 084 B 028 028 28 05142 01 2 056 01 2 056 C 024 024 24 04941 000 3 072 10 2 048 D 006 006 6 02435 001 3 018 11 2 012 1 1 100 17775 225 188 2 2 ehufHMNHUF ehuf 9455 efixoHMNFIX efixo 8888 NHUF PBITS NFIXO PBITS2 Média da coluna Média da coluna HM 042log2042 028log2028 024log2024 006log2006 17775 ehuf HMNhuf 100 17775188 100 9455 efixo HMNfixo100 177752100 8888 Respostas a Entropia 17775bits b Para Huffman a Número médio de bits 225 b Eficiência da codificação 9455 c Para codificação fixa a Número médio de bits 2 b Eficiência da codificação 8888 d Compare a e b para o exemplo apresentado a codificação de Huffman é 567 mais eficiente do que a codificação fixa otimizada IDEIAS EM PRÁTICA Atividade SUPONDO UM DADO COM 8 FACES A 035 E 008 B 025 F 005 C 012 G 003 D 010 H 002 Proponha a codificação de HUFFMAN e codificação FIXA OTIMIZADA e calcule a A entropia do conjunto b Para Huffman número médio de bits e eficiência da codificação c Para codificação fixa número médio de bits e eficiência da codificação d Compare a e b Construindo a árvore de Huffman A035 B025 C012 D010 E008 F005 G003 H002 Ordene do maior para o menor e reúna os dois menores Em seguida reordene do maior para o menor Perceba que neste caso os dois menores são iguais 005 Então basta reunir os dois menores novamente Agora sim precisamos reordenar do maior para o menor 005 010 Construindo a árvore de Huffman A035 B025 C012 D010 E008 F005 G003 H002 Reúna os dois menores e reordene 005 010 018 Construindo a árvore de Huffman A035 B025 C012 D010 E008 F005 G003 H002 Reúna os dois menores e reordene 005 010 018 022 Construindo a árvore de Huffman A035 B025 C012 D010 E008 F005 G003 H002 Reúna os dois menores e reordene 005 010 018 022 040 Construindo a árvore de Huffman A035 B025 C012 D010 E008 F005 G003 H002 Reúna os dois menores e reordene 005 010 018 022 040 060 Construindo a árvore de Huffman A035 B025 C012 D010 E008 F005 G003 H002 Reúna os dois últimos nós e distribua os 0s e 1s 005 010 018 022 040 060 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 Da árvore retiramos o código de Huffman Letra COD HUFFMAN BITS A 00 2 B 01 2 C 100 3 D 101 3 E 111 3 F 1100 4 G 11010 5 H 11011 5 Para a codificação fixa 3 bits Letra COD FIXA BITS A 000 3 B 001 3 C 010 3 D 011 3 E 100 3 F 101 3 G 110 3 H 111 3 Agora já temos os elementos para realizar os demais cálculos Realizando os cálculos temos ENTROPIA CÓDIGO HUFFMAN CÓDIGO FIXO Letra ocorrência P 100 HM COD BITS NHUF FIXO BITS2 NFIXO A 035 035 35 05301 00 2 07 000 3 105 B 025 025 25 05000 01 2 05 001 3 075 C 012 012 12 03671 100 3 036 010 3 036 D 01 01 10 03322 101 3 03 011 3 03 E 008 008 8 02915 111 3 024 100 3 024 F 005 005 5 02161 1100 4 02 101 3 015 G 003 003 3 01518 11010 5 015 110 3 009 H 002 002 2 01129 11011 5 01 111 3 006 1 1 2 25016 3375 255 0 3 3 ehufHMNHUF ehuf 9810 efixoHMNFIX efixo 8339 Respostas a Entropia 25016bits b Para Huffman a Número médio de bits 255 b Eficiência da codificação 9810 c Para codificação fixa a Número médio de bits 3 b Eficiência da codificação 8339 d Compare a e b para o exemplo apresentado a codificação de Huffman é 1472 mais eficiente do que a codificação fixa otimizada Suponha que OS CARACTERES fossem Letra COD HUFFMAN BITS A 0 2 O 1 2 C 100 3 R 101 3 E 111 3 1100 4 U 11010 5 T 11011 5 Letra COD HUFFMAN BITS A 00 2 B 01 2 C 100 3 D 101 3 E 111 3 F 1100 4 G 11010 5 H 11011 5 ESTES E NÃO ESTES Decodifique a mensagem 0100111101110111110101100 Vamos lá Letra COD HUF BITS A 0 2 O 1 2 C 100 3 R 101 3 E 111 3 1100 4 U 11010 5 T 11011 5 0100111101110111110101100 A C E R T O U ACERTOU VAMOS PRATICAR UM POUCO MAIS Claro profe Então Vamos aos exercícios propostps no UFPR Virtual Obrigada pessoal e até a próxima DTSUNODAUFPRBR