ITI Slides

Introdução à Teoria da Informação / Compressão de

Dados

Prof. Leonardo Vidal BatistaDI/PPGI/PPGEM

leonardo@di.ufpb.brleovidal@terra.com.br

http://www.di.ufpb.br/~leonardo

O Que É “Teoria da Informação”?

Claude Shannon, 1948, “A Mathematical Theory of Communications”Área que estuda as comunicaçõesAlicerçada na conceituação formal de “informação” e capacidade de transmissão de informação pelos canais de comunicaçãoCompressão de Dados: aplicação de Teoria da Informação.

Sistemas de comunicação

Fonte

De Informação

Transmissor

MensagemM

Canal Ruído

Receptor Destinatário

Da Informação

MensagemM~

Sinals~

Sinals

Questões

Pode-se garantir comunicação perfeita?Pode-se garantir comunicação confiável?Comunicação equivale a "transmissão de dados"?

Respostas de Shannon:

Não Sim. Pode-se projetar e construir sistemas de comunicação tão confiáveis quanto se deseje: 1 bit errado em 1 bilhão, 1 em 1 trilhão,...Não. Comunicação envolve transmissão de informação. Compressores sem perdas reduzem a quantidade de dados em uma mensagem, preservando a informação

O Que É “Informação”?

Informação (ou entropia) é uma medida da incerteza ou surpresa relacionada a um eventoO processo de comunicação éinerentemente probabilísticoInformação é relativa!

Informação e Incerteza

Tarefa para a próxima aula: decorar letra por letra o livro “Os Sertões”Na próxima aula, farei apenas a

leitura de “Os Sertões”Quem virá? Transmitirei informação? Ocorrerá comunicação?

Teoria da Informação e Física

A equação de entropia (informação) de Shannon é análoga à entropia da termodinâmicaEra Newton: matéria, energia e informaçãoEra Einstein: energia e informaçãoEra Shannon: informação

Relatividade da informação

010101010101...

Pedro Álvares Cabra...

14159265...

27033903618375114...

Marcela amou-me durante quinze meses e onze ...

Entropia e Compressão

A entropia é um limite para o grau de compressão máxima que se pode obter

Entropia elevada => grau de compressão reduzidoEntropia reduzida => grau de compressão elevado

Procurar construir modelos que reduzam a entropia!

Modelagem e Compressão

Um bom modelo prevê com precisão os símbolos sucessivos da mensagemPortanto:Bom modelo => surpresa reduzida => entropia reduzida => compressão elevadaCompressão elevada=> entropia reduzida => surpresa reduzida => Bom modeloBom modelo equivale a boa compressãoGrau de compressão é uma medida da qualidade de um modelo

Entropia da Língua Inglesa

Qual é a entropia da Língua Inglesa?O que é a língua inglesa???Qual é a entropia da língua inglesa nos livros de Swift?

Entropia da Língua Inglesa

Qual é a entropia da língua inglesa nos livros de Swift?

Por um especialista em Literatura Inglesa?Por um engenheiro inglês?Por um modelo computacional?Por uma criança recém-alfabetizada em inglês?

Entropia da Língua Inglesa

Shannon, 1952: entropia da "língua inglesa" escrita, por americanos adultos: aprox. 1 bit/símboloVários estudos posteriores confirmaram esta estimativaMelhores modelos computacionais: aprox. 1,2 bit/símboloQuando um modelo computacional tornar-se tão bom quanto um humano, o computador terá "entendido" os textos??

Entropia da Língua Inglesa

Aplicações para um bom modelo computacional para um idioma: OCR; conversão de voz para texto; síntese de voz; atribuição de autoria etcDificuldade: Pedro Álvares Cabra...

Entropia de outras mensagens

Língua portuguesaDNAIBOVESPADados sísmicosEtc

Compressão para Não Comprimir!

Compressores modernos possuem excelente capacidade de modelagemOs modelos podem ser utilizados para vários outros fins que não compressão: reconhecimento de locutor, face, microorganismos, textura, atribuição de autoria, etc.

Compressão para Comprimir!

Compressão é tecnologia-chave em:DVDsTV digitalMP3Câmeras fotográficas e de vídeoRedes de comunicaçãoEtc

Fonte de Informação

Fonte de informação: elemento de um processo de comunicação que produz informaçãoFonte S: produz mensagens que são seqüências de elementos selecionados de um conjunto A = {a0, a1, a2,...}A: alfabeto da fonteai: símbolo ou letra

Fontes decimais e binárias

Fonte de dígitos decimais:A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}Mensagem M = 590126885122380546

Fonte binária:A = {0, 1}

Representação da InformaçãoSemáforo de três cores: informação de interesse são coresRepresentação da informação:

Texto em inglês: {R, Y, G}; {Red, Yellow, Green}Texto em português: {Vermelho, Amarelo, Verde}Computador: {00, 01, 10}Outras aplicações: {0, 1, 2}; sons; sinais elétricos

Codificação

Codificação: representação da informaçãoPalavra-código: representação de um símbolo ou seqüência de símbolosCódigo de fonte: conjunto de palavras-código capaz de representar qualquer mensagem emitida pela fonte

Codificação

Alguns códigos para fonte de dígitos decimais

Decimal ASCII Binário 1 Binário 2 Binário 3 Octal Alfabético0 3016 00002 002 1111112 008 a 1 3116 00012 012 1111102 018 f 2 3216 00102 102 1111012 028 k 3 3316 00112 11002 1111002 038 m 4 3416 01002 11012 11102 048 n 5 3516 01012 11102 11012 058 b 6 3616 01102 1111002 11002 068 z 7 3716 01112 1111012 102 078 x 8 3816 10002 1111102 012 108 p 9 3916 10012 1111112 002 118 s

Codificador e Decodificador

Codificador: elemento (ser humano, circuito, programa, etc) que representa as mensagens geradas pela fonte empregando um código específico. Decodificador: elemento responsável por desfazer o mapeamento realizado por um codificador.

Códigos de Propósito Específico

Códigos de propósito específico:Códigos de transmissão (Morse, códigos corretores de erros, etc)Códigos de criptografiaCódigos de compressão: representar a informação da forma mais eficiente possível

Códigos binários -> usar o menor número de bits possível

Códigos de CompressãoEm termos de compressão, qual é o melhor código binário?

