formatos de compressão com um bom suporte para acesso aleatório dentro de arquivos?

Question

Este é semelhante a um anterior pergunta , mas as respostas lá não satisfazer as minhas necessidades e minha pergunta é um pouco diferente :

Eu uso atualmente compressão gzip para alguns arquivos muito grandes que contêm dados classificados. Quando os arquivos não são compactados, busca binária é uma maneira prática e eficiente para apoiar buscando um lugar nos dados classificados.

Mas quando os arquivos são compactados, as coisas ficam complicadas. Recentemente eu descobri sobre zlib 's Z_FULL_FLUSH opção, que pode ser usado durante a compressão para inserir 'pontos de sincronização' na a saída comprimido (inflateSync() pode então começar a ler a partir de vários pontos no arquivo). Este é OK, embora os arquivos que já tenho teria que ser recompressed para adicionar esta funcionalidade (e gzip estranhamente não tem uma opção para isso, mas eu estou disposto a escrever meu próprio programa de compactação se for preciso).

Parece que a partir um fonte que mesmo Z_FULL_FLUSH não é uma solução perfeita ... não só não é suportado por todos os arquivos gzip, mas a própria idéia de detectar pontos de sincronização de arquivos pode produzir falsos positivos (seja por coincidência com o número mágico para pontos de sincronização, ou devido a o fato de que Z_SYNC_FLUSH também produz pontos de sincronização, mas eles não são utilizáveis ??para acesso aleatório).

Existe uma solução melhor? Eu gostaria de evitar que arquivos auxiliares para a indexação, se possível, e explícita, suporte padrão para acesso quase aleatória seria útil (mesmo que seja grande de grãos - como ser capaz de começar a ler a cada intervalo de 10 MB). Existe um outro formato de compressão com melhor suporte para leituras aleatórias que o gzip?

Editar : Como mencionei, eu gostaria de fazer nos dados comprimidos de busca binária. Eu não preciso procurar uma posição específica (não comprimido) - apenas para buscar com alguma granularidade grossa dentro do arquivo comprimido. Eu só quero o apoio para algo como "descomprimir os dados começando cerca de 50% (25%, 12,5%, etc.) do caminho para este arquivo compactado."

Answer 1

Eu não sei de qualquer formato de arquivo comprimido que iria apoiar o acesso aleatório a um local específico nos dados não comprimidos (bem, exceto para formatos multimídia), mas você pode preparar o seu próprio.

Por exemplo, arquivos bzip2 compactado são compostas por blocos compactados independentes de tamanho <1MB descompactado, que são delimitados por seqüências de bytes mágicos, para que você possa analisar o arquivo bzip2, obter os limites de bloco e depois é só descompactar o bloco de direita. Isso iria precisar de algum indexação de lembrar onde é que os blocos começar.

Ainda assim, eu acho que a melhor solução seria a de dividir o seu arquivo em pedaços de sua escolha, em seguida, comprimi-lo com algumas archiver, como zip ou rar, que suportam acesso aleatório a arquivos individuais no arquivo.

Answer 2

Dê uma olhada em dictzip . É compatível com gzip e permite acesso aleatório grossa.

Um trecho de sua página man:

dictzip comprime arquivos usando o gzip (1) algoritmo (LZ77) de uma forma que é totalmente compatível com o formato de arquivo gzip. Uma extensão para o gzip formato de arquivo (campo extra, descrito em 2.3.1.1 do RFC 1952) permite que dados adicionais para ser armazenado no cabeçalho de um arquivo compactado. Programas como o gzip e zcat irá ignorar esses dados extra. No entanto, [dictzcat --start] fará uso desses dados para executar o acesso pseudo-aleatório no arquivo.

Eu tenho o dictzip pacote no Ubuntu. Ou seu código fonte está em um dictd - *. Tar.gz . Sua licença é GPL. Você é livre para estudá-lo.

Update:

Eu melhorei dictzip não ter limite de tamanho de arquivo. Minha implementação está sob licença MIT.

Answer 3

O .xz formato de arquivo (que usa compressão LZMA) parece apoiar esta:

