Compressão em Big Data: Tipos e Técnicas

\

Introdução

Este artigo irá discutir a compressão no contexto de Big Data, abordando os tipos e métodos de compressão. Também destacarei por que e quando cada tipo e método deve ser usado.

\

O que é compressão?

De acordo com a definição geral em inglês de compressão, refere-se a reduzir algo para ocupar um espaço menor. Em Ciência da Computação, compressão é o processo de reduzir dados para um tamanho menor. Dados, neste caso, podem ser representados em texto, ficheiros de áudio, vídeo, etc. Pense nisso como qualquer coisa que armazene no disco rígido do seu computador, como dados representados em diferentes formatos. Para fornecer uma definição mais técnica, compressão é o processo de codificar dados para usar menos bits.

\ Existem múltiplas razões para comprimir dados. A razão mais comum e intuitiva é poupar espaço de armazenamento. Outras razões são resultado dos dados serem menores. Os benefícios de trabalhar com dados menores incluem:

1. Tempo de transmissão de dados mais rápido: Os dados comprimidos são menores em tamanho e levam menos tempo a ser transmitidos da fonte ao destino.
2. Consumo reduzido de largura de banda: Esta razão está fortemente ligada à vantagem de transmissão de dados mais rápida. Os dados comprimidos usam menos largura de banda da rede, aumentando assim o débito e reduzindo a latência.
3. Desempenho melhorado para sistemas digitais que dependem fortemente de dados: Isto é evidente em sistemas que dependem do processamento de dados. Esses sistemas aproveitam a compressão para melhorar o desempenho dos sistemas ao reduzir o volume de dados que precisam ser processados. Note que isto pode ser específico do sistema e dependerá do uso da técnica de compressão apropriada. As técnicas de compressão serão discutidas mais tarde neste artigo.
4. Eficiência de custos: Os serviços em nuvem cobram pelo armazenamento de dados. Ao usar menos armazenamento, são introduzidas poupanças de custos, especialmente em sistemas de Big Data.

\ Outras razões para compressão dependem de diferentes técnicas e formatos de compressão. Alguns algoritmos de encriptação podem ser usados como método de compressão. Ao fazê-lo, inclui uma camada de segurança para as razões discutidas anteriormente para comprimir dados. Além disso, usar formatos de compressão comuns traz compatibilidade e espaço para extensibilidade a sistemas externos para fins de integração.

\ Vale a pena notar que as razões para compressão também soam como benefícios. No entanto, a compressão não é sem compromissos. Um compromisso comum à compressão é a necessidade de descompressão, o que pode ser preocupante para sistemas com recursos limitados. Outros compromissos dependem da técnica de compressão e tipo de dados usados.

\

Tipos de compressão

Para discutir as diferentes técnicas usadas para comprimir dados, primeiro categorizarei a compressão em 2 categorias principais. Este artigo discutirá então as técnicas relevantes para cada categoria. A compressão pode ser amplamente agrupada em compressão com perdas e sem perdas.

\ Como os nomes já revelam o que significam, técnicas de compressão com perdas são técnicas que não preservam a fidelidade completa dos dados. Simplificando, alguns dados são descartados, mas não o suficiente para tornar o que os dados representam irreconhecível. Portanto, a compressão com perdas pode oferecer um nível muito alto de compressão comparado à compressão sem perdas, que será introduzida em breve.

\ Uma característica da compressão com perdas é que é irreversível, ou seja, quando apresentado com o ficheiro comprimido, não se pode restaurar os dados brutos com sua fidelidade original. Certos ficheiros e formatos de ficheiro são adequados para compressão com perdas. É tipicamente usado para imagens, áudio e vídeos. Por exemplo, imagens formatadas em JPEG prestam-se bem à compressão, e ao comprimir uma imagem JPEG, o criador ou editor pode escolher quanta perda introduzir.

\ Por outro lado, compressão sem perdas é reversível, o que significa que quando comprimida, todos os dados são preservados e restaurados totalmente durante a descompressão. Isto implica que a compressão sem perdas é adequada para ficheiros tipo texto, e no mundo de armazém de dados e lakehouse, seria o único tipo relevante a usar. Alguns formatos de ficheiros de áudio (FLAC e ALAC) e imagem (GIF, PNG, etc.) funcionam bem com este tipo de compressão.