Decimal ASCII Binário 1 Binário 2 Binário 3 Octal Alfabético0 3016 00002 002 1111112 008 a 1 3116 00012 012 1111102 018 f 2 3216 00102 102 1111012 028 k 3 3316 00112 11002 1111002 038 m 4 3416 01002 11012 11102 048 n 5 3516 01012 11102 11012 058 b 6 3616 01102 1111002 11002 068 z 7 3716 01112 1111012 102 078 x 8 3816 10002 1111102 012 108 p 9 3916 10012 1111112 002 118 s

Códigos de Compressão

Resposta: Depende da freqüência relativa (probabilidade) com que a fonte produz cada símbolo.

Exemplo: Codificação/DecodificaçãoCodificar e decodificar a mensagem RGBRBRR usando RGB1, RGB2, RGB3

RGB1Codificar: 00011000100000 (14 bits)Decodificar: RGBRBRR

Símbolo Código RGB1 Código RGB2 Código RGB3Cor vermelha 00 0 0 Cor verde 01 1 10 Cor azul 10 00 11

Exemplo: Codificação/Decodificação

Codificar e decodificar a mensagem RGBRBRR usando RGB1, RGB2, RGB3

RGB2Codificar: 010000000 (9 bits)Decodificar: RG ?

Símbolo Código RGB1 Código RGB2 Código RGB3Cor vermelha 00 0 0 Cor verde 01 1 10 Cor azul 10 00 11

Exemplo: Codificação/Decodificação

Codificar e decodificar a mensagem RGBRBRR usando RGB1, RGB2, RGB3

RGB3:Codificar: 0101101100 (10 bits)Decodificar: RGBRBRR

Símbolo Código RGB1 Código RGB2 Código RGB3Cor vermelha 00 0 0 Cor verde 01 1 10 Cor azul 10 00 11

Códigos de Prefixo

RGB1 e RGB3 são códigos de prefixo: nenhuma palavra-código é prefixo de outra.

Códigos unicamente decodificáveis.

RGB2 não é um código de prefixo.

Exemplo: comprimento médio

Codificar a mensagem W usando Bin2W = 1 0 2 4 5 0 0 1 0 2 1 1 0 0 0 7 0 3 0 6

0 0 9 0 0 0 2 4 5 0 2 3 3 0 0 4 0 5 0 06 0 0 7 8 6 0 0 0 0 7 6 8 8 0 0 0 7 8 5

Alfabeto: {0, 1, ..., 9}N = 60 símbolosNi: No. de ocorrências de ai

N0 = 29; N1 = 4; N2 = 4; N3 = 3; N4 = 3; N5 = 4; N6 = 4; N7 = 4; N8 = 4; N9 = 1

Exemplo: comprimento médio

bi: Número de bits da palavra-código associada a ai:

b0 = 2; b1 = 2; b2 = 2; b3 = 4; b4 = 4; b5 = 4; b6 = 6; b7 = 6; b8 = 6; b9 = 6

Binário 2 002 012 102

11002 11012 11102

1111002 1111012 1111102 1111112

Exemplo: comprimento médioTotal de bits: l = 29x2 + 4x2 + 4x2 + 3x4 + 3x4 + 4x4 +

4x6+ 4x6+ 4x6+ 1x6 = 192 bits

Número médio de bits por símbolo:

= (29x2 + 4x2 + 4x2 + 3x4 + 3x4 + 4x4 + 4x6+ 4x6+ 4x6+ 1x6)/60

= (29/60)x2 + (4/60)x2 + (4/60)x2 + (3/60)x4 + (3/60)x4 + (4/60)x4 + (4/60)x6+ (4/60)x6+ (4/60)x6+ (1/60)x6

= 3,2 bits/símbolo.

l

Exemplo: comprimento médio

Para alfabeto A = {a0, a1, ... aM-1}Pi = estimativa da probabilidade de ai

= freqüência relativa de ai = Ni/N= P0 b0+ P1 b1+… PM-1 bM-1l

∑−

==

1

0

M

iiibPl

Exemplo: comprimento médio

Codificar a mensagem W usando Bin3b0 = 6; b1 = 6; b2 = 6; b3 = 6; b4 = 4; b5 = 4; b6 = 4; b7 = 2; b8 = 2; b9 =

= 29x6 + 4x6 + 4x6 + 3x6 + 3x4 + 4x4 + 4x4 + 4x2 + 4x2 + 2x1)/60 = 5,03 bits/símbolo

Para compressão, qual é o melhor código, BIN2 ou BIN3? Há algum código de prefixo melhor?

l

Problema da Codificação para Compressão

Dado um modelo probabilístico para a fonte, encontrar um código unicamente decodificável ótimo, ou seja, que represente a saída da fonte com o menor no. possível de bits. Encontrar bi de forma a minimizar

l

∑−

==

1

0

M

iiibPl

InformaçãoSolução: bi = Informação Ii associada ao símbolo ai:

iii P

Ib 1log==

Se log2 -> informação em bitsSe log3 -> informação em tritsSe ln -> informação em natsSe log10 -> informação em dígitos decimais

Entropia

Unidade (para base 2): bits/símboloEntropia da fonte ou da mensagem?Shannon, 1948: entropia e compressãoHuffman, 1952: codificação ótima de comprimento inteiroPesquisadores da IBM, 1978: codificação ótima

∑−

===

1

02min

1logM

i ii P

PlH

Exemplo: Informação e entropiaW =1 0 2 4 5 0 0 1 0 2 1 1 0 0 0 7 0 3 0 6

0 0 9 0 0 0 2 4 5 0 2 3 3 0 0 4 0 5 0 06 0 0 7 8 6 0 0 0 0 7 6 8 8 0 0 0 7 8 5

P0 = 29/60 => I0 = log2 60/29 =1,05 bitP1 = P2 = P5 = P6 = P7 = P8 = 4/60 => I1=I2=I5=I6=I7=I8= log2 60/4 =3,91 bitsP3= P4 = 3/60 => I3=I4= log2 60/3=4,32 bits P9 = 1/60 => I9 = log2 60 = 5,91 bitsH = (29/60)*1,05 +(4/60)*3,91

+…+(1/60)*5,91 = 2,602 bits/símbolo

Exemplo: Informação e entropia

