¿Cómo decodificar el código huffman rápidamente?

Question

He implementated a simple compressor utilizando el código de Huffman pura bajo Windows.But No sé mucho acerca de cómo decodificar el archivo comprimido rápidamente, mi mal algoritmo es:

Enumerar todo el código Huffman en la tabla de códigos y luego compararlo con los bits en el archivo comprimido. Resulta un resultado horrible: la descompresión de un archivo de 3MB necesitaría 6 horas.

¿Podría proporcionar un algoritmo mucho más eficiente? ¿Debo usar Hash o algo así?

actualización: he implementated the decoder con tabla de estado, sobre la base de mi amigo advice.I de Lin que este método debe ser mejor que el árbol travesal Huffman, 3 MB dentro de 6s.

gracias.

Answer 1

Una forma de optimizar el enfoque árbol binario es utilizar una tabla de consulta. Organiza la tabla para que pueda buscar un patrón de bits codificado particular directamente, lo que permite el máximo ancho de bits posible de cualquier código.

Dado que la mayoría de los códigos no utilizan el ancho máximo completo, se incluyen en varias ubicaciones de la tabla, una ubicación para cada combinación de los bits no utilizados. La tabla indica cuántos bits descartar de la entrada, así como la salida decodificada.

Si el código más largo es demasiado largo, por lo que la tabla no es práctica, un compromiso es utilizar un árbol de búsquedas de subíndices de ancho fijo más pequeños. Por ejemplo, puede usar una tabla de 256 elementos para manejar un byte. Si el código de entrada es más de 8 bits, la entrada de la tabla indica que la decodificación está incompleta y lo dirige a una tabla que maneja el siguiente hasta 8 bits. Las tablas más grandes intercambian memoria por la velocidad: 256 elementos es probablemente demasiado pequeño.

Creo que este enfoque general se llama "tablas de prefijos", y es lo que está haciendo el código citado de BobMcGees. Una diferencia probable es que algunos algoritmos de compresión requieren que la tabla de prefijos se actualice durante la descompresión; esto no es necesario para Huffman simple.IIRC, lo vi por primera vez en un libro sobre formatos de archivos gráficos en mapas de bits que incluía GIF, algún tiempo antes del pánico de patentes.

Debería ser fácil precalcular una tabla de búsqueda completa, un equivalente de hashta o un árbol de tablas pequeñas de un modelo de árbol binario. El árbol binario sigue siendo la representación clave del código; esta tabla de búsqueda es solo una optimización.

Answer 2

¿Por qué no utilizar el algoritmo de descompresión en el mismo módulo de origen? Parece ser un algoritmo decente.

Answer 3

La forma típica de descomprimir un código de Huffman es utilizando un árbol binario. Inserta sus códigos en el árbol, de modo que cada bit en un código representa una rama a la izquierda (0) o a la derecha (1), con bytes decodificados (o los valores que tenga) en las hojas.

La decodificación es entonces solo una cuestión de lectura de bits del contenido codificado, caminando por el árbol para cada bit. Cuando llegue a una hoja, emita ese valor decodificado y continúe leyendo hasta que la entrada se agote.

Actualización:this page describe la técnica, y tiene gráficos sofisticados.

Answer 4

¿Por qué no echarle un vistazo a cómo lo hace el GZIP source, específicamente el código de descompresión de Huffman específicamente en unpack.c? Está haciendo exactamente lo que eres, excepto que lo está haciendo mucho, mucho más rápido.

Por lo que puedo decir, está usando una matriz de búsqueda y operaciones de cambio/máscara que operan en palabras completas para correr más rápido. Código bastante denso sin embargo.

EDIT: aquí es la fuente completa

/* 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; 
} 

Answer 5

Puede llevar a cabo una especie de búsqueda por lotes en el árbol de búsqueda habitual Huffmann:

1. La elección de una profundidad de bits (lo llaman profundidad n); esto es una compensación entre la velocidad, la memoria y la inversión de tiempo para construir tablas;
2. Cree una tabla de búsqueda para todos 2^n cadenas de bits de longitud n. Cada entrada puede codificar varios tokens completos; normalmente también quedarán algunos bits que son solo un prefijo de los códigos de Huffman: para cada uno de ellos, haga un enlace a una tabla de búsqueda adicional para ese código;
3. Genere las tablas de búsqueda adicionales. El número total de tablas es como máximo uno menos que el número de entradas codificadas en el árbol de Huffmann.

Elegir una profundidad que es un múltiplo de cuatro, por ejemplo, profundidad 8, es una buena opción para operaciones de cambio de bit.

PostScript Esto difiere de la idea en el comentario de potatoswatter sobre la respuesta de desenredo y de la respuesta de Steve314 en el uso de varias tablas: esto significa que todas las operaciones de búsqueda n bit se pone en uso, por lo que debe ser más rápido, pero las marcas la construcción y la búsqueda de tablas son mucho más complicadas y consumirán mucho más espacio para una profundidad determinada.