Do ponto de vista de hardware, um disco é um tipo de memória secundária de acesso direto e não volátil, ou seja, não perde os dados quando o computador é desligado. Pode ser disco rígido ou memória flash.

Um disco rígido é composto de:

• Braço: Suporta as cabeças de leitura e gravação enquanto elas se movem pela superfície do disco;
• Prato: Disco individual. Um “*disk drive*” pode ter vários pratos;
• Cabeça de leitura/gravação: Dispositivo que realiza leitura e escrita na superfície de armazenamento;
• Superfície: Cada prato tem duas superfícies;
• Trilha: Um círculo único na superfície de armazenamento;
• Setor: As trilhas são divididas em setores e as operações de leitura e gravação ocorrem em um setor inteiro;
• Cilindro: É o conjunto de trilhas que ficam na mesma posição do braço em um dado instante.

O disco gira em alta velocidade para ler ou gravar os dados em círculos concêntricos na superfície. No momento de usar o disco, o número da trilha ou cilindro e o setor devem ser especificados. O braço se move para posicionar a cabeça no ponto correto e então há transmissão de dados. Normalmente há 512 bytes de dados em cada setor.

Há três tipos básicos de intervalos de tempo para leitura / gravação: posicionamento (posicionar braço na trilha correta), latência (encontrar setor) e transmissão (enviar / receber dados).

Os setores são administrados pelo sistema de arquivos, que é o software responsável por gerenciar qual sequência de bytes é de qual arquivo e quais setores estão vazios. Um arquivo é um conjunto de registros formados por campos, que por sua vez podem ser chaves, um identificador único do registro. Um arquivo deve possuir um ponteiro que indica sua próxima leitura ou gravação. Registros são objetos com numeração sequencial e podem ter tamanho fixo ou variável.

As operações básicas em arquivos são: abrir, fechar, ler, escrever, testar pelo final do arquivo, posicionar em determinado registro, achar posição do ponteiro. Um arquivo pode ser aberto de três modos; leitura, leitura e escrita e apenas escrita.

Para acessar um arquivo utilizamos as consultas, onde podemos pesquisar através de um campo, intervalos de valores em um campo, valores dentro do arquivo ou uma combinação dos anteriores. Para que isso seja eficiente é necessário organizar o arquivo de acordo com uma determinada estrutura que será mais útil para pesquisa posteriormente. Em casos onde o arquivo original é muito grande, pode-se quebrá-lo em partes menores, ordenar cada parte por um campo e depois aplicar o método de intercalação (ou merge) para juntar as partes em um arquivo final. A intercalação é um tipo de operação cossequencial no processamento de arquivos, ou seja, elas envolvem a execução coordenada de duas ou mais entradas para produzir uma saída.

O chamado acesso sequencial, muito comum em fitas magnéticas, é muito ineficiente porque deve passar por todos os dados até chegar no setor desejado. Os novos registros só poderiam ser gravados no final do arquivo.

Os arquivos possuem diversos atributos, que são metadados úteis para sua identificação no sistema operacional.

A memória secundária do computador tem um espaço de armazenamento ordens de grandeza superiores à memória principal, por isso, é importante que programas utilizem estruturas de dados eficientes para permitir a manipulação através da memória principal. Algumas estruturas de dados úteis são:

• Árvore B
• Tabela Hash Extensível
• Listas Invertidas
• Árvore Digital

O método de hash extensível é uma técnica utilizada em estruturas de dados para arquivos que permite lidar com a expansão dinâmica dos dados sem a necessidade de reconstruir completamente a estrutura. Esse método é particularmente útil em situações em que o tamanho do arquivo pode aumentar com o tempo, e você deseja evitar custos elevados de reorganização frequente da estrutura.

Diretórios são organizações lógicas para agrupar certos arquivos gravados em um disco. Podemos dizer que o diretório utiliza uma estrutura de dados para armazenar as informações do arquivo e seus atributos. Quando abrimos um arquivo, suas informações vão para uma tabela na memória principal do computador, assim como dos outros arquivos presentes no diretório.

