Transcrição do Slide - Compressão de Arquivos

Slide 1: Compressão de arquivos Como funciona a compressão de arquivos Se você baixa muitos programas e arquivos da Internet, você provavelmente encontra arquivos do tipo ZIP. Este sistema de compressão é uma invenção muito útil, especialmente para usuários da Rede, porque deixa reduzir o número global de bits e bytes em um arquivo que pode ser transmitido mais depressa pelas conexões de Internet mais lentas, ou ocupa menos espaço em um disco. Uma vez baixado o arquivo, seu computador usa um programa como Winzip ou Stuffit, para convertê-lo ao tamanho original. Se tudo trabalhar corretamente, o arquivo expandido será idêntico ao arquivo original antes de ser comprimido. À primeira vista, isto parece muito misterioso. Como você pode reduzir o número de bits e bytes e então poder recompor esses bits e bytes? Mas, a idéia básica atrás do processo é bastante direta. Nesta edição, examinaremos este método simples de como lidamos com arquivos no processo básico de compressão.

Slide 2: Compressão de arquivos Descobrindo redundâncias As maiorias dos tipos de arquivos são bastante redundantes, eles têm a mesma informação listada inúmeras vezes. Os programas de compressão simplesmente eliminam as redundâncias. Em vez de listar um pedaço de informação inúmeras vezes, o programa de compressão lista a informação somente uma vez e então e se refere a ela sempre que a mesma aparece no programa original. Como exemplo, olhemos um tipo de informação nós estamos todos familiarizados com as palavras de John F. Kennedy em 1961 na sua posse, fez sua famosa declaração: " Ask not what your country can do for you, ask what you can do for your country." (Não pergunte o que seu país pode fazer para você--pergunte o que você pode fazer pelo seu país).

Slide 3: Compressão de arquivos A citação tem 17 palavras, compostas de 61 letras, 16 espaços, uma virgula e um período. Se cada letra, espaço ou pontuação ocupa uma unidade de memória, nós obtemos um arquivo do tamanho total de 79 unidades. Para baixar o tamanho do arquivo, nós precisamos procurar redundâncias. Imediatamente nós notamos: Ask: aparece duas vezes What: aparece duas vezes Your: aparece duas vezes Country: aparece duas vezes Can: aparece duas vezes Do: aparece duas vezes For: aparece duas vezes You: aparece duas vezes

Slide 4: Compressão de arquivos Ignorando a diferença entre letras maiúsculas e minúsculas, certamente metade da frase é redundante. Nove palavras, ask, not, what, your, country, can, do for, you, nos dá quase tudo que precisamos para a citação inteira. Para construir a segunda metade da frase, nós apenas apontamos para as palavras da primeira metade, e preenchemos os espaços e a pontuação. Na próxima seção, veremos como os sistemas de compressão realizam isto. Olhando o dicionário O esquema básico da maioria programas de compressão estão baseado no LZ algoritmo dicionário baseado adaptável. LZ se refere a Lempel e Ziv, os criadores do algoritmo, e do dicionário a que se refere o método de catalogar bits de dados. O sistema de organização de dicionários varia, mas poderia ser tão simples quanto uma lista numerada. Quando nós passamos pelas famosas palavras de Kennedy, nós escolhemos as palavras repetidas, e as colocamos em um índice numerado. Então, escrevemos o número, em vez de escrever a palavra inteira.

Slide 5: Compressão de arquivos Assim seria nosso dicionário: 1. ASK 2. WHAT 3. YOUR 4. COUNTRY 5. CAN 6. DO 7. FOR 8. YOU Nossa oração seria lida como: “1 not 2 3 4 5 6 7 8; 1 2 8 5 6 7 3 4”. Se conhecêssemos o sistema, poderíamos reconstruir a frase original usa apenas este dicionário e numero padrão. Isto é o que o programa de expansão do seu computador faz quando expande um arquivo carregado.

