Compresso sem PerdaCdigos de HuffmanCodificao AritmticaAnderson
Zanardo DiasAnselmo Luiz den BattistiDarlon Vasata
Compresso sem Perda
Mtodo de compresso que permite arecuperao exata dos dados
originais apso processo de descompresso Exemplos de aplicaes que
exigem que oprocesso de compresso e descompressoseja livre de
perdas de informaoImagens mdicas digitaisTransmisso de
textosProgramas executveisBanco de Dados
Compresso sem Perda
Divididos basicamente em duas categoriasBaseados em dicionrio ou
universalGeram um arquivo comprimido contendo cdigos decomprimento
fixo, normalmente, com 12 a 16 bitsNo necessitam do conhecimento da
freqncia comque os smbolos fonte ocorrem na informao originalMtodos
estatsticosCdigos de comprimentos variveisOs dados na informao
original que aparecem commaior freqncia so representados por
palavras-cdigo menores
Cdigos de Huffman O algoritmo de usa uma tabela de freqncia
deocorrncias para cada smbolo A codificao para cada caractere deve
ter umprefixo nico necessrio atribuir uma string de tamanhovarivel
para cada caractere Se os dados forem arranjados em uma
rvorebinria, uma codificao para cada caractere encontrada seguindo
a rvore da raiz para ocaractere folha
Huffman - Exemplo
Comprimr a seqncia de caracteresAAAAAABBBBBCCCCDDDEEF A menor
codificao que pode ser utilizadapara represent-la em binrio de trs
bitspor caractereCaractereABCDEF
Cdigo000001010011100101
Huffman - Exemplo
Gera-se assim os
bits00000000000000000000loolooloolooloinionooiooiioiioiiiooiooioi
para representar aseqncia original Isso d 63 bits de comprimento
Para usar o cdigo Huffman e comprimir estaseqncia, necessrio
primeiro montaruma rvore de Huffman com base nafreqncia de
ocorrncia de cada caractere
Huffman - Exemplo FreqnciaCaractereABCDEF
Cdigo654321
Huffman - Exemplo
.._-40.55 ,--.-.._,.".-~1").....e',,n