Diretórios podem ter um nível único ou separado para cada usuário (UFD = User File Directory). O nível controlador dos diretórios lógicos é o MDF (Master File Directory), onde a indexação ocorre para cada usuário. O modelo mais usado, entretanto, é o de árvore (Tree-Structured Directory), onde os usuários podem criar subníveis em cada diretório.

Para gerenciar o espaço livre em disco o sistema operacional implementa uma tabela chamada de mapa de bits (bitmap). Cada entrada na tabela fica associada a um bloco do disco e representada por um bit, se valor for 0 está livre, caso contrário, alocado. Outro modo de fazer isso é através de uma lista encadeada de blocos livres. Há ainda a opção de organizar o disco com blocos contíguos (lado a lado) que podem ser alocados ou liberados ao mesmo tempo. Essa técnica é chamada de tabela de blocos livres.

Para gerenciar a alocação de dados, o SO utilizada as técnicas de alocação contígua, encadeada e indexada.

• Alocação Encadeada: Neste método, os blocos de dados são ligados em sequência. Cada bloco de dados contém o conteúdo real do arquivo e um ponteiro para o próximo bloco de dados. O último bloco da cadeia tem um ponteiro especial para indicar o fim do arquivo. Essa estrutura permite que os blocos de dados sejam dispersos pelo disco, não necessariamente ocupando espaço contíguo.

• Alocação Contígua: Neste método, cada arquivo é armazenado como uma sequência contígua de blocos de dados no disco. Isso significa que todos os blocos de um arquivo são armazenados em locais adjacentes. A alocação contígua reduz a fragmentação, mas requer um espaço contíguo disponível para armazenar o arquivo inteiro.

• Alocação Indexada: Neste método, cada arquivo possui um bloco de índice associado a ele. O bloco de índice contém uma tabela de índices, onde cada entrada aponta para um bloco de dados correspondente ao arquivo. A alocação indexada permite que os blocos de dados sejam espalhados pelo disco, pois o bloco de índice atua como um índice para localizá-los.

Na alocação contígua, utilizam-se blocos sequenciais e há algoritmos utilizados: first-fit (primeiro seguimento livre), best-fit (menor segmento livre com tamanho suficiente) e worst-fit (maior segmento). O problema do método é a fragmentação de dados. No caso encadeado os blocos são ligados logicamente com um ponteiro em cada bloco apontando para o próximo. A técnica indexada mantém as informações dos blocos que formam um arquivo no bloco índice, facilitando o acesso direito aos blocos do arquivo.

• First-Fit (Primeiro Ajuste): O algoritmo First-Fit busca o primeiro espaço livre que seja grande o suficiente para acomodar o arquivo. Ele percorre a lista de espaços livres e seleciona o primeiro que atende aos requisitos do arquivo. Esse espaço é usado para alocar o arquivo, e qualquer espaço restante é dividido em um novo espaço livre. O First-Fit é simples de implementar e eficiente em termos de tempo de busca, pois não é necessário percorrer toda a lista de espaços livres. No entanto, pode resultar em fragmentação, pois os espaços não utilizados podem ser deixados entre arquivos alocados.
• Best-Fit (Melhor Ajuste): O algoritmo Best-Fit procura o espaço livre que seja o mais próximo possível do tamanho do arquivo. Em vez de selecionar o primeiro espaço livre disponível, ele examina todos os espaços livres e escolhe o que é menor o suficiente para acomodar o arquivo, mas ainda mantém o desperdício mínimo. O Best-Fit é eficiente em termos de utilização de espaço, pois minimiza a fragmentação e evita que pequenos espaços livres se acumulem. No entanto, requer uma busca mais intensiva, comparando todos os espaços livres, o que pode resultar em um tempo de alocação mais longo.
• Worst-Fit (Pior Ajuste): O algoritmo Worst-Fit busca o espaço livre mais amplo disponível para alocar o arquivo. Ao contrário do Best-Fit, ele seleciona o maior espaço livre, mesmo que seja maior do que o tamanho do arquivo. Isso pode resultar em um desperdício significativo de espaço livre. O Worst-Fit é menos eficiente em termos de utilização de espaço, pois tende a gerar fragmentação e desperdício. No entanto, pode ser útil em cenários em que é esperado que arquivos grandes sejam alocados posteriormente, aproveitando ao máximo os espaços disponíveis.