Slide 6: Compressão de arquivos Você também poderia ter encontrado arquivos comprimidos que se expendem automaticamente. Para criar este tipo de arquivo, o programador inclui um programa de expansão simples com o arquivo comprimido. Ele automaticamente reagrupa o arquivo original à medida que é baixado. Mas quanto espaço realmente economizamos com este sistema? “1 not 2 3 4 5 6 7 8 --1 2 8 5 6 7 3 4 é certamente menor que” Ask not what your country can do for you -- ask what you can do for your country “; mas lembre-se de que nós precisamos economizar o próprio dicionário junto com o arquivo”. Nos esquemas de compressão atuais, seria complicado entender as várias exigências do arquivo razoavelmente; mas para nossos propósitos, voltemos para a idéia que todo caracter e todo espaço ocupado uma unidade de memória. Nós já vimos que a frase inteira tem 79 unidades. Nossa oração comprimida (inclusive espaços) temos 37 unidades, e o dicionário (palavras e números) também tem 37 unidades. Isto nos dá um tamanho de arquivo de 74, assim nós não reduzimos o tamanho de arquivo o bastante.

Slide 7: Compressão de arquivos Mas esta é só uma oração. Você pode imaginar que se o programa de compressão trabalhasse pelo resto do discurso de Kennedy, acharia estas palavras e muitas outras repetidas mais vezes. E, como nós veremos na próxima seção, também estaria ré-escrevendo o dicionário para obter a organização mais eficiente possível Procurando padrões Em nosso exemplo, nós escolhemos todas as palavras repetidas e as pusemos em um dicionário. Para nós, este é o modo mais óbvio para escrever um dicionário. Mas um programa de compressão vê isto diferentemente: Não tem qualquer conceito de palavras separadas, só procura padrões. E para reduzir o tamanho do arquivo ao máximo possível, seleciona cuidadosamente quais padrões a serem incluídos no dicionário. Se nós supusermos a frase sob esta perspectiva, nós terminamos com um dicionário completamente diferente.

Slide 8: Compressão de arquivos Se o programa de compressão esquadrinhasse a frase de Kennedy, a primeira redundância que encontraria seria apenas um par de letras. Em “ask not what your", há um padrão repetido da letra "t" seguida por um espaço, em “not" e “what". Se o programa de compressão incluísse isto no dicionário, poderia escrever um 1 toda vez que “t" venha seguido de um espaço. Mas nesta frase pequena, este padrão não acontece o bastante para fazer isto uma entrada que valha a pena, assim o programa re-escreveria isto. A próxima coisa que o programa poderia notar é "ou" qual aparece ambos “your" e "country". Se este fosse um documento mais longo e se escrevessemos este padrão no dicionário poderíamos economizar muito espaço, é uma combinação bastante comum no idioma inglês. Mas como o programa de compressão trabalhou nestas orações, rapidamente descobriria uma escolha melhor para uma entrada de dicionário: Não é só é o "ou" repetido, mas as palavras “your” e “country” são ambas repetidas, e elas são repetidos em conjunto, como na frase “your country". Neste caso o programa escreveria elaboradamente a entrada do dicionário para “ou” com a entrada para “your country".

Slide 9: Compressão de arquivos A frase "can do for" também é repetida, uma vez seguida por “your” e uma vez seguida por “you" nos fornecendo o padrão "can do for you". Isto nos deixa escrever 15 caracteres (inclusive espaços) como um valor numérico, enquanto “your country" só nos deixa escrever 13 caracteres (com espaços), assim o programa escreveria elaboradamente a entrada “r country”, e escreveria uma entrada separada para "can do for you". O programa procede deste modo, capturando todos os pedaços de informações repetidas e calculando então quais padrões deverá escrever no dicionário. Esta habilidade para rescrever o dicionário é a parte adaptável do algoritmo dicionário-baseado adaptável LZ. O modo pelo qual um programa faz isto é bastante complicado, como você pode ver pelas discussões.

Slide 10: Compressão de arquivos Não importa que método específico você usa, este sistema de procura deixa comprimir o arquivo muito mais eficazmente do que você pode ao escolher palavras. Usando os padrões acima, e somando __ para os espaços, nós propomos este dicionário maior: 9. Ask__ 10. What__ 11. You__ 12. For__country 13. __Can__do__for__you E esta é oração menor: " 1 not__2345--12354 ". A oração usa 16 unidades de memória agora, e nosso dicionário contem 41 unidades. Assim nós comprimimos o tamanho de arquivo total de 79 unidades para 57 unidades. Esta é uma das maneiras de comprimir a frase, e não necessariamente a mais eficiente. (Veja se você pode achar um modo melhor!)

