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 1 ) 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).
1 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.