A escolha entre os algoritmos First-Fit, Best-Fit e Worst-Fit depende das características específicas do sistema de arquivos, das necessidades de alocação e do equilíbrio entre fragmentação e utilização de espaço. Cada algoritmo tem seus prós e contras, e a escolha adequada depende das prioridades do sistema operacional em relação ao uso eficiente do espaço e ao desempenho da alocação.

Como vimos anteriormente, os arquivos podem ser armazenados em diretórios, que são abstrações úteis para agrupar arquivos, além de poderem gerenciar as permissões de acesso e compartilhamento. Atalhos também são abstrações que permitem que determinados objetos sejam encontrados mais facilmente. O sistema de arquivo virtual é a entidade responsável por essas abstrações, além de controlar o registro de cada arquivo aberto por cada processo, mantendo as informações dos ponteiros, modo de abertura e quem está utilizando cada arquivo.

Os discos podem ser separados em partições, que são espaços lógicos independentes, muito úteis para organização de arquivos, diretórios e até sistemas operacionais distintos. Na área com os dados da participação temos o código de inicialização (boot) chamado de boot sector ou MBR (Master Boot Record). Se a partição tem um sistema operacional, ou seja, é inicializável, temos uma área chamada VBR (Volume Boot Record) ou bloco de inicialização.

Discos são muito mais lentos do que as memórias voláteis, por isso, é necessário criar estratégias para procurar e acessar os arquivos. Uma delas é através do uso de cache, que são áreas na memórias RAM, na parte de gestão de blocos, onde conteúdos podem ser armazenados para acesso em outro momento. O cache pode ser de leitura e de escrita. Há quatro estratégias usuais de caching:

1. Read-through: consulta o cache primeiro e retorna o dado se existir; caso não exista, consulta o disco e depois grava no cache.
2. Read-ahead: grava mais dados no cache do que os solicitados para antecipar pedidos futuros;
3. Write-through: mantém cópia do conteúdo em cache depois de gravar no disco ou memória RAM para facilitar leituras futuras;
4. Write-back: copia primeiro para o cache, libera o processo e depois escreve no disco.

Os tipos de acesso aos arquivos são: sequencial, direto e indexado.

Em cada tipo de alocação há vantagens e desvantagens na hora de buscar os dados. Sendo os mais rápidos os modos contíguo, FAT e indexado.

Algumas estruturas de dados são mais eficientes que outras, dado o problema de pesquisa:

• Árvore B+: É uma estrutura de dados em forma de árvore que é amplamente utilizada em bancos de dados e sistemas de arquivos para organizar e indexar grandes volumes de dados. Ela é semelhante à árvore B, mas com algumas diferenças importantes. Uma árvore B+ possui um nó raiz, nós internos e nós folha. Os nós folha contêm os dados propriamente ditos, enquanto os nós internos são usados para navegação. Uma das principais características da árvore B+ é a sua capacidade de lidar com eficiência consultas por intervalo. Os nós folha são ligados em uma lista duplamente encadeada, permitindo a busca sequencial eficiente de dados. Além disso, os nós internos contêm chaves que servem como pontos de referência para direcionar a busca.
• Árvore Binária de Pesquisa: Como o nome sugere, é uma estrutura de dados em forma de árvore em que cada nó possui no máximo dois filhos: um à esquerda e outro à direita. A árvore binária de pesquisa tem a propriedade de que o valor de qualquer nó à esquerda é menor do que o valor do próprio nó, enquanto o valor de qualquer nó à direita é maior. Essa propriedade torna a árvore binária de pesquisa eficiente para a busca de elementos. Ao realizar uma busca em uma árvore binária de pesquisa, podemos comparar o valor procurado com o valor do nó atual e decidir se devemos seguir pela subárvore esquerda ou direita. Essa abordagem de divisão e conquista permite que a busca seja realizada de forma eficiente.
• Hash: O hash (ou tabela hash) é uma estrutura de dados que mapeia chaves a valores. É amplamente utilizado para implementar a busca rápida e eficiente de elementos. Uma tabela hash consiste em um array de "slots" ou "buckets", onde os elementos são armazenados com base em sua chave. A função de hash é responsável por converter a chave em um índice na tabela hash. Idealmente, essa função deve distribuir uniformemente as chaves nos slots da tabela hash. No entanto, colisões podem ocorrer, quando duas ou mais chaves são mapeadas para o mesmo slot. Existem várias técnicas para lidar com colisões, como encadeamento (utilizando listas ligadas) ou endereçamento aberto (tentando encontrar o próximo slot vazio). A principal vantagem das tabelas hash é a sua capacidade de busca extremamente rápida, uma vez que a posição do elemento desejado pode ser calculada diretamente a partir de sua chave, em média, em tempo constante.
• Árvore AVL: É uma estrutura de dados em forma de árvore binária de pesquisa balanceada. Ela recebe esse nome em homenagem aos seus inventores, Adelson-Velskii e Landis. A árvore AVL mantém a propriedade de balanceamento, que garante que a diferença de altura entre as subárvores esquerda e direita de qualquer nó seja no máximo 1. Quando um novo nó é inserido ou removido de uma árvore AVL, pode ser necessário realizar rotações para restaurar o balanceamento. As rotações modificam a estrutura da árvore, garantindo que ela permaneça balanceada. A principal vantagem da árvore AVL é que as operações de busca, inserção e remoção são realizadas em tempo logarítmico, garantindo um desempenho eficiente mesmo com um grande número de elementos. No entanto, o balanceamento contínuo requer um certo overhead computacional em comparação com estruturas não balanceadas.
• Árvore Digital de Pesquisa: Também conhecida como Trie, é uma estrutura de dados especializada na busca eficiente de palavras ou strings. Ela é particularmente útil quando precisamos armazenar e pesquisar um grande número de palavras ou quando precisamos realizar operações como prefixo ou correspondência exata. Na árvore digital de pesquisa, cada nó representa um caractere da palavra. A partir do nó raiz, seguimos o caminho correspondente aos caracteres da palavra, cada caminho representando uma possível sequência de caracteres. Os nós folha indicam o final de uma palavra válida. Essa estrutura de árvore permite que a busca por palavras seja realizada de maneira eficiente, percorrendo apenas os caminhos relevantes da árvore. É especialmente útil para aplicações como sugestões de digitação, corretores ortográficos e indexação de palavras-chave.

Em resumo, as árvores B+, árvores binárias de pesquisa, tabelas hash, árvores AVL e árvores digitais de pesquisa são estruturas de dados importantes que oferecem diferentes características e eficiências para a organização e busca de elementos. A escolha da estrutura mais adequada depende dos requisitos específicos da aplicação e das propriedades desejadas, como eficiência de busca, economia de espaço ou capacidade de manipular dados em forma de árvore.

Os arquivos são compostos de seu conteúdo, o dado em si (foto, música, texto, etc…), e seus atributos (criação, alteração, autor, permissão, etc), além das informações de controle para localizá-lo no disco.

Representação analógica e digital são dois conceitos fundamentais no mundo dos computadores, principalmente quando se trata de armazenamento e processamento de arquivos.