Slide 11: Compressão de arquivos Na próxima seção, nós veremos alguns das maneiras na qual a porcentagem de compressão poderia variar. Quanto pode você pode comprimir? Quão bom este sistema é? A relação de redução de arquivo depende de vários fatores, inclusive do tipo de arquivo, tamanho de arquivo e esquema de compressão. Na maioria dos idiomas do mundo, certas letras e palavras freqüentemente aparecem juntas e no mesmo padrão. Por causa desta taxa alta de redundância, arquivos textos são bem comprimidos. Uma redução de 50 % ou mais é típica para um arquivo texto de bom tamanho. A maioria da linguagens de programação também são muito redundantes porque usam uma coleção relativamente pequena de comandos que freqüentemente entram junto em um padrão fixo. Arquivos que incluem informações únicas, como gráficos ou MP3, não podem ser muito bem comprimidos, pois eles não repetem muitos padrões.

Slide 12: Compressão de arquivos Se um arquivo tem muitos padrões repetidos, a taxa de redução aumenta com tamanho de arquivo. Você só pode ver isto olhando nosso exemplo, se nós tivéssemos mais da fala de Kennedy, nós poderíamos nos referir mais freqüentemente aos padrões do nosso dicionário, e assim mais espaço do arquivo a cada entrada. Também, padrões mais penetrantes poderiam emergir em tarefas mais longas e poderia nos permitir criar um dicionário mais eficiente. Esta eficiência também depende do algoritmo específico usado pelo programa de compressão. Alguns programas são investidos particularmente em capturar padrões em certos tipos de arquivos, e assim pode comprimi0los mais sucintamente. Outros têm dicionários dentro de dicionários que poderiam comprimir eficazmente arquivos maiores, mas não menores. Enquanto todo programa de compressão trabalhe com a mesma idéia básica, há bastante variações na maneira de execução. Programadores sempre estão tentando para construir um sistema melhor.

Slide 13: Compressão de arquivos Lossy e Lossless O tipo de compressão aqui discutido é chamado compressão de lossless, porque lhe deixa recriar exatamente o arquivo original. Toda a compressão lossless está baseado na idéia de quebrar um arquivo em uma "forma menor" para transmissão ou armazenamento e recupera-lo na outra ponta, assim podendo ser usado novamente. Compressão Lossy trabalha muito diferentemente. Estes programas simplesmente eliminam "pedaços desnecessários" de informação e organizando o arquivo de forma que se torne menor. Este tipo de compressão é muito usado para reduzir o tamanho dos arquivo de figuras bitmap que tendem a ser bastante vultosos. Veja como isto funciona, consideremos que seu computador poderia comprimir uma fotografia. Um programa de compressão lossless não pode fazer muito com estes arquivos.

Slide 14: Compressão de arquivos Lossy e Lossles Enquanto partes grandes das figuras parecem ser as mesmas, o céu inteiro é azul, por exemplo, a maioria do pixels individuais são um pouco diferentes. Fazer este quadro menor, sem assumir compromisso a resolução, você com certeza tem que mudar o valor da cor para certos pixels. Se a figura tivesse ainda muito azul no céu, o programa escolheria um tipo de cor azul que poderia ser usada para todo os pixels. Então, o programa rescreve o arquivo de forma que o valor de todos os pixels do céu se refira a esta informação anterior. Se o esquema de compressão funcionar bem, você não notará a mudança, mas o tamanho do arquivo será reduzido significativamente. Claro que, você não pode voltar o arquivo original depois de comprimido. Você está preso a uma re-interpretação do programa de compressão ao arquivo original. Por isto, você não pode usar este tipo de compressão para qualquer coisa que precisar ser reproduzida, inclusive aplicações de software, bancos de dados e discursos presidenciais.