Comparar H = 2,602 bits/símbolo com codificação por Bin2 e Bin3 (3,2 bits/símbolo e 5,03 bits/símbolo)Código eficiente? Comparar sempre com a entropia!

Código de Hufmann

Código de comprimento inteiro ótimoPara mensagem dos exemplos anteriores:

Símbolo Código de Huffman

Comprimento Palavra-código

Informação

0 1 1 1,05 1 0111 4 3,91 2 0110 4 3,91 5 0101 4 3,91 6 0100 4 3,91 7 0011 4 3,91 8 0010 4 3,91 3 0001 4 4,32 4 00001 5 4,32 9 00000 5 5,91

Código de Hufmann

lHuff = 29x1 + 4x4 + 4x4 + …+ 1x5 = 157 bitsCompr. Médio = (29x1 + 4x4 + 4x4 + …+ 1x5)/60 = 2,62 bits/símbolo.Entropia H = 2,60Eficiência? Código binário de comprimento fixo de 4 bits/símbolo:RC = 60x4/(60x2,62) = 1,53 (1,53:1)

Código de Hufmann

Outras árvores de Huffman?Como quebrar empates?Que informação passar ao decodificador para permitir decodificação? Tabela de códigos OU a árvore OU contadoresQuando o Huffman se torna ineficiente?

Código de Hufmann

Quando o Huffman se torna ineficiente?Pi >> 0,5

Redundância do código de Huffman:

Pode-se mostrar que

Ou seja:

1+≤ HlHuff

1≤HuffR

HlR HuffHuff −=

Código de Hufmann -ExemploA = {a, b, c, d, r}P(a) = 0,99 => I(a) = 0,0145P(b)=P(c)=P(d)=0,003 => I(b) = I(c) = I(d) = 8,3817P(r) = 0,001 => I(r) = 9,9668

Huffl =0,99x1 + 3x 0,003x3 + 0,001x3 = 1,02 bits/símbolo

RC= 3/1,02 = 2,94:1H = 0,0998 bits/símbolo.

Código de Hufmann -Exemplo

RCmax= 3/0,0998 = 30,06:1 RCmax = 10,22 x RCHuff

O que fazer para aplicar o código de Huffman eficientemente nestes casos? RLE, por exemplo.Huffman para alfabetos binários?

obit/símbol 0,9202=HuffR

10,22/ =HlHuff

Código de Hufmann

Programação = estrutura de dados + algoritmosCompressão = modelagem + codificaçãoEquiprobablidade <=> Entropia máxima: H = log2 |A|. Se |A| = 2k, H = k.P(ai) = 1, para algum i <=> Entropia mínima: H = 0.

Modelos probabilísticos

Estáticos: probabilidades estáticas durante todo o processo de codificaçãoSemiadaptativos: probabilidades estimadas para cada mensagem a ser codificada, e mantidas estáticas durante a codificaçãoAdaptativos: probabilidades atualizadas durante a codificação

Modelos probabilísticos

Não-contextuais: símbolos independentes, probabilidades não condicionais.Contextuais: símbolos dependentes, probabilidades condicionais.Modelos contextuais estáticos, não-contextuais semi-adaptativos, etc.Modelagem + Codificação: Huffman não-contextual semi-adaptativo, aritmético contextual adaptativo, etc

Modelos probabilísticos

Família LZ (contextuais adaptativos)PPMs (contextuais adaptativos)Equivalência entre compressores baseados em dicionários e compressores estatísticos

Modelos probabilísticos

Exemplo: Huffman adaptativo de decremento para abracadabra.Exemplo: Huffman adaptativo de incremento para abracadabra.O que ocorre se codificarmos por Huffmanuma mensagem já codificada por Huffman?

Modelos Contextuais

Fonte S com A = {ao, a1,..., aM-1} Elemento x gerado por S é uma variável aleatóriaModelos não-contextuais: P(x = ai)Modelos contextuais: P(xn=ai|xn-1,xn-2,...)Modelo de Markov de k-ésima ordem: P(xn=ai | xn-1, xn-2,..., xn-k)Modelos de memória finita

Modelos Contextuais

xk = xn-1, xn-2,..., xn-k

Define-se informação condicional associada a ai, dado um contexto xk