Representação Analógica:Em uma representação analógica, os dados são representados usando quantidades físicas contínuas, como tensão, corrente ou amplitude. Os sinais analógicos podem assumir qualquer valor dentro de uma faixa, permitindo variações suaves e contínuas. Exemplos de meios de armazenamento analógicos incluem discos de vinil, fitas magnéticas ou fotografias analógicas.

Arquivos analógicos, como gravações de áudio ou imagens, capturam as informações do mundo real de maneira direta e contínua. Por exemplo, um arquivo de áudio analógico representa as ondas sonoras como variações contínuas na tensão ou na pressão do ar ao longo do tempo. A fotografia analógica captura imagens registrando a intensidade variável da luz por meio de processos químicos.

Embora a representação analógica seja ótima para capturar a riqueza e as sutilezas das informações do mundo real, ela apresenta algumas desvantagens quando se trata de processar e armazenar arquivos em computadores.

Representação digital: A representação digital, por outro lado, envolve a conversão de dados analógicos em valores discretos e quantizados. Em uma representação digital, os dados são representados por um sistema binário, que consiste em apenas dois dígitos: 0 e 1. Esses dígitos são usados para representar informações na forma de bits (dígitos binários) e bytes (grupos de bits).

Arquivos digitais, como documentos de texto, imagens ou vídeos, são armazenados como sequências desses dígitos binários. Os dados são codificados em formato binário usando diferentes esquemas de codificação, como ASCII ou Unicode para texto e formatos como JPEG ou PNG para imagens. A representação digital permite o armazenamento preciso e a manipulação de informações em um computador.

Vantagens da Representação Digital:

• Precisão: A representação digital oferece armazenamento preciso e consistente de dados, garantindo que as informações sejam preservadas fielmente sem degradação ou perda.
• Escalabilidade: os arquivos digitais podem ser facilmente copiados, duplicados e distribuídos sem qualquer perda de qualidade. Essa escalabilidade permite compartilhar e transmitir arquivos entre diferentes sistemas e redes de computadores.
• Correção de erros: Os dados digitais podem ser protegidos contra erros e ruídos por meio de várias técnicas de correção de erros. Isso garante que, mesmo que haja erros de transmissão ou corrupção de dados, as informações originais possam ser recuperadas com precisão.
• Compressão: Arquivos digitais podem ser compactados usando algoritmos como codificação Huffman ou Lempel-Ziv-Welch (LZW). A compactação reduz o tamanho do arquivo, fazendo uso eficiente do espaço de armazenamento e permitindo uma transmissão mais rápida pelas redes.
• Flexibilidade: A representação digital permite manipulação e processamento de dados flexíveis. Ele permite várias operações computacionais como busca, classificação, filtragem e análise, que são essenciais para o processamento de dados e recuperação de informações.

Embora a representação digital tenha inúmeras vantagens, é importante observar que, durante o processo de conversão de dados analógicos para digitais, algumas informações podem ser perdidas devido a limitações de quantização e amostragem. No entanto, os avanços na tecnologia levaram a formatos digitais de alta resolução que podem se aproximar dos sinais analógicos.

A compressão ou codificação é um modo de reduzir o tamanho do arquivo original através de técnicas de manipulação dos dados. A expansão, ou decodificação, é o processo inverso. O objetivo é reduzir o espaço ocupado pelo arquivo com a restrição de não perder contéudo (lossless compression). Há diversos algoritmos de compressão.

Normalmente os algoritmos atuam nas redundâncias ou repetições de símbolos. Por exemplo, um arquivo .txt com o seguinte conteúdo

abababababababababababab

pode ser reduzido para

12ab

onde o número no começo indica o número de repetições do termo “ab”.

A estrutura básica de compressão é formada por um compressor e um expansor. Eles atuam em um fluxo de bits, que são separados em blocos (8, 16 ou 32 bits).