Escolher um método

Não existe um melhor método de compressão geral. Diferentes fatores entram na escolha de qual método seria adequado caso a caso. Para reforçar isto com exemplos, um engenheiro de dados na indústria financeira trabalhando em dados tabulares armazenados tenderia a usar compressão sem perdas devido ao impacto de dados em falta na criação de relatórios precisos. Alternativamente, a compressão com perdas poderia ser o caminho a seguir na otimização da página web com muitas imagens ao comprimir as imagens e reduzir os itens de carregamento tornando o website mais leve. Portanto, é crucial conduzir uma avaliação para determinar o método de compressão mais apropriado que se alinha com os requisitos do negócio.

Técnicas de compressão

Esta secção cobrirá apenas as técnicas de compressão comuns para compressão com e sem perdas. Note que isto não é de forma alguma exaustivo. Além disso, as técnicas discutidas podem ter ligeiras variações para melhorar seu desempenho, conforme apoiado por diferentes pesquisas.

Técnicas de compressão sem perdas

Três técnicas comuns sem perdas são a codificação Run-Length (RLE), codificação Huffman e as técnicas Lempel-Ziv-Welch.

\ Codificação Run-Length: RLE baseia-se em codificar dados, de tal forma que substitui sequências de dados repetidos por uma única peça de dados e a contagem dessa peça de dados. É eficaz para longas execuções de dados repetidos. Além disso, conjuntos de dados que têm dimensões (campos) que estão ordenados de um nível baixo para um nível alto de cardinalidade beneficiam de RLE.

\ Por exemplo, tome uma string simples como AAAAABBCDDD. RLE comprime os dados para se tornar A(5)B(2)C(1)D(3). Para ser mais prático, tome uma tabela na imagem abaixo.

\ Figura 1 - antes de RLE. É importante observar que o nível de cardinalidade está a aumentar nos campos da esquerda para a direita

Figura 2 - Após RLE

Como RLE depende de execuções de campos repetidos, e no segundo exemplo, a cardinalidade e a ordem de classificação dos dados, o registo Mouse na coluna item não pode ser comprimido para apenas Mouse (3) porque a coluna anterior divide todos os valores em IT, Mouse e HR, Mouse. Certos formatos de ficheiro são compatíveis com RLE, como formatos de ficheiro bitmap como TIFF, BMP, etc. Os ficheiros Parquet também suportam RLE, tornando-o muito útil em lakehouses de dados modernos usando armazenamento de objetos como S3 ou GCS.

\ Codificação Huffman: Baseia-se em modelagem estatística que atribui códigos de comprimento variável a valores nos dados brutos com base na frequência com que ocorrem nos dados brutos. A representação desta modelagem pode ser referida como uma árvore Huffman, que é semelhante a uma árvore binária. Esta árvore é então usada para criar um código Huffman para cada valor nos dados brutos. O algoritmo prioriza codificar os valores mais frequentes no menor número possível de bits.

\ Vamos pegar os mesmos dados usados no exemplo RLE AAAAABBCDDD. A árvore Huffman correspondente parece assim.

\ Árvore Huffman

Da árvore, podemos ver que a letra A é representada por 0 da mesma forma D é apresentado por 10. Comparado com as letras B: 111 e C:110, observamos que A e D são representados por menos bits. Isto é porque têm uma frequência maior; portanto, o algoritmo Huffman representa-os com menos bits por design. Os dados comprimidos resultantes tornam-se 00000111111110101010.

\ A codificação Huffman usa a regra de prefixo, que afirma que o código que representa um caractere não deve estar presente no prefixo de qualquer outro código. Por exemplo, um código Huffman válido não pode ter as letras c e d representadas usando C: 00 e D: 000 porque a representação de C é um prefixo de D.

\ Para ver isto em ação, o Computer Science Field Guide tem um Gerador de Árvore Huffman com o qual pode brincar.

