Aceder aleatoriamente a pacotes de dados num ficheiro comprimido

Os esquemas de compactação baseados em LZ são baseados em encontrar e eliminar seqüências de caracteres repetidas. À medida que comprimem um fluxo, eles criam um dicionário de strings que foram encontradas, portanto, quando a mesma string é encontrada novamente, elas transmitem a localização dessa string no dicionário, em vez de retransmitir a string inteira.

Em um caso típico, os primeiros poucos kilobytes de dados na verdade se expandem um pouco, porque o dicionário começa (essencialmente ¹ ) vazio. Somente após alguns kilobytes terem sido verificados e as strings adicionadas ao dicionário você começa a obter muita compactação.

Para que esse algoritmo trabalhe de forma decente em dados orientados a registros, você provavelmente deseja agrupar seus registros em blocos de, digamos, algo como 64 KB cada. Ler um registro será um processo de duas etapas. Primeiro você encontrará o bloco que contém o registro, lerá na memória e comprimirá todo o bloco. Em seguida, você encontrará o registro com o qual você se importa nesses dados descompactados.

O tamanho do bloco selecionado é um compromisso entre a eficiência da compactação e a eficiência do acesso aleatório. Um bloco maior geralmente melhora a compactação, mas (obviamente, o suficiente) exige que você leia mais dados para obter os registros em um bloco. Um tamanho de bloco menor reduz os dados extras que você precisa ler para chegar a um registro específico, mas também reduz a compactação.

Se você estiver disposto a fazer sua compressão manualmente, poderá fazer as coisas de maneira diferente. A ideia geral seria varrer uma grande quantidade de dados para construir um dicionário (semelhante ao LZ) de cadeias repetidas, mas não faz uma compressão imediata como a LZ. Em vez disso, armazene o dicionário (separadamente dos dados). Depois de digitalizar todos os dados, use o dicionário completo para compactar os dados. Isso requer que você armazene o dicionário (que usa algum espaço), mas permite que você o pré-construa ao descompactar os dados. Isso reduz a penalidade de compactar cada registro separadamente, portanto, quando você ler dados, precisará ler apenas um registro (além de partes associadas do dicionário - mas, quando estiver em uso, você provavelmente terá a maior parte do dicionário na RAM na maior parte do tempo).

¹ Em algumas implementações, o dicionário começa inicializado com entradas para os 256 valores de byte possíveis, mas isso ainda resulta em expansão - cada uma dessas cadeias de um caractere é representada no bit-stream com um (mínimo de um) código de 9 bits. Em outros casos, essas entradas de dicionário são "virtuais" - cada uma é tratada como estando presente na posição correta no dicionário, mas nunca armazenada de fato.

Se você está lidando com pacotes bem definidos, então a resposta é que sim, tudo isso é possível.

Eu sugeriria: - o arquivo contém 2 tipos de informação: um índice e um registro de dados - registros de dados são compactados - índices apontam para registros de dados ou um novo índice

Os índices precisam ser extensíveis para que, à medida que você desenvolve um arquivo adicionando mais registros, você possa criar e adicionar um novo índice, se necessário.

Tudo isso pode ser resumido em uma API razoavelmente boa.

Se você quisesse compactar os registros de dados, sugiro que veja o 7-zip, pareça ter uma interface COM ou similar, e comprima melhor que o zip simples.

Algo a ter em mente é que, ao lidar com arquivos grandes, você perceberá que obtém uma compactação muito melhor do arquivo inteiro, quando comparado à compactação dos registros individualmente. Isso ocorre porque a maioria desses algoritmos de compactação depende da detecção de padrões repetidos em um arquivo e, se houver informações repetidas nos registros, isso será muito bem processado. Um registro individual pode não ter muitas informações repetidas e, portanto, pode não ser compactado também.

Muito disso depende dos tipos de arquivos que você está lidando e de sua estrutura interna.

Existe uma razão lógica / estrutural para os arquivos serem tão grandes quanto eles?

Como estão interconectados os dados dentro de cada arquivo?

É provável que, uma vez que você comece a ler, você termine a sua leitura localmente, ou você perceberá que está pulando o arquivo para concluir a leitura?

Supondo que suas leituras sejam na maioria locais e relativamente pequenas, um algoritmo de compactação LZ modificado deve resolver o problema. Você pode fazer o seu próprio, ou usar um dos exemplos disponíveis na web, e obter uma compressão bastante decente, permitindo acesso aleatório.

Se você estiver lidando com arquiteturas e conteúdos mais complexos, terá de ser mais criativo. Você pode querer analisar o conteúdo de cada arquivo e, em seguida, armazená-los em um banco de dados que vem com algoritmos de compactação incorporados, como o Oracle, por exemplo, uma vez que pode poupar dores de cabeça significativas.

Você pode considerar isso de uma direção diferente. Que tal armazenar os arquivos em uma unidade compactada? Eles estarão acessíveis como arquivos comuns, mas ocupam menos espaço nas unidades.