Algumas compressões tem perdas, como por exemplo: JPEG, GIF, PNG, MP3, FFT, etc…

A taxa de compressão é dada por |C| que é o tamanho do objeto comprimido, dividido por |B| que é tamanho de bits do objeto original B.

$TC=|C(B)|/|B|$

Espera-se que esse valor seja estritamente menor do que 1.

O algoritmo de comprimento de carreira lê a sequência de zeros ou uns e a representa por esses comprimentos. Por exemplo, `00001111 00000111 00000111 00001011`, de 32 bits, é a representação da cadeia de bits `0000000000000001111111000000011111111111` , que em decimal tem 15 zeros, 7 uns, 7 zeros e 11 uns em sequência.

Com a evolução das estruturas de transmissão de dados, hoje em dia podemos assistir conteúdo de altíssima qualidade em televisores, celulares, tablets e computadores, sem se preocupar com as taxas de movimentação de bits de um ponto a outro. Porém, para economizar na transmissão e no armazenamento de dados, podemos comprimir os objetos antes de enviá-los e, dependendo de seu tipo, essa compressão acontece sem perda e é muito eficiente.

No caso de uma imagem, há diversas formas de representar as cores em cada pixel: RGB, YUV, entre outros. É possível converter de um para outro sem perda de informação, mas certos padrões são mais práticos durante a compressão do que outros. Alguns algoritmos, como downsampling, descartam certos bits relacionados com informações visuais que não conseguimos enxergar e com isso podemos economizar até 40% na compressão. Entretanto, há perda de informação nesse processo.

Quando trabalhamos com áudio, o processo é semelhante, podemos descartar frequências fora do intervalo audível pelo ser humano e modificar as taxas de amostragem para comprimir o arquivo final. Quando aumentamos o número de amostras por segundo, por exemplo, em um CD há 44.1 kHz amostras ou 44 mil e 100 amostras por segundo, aumentamos o espaço ocupado por um arquivo.

Como vídeos são sequências de imagens, ao aplicarmos a compressão ao vídeo, na verdade estamos processando cada imagem. Isso pode ser feito utilizando a transformada rápida de Fourier, que é um método matemático de conversão de ondas do modo contínuo para o discreto. Em alguns casos pode-se utilizar o DCT (Discrete Cosine Transform) que representa uma sequência finita de pontos em uma soma de cossenos oscilando em frequências diferentes.

Além das mudanças na conversão do contínuo para o discreto, podemos também aplicar compressões com uma árvore de frequências, muito utilizada para gerar uma nova sequência de bits com base em símbolos repetidos. A combinação desse modelo com o de comprimento de carreira é chamado de codificação de Huffman.

O algoritmo de compressão "codificação de corrida" (Run-length encoding - RLE) é uma técnica simples e eficiente utilizada na compressão de dados. Ele se baseia na repetição de caracteres ou sequências de dados para reduzir o tamanho do arquivo original. O RLE é frequentemente usado em situações em que há padrões repetitivos ou longas sequências de caracteres idênticos.

O funcionamento básico do algoritmo RLE é bastante simples. Ele examina o arquivo original em busca de sequências consecutivas de caracteres repetidos e substitui essas sequências por um único caractere seguido pelo número de vezes que ele se repete. Por exemplo, se uma sequência contém 15 caracteres 'A', ela pode ser comprimida para 'A15'.

A principal vantagem do RLE é a sua simplicidade. É um algoritmo fácil de implementar e compreender. Além disso, o RLE é muito eficiente em casos em que o arquivo de entrada possui padrões repetitivos, como imagens em preto e branco, documentos de texto com muitas letras repetidas ou arquivos de áudio com longos períodos de silêncio. Nessas situações, o RLE pode reduzir significativamente o tamanho do arquivo de saída.