como:

)|(1log ) | I( 2 k

in

ki

axPa

xx

==

Modelos Contextuais

Exemplo: Huffman semi-adaptativo contextual de ordem 1Mensagem: abracadabra

Modelos ContextuaisSolução:O símbolo a ocorre 5 vezes na mensagem, mas apenas em 4 é contexto de outro. Quatro ocorrências do contexto a:

em 2 o símbolo subseqüente é bem 1 o símbolo subseqüente é cem 1 o símbolo subseqüente é d

Portanto,P(b | a) = 2/4 -> I(b | a) = 1P(c | a) = 1/4 -> I(c | a) = 2P(d | a) = 1/4 -> I(d | a) = 2

Modelos ContextuaisSolução (cont.)Árvore de Huffman (. | a)

Por um raciocínio análogo:P(r | b) = 1 -> I(r | b) = 0P(a | c) = 1 -> I(a | c) = 0 P(a | d) = 1 -> I(a | d) = 0P(a | r) = 1 -> I(a | r) = 0

Modelos ContextuaisPrimeiro símbolo: não codificar.Comprimento médio atingido = (1 + 1 + 1 + 2 + 2) / 11 = 0,6363 bits/símbolo.O Huffman atingiu desempenho ótimo porque as probabilidades eram todas potências de 2. O uso de modelos contextuais tende a produzir muitos valores de informação condicional bem inferiores a 1, mas não nulos e o Huffman se torna ineficiente

Modelos ContextuaisExemplo: Huffman semi-adaptativo contextual de ordem 1 Mensagem: abracadabraabraabarcabraba

Modelos Contextuais

Exemplo: A = {0,1}, Mensagem: 1010101010101010101010101010101010101010101010101010101010Modelo não-contextual: H=1 bit/símbolo (1 bit/bit!)Modelo contextual: H aprox. 0 bit/símbolo

Modelos Contextuais

Se uma fonte gera símbolos que dependem dos valores presentes em um contexto de tamanho L, um modelo de Markov de ordem k, com k <= L, émelhor que um modelo de ordem k-1 e, conseqüentemente, conduz a uma redução na entropia. Seria natural empregar modelos de ordem muito elevada para obter boas compressões, mas alguns problemas práticos limitam a aplicabilidade da idéia.

Modelos Contextuais

Com um modelo de ordem k e um alfabeto de tamanho M, tem-se Mk

possíveis contextos, ou seja, o número de contextos diferentes cresce exponencialmente com a ordem do modelo. Quantos contadores devem ser passados ao decodificador utilizando um modelo semi-adaptativo?

Modelos Contextuais

Se M = 256 e k = 5: aproximadamente um trilhão de contextos diversos. Problemas práticos: memória, tempo de processamento, estimativas de probabilidades, transmissão para o decodificador das probabilidades condicionais. Usar modelos adaptativos elimina apenas o último dos problemas citados!Na prática, para M = 256, k = 0, 1,..., 10

Modelos Contextuais

Exemplo:Huffman adaptativo contextual de ordem 1.Mensagem: abracadabra

Entropia de Modelo De Markov de Ordem 1

Fonte com alfabeto A = {a0, a1,...aM-1}. Bigrama: par ordenado de símbolos consecutivos gerados pela fonte. Bigrama (ai, aj) é diferente do bigrama (aj ai), para i diferente de j. Experimento probabilístico: observar um bigrama da mensagem. Eventos de interesse:Ai: ai é o 1o. elemento do bigramaBi: ai é o 2o. elemento do bigrama

Entropia de Modelo De Markov de Ordem 1

Probabilidade de ocorrência simultânea dos eventos Ai e Bj:

P(Ai, Bj) = P(Bj, Ai)Probabilidade de ocorrência de Bj dada a ocorrência de Ai:

)|()|( jiij BAPABP ≠

Entropia de Modelo De Markov de Ordem 1

Regra da probabilidade condicional:

)(),(

)|(i

jiij AP

BAPABP =

Exemplo

Mensagem W = abracadabraabraabarcabraba. A = {a, b, c, d, r}. Evento B2: símbolo c na 2a. posição de um bigramaEvento A0: símbolo a na primeira posição de um bigrama

Exemplo (Cont)

W: 26 símbolos, 25 bigramas (ab, br, ra, ...ba). A0 ocorre 11 vezes na mensagemB2 ocorre 2 vezes. Estimando-se as probabilidades pela freqüência relativa, tem-se:

Exemplo (Cont)

A0 ocorreu 11 vezes em 25 bigramas: P(A0)=11/25 B2 ocorreu 2 vezes em 25 bigramas: P(B2)=2/25A0 ocorreu 11 vezes; destas, em uma B2 ocorreu: P(B2 | A0) = 1/11B2 ocorreu 2 vezes; destas, em uma A0 ocorreu: P(A0 | B2) = ½A0 e B2 ocorreram 1 vez nos 25 bigramas observados: P(A0, B2) = P(B2, A0) = 1/25

Exemplo (Cont)

Observe que:

111

25/1125/1

)(),(

)|(0

2002 ===

APBAP

ABP

21

25/225/1

)(),(

)|(2

2020 ===

BPBAP

BAP

Exemplo (Cont)

Distribuição de probabilidades conjuntas:

2o símbolo do bigrama 1o símbolo do bigrama a b c d r

a 2/25 6/25 1/25 1/25 1/25b 2/25 0 0 0 4/25c 2/25 0 0 0 0 d 1/25 0 0 0 0 r 4/25 0 1/25 0 0

Observe que o somatório de todas as células da tabela resulta em 1

Exemplo (Cont)

Distribuição de probabilidades condicionais P(Bj | Ai)

O somatório de todas as células de cada linha da tabela resulta em 1

2o símbolo do bigrama 1o símbolo do bigrama a b c d r

a 2/11 6/11 1/11 1/11 1/11b 2/6 0 0 0 4/6 c 2/2 0 0 0 0 d 1/1 0 0 0 0 r 4/5 0 1/5 0 0

Entropia de Modelo De Markov de Ordem 1

Markov de ordem 1=>entropia de ordem 2I(Bj|Ai)=log2[1/P(Bj|Ai)]: informação associada a aj dado o contexto ai

Nij: no. De ocorrências de aj no contexto ai= no. ocorrências de aiaj

Nb: total de bigramas em uma mensagem

)]|(log...)|(log

)|(log)|(log[1

1121,102202

01201002002

−−−−++

++×−=

MMMM

bABPNABPN

ABPNABPNN

H

Entropia de Modelo De Markov de Ordem 1

Estimando probabilidades por freqüência relativa:

)]|(log),(...)|(log),()|(log),([

11211

01210002002

−−−−+++−=

MMMM ABPBAPABPBAPABPBAPH

∑ ∑−

=

−

=−=

1

0

1

022 )|(log),(

M

i

M

jijji ABPBAPH

Entropia de Ordem N (Markov de Ordem N-1)

Contexto vi: N-1 símbolos consecutivosAlfabeto A = {a0, a1,...aM-1}: C = MN-1

contextos distintosv0 = a0 a0 a0...a0

v1 = a0 a0 a0... a1

...vC-1 = aM-1 aM-1 aM-1... aM-1

Entropia de Ordem N (Markov de Ordem N-1)

EventosAi: o contexto vi ocorre no início de um N-gramaBi: o símbolo ai ocorre na última posição de um N-gramaValem as mesmas equações de probabilidades condicionais anteriormente apresentadas.

Entropia de Ordem N (Markov de Ordem N-1)

Distribuição de probabilidades conjuntas:

Observe que o somatório de todas as células da tabela resulta em 1

símbolo Contexto a0 a1 ... aM-1

v0 v1 … vC-1

Entropia de Ordem N (Markov de Ordem N-1)

Distribuição de probabilidades condicionais P(Bj | Ai)

O somatório de todas as células de cada linha da tabela resulta em 1

símbolo Contextoa0 a1 ... aM-1

v0 v1 … vC-1

Entropia de Ordem N (Markov de Ordem N-1)

Entropia de ordem N:

∑ ∑−

=

−

=−=

1

0

1

02 )|(log),(

C

i

M

jijjiN ABPBAPH

Entropia (fonte estacionária):

NN

HH∞→

= lim

PPM

Prediction by Partial MatchingCleary, J.G. and Witten, I.H. (1984) “Data compression usingadaptive coding and partial string matching," IEEE Transactions onCommunications,32(4), 396-402

Codificação Baseada em Dicionário

Ziv e Lempel, 1976: Complexidade de sistemas dinâmicosZiv e Lempel, 1977: LZ77Ziv e Lempel, 1978: LZ78Welch, 1984: LZWLZA, LZM, LZFA, ...

Codificação Baseada em Dicionário

Ziv e Lempel, 1976: Complexidade de sistemas dinâmicosZiv e Lempel, 1977: LZ77Ziv e Lempel, 1978: LZ78

LZ77

(Elementos previamente codificados)

área de previsão

dicionário

D-1 L-1 0

(Próx. Elem.)

Exemplo LZW

Exemplo:W = abracadabra; alfabeto = {a, b, c, d, r}CodificaçãoDicionário inicial:0 a1 b2 c3 d4 r

Exemplo LZW (Cont.)Frase ‘a’ está no dicionárioFrase ‘ab’ não está no dicionárioMensagem codificada = 0 (última frase encontrada no dicionário)

Dicionário:0 a 5 ab1 b2 c3 d4 r

Exemplo LZW (Cont.)‘b’ está no dicionário; ‘br’ não está no dicionárioMensagem codificada = 01

Dicionário:0 a 5 ab1 b 6 br2 c3 d4 r

Exemplo LZW (Cont.)‘r’ está no dicionário; ‘ra’ não está no dicionárioMensagem codificada = ‘0’ ‘1’ ‘4’

Dicionário:0 a 5 ab1 b 6 br2 c 7 ra3 d4 r

Exemplo LZW (Cont.)‘a’ está no dicionário; ‘ac’ não está no dicionárioMensagem codificada = ‘0’ ‘1’ ‘4’ ‘0’

Dicionário:0 a 5 ab1 b 6 br2 c 7 ra3 d 8 ac4 r

Exemplo LZW (Cont.)‘c’ está no dicionário; ‘ca’ não está no dicionárioMensagem codificada = ‘0’ ‘1’ ‘4’ ‘0’ ‘2’

Dicionário:0 a 5 ab1 b 6 br2 c 7 ra3 d 8 ac4 r 9 ca

Exemplo LZW (Cont.)‘a’ está no dicionário; ‘ad’ não está no dicionárioMensagem codificada = ‘0’ ‘1’ ‘4’ ‘0’ ‘2’‘0’

Dicionário:0 a 5 ab 10 ad1 b 6 br2 c 7 ra3 d 8 ac4 r 9 ca

Exemplo LZW (Cont.)‘d’ está no dicionário; ‘da’ não está no dicionárioMensagem codificada = ‘0’ ‘1’ ‘4’ ‘0’ ‘2’‘0’ ‘3’

Dicionário:0 a 5 ab 10 ad1 b 6 br 11 da2 c 7 ra3 d 8 ac4 r 9 ca

Exemplo LZW (Cont.)‘a’ está no dicionário; ‘ab’ está no dicionário; ‘abr’ não está no dicionárioMensagem codificada = ‘0’ ‘1’ ‘4’ ‘0’ ‘2’‘0’ ‘3’ ‘5’

Dicionário:0 a 5 ab 10 ad1 b 6 br 11 da2 c 7 ra 12 abr3 d 8 ac4 r 9 ca

Exemplo LZW (Cont.)‘r’ está no dicionário; ‘ra’ está no dicionário; EOFMensagem codificada = ‘0’ ‘1’ ‘4’ ‘0’ ‘2’‘0’ ‘3’ ‘5’ ‘7’

Dicionário:0 a 5 ab 10 ad1 b 6 br 11 da2 c 7 ra 12 abr3 d 8 ac 13 raEOF4 r 9 ca

Exemplo LZW (Cont.)DecodificaçãoW codificada: ‘0’ ‘1’ ‘4’ ‘0’ ‘2’ ‘0’ ‘3’ ‘5’ ‘7’Dicionário inicial:0 a1 b2 c3 d4 r

Exemplo LZW (Cont.)W codificada: ‘0’ ‘1’ ‘4’ ‘0’ ‘2’ ‘0’ ‘3’ ‘5’ ‘7’W: aDicionário :0 a 5 a?1 b2 c3 d4 r

Exemplo LZW (Cont.)W codificada: ‘0’ ‘1’ ‘4’ ‘0’ ‘2’ ‘0’ ‘3’ ‘5’ ‘7’W: a bDicionário :0 a 5 ab1 b 6 b?2 c3 d4 r

Exemplo LZW (Cont.)W codificada: ‘0’ ‘1’ ‘4’ ‘0’ ‘2’ ‘0’ ‘3’ ‘5’ ‘7’W: a b rDicionário :0 a 5 ab1 b 6 br2 c 7 r?3 d 4 r

Exemplo LZW (Cont.)W codificada: ‘0’ ‘1’ ‘4’ ‘0’ ‘2’ ‘0’ ‘3’ ‘5’ ‘7’W: a b r aDicionário :0 a 5 ab1 b 6 br2 c 7 ra3 d 8 a?4 r

Exemplo LZW (Cont.)W codificada: ‘0’ ‘1’ ‘4’ ‘0’ ‘2’ ‘0’ ‘3’ ‘5’ ‘7’W: a b r a cDicionário :0 a 5 ab1 b 6 br2 c 7 ra3 d 8 ac4 r 9 c?

Exemplo LZW (Cont.)W codificada: ‘0’ ‘1’ ‘4’ ‘0’ ‘2’ ‘0’ ‘3’ ‘5’ ‘7’W: a b r a c aDicionário :0 a 5 ab 10 a?1 b 6 br2 c 7 ra3 d 8 ac4 r 9 ca

Exemplo LZW (Cont.)W codificada: ‘0’ ‘1’ ‘4’ ‘0’ ‘2’ ‘0’ ‘3’ ‘5’ ‘7’W: a b r a c a dDicionário :0 a 5 ab 10 ad1 b 6 br 11 d?2 c 7 ra3 d 8 ac4 r 9 ca

Exemplo LZW (Cont.)W codificada: ‘0’ ‘1’ ‘4’ ‘0’ ‘2’ ‘0’ ‘3’ ‘5’ ‘7’W: a b r a c a d abDicionário :0 a 5 ab 10 ad1 b 6 br 11 da2 c 7 ra 12 ab?3 d 8 ac4 r 9 ca

Exemplo LZW (Cont.)W codificada: ‘0’ ‘1’ ‘4’ ‘0’ ‘2’ ‘0’ ‘3’ ‘5’ ‘7’W: a b r a c a d ab raDicionário :0 a 5 ab 10 ad1 b 6 br 11 da2 c 7 ra 12 abr3 d 8 ac 13 raEOF4 r 9 ca

LZW - Exemplo 2

Exemplo:W = aabababaaa; alfabeto = {a, b}CodificaçãoDicionário inicial:0 a1 b

LZW - Exemplo 2 (Cont.)W = aabababaaa‘a’ está no dicionário; ‘aa’ não está no dicionárioMensagem codificada: 0 Dicionário:0 a1 b2 aa

LZW - Exemplo 2 (Cont.)W = aabababaaa‘a’ está no dicionário; ‘ab’ não está no dicionárioMensagem codificada: ‘0’ ‘0’Dicionário:0 a1 b2 aa3 ab

LZW - Exemplo 2 (Cont.)W = aabababaaa‘b’ está no dicionário; ‘ba’ não está no dicionárioMensagem codificada: ‘0’ ‘0’ ‘1’Dicionário:0 a 4 ba1 b2 aa3 ab

LZW - Exemplo 2 (Cont.)W = aabababaaa‘a’ está no dicionário; ‘ab’ está no dicionário; ‘aba’ não está no dicionárioMensagem codificada: ‘0’ ‘0’ ‘1’ ‘3’Dicionário:0 a 4 ba1 b 5 aba2 aa3 ab

LZW - Exemplo 2 (Cont.)W = aabababaaa‘a’ está no dic.; ‘ab’ está no dic.; ‘aba’está no dic.; ‘abaa’ não está no dic.Mensagem codificada: ‘0’ ‘0’ ‘1’ ‘3’ ‘5’Dicionário:0 a 4 ba1 b 5 aba2 aa 6 abaa3 ab

LZW - Exemplo 2 (Cont.)W = aabababaaa‘a’ está no dic.; ‘aa’ está no dic.; aaEOFnão está no dic.Mensagem codificada: ‘0’ ‘0’ ‘1’ ‘3’ ‘5’ ‘2’Dicionário:0 a 4 ba1 b 5 aba2 aa 6 abaa3 ab 7 aaEOF

LZW - Exemplo 2 (Cont.)DecodificaçãoW codificada: ‘0’ ‘0’ ‘1’ ‘3’ ‘5’ ‘2’Dicionário inicial:0 a1 b

LZW - Exemplo 2 (Cont.)W codificada: ‘0’ ‘0’ ‘1’ ‘3’ ‘5’ ‘2’W: aDicionário:0 a1 b2 a?

LZW - Exemplo 2 (Cont.)W codificada: ‘0’ ‘0’ ‘1’ ‘3’ ‘5’ ‘2’W: a aDicionário:0 a1 b2 aa3 a?

LZW - Exemplo 2 (Cont.)W codificada: ‘0’ ‘0’ ‘1’ ‘3’ ‘5’ ‘2’W: a a bDicionário:0 a 4 b?1 b2 aa3 ab

LZW - Exemplo 2 (Cont.)W codificada: ‘0’ ‘0’ ‘1’ ‘3’ ‘5’ ‘2’W: a a b abDicionário:0 a 4 ba1 b 5 ab?2 aa3 ab

LZW - Exemplo 2 (Cont.)Mas 1o símbolo da frase em 5 é o último símbolo da última frase (5):W codificada: ‘0’ ‘0’ ‘1’ ‘3’ ‘5’ ‘2’W: a a b ab abaDicionário:0 a 4 ba1 b 5 aba2 aa 6 aba?3 ab

LZW - Exemplo 2 (Cont.)W codificada: ‘0’ ‘0’ ‘1’ ‘3’ ‘5’ ‘2’W: a a b ab aba aaDicionário:0 a 4 ba1 b 5 aba2 aa 6 abaa3 ab 7 aaEOF

LZW - ObservaçõesDicionário de tamanho limitado a P frasesNúmero de bits, b, dos índices das frases pode crescer conforme necessário, a medida em que novas frases são inseridasNo LZW padrão, índices de tamanho fixo b = log2P

LZW - Observações

O que fazer quando o dicionário enche?Eliminar frases LRUEliminar frases menos utilizadasManter dicionário estáticoReiniciar dicionárioMonitorar compressão e, caso se detecte redução na RC, reiniciar dicionário.

Burrows-Wheeler Transform(BWT)

Transformada reversível criada por Wheeler in 1983, mas não publicadaAplicação para compressão: Michael Burrows and David Wheeler, 1994BWT não comprime, mas torna a seqüência mais apropriada àcompressão por métodos simples

Burrows-Wheeler Transform(BWT)

Mensagem com N símbolosPassos:

1. Listar as N mensagens diferentes obtidas por rotações (deslocamentos cíclicos) da mensagem original

2. Ordenar lexicograficamente as N mensagens obtidas com as rotações e indexar a lista ordenada

3. Reter o índice da mensagem original e o último símbolos das mensagens da lista ordenada, preservando a ordem

BWT

Exemplo: W = quequalquasequando (N = 18); Alfabeto = {a, d, e, l, n, o, q, s, u}Rotações:

quequalquasequandooquequalquasequanddoquequalquasequan...

BWT – Rotaçõesquequalquasequandooquequalquasequanddoquequalquasequanndoquequalquasequaandoquequalquasequuandoquequalquaseqquandoquequalquaseequandoquequalquassequandoquequalquaasequandoquequalquuasequandoquequalqquasequandoquequallquasequandoquequaalquasequandoquequualquasequandoqueqqualquasequandoqueequalquasequandoquuequalquasequandoq

BWT – Ordenação e Indexação

0 alquasequandoquequ1 andoquequalquasequ2 asequandoquequalqu3 doquequalquasequan4 equalquasequandoqu5 equandoquequalquas6 lquasequandoquequa7 ndoquequalquasequa8 oquequalquasequand9 qualquasequandoque10 quandoquequalquase11 quasequandoquequal12 quequalquasequando13 sequandoquequalqua14 ualquasequandoqueq15 uandoquequalquaseq16 uasequandoquequalq17 uequalquasequandoq

BWT – Passo 3

Mensagem transformada:

12 uuunusaadeeloaqqqq

BWT – Passo 3

A BWT informa explicitamente o último símbolo de cada rotação na lista ordenadaLista ordenada -> sabe-se o símbolo que se segue a cada um destes símbolos finais, na mensagem original

BWT – Passo 3O 1o símbolo da 1a rotação (‘a’) encontra-se na última posição da rotação de índice 6, e é o símbolo que se segue ao último símbolo da 1a

rotação (‘u’)O 1o símbolo da 2a rotação (‘a’) encontra-se na última posição da rotação de índice 7, e é o símbolo que se segue ao último símbolo da 2a

rotação (‘u’)

BWT – Passo 3O 1o símbolo da 3a rotação (‘a’) encontra-se na última posição da rotação de índice 13, e é o símbolo que se segue ao último símbolo da 3a

rotação (‘u’)O 1o símbolo da 4a rotação (‘d’) encontra-se na última posição da rotação de índice 8, e é o símbolo que se segue ao último símbolo da 4a

rotação (‘n’)...

BWT – Passo 3

Localizam-se os símbolos seguintes observando-se apenas a BWT:

uuunusaadeeloaqqqq

BWT – Passo 3Índice do símbolo na BWT->índice do símbolo seguinte na mensagem original:

u u u n u s a a d e e l o a q q q q 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 6 7 13 8 9 10 11 3 12 14 15 16 17 5 0 1 2 4

BWT – DecodificaçãoÍndice da mensagem original informa a posição, na BWT, do último símbolo da mensagemMapeamento informa o índice do símbolo seguinte, ou seja, do 1o

símbolo da mensagemSeguindo-se o mapeamento, encontram-se todos os símbolos seguintes

BWT – Decodificação

12 -> 17 (q) -> 4 (u) -> 9(e) -> 14(q) -> 0(u) -> 6(a) -> 11(l) -> 16(q) -> 2(u) -> 13(a) -> 5(s) -> 10(e) -> 15(q) -> 1(u) -> 7(a) -> 3(n) -> 8(d) -> 12(o)

u u u n u s a a d e e l o a q q q q 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 6 7 13 8 9 10 11 3 12 14 15 16 17 5 0 1 2 4

Compressão com BWT

Passos:1. BWT2. Move-To-Front3. Codificação de entropia (aritmético)

Move-To-Front (MTF)

Inicialmente, símbolos são ordenados e indexados (índices 0, 1, ...)Na codificação, cada símbolo da mensagem é substituído pelo seu índice, e então passa a ocupar a 1a

posição na lista

MTF - exemplo

W = quequalquasequandoBWT(W) = uuunusaadeeloaqqqq

Índice 0 1 2 3 4 5 6 7 8Símbolo a d e l n o q s u

Codificação do 1o símbolo: 8

MTF - exemplo

BWT(W) = uuunusaadeeloaqqqq

Índice 0 1 2 3 4 5 6 7 8Símbolo u a d e l n o q s

Codificação do 2o símbolo: 0Codificação do 3o símbolo: 0Codificação do 4o símbolo: 5

MTF - exemplo

BWT(W) = uuunusaadeeloaqqqq

Índice 0 1 2 3 4 5 6 7 8Símbolo n u a d e l o q s

Codificação do 5o símbolo: 1

MTF - exemplo

BWT(W) = uuunusaadeeloaqqqq

Índice 0 1 2 3 4 5 6 7 8Símbolo u n a d e l o q s

Codificação do 6o símbolo: 8

MTF - exemplo

BWT(W) = uuunusaadeeloaqqqq

Índice 0 1 2 3 4 5 6 7 8Símbolo s u n a d e l o q

Codificação do 7o símbolo: 3

MTF - exemplo

BWT(W) = uuunusaadeeloaqqqq

Índice 0 1 2 3 4 5 6 7 8Símbolo a s u n d e l o q

Codificação do 8o símbolo: 0Codificação do 9o símbolo: 4

MTF - exemplo

BWT(W) = uuunusaadeeloaqqqq

Índice 0 1 2 3 4 5 6 7 8Símbolo d a s u n e l o q

Codificação do 10o símbolo: 5

MTF - exemplo

BWT(W) = uuunusaadeeloaqqqq

Índice 0 1 2 3 4 5 6 7 8Símbolo e d a s u n l o q

Codificação do 11o símbolo: 0Codificação do 12o símbolo: 6

MTF - exemplo

BWT(W) = uuunusaadeeloaqqqq

Índice 0 1 2 3 4 5 6 7 8Símbolo l e d a s u n o q

Codificação do 13o símbolo: 7

MTF - exemplo

BWT(W) = uuunusaadeeloaqqqq

Índice 0 1 2 3 4 5 6 7 8Símbolo o l e d a s u n q

Codificação do 14o símbolo: 4

MTF - exemplo

BWT(W) = uuunusaadeeloaqqqq

Índice 0 1 2 3 4 5 6 7 8Símbolo a o l e d s u n q

Codificação do 15o símbolo: 8

MTF - exemplo

BWT(W) = uuunusaadeeloaqqqq

Índice 0 1 2 3 4 5 6 7 8Símbolo q a o l e d s u n

Codificação do 16o símbolo: 0Codificação do 17o símbolo: 0Codificação do 18o símbolo: 0

MTF - exemploMTF(BWT(W)) = 8 0 0 5 1 8 3 0 4 5 0 6 7 4 8 0 0 0No exemplo, Huffman semi-adaptativo não- contextual produz 53 bits sobre W, e 48 bits sobre MTF(BWT(W))O ganho de compressão tende a aumentar com o aumento de WModelos não-contextuais são eficientes com a BWT, que já explora informação contextual

Modelos Determinísticos

Modelos estatísticos contextuais: número de contextos diferentes cresce exponencialmente com o aumento do tamanho do contextoAlternativa: modelos determinísticos de prediçãoPara sinais físicos: predição polinomial de ordem K

Predição Polinomial de Ordem K

Predição do próximo símbolo baseada nos últimos K símbolosMensagem: W = w0w1...wi-1

Predição para o próximo símbolo: vi

Valor real do próximo símbolo: wi

Erro de predição: ei = wi – vi

Predição Polinomial de Ordem K

K vi ei

1 wi-1 wi-wi-1

2 2wi-1- wi-2 wi-2wi-1+wi-2

3 3wi-1-3wi-2+ wi-3 wi-3wi-1+3wi-2- wi-3

Predição Polinomial de Ordem K

Exemplo (mensagem com 32 símbolos)W = 7 6 5 4 4 4 3 4 3 2 1 0 0 0 0 1 2 3 2 1

1 2 3 5 5 5 6 6 6 7 7 7

N0= N1= N2= ... = N7 -> H = 3 bits/símbolo = comprimento médio do código de Huffman

Predição Polinomial de Ordem K

Exemplo (mensagem com 32 símbolos)K = 1 -> V = 7 -1 -1 -1 0 0 -1 1 -1 -1 -1 –1

0 0 0 1 1 1 -1 -1 0 1 1 2 0 0 10 0 1 0 0

N0=12; N-1=10; N1=8; N2=1; N7=1H = 1,87 bits/símbolo Compr. médio código de Huffman = 2

bits/símbolo

Neste caso, não codificar 1o símbolo aumenta RC

Predição Polinomial de Ordem K

Exemplo (mensagem com 32 símbolos)K = 2 -> V = 7 6 0 0 1 0 -1 2 -2 0 0 0 1 0 0

1 0 0 -2 0 1 1 0 1 -2 0 1 -1 01 -1 0

N0=15; N1=8; N-1=3; N-2=3; N2=1; N6=1; N7=1 -> H = 1, 76 bits/símbolo

Compr. médio código de Huffman = 2,16 bits/símbolo

Predição Polinomial de Ordem K

Exemplo (mensagem com 32 símbolos)K = 3 -> V = 7 6 5 4 3 5 ...H = ?Compr. médio código de Huffman = ?

Compressão com perdas

Em alguns casos, distorções introduzidas pela compressão são aceitáveisEx: vídeo, imagens, som, outros sinaisImagens e sinais críticos (e. g. utilizados no diagnóstico médico): distorções devem ser cuidadosamente controladasEficácia medida pelo compromisso entre RC e distorção Sub-amostragem ou quantização (redução de alfabeto)

Compressão com perdas

Compressor/descompressor genérico

x (n bits)

x(m bits)

Canal

x~

Compressor Descompressorx

Amostragem e Quantização

Sinal digital

Sinal analógico

Erros de quantização 0 T 2T 3T ...

0 q

2q

-2q ...

-q

...

Tempo ou espaço

Ampl

itude

Quantização Vetorial (QV)

Complexidade computacional extremamente elevada para compressãoComplexidade computacional extremamente reduzida para descompressãoShannon, 1948: codificar elementos agrupados em vetores é mais eficiente (do ponto de vista de compressão) que codificá-los isoladamente.

Quantização Vetorial (QV)

Mensagens são particionadas em blocos ou vetores com L elementos consecutivosK vetores (vetores-código) são selecionados, dentre aqueles que podem ser gerados pela fonte, e armazenados em uma tabela (codebook) disponível para o compressor e para o descompressorEspera-se que os vetores-código representem adequadamente a fonte

Quantização Vetorial (QV)

Alfabeto original com cardinalidade M: V = ML vetores diferentesM = 8 e L = 3 => V = 83 = 512M = 16 e L = 4 => V = 64KM = 256 e L = 4 => V = 4G

Quantização Vetorial (QV)

ck, k = 0, 1,..., K-1: k-ésimo vetor-código do codebookckj, j = 0, 1,..., L-1: j-ésimo elemento de ck

vi, i = 0, 1,...: i-ésimo vetor na mensagem produzida pela fontevij, j = 0, 1,..., L-1: j-ésimo elemento de vi.

Quantização Vetorial (QV)

Um codebook exemplo

k ck0 ck1 … ck,L-1 0 100 110 … 99 1 45 225 … 230

… … … … … K 2 0 … 3

Quantização Vetorial (QV)

Para codificar vi, o QV calcula a distorção D(vi, ck), k = 0, 1, ..., K-1. Erro médio quadrático:

21

0

)(1),( ∑−

=

−=L

jkjijki cv

LD cv

Se D(vi, ck) é mínima para k = k’, índice k’é anexado à mensagem comprimida. Na descompressão, k’ é substituído pelo vetor-código ck’

Quantização Vetorial (QV)

Se os índices são codificados com log2(K) bits, a taxa resultante é de log2(K)/L bits/elemento. Alfabeto original com cardinalidade M:RC = log2(ML)/log2(K)Ex: M = 256, L = 4, K = 128RC = log2(2564)/log2(128) = 4,57

Quantização Vetorial (QV)

Teoricamente, quanto maior L, mais eficiente a quantização. Dimensão dos vetores é limitada na prática. Desempenho depende ainda do tamanho do codebook, da escolha dos vetores-código e da medida de distorção. Como selecionar vetores-código?

Quantização Vetorial (QV)

O codebook é gerado por treinamento.No treinamento, uma quantidade elevada

de mensagens é examinada. Vetores mais representativos são selecionados como vetores-código. O algoritmo LBG é um método de treinamento popular, mas uma grande variedade de técnicas tem sido apresentada, incluindo redes neuraisCodebooks estáticos x dinâmicos

Quantização Escalar

Como QV, opera por redução de alfabetoSímbolos tratados individualmenteQuantização uniforme: divisão seguida por arredondamento para inteiro:

x // qx =ˆValor “dequantizado”:

x qx ˆ~ =q: tamanho do passo de quantização

Quantização Escalar

Ex: Alfabeto A = {0, 1, ..., 255}q = 2 -> Q2 = {0, 1, ... 128}

-> D2 = {0, 2, 4, ... 256}q = 3 -> Q3 = {0, 1, ... 85}

-> D3 = {0, 3, 6, ... 255}q = 4 -> Q4 = {0, 1, ... 64}

-> D4 = {0, 4, 8, ... 256}

⎣ ⎦2/max qE =

Paradigma Transformada, Quantização, Codificação (TQC)

Transformadas: Cosseno Discreta (DCT) e wavelets, principalmenteQuantização: normalmente, escalarComparado com QV, TQC apresenta baixo custo computacional e compromisso taxa-distorção semelhanteUtilizado nos padrões JPEG, JPEG2000, MPEG2, MPEG4, MPEG7, MP3...