Se você está vendo esta mensagem, significa que estamos tendo problemas para carregar recursos externos em nosso website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Conteúdo principal

Códigos de compressão

Qual é o limite de compressão? Versão original criada por Brit Cruise.

Quer participar da conversa?

  • Avatar old spice man green style do usuário Welton Vaz de Souza
    O que isso quer dizer? Porque entendo que compressão de dados diminui a quantidade de informação enviada, mas, com um espaço/tempo menor? Sim, a compressão de dados é um processo que busca reduzir o tamanho de um arquivo ou conjunto de dados ao remover informação redundante ou irrelevante. Isso permite que os dados sejam armazenados ou transmitidos mais eficientemente, pois requer menos espaço de armazenamento e tem menos dados para serem transmitidos.

    A compressão de dados é geralmente classificada em dois tipos: perda e sem perda. A compressão com perda remove informações que o algoritmo considera menos importantes, como pequenos detalhes de imagens ou áudios, enquanto a compressão sem perda mantém todas as informações originais dos dados.

    O limite de compressibilidade é a taxa máxima teórica de compressão que um algoritmo pode alcançar para um determinado conjunto de dados. Isso é determinado pela entropia dos dados, ou seja, a incerteza inerente nos dados. Dados com alta entropia são menos previsíveis e, portanto, mais difíceis de comprimir. Por exemplo, um arquivo de texto cujos caracteres são distribuidos aleatoriamente teria uma entropia mais alta do que um arquivo de texto com caracteres altamente correlacionados.

    Em resumo, a compressão de dados é um processo que busca reduzir o tamanho de um arquivo ou conjunto de dados ao remover informação redundante ou irrelevante, permitindo que os dados sejam armazenados ou transmitidos mais eficientemente. O limite de compressibilidade é a taxa máxima teórica de compressão que um algoritmo pode alcançar para um determinado conjunto de dados e é determinado pela entropia dos dados.
    (1 voto)
    Avatar Default Khan Academy avatar do usuário
Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.

Transcrição de vídeo

RKA10GM Quando representamos uma informação digitalmente, tal como uma imagem, significa que devemos cortá-la em pequenos pedaços. Isso nos permite enviar a imagem como uma sequência de símbolos coloridos, e essas cores podem ser representadas como números únicos usando alguns códigos. Considere o desafio a seguir: Alice e Bob podem transmitir e receber mensagens em binário. Eles cobram de seus clientes um centavo por bit para usar o seu sistema. Suponha que um cliente chegue e queira mandar uma mensagem, sendo que esta mensagem tem um tamanho de 1.000 símbolos. O significado das mensagens é completamente desconhecido. Normalmente, isso é enviado por um código padrão de 2 bits, o que resulta em cobrar 2.000 bits. No entanto, Alice e Bob já fizeram algumas análises desse cliente anteriormente e determinaram que a probabilidade de aparecer cada símbolo na mensagem é diferente. Será que eles podem usar essas probabilidades conhecidas para comprimir a transmissão e aumentar seu lucro? Qual é a estratégia de codificação ideal? David Huffman forneceu a estratégia ideal, que ele publicou em 1952, e na qual se baseou em construir uma árvore binária da base ao topo. Para começar, podemos listar todos os símbolos na base, que chamamos de nós. Então, achamos os dois nós menos prováveis. Nesse caso, "B" e "C", e os fundimos em um só, e adicionamos as probabilidades umas às outras. Depois, repetimos isso com os próximos dois nós menos prováveis e continuamos fundindo até termos apenas um único nó no topo. Finalmente, etiquetamos as pontas nesta árvore com zero ou 1 em qualquer ordem. Agora, o código para cada letra é apenas o caminho do topo da árvore até a letra dada. Então, para "A" é apenas uma ponta ou 1. Agora, isto é conhecido como codificação Huffman e levando em conta os exemplos a seguir, não é possível decifrá-la. Vá em frente e tente. Por exemplo, se você diminuir o código para "D", para apenas zero, então, a mensagem 011 poderá significar, talvez, DAA. Ou talvez apenas "B". Para isso funcionar, você precisa introduzir o espaço das letras, que cancelarão qualquer economia durante a transmissão. Até onde vai essa compressão de mensagem comparada ao original de 2.000 bits? Precisamos calcular o número de bits por letra em média. Então, multiplicamos o comprimento de cada código vezes a probabilidade de ocorrência e adicionamos um ao outro, o que resultará no comprimento médio de 1,75 bits por símbolo em média. Significa que com essa codificação Huffman, esperamos comprimir as mensagens de 2.000 bits para 1.750 bits. E Claude Shannon foi o primeiro a reivindicar que o limite da compressão será sempre a entropia da fonte da mensagem. À medida que a entropia ou a incerteza de nossa fonte diminui para estruturas estatísticas conhecidas, a habilidade de compressão aumenta. Enquanto que se a entropia aumenta devido à imprevisibilidade, nossa habilidade de compressão diminui. Se queremos comprimir além da entropia, precisamos, necessariamente, retirar informação das nossas mensagens.