Como decodificar código Huffman rapidamente?
-
19-09-2019 - |
Pergunta
Eu implementated um compressor simples usando o código Huffman puro sob Windows.But Eu não sei muito sobre como decodificar o arquivo compactado rapidamente, meu mau algoritmo é:
enumerar todas as código Huffman na tabela de código, em seguida, compará-lo com os bits na file.It comprimido despeja resultado horrível:. Descomprimir arquivo de 3MB precisaria de 6 horas
Você poderia fornecer um algoritmo muito mais eficiente? Devo usar Hash ou algo assim?
Atualizar : Eu tenho implementated descodificador com tabela de estado, baseada em meu amigo advice.I de Lin acha que este método deve ser melhor do que a árvore travesal Huffman, 3MB dentro 6s.
obrigado.
Solução
Uma forma de otimizar a abordagem binário-árvore é usar uma tabela de pesquisa. -Lo a organizar a mesa de modo que você pode olhar para cima um pouco de padrão codificado determinado diretamente, permitindo a máxima de bits de largura possível de qualquer código.
Uma vez que a maioria dos códigos não usar a largura máxima cheia, eles estão incluídos em vários locais na tabela - um local para cada combinação dos bits não utilizados. A tabela indica quantos bits para descartar a partir da entrada, bem como a saída decodificado.
Se o código mais longo é muito longo, por isso a tabela é impraticável, um compromisso é usar uma árvore de menores pesquisas-de largura fixa subscrito. Por exemplo, você pode usar uma tabela de 256 itens para lidar com um byte. Se o código de entrada é mais de 8 bits, a entrada da tabela indica que a decodificação é incompleta e direciona para uma tabela que manipula o próximo up-to 8 bits. tabelas maiores comércio de memória para a velocidade - 256 itens é provavelmente muito pequena
.Eu acredito que esta abordagem geral é chamado de "tabelas prefixo", e é o que BobMcGees código citado está fazendo. A diferença provável é que alguns algoritmos de compressão requerem tabela de prefixo a ser actualizado durante a descompressão - isso não é necessário para simples Huffman. IIRC, eu vi pela primeira vez em um livro sobre formatos de arquivos gráficos bitmap que incluiu GIF, algum tempo antes de o pânico patente.
Deve ser fácil para precalculate quer uma mesa cheia de pesquisa, um equivalente hashtable ou uma árvore-de-pequenas mesas a partir de um modelo de árvore binária. A árvore binária ainda é a representação chave do código -. Esta tabela de pesquisa é apenas otimização
Outras dicas
Por que não dar uma olhada em como o GZIP fonte faz, especificamente o código de descompressão Huffman em especificamente unpack.c? É fazendo exatamente o que você é, exceto que ele está fazendo isso muito, muito mais rápido.
Do que eu posso dizer, ele está usando uma matriz de pesquisa e shift / mascarar operações operando em palavras inteiras para correr mais rápido. código muito denso embora.
EDIT: aqui está a fonte completo
/* unpack.c -- decompress files in pack format.
* Copyright (C) 1992-1993 Jean-loup Gailly
* This is free software; you can redistribute it and/or modify it under the
* terms of the GNU General Public License, see the file COPYING.
*/
#ifdef RCSID
static char rcsid[] = "$Id: unpack.c,v 1.4 1993/06/11 19:25:36 jloup Exp $";
#endif
#include "tailor.h"
#include "gzip.h"
#include "crypt.h"
#define MIN(a,b) ((a) <= (b) ? (a) : (b))
/* The arguments must not have side effects. */
#define MAX_BITLEN 25
/* Maximum length of Huffman codes. (Minor modifications to the code
* would be needed to support 32 bits codes, but pack never generates
* more than 24 bits anyway.)
*/
#define LITERALS 256
/* Number of literals, excluding the End of Block (EOB) code */
#define MAX_PEEK 12
/* Maximum number of 'peek' bits used to optimize traversal of the
* Huffman tree.
*/
local ulg orig_len; /* original uncompressed length */
local int max_len; /* maximum bit length of Huffman codes */
local uch literal[LITERALS];
/* The literal bytes present in the Huffman tree. The EOB code is not
* represented.
*/
local int lit_base[MAX_BITLEN+1];
/* All literals of a given bit length are contiguous in literal[] and
* have contiguous codes. literal[code+lit_base[len]] is the literal
* for a code of len bits.
*/
local int leaves [MAX_BITLEN+1]; /* Number of leaves for each bit length */
local int parents[MAX_BITLEN+1]; /* Number of parents for each bit length */
local int peek_bits; /* Number of peek bits currently used */
/* local uch prefix_len[1 << MAX_PEEK]; */
#define prefix_len outbuf
/* For each bit pattern b of peek_bits bits, prefix_len[b] is the length
* of the Huffman code starting with a prefix of b (upper bits), or 0
* if all codes of prefix b have more than peek_bits bits. It is not
* necessary to have a huge table (large MAX_PEEK) because most of the
* codes encountered in the input stream are short codes (by construction).
* So for most codes a single lookup will be necessary.
*/
#if (1<<MAX_PEEK) > OUTBUFSIZ
error cannot overlay prefix_len and outbuf
#endif
local ulg bitbuf;
/* Bits are added on the low part of bitbuf and read from the high part. */
local int valid; /* number of valid bits in bitbuf */
/* all bits above the last valid bit are always zero */
/* Set code to the next 'bits' input bits without skipping them. code
* must be the name of a simple variable and bits must not have side effects.
* IN assertions: bits <= 25 (so that we still have room for an extra byte
* when valid is only 24), and mask = (1<<bits)-1.
*/
#define look_bits(code,bits,mask) \
{ \
while (valid < (bits)) bitbuf = (bitbuf<<8) | (ulg)get_byte(), valid += 8; \
code = (bitbuf >> (valid-(bits))) & (mask); \
}
/* Skip the given number of bits (after having peeked at them): */
#define skip_bits(bits) (valid -= (bits))
#define clear_bitbuf() (valid = 0, bitbuf = 0)
/* Local functions */
local void read_tree OF((void));
local void build_tree OF((void));
/* ===========================================================================
* Read the Huffman tree.
*/
local void read_tree()
{
int len; /* bit length */
int base; /* base offset for a sequence of leaves */
int n;
/* Read the original input size, MSB first */
orig_len = 0;
for (n = 1; n <= 4; n++) orig_len = (orig_len << 8) | (ulg)get_byte();
max_len = (int)get_byte(); /* maximum bit length of Huffman codes */
if (max_len > MAX_BITLEN) {
error("invalid compressed data -- Huffman code > 32 bits");
}
/* Get the number of leaves at each bit length */
n = 0;
for (len = 1; len <= max_len; len++) {
leaves[len] = (int)get_byte();
n += leaves[len];
}
if (n > LITERALS) {
error("too many leaves in Huffman tree");
}
Trace((stderr, "orig_len %ld, max_len %d, leaves %d\n",
orig_len, max_len, n));
/* There are at least 2 and at most 256 leaves of length max_len.
* (Pack arbitrarily rejects empty files and files consisting of
* a single byte even repeated.) To fit the last leaf count in a
* byte, it is offset by 2. However, the last literal is the EOB
* code, and is not transmitted explicitly in the tree, so we must
* adjust here by one only.
*/
leaves[max_len]++;
/* Now read the leaves themselves */
base = 0;
for (len = 1; len <= max_len; len++) {
/* Remember where the literals of this length start in literal[] : */
lit_base[len] = base;
/* And read the literals: */
for (n = leaves[len]; n > 0; n--) {
literal[base++] = (uch)get_byte();
}
}
leaves[max_len]++; /* Now include the EOB code in the Huffman tree */
}
/* ===========================================================================
* Build the Huffman tree and the prefix table.
*/
local void build_tree()
{
int nodes = 0; /* number of nodes (parents+leaves) at current bit length */
int len; /* current bit length */
uch *prefixp; /* pointer in prefix_len */
for (len = max_len; len >= 1; len--) {
/* The number of parent nodes at this level is half the total
* number of nodes at parent level:
*/
nodes >>= 1;
parents[len] = nodes;
/* Update lit_base by the appropriate bias to skip the parent nodes
* (which are not represented in the literal array):
*/
lit_base[len] -= nodes;
/* Restore nodes to be parents+leaves: */
nodes += leaves[len];
}
/* Construct the prefix table, from shortest leaves to longest ones.
* The shortest code is all ones, so we start at the end of the table.
*/
peek_bits = MIN(max_len, MAX_PEEK);
prefixp = &prefix_len[1<<peek_bits];
for (len = 1; len <= peek_bits; len++) {
int prefixes = leaves[len] << (peek_bits-len); /* may be 0 */
while (prefixes--) *--prefixp = (uch)len;
}
/* The length of all other codes is unknown: */
while (prefixp > prefix_len) *--prefixp = 0;
}
/* ===========================================================================
* Unpack in to out. This routine does not support the old pack format
* with magic header \037\037.
*
* IN assertions: the buffer inbuf contains already the beginning of
* the compressed data, from offsets inptr to insize-1 included.
* The magic header has already been checked. The output buffer is cleared.
*/
int unpack(in, out)
int in, out; /* input and output file descriptors */
{
int len; /* Bit length of current code */
unsigned eob; /* End Of Block code */
register unsigned peek; /* lookahead bits */
unsigned peek_mask; /* Mask for peek_bits bits */
ifd = in;
ofd = out;
read_tree(); /* Read the Huffman tree */
build_tree(); /* Build the prefix table */
clear_bitbuf(); /* Initialize bit input */
peek_mask = (1<<peek_bits)-1;
/* The eob code is the largest code among all leaves of maximal length: */
eob = leaves[max_len]-1;
Trace((stderr, "eob %d %x\n", max_len, eob));
/* Decode the input data: */
for (;;) {
/* Since eob is the longest code and not shorter than max_len,
* we can peek at max_len bits without having the risk of reading
* beyond the end of file.
*/
look_bits(peek, peek_bits, peek_mask);
len = prefix_len[peek];
if (len > 0) {
peek >>= peek_bits - len; /* discard the extra bits */
} else {
/* Code of more than peek_bits bits, we must traverse the tree */
ulg mask = peek_mask;
len = peek_bits;
do {
len++, mask = (mask<<1)+1;
look_bits(peek, len, mask);
} while (peek < (unsigned)parents[len]);
/* loop as long as peek is a parent node */
}
/* At this point, peek is the next complete code, of len bits */
if (peek == eob && len == max_len) break; /* end of file? */
put_ubyte(literal[peek+lit_base[len]]);
Tracev((stderr,"%02d %04x %c\n", len, peek,
literal[peek+lit_base[len]]));
skip_bits(len);
} /* for (;;) */
flush_window();
Trace((stderr, "bytes_out %ld\n", bytes_out));
if (orig_len != (ulg)bytes_out) {
error("invalid compressed data--length error");
}
return OK;
}
A forma habitual para descomprimir um código Huffman está usando uma árvore binária. Inserir os seus códigos na árvore, de modo que cada bit em um código representa um ramo, quer à esquerda (0) ou direito (1), com bytes decodificados (ou o que valoriza você tem) nas folhas.
Decoding é, então, apenas um caso de leitura de pedaços do conteúdo codificado, caminhando a árvore para cada bit. Quando você chegar a uma folha, emitem esse valor decodificado, e manter a leitura até que a entrada está esgotado.
Update: desta página descreve a técnica, e tem fantasia gráficos.
Você pode executar um tipo de pesquisa de lote no habitual lookup árvore Huffmann:
- Escolhendo uma profundidade de bits (chamemos-lhe profundidade n ); este é um trade-off entre velocidade, memória e investimento de tempo para mesas construto;
- Criar uma tabela de referência para todos 2 ^ n strings de comprimento bit n . Cada entrada pode codificar várias fichas completas; haverá comumente também ser alguns pedaços que sobraram que são apenas um prefixo de códigos Huffman: para cada um deles, fazer um link para uma tabela mais pesquisa para que o código;
- construir as novas tabelas de pesquisa. O número total de tabelas é, no máximo, um a menos que o número de entradas codificadas na árvore Huffmann.
A escolha de uma profundidade que é um múltiplo de quatro, por exemplo, a profundidade 8, é um bom ajuste para operações de bit mudando.
Postscript Isso difere da idéia no comentário de potatoswatter sobre a resposta de descontrair e de resposta de Steve314 em usar várias tabelas: isto significa que todo o n bits pesquisa é put para uso, por isso deve ser mais rápido, mas torna a construção de mesa e lookup significativamente mais complicado, e vai consumir muito mais espaço para uma determinada profundidade.
Por que não usar o algoritmo descomprimir no mesmo módulo de origem? Parece ser um algoritmo decente.