AED3 10 03 Compressão estatística e entropia

  Рет қаралды 460

Marcos André Silveira Kutova

Marcos André Silveira Kutova

Күн бұрын

Videoaula da disciplina Algoritmos e Estruturas de Dados III no curso de Ciência da Computação da PUC Minas - 2018
ERRATA: No vídeo, falei de entropia de símbolo e entropia total. Na verdade, esses conceitos não existem. O termo entropia se refere apenas ao tamanho médio dos símbolos.
----------------------
A compressão estatística é uma compressão baseada na probabilidade de cada símbolo. Quando mais provável for a ocorrência de um símbolo em uma informação, então menos bits ela deve usar. É possível se estimar quantos bits uma informação precisa para ser representada (de forma compactada) por meio da sua entropia.
----------------------
Se existem vários sistemas de codificação usados na compressão de dados, como saber qual é a melhor? Para isso, a Teoria da Informação nos dá um conceito chamado de entropia. Basicamente, a entropia nos diz é quantos bits são necessários, em média, para representarmos os símbolos de uma mensagem. Em outras palavras, ela nos diz qual é o resultado esperado de um bom sistema de codificação.
Vamos tentar entender esse conceitos de entropia por meio de um exemplo. Suponha a seguinte mensagem: "ABCD". Temos nessa mensagem, 4 letras, cada uma com a probabilidade de 25%. Assim, todas têm a mesma chance de aparecer e, portanto, cada uma acabará usando 2 bits para ser representada: A=00, B=01, C=10 e D=11. A entropia, que indica o tamanho médio de cada símbolo, é, aqui, de 2 bits.
Mas, se tivermos a seguinte mensagem: "AAAABBCD", então as frequências são: A=1/2, B=1/4, C=1/8 e D=1/8. Em termos de probabilidade, temos os seguintes valores: A=50%, B=25%, C=12,5% e D=12,5%. E como calcular a entropia dessa mensagem?
Aí a coisa aperta um pouco. Vamos começar vendo qual é a estimativa individual de cada símbolo. Para isso, usamos a seguinte fórmula:
Si = - log2(Pi)
Nesse caso, a estimativa de bits Si para cada símbolo i depende da probabilidade Pi desse símbolo e fica assim:
Sa = - log2(Pa) = -log2(0.5) = 1
Sb = - log2(Pb) = -log2(0.25) = 2
Sc = - log2(Pc) = -log2(0.125) = 3
Sd = - log2(Pd) = -log2(0.125) = 3
Agora, podemos ver quantos bits são necessários para toda a mensagem, sabendo que são 4 letras A, 2 letras B, 1 letra C e 1 letra D:
4*1 + 2*2 + 1*3 + 1*3 = 14
Portanto, precisamos de 14 bits para toda a mensagem. Sabendo que ela contém 8 caracteres, o tamanho médio de cada símbolo (letra) é:
14/8 = 1,75
Assim, a entropia da mensagem é 1,75 bits, isto é, em média, os símbolos gastarão 1,75 bits.
Nós poderíamos ter calculado a entropia diretamente sem precisarmos saber o tamanho da mensagem. Para isso, basta conhecermos a probabilidade de cada um deles. Aí, a fórmula ficaria assim:
S = Σ (Pi * log2(Pi) )
Então, basta multiplicar o tamanho de cada símbolo pela sua própria probabilidade. Desenvolvendo esse cálculo, ficamos assim:
0,5*1 + 0,25*2 + 0,125*3 + 0,125*3 = 1,75
Hum... deu na mesma, não é? Ainda bem, porque, caso contrário, seria algum erro meu no cálculo. Bem, a vantagem de calcularmos diretamente é que não precisamos analisar toda a mensagem. Basta sabermos a probabilidade de cada símbolo e daí calculamos a entropia. Depois, para sabermos quanto bits precisamos para uma mensagem, é só multiplicar a entropia pelo tamanho total da mensagem.
Isso tudo está demonstrado no vídeo. Mas eu queria fazer um alerta. No vídeo, falei de entropia de símbolo e entropia total. Na verdade, esses conceitos não existem. O termo entropia se refere apenas ao tamanho médio dos símbolos.
Enfim, um bom sistema de codificação deve resultar em um tamanho médio dos símbolos bem próximo (senão igual) ao da entropia. E uma das melhores codificações, que alcança esse resultado, é a codificação de Huffman, apresentada no próximo vídeo.

Пікірлер
AED3 10 04 Codificação de Huffman
6:58
Marcos André Silveira Kutova
Рет қаралды 4,6 М.
AED3 11 05 Tipos de criptografia
6:12
Marcos André Silveira Kutova
Рет қаралды 281
Непосредственно Каха: сумка
0:53
К-Media
Рет қаралды 12 МЛН
Every team from the Bracket Buster! Who ya got? 😏
0:53
FailArmy Shorts
Рет қаралды 13 МЛН
Жездуха 42-серия
29:26
Million Show
Рет қаралды 2,6 МЛН
AED3 11 01 Criptografia e suas aplicações
13:42
Marcos André Silveira Kutova
Рет қаралды 326
AED3 10 07 Codificação por LZW
8:34
Marcos André Silveira Kutova
Рет қаралды 1,6 М.
AED3 11 08 Criptografia assimétrica e o RSA
14:46
Marcos André Silveira Kutova
Рет қаралды 675
Árvore B*
7:16
ronaldoframos
Рет қаралды 1,6 М.
AED3 11 06 Criptografia Simétrica   Cifras de fluxo
11:55
Marcos André Silveira Kutova
Рет қаралды 513
AED3 11 07 Criptografia simétrica   Cifras de bloco
8:30
Marcos André Silveira Kutova
Рет қаралды 773
AED3 12 03 Casamento de padrões por KMP
21:17
Marcos André Silveira Kutova
Рет қаралды 1 М.
AED3 12 04 Casamento de padrões por Boyer Moore - Deslocamento por Caractere Ruim
12:39
AED3 12 05 Casamento de padrões por Boyer Moore - Deslocamento por Sufixo Bom
16:52
Marcos André Silveira Kutova
Рет қаралды 806
Непосредственно Каха: сумка
0:53
К-Media
Рет қаралды 12 МЛН