\ Codificação Lempel–Ziv–Welch: Foi criada por Abraham Lempel, Jacob Ziv e Terry Welch em 1984 e tem o nome dos criadores, obviamente 😅. Semelhante ao RLE e codificação Huffman, LZW funciona bem com dados que contêm muitos dados repetidos. O algoritmo LZW é baseado em dicionário e cria um dicionário contendo pares chave-valor de padrões comumente vistos nos dados brutos. Tal dicionário também pode ser referido como a tabela de código. Usando uma ilustração para explicar como esta técnica funciona, vamos considerar que nossos dados brutos sejam representados por ABBABABABA. Quando passado pelo algoritmo usando uma configuração de A-Z como valores possíveis, a tabela de código resultante parece:

\ Tabela de código LZW

Da tabela de código acima, há um par chave-valor para todas as letras A-Z e pares chave-valor para padrões como AB, BB, BA e ABA. Ao ter uma representação mais curta destes padrões, o algoritmo LZW pode comprimir os dados brutos codificando-os em menos bits. Portanto, usando a tabela de código gerada a partir dessa entrada, a versão comprimida é 0 1 1 26 29 28. É fundamental notar os espaços nos dados comprimidos. Pode-se pensar neles como o fim de um caractere, para que o decodificador não interprete um 1,0 como um 10 já que significam coisas diferentes.

\ LZW é geralmente de uso geral e amplamente usado hoje. Está integrado em muitos sistemas operativos baseados em Unix/Linux por trás do comando shell compress. Além disso, formatos de ficheiro comuns compatíveis com LZW são GIF, TIFF e PDF. Outras aplicações de compressão LZW podem ser vistas no campo de Processamento de Linguagem Natural, conforme discutido neste artigo sobre tokenização em NLP.

\ RLE, codificação Huffman e codificação LZW são apenas exemplos comuns. As técnicas de compressão sem perdas vão além destas três (3) descritas acima. Outras técnicas incluem DEFLATE, que usa uma combinação de codificação Huffman e LZW - especificamente LZ77.

Técnicas de compressão com perdas

Nesta secção, veremos dois tipos de compressão com perdas. Lembre-se de que a compressão com perdas introduz uma perda nos dados originais, o que significa que nem todos os dados são mantidos.

\ Transformada Discreta de Cosseno (DCT): Este método de compressão é usado principalmente em ficheiros de áudio, imagem e vídeo e também é comumente referido como compressão de blocos. Usa uma função matemática - a função cosseno, como o nome indica - para converter blocos dos dados originais em frequências. Os blocos de dados são geralmente uma matriz de 8x8, 4x4, e assim por diante, nessa ordem de magnitude.

\ A compressão entra ao lidar com as altas frequências que ocorrem nos dados, uma vez que os dados brutos são traduzidos para o domínio da frequência usando a função matemática. O processo geral de usar DCT para compressão é:

• Dividir dados brutos em pedaços. Por exemplo, na compressão de imagem, isto poderia ser 8x8 pixels.
• Aplicar a função matemática para converter os pedaços de dados em frequências. Isto resultará em algumas frequências altas e frequências baixas.
• As frequências altas são então reduzidas ou removidas dependendo do grau aceitável de perda que se está disposto a introduzir. É aqui que realmente se torna compressão com perdas.
• Para converter de volta em dados representáveis, todas as frequências restantes são passadas por uma Transformada Discreta de Cosseno Inversa - IDCT - para restaurar os dados a partir das frequências.

\ DCT é amplamente usado em diferentes campos hoje, não apenas em compressão mas também em processamento de sinal. Formatos de ficheiro comuns compatíveis com DCT são JPEG (imagens), MP3 (áudio) e MPEG (vídeo). Além disso, DCT pode alcançar altas taxas de compressão, tornando-o adequado para sistemas digitais com muitas imagens, como páginas web na Internet.

\ Compressão fractal: Um fractal é um padrão infinito auto-repetitivo que se repete em diferentes escalas. Quando visto de qualquer ponto na escala, o padrão parece semelhante. Como os padrões são semelhantes em qualquer escala, a compressão fractal reduz a escala de fractais 'grandes' para reduzir o tamanho dos dados.

\ Exemplos de fractais

A compressão fractal foi introduzida por Michael Barnsley nos anos 1980. A ideia geral usando uma imagem é que se uma imagem contém várias partes que parecem iguais, por que armazená-las duas vezes? Para fazer isto, a compressão fractal faz o seguinte:

