Determinar melhor algoritmo de compressão para uso em uma série de bytes

Question

Para um projeto pessoal meu, eu estou escrevendo uma pequena classe para comprimir e descomprimir a partir de um formato bastante obscura. Eu tenho a especificação completa, mas isso não é onde está o problema.

Em primeiro lugar, este 'formato' usa um conjunto de 6 tipos diferentes de compressão, bem como blocos sem compressão de dados byte. Os formatos são RLE, uma ramificação de RLE onde os incrementos do número cada byte (por exemplo, 3, 4, 5, ...), um 16-bit RLE, LZ-Copiar, um LZ-cópia inversa, e LZ-Copiar Xor' d com 255. não é o mais limpo de especificações, mas eu não projetá-lo também.

A minha rotina de compressão é suposto ter em uma matriz de qualquer lugar de 1 a 65535 bytes, e (espero) comprimi-lo tanto quanto possível. Meu tentativa anterior neste simplesmente calculada para fora, a partir de qualquer índice no fluxo de não-comprimido, o qual das técnicas de compressão acima irá proporcionar o melhor compressão, e em seguida comprime no entanto muitos bytes que o método irá comprimir a matriz de bytes comprimido antes de repetir a partir da índice novo 'descomprimido', por exemplo:

{0,0,0,1,2,3,4}

O algoritmo iria ler primeiro que havia três zeros no início, e depois a saída RLE que codifica para eles que a especificação utilizado, e, em seguida, a partir do quarto elemento, lia que incrementando RLE cobriria o 1,2' , 3,4' suficientemente bem e compressa que antes de retornar.

O problema resumida é que, enquanto tentando descobrir o melhor especificação para uso, a rotina é muito lento mesmo em pequenas (20-30) matrizes de bytes. Alguém pode ajudar com dicas sobre como eu poderia olhar para otimizar isso, ou se há mais alguma informação que eu poderia fornecer a ajuda?

Answer 1

Parece que você está tentando fazer é trabalhar para fora um grande número de possibilidades de compressão para todos os segmentos possíveis (vamos chamar seu comprimento variável 1-64K bloqueia segmentos) do arquivo. Corrija-me se eu estiver errado, mas você está trabalhando para fora o melhor de compressão para o primeiro segmento a partir das seguintes opções (método 0 é descompactado):

• método de compressão de 0, comprimento de um byte.
• método de compressão de um, comprimento de um byte.
• :::::
• método de compressão 6, comprimento de 1 byte.
• método de compressão de 0, comprimento de 2 bytes.
• método de compressão de um, comprimento de 2 bytes.
• :::::
• método de compressão de 6, de comprimento 65534 bytes.
• método de compressão de 0, comprimento de 65535 bytes.
• método de compressão de um, comprimento de 65535 bytes.
• método de compressão 2, comprimento de 65535 bytes.
• método de compressão 3, o comprimento 65535 bytes.
• método de compressão 4, comprimento de 65535 bytes.
• método de compressão 5, comprimento de 65535 bytes.
• método de compressão de 6, de comprimento 65535 bytes.

Isso vai levar uma quantidade enorme de tempo (cerca de 420.000 tentativas de compressão por segmento). Se é isso que você está fazendo, você vai ser melhor escolher um único tamanho do segmento (por exemplo, 64K) e aplicação de cada um dos métodos de compressão de sete a ele para escolher o melhor. Em seguida, para cada segmento, a saída do "modo" bytes seguido pelos dados comprimidos.