leitura de acesso aleatório : Os dados podem ser divididos em blocos prensados ??de forma independente. Cada arquivo .xz contém um índice dos blocos, o que faz de acesso aleatório limitada lendo possível quando o tamanho do bloco é pequeno o suficiente.

Isso deve ser suficiente para a sua finalidade. A desvantagem é que a API de liblzma (para interagir com esses recipientes) não parece que bem documentado, por isso pode levar algum esforço para descobrir como aleatoriamente blocos de acesso.

Answer 4

existem

Soluções para fornecer acesso aleatório a gzip e bzip2 arquivos:

• gzip zran. c do código-fonte ghostscript
• bzip2 buscar-bzip por James Taylor

( Eu estou procurando algo para 7zip )

Answer 5

bgzip pode compactar arquivos em uma variante gzip que é indexável (e pode ser descompactado por gzip). Isto é usado em algumas aplicações de bioinformática, juntamente com o indexador tabix.

Veja explicações aqui: http: // blastedbio .blogspot.fr / 2011/11 / bgzf-bloqueado-maior-melhor-gzip.html , e aqui: http://www.htslib.org/doc/tabix.html .

Eu não sei até que ponto é adaptável a outras aplicações.

Answer 6

Eu não tenho certeza se isso seria prático em sua situação exata, mas você não pode apenas gzip cada arquivo grande em arquivos menores, digamos, 10 MB cada um? Você iria acabar com um monte de arquivos: file0.gz, file1.gz, file2.gz, etc. Com base em um determinado deslocamento dentro da grande original, você pode procurar no arquivo "file" + (offset / 10485760) + ".gz" nomeado. O deslocamento dentro do arquivo não compactado seria offset % 10485760.

Answer 7

Por causa compressão sem perdas funciona melhor em algumas áreas do que outros, Se você armazenar dados comprimidos em blocos de comprimento conveniente BLOCKSIZE, mesmo que cada bloco tem exatamente o mesmo número de bytes compactados, alguns blocos compactados vai expandir-se para um muito mais tempo pedaço de texto simples do que outros.

Você pode olhar para "Compressão: A Chave para o Next-Generation texto Recuperação de Sistemas" por Nivio Ziviani, Edleno Silva de Moura, Gonzalo Navarro, e Ricardo Baeza-Yates no Computador revista novembro 2000 http://doi.ieeecomputersociety.org/10.1109/2.881693

O descompressor leva 1, 2 ou 3 bytes inteiros de dados compactados e descomprime (usando uma lista de vocabulário) em uma palavra inteira. Pode-se pesquisar diretamente o texto comprimido por palavras ou frases, o que acaba por ser ainda mais rápido do que a pesquisa de texto descomprimido.

O descompressor permite apontar para qualquer palavra no texto com um (byte) ponteiro normal e começar a descomprimir imediatamente a partir desse ponto.

Você pode dar a cada palavra um código de 2 byte único, já que você provavelmente tem menos de 65.000 palavras únicas em seu texto. (Há quase 13.000 palavras únicas na Bíblia KJV). Mesmo se houver mais de 65.000 palavras, é muito simples de atribuir os primeiros 256 de dois bytes de código "palavras" a todos os bytes possíveis, para que possa soletrar palavras que não estão no léxico da 65.000 ou assim "mais frequente palavras e frases". (A compressão adquirida por embalagem palavras e frases freqüentes em dois bytes é geralmente vale a "expansão" de vez em quando soletrando uma palavra usando dois bytes por carta). Há uma variedade de maneiras para escolher um léxico de "palavras e frases frequentes" que lhe dará a compressão adequada. Por exemplo, você poderia ajustar um compressor LZW para despejar "frases" que ele usa mais de uma vez em um arquivo de léxico, uma linha por frase, e executá-lo sobre todos os seus dados. Ou você pode arbitrariamente pique seus dados não comprimidos em 5 Frases de bytes em um arquivo de léxico, uma linha por frase. Ou você poderia picar seus dados descompactado em palavras reais ingleses, e colocar cada palavra - incluindo o espaço no início da palavra - para o arquivo de léxico. Em seguida, use "tipo --unique" para eliminar palavras duplicadas em que arquivo de léxico. (É escolher o perfeito "ótimo" léxico wordlist ainda considerado NP-duro?)