• Particiona a imagem em blocos não sobrepostos conhecidos como blocos de intervalo. Isto poderiam ser blocos de intervalo de 8x8, 16x16 pixels, etc.
• Examina a imagem em busca de padrões auto-repetitivos (padrões fractais). Usando os blocos de intervalo, o algoritmo encontra secções maiores da imagem que são semelhantes a estes blocos de intervalo. Estas secções maiores são referidas como os blocos de domínio.
• Uma função de transformação é então aplicada ao bloco de domínio para aproximar os blocos de intervalo. Estas funções de transformação são funções matemáticas como escalamento, translação, rotação, etc. Também podem ser referidas como transformações. Estas transformações são chamadas códigos fractais no que diz respeito à compressão fractal.
• Os dados são então codificados para essas funções de transformação. Em vez de armazenar os dados pixel a pixel, as transformações são armazenadas. Estas transformações são as regras que descrevem como reconstruir a imagem a partir de blocos de domínio.

\ Com os códigos fractais, a imagem é reconstruída usando um processo iterativo. Este processo pode ser computacionalmente caro, mas a compressão fractal poderia alcançar uma alta taxa de compressão comparada a outras técnicas de compressão. Devido à sua dependência de padrões auto-repetitivos, teria melhor desempenho em dados que se conformam a ter tais padrões auto-repetitivos. Exemplos seriam fotografias de paisagens (imagens da natureza) e imagens de DNA.

\ Existem outras técnicas de compressão com perdas, como a Transformada Discreta de Wavelet, Quantização. Estas técnicas são geralmente usadas em ficheiros de imagens, áudio e vídeo e são adequadas para certos tipos ou formatos de ficheiro - JPEG, MP3 - para cada tipo de ficheiro.

\ A compressão com perdas geralmente tem taxas de compressão mais altas que a compressão sem perdas e às vezes espera que o utilizador saiba a quantidade de perda a introduzir antecipadamente. É pertinente enfatizar que a escolha do método e técnica de compressão depende de vários fatores. No centro destes fatores estão o formato de dados e o resultado desejado.

TL;DR

No geral, esta publicação discute compressão no mundo dos dados. Depende fortemente do corpo de conhecimento existente em ciência da computação e teoria da informação. Comprimir significa reduzir o volume que uma entidade ocupa, e no campo dos dados, volume refere-se ao espaço de armazenamento. A compressão em sistemas digitais tem muitas vantagens quando feita corretamente. O óbvio é que reduz o espaço e dá espaço para armazenar mais dados. Outras vantagens incluem transmissão mais rápida, menos uso de largura de banda e melhoria geral na eficiência do referido sistema. Lembre-se, isto é quando é feito corretamente.

\ Para aproveitar as vantagens da compressão, é fundamental saber que tipo usar. A compressão é com perdas ou sem perdas. A compressão com perdas introduz uma perda nos dados originais que geralmente é irreversível, enquanto a compressão sem perdas comprime os dados e retém toda a informação contida nos dados originais. Além disso, há discurso sobre tipos de compressão híbrida, mas penso que uma combinação de com perdas e sem perdas é apenas com perdas. Diga-me o que pensa nos comentários.

\ Por último, diferentes técnicas foram introduzidas tanto para compressão com perdas quanto sem perdas. A lista de técnicas e explicações destas técnicas não é nem exaustiva nem abrangente. Considero-as apenas um bom começo para lhe dar uma ideia de como cada técnica funciona. Para concluir, adicionei recursos adicionais para ajudá-lo a investigar mais e ler mais profundamente sobre compressão em big data.

Recursos adicionais

Vídeo: Fundamentos de Data Lake - codificação RLE com Parquet na prática

Artigo: Uma revisão de técnicas de compressão de dados

Artigo: técnicas de compressão sem perdas

Uma introdução concisa à compressão de dados por David Salomon

Artigo: Um estudo de várias técnicas de compressão de dados

Publicação de blog: Compressão em formatos de ficheiro abertos

Artigo: Formatos de ficheiro abertos

Artigo: Compressão em bases de dados

Compressão com perdas para dados genómicos (RNA)

\