Compression · Compressão
| English | Português |
|---|---|
| compression/kəmˈpreʃn/ | compressão |
| lossless/ˈlɒsləs/ | sem perda |
| lossy/ˈlɒsi/ | com perda |
| bandwidth/ˈbændwɪdθ/ | largura de banda |
| run-length encoding/rʌn leŋθ enˈkəʊdɪŋ/ | codificação por comprimento de corrida |
| dictionary coding/ˈdɪkʃənəri ˈkəʊdɪŋ/ | codificação dicionário |
| Huffman coding/ˈhʌfmən ˈkəʊdɪŋ/ | código Huffman |
| spatial/ˈspeɪʃl/ | espacial |
| temporal/ˈtempərəl/ | temporal |
The three letters that made the web possible
- In 1987 a programmer named Phil Katz wrote a compression program and put the file format in the public domain. He called it ZIP. He was 24.
- Nothing about the web works without that idea. A single uncompressed second of HD video is about 187 MB; a two-hour film would be 1.3 terabytes. Streaming it over a home connection is arithmetically impossible.
- The films you watch are perhaps a thousandth of that, and they still look right, because the compression throws away things your eye was never going to notice.
- This lesson is compression 压缩: the two families, the three lossless methods, and how to justify one for a given file.
As três letras que tornaram a web possível
- Em 1987, um programador chamado Phil Katz escreveu um programa de compressão e colocou o formato de arquivo em domínio público. Ele o chamou ZIP. Ele tinha 24 anos.
- Nada sobre a web funciona sem essa ideia. Um único segundo de vídeo HD não comprimido tem aproximadamente 187 MB; um filme de duas horas teria 1.3 terabytes. Transmiti-lo por uma conexão residencial é aritmeticamente impossível.
- Os filmes que você assistem talvez sejam um milésimo disso, e ainda parecem corretos, porque a compressão descarta coisas que seus olhos nunca notariam.
- Esta lição é compressão 压缩: as duas famílias, os três métodos sem perdas, e como justificar um para um arquivo dado.
Lossless and lossy
- Compression reduces a file's size, saving storage space and transmission bandwidth 带宽, and making downloads and streams faster.
- Lossless 无损 compression is compression from which the original data can be recovered exactly. ZIP and PNG are lossless.
- Lossy 有损 compression permanently removes some data, so the original cannot be recovered. JPEG, MP3 and streamed video are lossy.
Recover exactly, or shrink much further
Sem perdas e com perdas
- Compressão reduz o tamanho de um arquivo, economizando espaço de armazenamento e largura de banda 带宽 de transmissão, e tornando downloads e transmissões mais rápidos.
- Compressão sem perdas 无损 compression é aquela da qual os dados originais podem ser recuperados exatamente. ZIP e PNG são sem perdas.
- Compressão com perdas 有损 compression remove permanentemente alguns dados, então o original não pode ser recuperado. JPEG, MP3 e vídeo transmitido são com perdas.
Recupere exatamente, ou encolha muito mais
Lossless compression means: · Compressão sem perda significa:
Lossless compression lets you rebuild the original data exactly — essential for text, programs and ZIP/PNG. · A compressão sem perda permite reconstruir os dados originais exatamente — essencial para texto, programas e ZIP/PNG.
Match each compression idea to what it means. · Combine cada ideia de compressão com o que ela significa.
Lossless keeps every bit (needed for text/code); lossy trades quality for size (photos, audio). · Sem perda mantém todos os bits (necessário para texto/código); com perda troca qualidade por tamanho (fotos, áudio).
Lossless compression rebuilds the original data exactly (needed for text and programs), while lossy compression permanently removes some data to shrink the file (used for photos and audio). · A compressão sem perda reconstrói os dados originais exatamente (necessário para texto e programas), enquanto a compressão com perda remove permanentemente alguns dados para encolher o arquivo (usada para fotos e áudio).
That is why a program or a ZIP must be lossless, but a photo or a song can use lossy compression. · É por isso que um programa ou um ZIP deve ser sem perda, mas uma foto ou uma música pode usar compressão com perda.
Worked example: justify the choice
- A company archives its accounting spreadsheets. Which kind of compression, and why? Lossless, because the spreadsheet must be restored exactly; a single changed value would make the accounts wrong.
- A photographer uploads holiday photographs to a phone gallery. Lossy, because the photographs are viewed on a small screen where the dropped detail is not visible, and the smaller files upload faster and use less storage.
- Name the kind, then give the reason from the situation. "Lossy is smaller" on its own is not a justification.
Exemplo resolvido: justificar a escolha
- Uma empresa arquivaba suas planilhas contábeis. Que tipo de compressão, e por quê? Sem perdas, porque a planilha deve ser restaurada exatamente; um único valor alterado tornaria as contas erradas.
- Um fotógrafo faz upload de fotos de férias para uma galeria de celular. Com perdas, porque as fotos são visualizadas em uma tela pequena onde os detalhes perdidos não são visíveis, e os arquivos menores fazem upload mais rápido e usam menos armazenamento.
- Nomeie o tipo, depois dê a razão da situação. "Com perdas é menor" sozinho não é uma justificativa.
Which file should be compressed losslessly? · Qual arquivo deve ser comprimido sem perda?
Source code must be recovered exactly — a single changed character could break it — so it needs lossless compression. · O código-fonte deve ser recuperado exatamente — um único caractere alterado poderia quebrá-lo —, então precisa de compressão sem perda.
Run-length encoding
- Run-length encoding 行程编码 (RLE) replaces a run of repeated values with one value and a count: instead of eight identical white pixels, store "8, white".
- It is excellent on data with long runs, such as icons, diagrams, black-and-white scans and areas of flat colour.
- It is useless, and can make a file larger, on noisy data such as a photograph, where almost no two neighbouring values are equal.
Each row becomes counts and colours
Codificação run-length
- Codificação run-length 行程编码 (RLE) substitui uma sequência de valores repetidos por um valor e uma contagem: em vez de oito pixels brancos idênticos, armazene "8, branco".
- É excelente em dados com longas sequências, como ícones, diagramas, varreduras preto-e-branco e áreas de cor plana.
- É inútil, e pode tornar um arquivo maior, em dados ruidosos como uma fotografia, onde quase nenhum par de valores vizinhos é igual.
Cada linha torna-se contagens e cores
Run-length encoding works best on data that has: · A codificação por comprimento de corrida funciona melhor em dados que têm:
RLE replaces a run of identical values with a count + value, so it shines on flat areas and is useless on noisy data. · RLE substitui uma sequência de valores idênticos por uma contagem + valor, então brilha em áreas planas e é inútil em dados ruidosos.
Worked example: encode a row with RLE
- A row of an 8-pixel black-and-white image reads: white white white black black white white white. Encode it with RLE.
- Three white, two black, three white, so
3W 2B 3W, or as pairs,(3, 0) (2, 1) (3, 0)if white is 0. - Eight values became three pairs. Now encode
W B W B W B W B. Eight runs of one:1W 1B 1W 1B 1W 1B 1W 1B, which stores more than the original. That is exactly why RLE is not used on photographs.
Exemplo resolvido: codifique uma linha com RLE
- Uma linha de uma imagem preto-e-branco de 8 pixels lê: branco branco branco preto preto branco branco branco. Codifique-a com RLE.
- Três brancos, dois pretos, três brancos, então
3W 2B 3W, ou como pares,(3, 0) (2, 1) (3, 0)se branco for 0. - Oito valores tornaram-se três pares. Agora codifique
W B W B W B W B. Oito sequências de um:1W 1B 1W 1B 1W 1B 1W 1B, que armazena mais que o original. É exatamente por isso que RLE não é usado em fotografias.
Run-length encoding (a lossless method) · Codificação por comprimento de corrida (método sem perda)
Run-length encoding replaces a run of repeated values with one value plus a count. It is lossless — the original rebuilds exactly — but only shrinks data that has long runs. · A codificação por comprimento de corrida substitui uma sequência de valores repetidos por um valor mais uma contagem. É sem perda — os originais são reconstruídos exatamente —, mas só encolhe dados que tenham longas sequências.
Encode the pixel row W W W B B W W W with run-length encoding, using the form 3W 2B 3W. · Codifique a linha de pixels W W W B B W W W usando codificação por comprimento de corrida, usando a forma 3W 2B 3W.
Three white, two black, three white. Eight values become three pairs, but an alternating row would become eight pairs and grow. · Três brancos, dois pretos, três brancos. Oito valores tornam-se três pares, mas uma linha alternada tornaria-se oito pares e aumentaria.
Run-length encoding always makes a file smaller. · A codificação por comprimento de corrida sempre torna um arquivo menor.
On data with no runs, such as a photograph or an alternating pattern, every run has length one and the encoding stores more than the original. · Em dados sem sequências, como uma fotografia ou um padrão alternado, cada sequência tem comprimento um e a codificação armazena mais do que o original.
Dictionary coding and Huffman coding
- Dictionary coding 字典编码, used by ZIP and PNG, builds a dictionary of repeated byte sequences and replaces each occurrence with a short index. It suits text and program code, where words and patterns recur.
- Huffman coding 霍夫曼编码 gives short codes to common symbols and long codes to rare ones, so the average code length falls. In "BANANA" the A is commonest and gets the shortest code.
- Both are lossless: the decoder rebuilds the original byte for byte.
Codificação dicionário e codificação Huffman
- Codificação dicionário 字典编码, usada por ZIP e PNG, constrói um dicionário de sequências de bytes repetidas e substitui cada ocorrência por um índice curto. Adequa-se a texto e código de programas, onde palavras e padrões se repetem.
- Codificação Huffman 霍夫曼编码 dá códigos curtos para símbolos comuns e códigos longos para raros, então o comprimento médio do código cai. Em "BANANA", o A é o mais comum e recebe o código mais curto.
- Ambos são sem perdas: o decodificador reconstrói o byte original por byte.
Huffman coding reduces size by: · Código Huffman reduz o tamanho por:
Huffman assigns the shortest codes to the most frequent symbols, lowering the average code length. · Huffman atribui os códigos mais curtos aos símbolos mais frequentes, reduzindo o comprimento médio do código.
Match each lossless method to how it works. · Combine cada método sem perda com como ele funciona.
All three are lossless: the decoder rebuilds the original byte for byte. · Todos os três são sem perda: o decodificador reconstrói o byte original byte por byte.
Lossy methods
- Images (JPEG): fine detail and colour differences the eye barely notices are dropped.
- Sound (MP3, AAC): pitches we hear poorly are removed, along with quiet sounds masked by louder ones at the same moment.
- Video: spatial 空间 compression works within each frame, like JPEG, and temporal 时间 compression stores most frames as only the differences from the previous frame, since consecutive frames are nearly identical.
Métodos com perdas
- Imagens (JPEG): detalhes finos e diferenças de cor que o olho mal percebe são descartados.
- Som (MP3, AAC): tons que ouvimos mal são removidos, junto com sons quietos mascarados por sons mais altos no mesmo momento.
- Vídeo: compressão espacial 空间 funciona dentro de cada quadro, como JPEG, e compressão temporal 时间 armazena a maioria dos quadros apenas como as diferenças do quadro anterior, já que quadros consecutivos são quase idênticos.
Temporal compression of video works by: · A compressão temporal de vídeo funciona por:
Temporal compression stores how each frame differs from the one before, since most of the picture stays the same between frames. (Spatial compression handles within-frame detail.) · A compressão temporal armazena como cada quadro difere do anterior, já que a maior parte da imagem permanece igual entre quadros. (A compressão espacial lida com detalhes dentro do quadro.)
Worked example: how each kind of file is compressed
- Text file: dictionary and Huffman coding turn repeated words and common characters into short codes. It must stay lossless, because one changed character changes the meaning.
- Bitmap image: RLE for runs of identical pixels in icons and diagrams; lossy JPEG for photographs; or reduce the colour depth or resolution, which is also lossy.
- Vector graphic: the drawing list is already small. Remove drawing objects that are not needed, store coordinates to fewer decimal places, or apply a lossless method such as ZIP to the file.
- Sound file: lossy MP3 or AAC removes what the ear cannot hear; lowering the sampling rate or resolution is also lossy; lossless formats keep every sample and shrink much less.
Exemplo resolvido: como cada tipo de arquivo é comprimido
- Arquivo de texto: codificação dicionário e Huffman transformam palavras repetidas e caracteres comuns em códigos curtos. Deve permanecer sem perdas, porque um caractere alterado muda o significado.
- Imagen bitmap: RLE para sequências de pixels idênticos em ícones e diagramas; JPEG com perdas para fotografias; ou reduzir a profundidade de cor ou resolução, que também é com perdas.
- Gráfico vetorial: a lista de desenho já é pequena. Remova objetos de desenho desnecessários, armazene coordenadas com menos casas decimais, ou aplique um método sem perdas como ZIP ao arquivo.
- Arquivo de som: MP3 ou AAC com perdas remove o que o ouvido não consegue ouvir; baixar a taxa ou resolução também é com perdas; formatos sem perdas mantêm cada amostra e encolhem muito menos.
How can a vector graphic file be made smaller? Select all · todos that apply. · Como um arquivo de gráfico vetorial pode ser reduzido? Selecione todas as opções aplicáveis.
A vector file is a drawing list, not pixels, so it has no colour depth. Colour depth belongs to bitmaps. · Um arquivo vetorial é uma lista de desenhos, não de pixels, então não tem profundidade de cor. Profundidade de cor pertence a bitmaps.
Why streaming must be lossy
- Raw HD video is gigabytes per minute, and a home connection carries a few megabits per second.
- Lossless compression on video achieves perhaps a factor of two, nowhere near enough, so the picture would keep stopping to buffer.
- Lossy compression achieves a factor of a hundred or more by discarding detail the viewer does not notice at normal speed. The reason names the bandwidth and the data rate, not just "it is smaller".
Por que streaming deve ser com perdas
- Vídeo HD cru são gigabytes por minuto, e uma conexão doméstica carrega alguns megabits por segundo.
- Compressão sem perdas em vídeo alcança talvez um fator de dois, longe o suficiente, então a imagem continuaria travando para fazer buffer.
- Compressão com perdas alcança um fator de cem ou mais descartando detalhes que o espectador não nota em velocidade normal. A razão nomeia a largura de banda e a taxa de dados, não apenas "é menor".
Why does real-time video streaming use lossy compression? · Por que o streaming de vídeo em tempo real usa compressão com perda?
Raw HD video is gigabytes per minute; only lossy compression shrinks it enough to stream in real time without freezing. · Vídeo HD cruso é gigabytes por minuto; apenas a compressão com perda o encolhe o suficiente para fazer streaming em tempo real sem travamentos.
Marks that slip away
- Lossless means the original is recovered exactly; lossy means it cannot be. "Lossy loses quality" misses the point that the data is gone for good.
- RLE can make a noisy file larger. Say where it works and where it does not.
- Video compression is spatial and temporal; temporal stores the differences between frames.
- A "justify" answer ties the method to the file's use: exactness for accounts and medical images, size for streaming and phone galleries.
Marcas que escapam
- Sem perdas significa que o original é recuperado exatamente; com perdas significa que ele não pode ser. "Com perdas perde qualidade" perde o ponto de que os dados estão perdidos para sempre.
- A codificação RLE pode tornar um arquivo ruidoso maior. Indique onde ela funciona e onde não funciona.
- A compressão de vídeo é espacial e temporal; a temporal armazena as diferenças entre os frames.
- Uma resposta "justificativa" vincula o método ao uso do arquivo: exatidão para contas e imagens médicas, tamanho para streaming e galerias de celular.
You've got it
- compression saves storage and bandwidth; lossless recovers the original exactly, lossy removes data permanently
- lossless methods: RLE (a value and a count, good on runs, bad on noise), dictionary coding (repeated sequences to short indices), Huffman coding (short codes for common symbols)
- lossy methods drop what the eye or ear misses; video adds spatial within a frame and temporal between frames
- justify from the use: exact data means lossless, limited bandwidth for streaming means lossy
Entendeu?
- A compressão economiza armazenamento e largura de banda; o lossless recupera o original exatamente, o lossy remove dados permanentemente
- Métodos lossless: RLE (um valor e uma contagem, bom em sequências, ruim em ruído), codificação por dicionário (sequências repetidas para índices curtos), codificação Huffman (códigos curtos para símbolos comuns)
- Métodos lossy descartam o que o olho ou ouvido não percebe; o vídeo adiciona espacial dentro de um frame e temporal entre frames
- Justifique pelo uso: dados exatos significam lossless, largura de banda limitada para streaming significa lossy