Loja do léxico no início do seu arquivo comprimido enorme, pad-lo para algum BLOCKSIZE conveniente, e depois armazenar o texto comprimido - uma série de dois "palavras" byte - de lá para o final do arquivo. Presumivelmente, o pesquisador irá ler este léxico uma vez e mantê-lo em algum formato quick-to-decodificação na RAM durante a descompressão, para acelerar descomprimir "dois byte código" a "frase de comprimento variável". O meu primeiro projecto iria começar com um simples uma linha por frase lista, mas depois que você pode mudar para armazenar o léxico de uma forma mais comprimido usando algum tipo de incremento de codificação ou zlib.

Você pode escolher qualquer mesmo deslocamento no texto comprimido byte aleatório, e começar a descomprimir de lá. Eu não acho que é possível fazer um acesso aleatório formato de arquivo comprimido de grão mais fino.

Answer 8

Duas soluções possíveis:

1. Deixe o negócio OS com compressão, criar e montar um sistema de arquivo compactado (SquashFS, clicfs, cloop, cramfs, e2compr ou qualquer outro) contendo todos os seus arquivos de texto e não fazer nada a respeito de compressão em seu programa de aplicação .

2. Use clicfs diretamente em cada arquivo de texto (um clicfs por arquivo de texto) em vez de comprimir uma imagem de sistema de arquivos. Pense em "mkclicfs mytextfile mycompressedfile" ser "gzip mycompressedfile" e "clicfs diretório mycompressedfile" como uma forma de obter acesso aleatório aos dados através do arquivo "diretório / mytextfile".

Answer 9

Eu não sei se a sua sido mencionado ainda, mas o projeto Kiwix tinha feito um grande trabalho nesse sentido. Através de seu programa Kiwix, eles oferecem acesso aleatório a arquivos de ficheiros ZIM. Boa compressão, também. O projeto surgiu quando houve uma demanda por cópias off-line da Wikipedia (que atingiu acima de 100 GB em forma descompactada, com todos os meios incluído). Eles tomaram com êxito um arquivo GB 25 (uma modalidade de arquivo único da wikipedia sem a maioria dos meios de comunicação) e comprimido-lo para um arquivo de arquivo míseros 8 GB zim. E através do programa Kiwix, você pode chamar qualquer página da Wikipedia, com todos os dados associados, mais rápido do que você pode navegar na net.

Apesar de programa Kiwix é uma tecnologia baseada em torno da estrutura de banco de dados wikipedia, isso prova que você pode ter excelentes relações de compressão e de acesso aleatório ao mesmo tempo.

Answer 10

Esta é uma questão muito antiga, mas parece que zindex poderia fornecer uma solução bom (embora I don 't tem muita experiência com ele)

Answer 11

suportes razip acesso aleatório com melhor desempenho do que gzip / bzip2 que tem que ser ajustado para este apoio - reduzindo a compressão à custa de acesso aleatório "ok":

http://sourceforge.net/projects/razip/

Answer 12

Eu sou o autor de uma ferramenta de código aberto para comprimir um determinado tipo de dados biológicos. Esta ferramenta, denominada starch, divide os dados por cromossomo e usa essas divisões como índices para o acesso rápido às unidades de dados comprimidos dentro do arquivo maior.

dados Per-cromossómicas são transformados para remover redundância em coordenadas genómicos, e os dados transformados são comprimidas com qualquer bzip2 ou gzip algoritmos. Os deslocamentos, metadados e dados genômicos compactados são concatenados em um arquivo.

código

Fonte está disponível no nosso GitHub local . Reunimos-lo sob Linux e Mac OS X.

Para o seu caso, você pode armazenar (10 MB, ou qualquer outro) offsets em um cabeçalho para um formato de arquivo personalizado. Você analisar o cabeçalho, recuperar os deslocamentos, e de forma incremental fseek através do arquivo por current_offset_sum + header_size.