Outra vantagem do RLE é a rapidez da compressão e descompressão. Como o algoritmo envolve apenas a identificação e a contagem de sequências repetitivas, ele é muito rápido em termos de processamento. Isso o torna uma boa opção para sistemas com recursos limitados ou onde a velocidade de compressão é uma prioridade.

No entanto, o RLE também possui algumas limitações e desvantagens. Em primeiro lugar, seu desempenho de compressão é bastante limitado em arquivos que não possuem padrões repetitivos. Se o arquivo contém pouca repetição de caracteres ou não possui padrões óbvios, a taxa de compressão do RLE será baixa e a diferença de tamanho entre o arquivo original e o comprimido será mínima.

Além disso, o RLE não é eficiente para compressão de dados de alta entropia, como arquivos binários complexos ou imagens coloridas. Nessas situações, outros algoritmos de compressão, como Huffman ou LZW, geralmente apresentam melhores resultados, pois são capazes de identificar padrões mais complexos e criar representações mais compactas dos dados.

A codificação Run-Length (RLE) pode ser usada para compactar uma imagem de bitmap aproveitando os pixels consecutivos repetidos na imagem. Veja como o RLE pode ser aplicado para compactar uma imagem bitmap:

1. Digitalize a imagem linha por linha:
   Comece com o primeiro pixel da primeira linha.
   Compare-o com o próximo pixel na mesma linha.
2. Conte o número de pixels idênticos consecutivos:
   Se o próximo pixel for igual ao pixel atual, incremente um contador.
   Se o próximo pixel for diferente, pare de contar e vá para a próxima etapa.
3. Codifique o comprimento de execução e o valor do pixel:
   Armazene o comprimento da execução (o número de pixels consecutivos) e o valor do pixel (cor) da execução.
   Isso pode ser representado como um par: (comprimento de execução, valor de pixel).

Repita as etapas 2 e 3 para cada linha da imagem até que todos os pixels tenham sido processados.

Armazene os dados codificados:
Os dados codificados consistirão em uma série de pares (comprimento de execução, valor de pixel).
Esses dados podem ser armazenados em um formato compactado, usando uma representação mais eficiente do que a imagem bitmap original.

Ao aplicar o RLE a uma imagem bitmap, sequências de pixels idênticos são representadas por um único valor e uma contagem, reduzindo o tamanho geral da representação da imagem. Essa compactação é particularmente eficaz nos casos em que a imagem contém grandes áreas de cores sólidas ou padrões repetitivos, pois podem ser codificados com eficiência usando comprimentos de execução.

Aqui está um exemplo para ilustrar o processo de compactação usando RLE em uma imagem de bitmap simples:

Imagem bitmap original:

    [11111111]
    [22222222]
    [11111111]   

Com a compressão RLE:

    [(8, 1)]     // Eight consecutive pixels with a value of 1
    [(8, 2)]     // Eight consecutive pixels with a value of 2
    [(8, 1)]     // Eight consecutive pixels with a value of 1

Na representação compactada, a imagem é representada usando menos pixels, armazenando os comprimentos de execução e os valores de pixel. Nesse caso, a imagem bitmap original requer 24 pixels, enquanto a representação compactada usando RLE requer apenas 6 pares de valores.

Ao descompactar, os dados compactados podem ser usados para reconstruir a imagem de bitmap original repetindo cada valor de pixel de acordo com seu comprimento de execução.

É importante observar que a eficácia da compactação RLE depende das características da imagem que está sendo compactada. Imagens com grandes áreas de cores uniformes ou padrões repetitivos atingirão taxas de compactação mais altas com RLE, enquanto imagens mais complexas ou aleatórias podem não ser compactadas significativamente usando essa técnica.

Referências:

1. Sistemas Operacionais
2. Organização de arquivos
3. Sistemas operacionais: Conceitos e Mecanismos
4. Compressão de Dados
5. De 5 Tera a 25 Giga

< 13 - Linguagens Formais, Autômatos e Computabilidade > 15 - Sistemas Operacionais