Comment décoder le code huffman rapidement?

Question

J'implementated un simple compresseur en utilisant le code pur sous huffman Windows.But Je ne sais pas grand-chose sur la façon de décoder rapidement le fichier compressé, mon mauvais algorithme est:

Énumérer tout le code huffman dans le tableau de code, puis le comparer avec les bits dans le file.It comprimé se révèle résultat horrible. Fichier 3MB décompresser aurait besoin de 6 heures

Pourriez-vous donner un algorithme beaucoup plus efficace? Dois-je utiliser Hash ou quelque chose?

Mise à jour : J'implementated le décodeur avec table d'état, sur la base de mon ami advice.I Lin pense que cette méthode devrait être meilleure que l'arbre travesal de huffman, 3MB dans les 6s.

merci.

Answer 1

Une façon d'optimiser l'approche binaire arbre est d'utiliser une table de consultation. Vous arrangez la table afin que vous puissiez regarder un peu-modèle encodée particulier directement, ce qui permet de la largeur de bit maximum de tout code.

Étant donné que la plupart des codes ne pas utiliser toute la largeur maximale, ils sont inclus à plusieurs endroits dans la table - un endroit pour chaque combinaison des bits non utilisés. Le tableau indique le nombre de bits à défausser de l'entrée ainsi que la sortie décodée.

Si le code le plus long est trop long, la table est peu pratique, un compromis est d'utiliser un arbre de plus petites largeur fixe lookups-indice. Par exemple, vous pouvez utiliser une table de 256 élément pour traiter un octet. Si le code d'entrée est plus de 8 bits, l'entrée de la table indique que le décodage est incomplet et vous dirige vers une table qui gère les prochaines mises à 8 bits. les grandes tables commerce mémoire pour la vitesse - 256 éléments est probablement trop petit

.

Je crois que cette approche générale est appelée « tables préfixe », et est ce que le code BobMcGees cité est en train de faire. Une différence probable est que certains algorithmes de compression nécessitent la table de préfixe à jour lors de la décompression - ce n'est pas nécessaire pour de simples Huffman. IIRC, je l'ai vu d'abord dans un livre sur les formats de fichiers graphiques bitmap qui inclus GIF, quelque temps avant la panique des brevets.

Il doit être facile à précalculer soit une table de consultation complète, un équivalent Hashtable, ou un arbre de petite-tables à partir d'un modèle d'arbre binaire. L'arbre binaire est toujours la représentation clé du code -. Ce tableau de recherche est juste optimisation

Answer 2

Pourquoi ne pas jeter un oeil à la façon dont la la source GZIP le fait, en particulier le code de décompression de Huffman spécifiquement unpack.c? Il est en train de faire exactement ce que vous êtes, sauf qu'il fait beaucoup, beaucoup plus rapide.

D'après ce que je peux dire, il utilise un tableau de recherche et les opérations de décalage / masque d'exploitation sur des mots entiers pour courir plus vite. Code assez dense cependant.

EDIT: voici la source complète

/* 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 3

La façon typique de décompresser un code de Huffman utilise un arbre binaire. Vous insérez vos codes dans l'arbre, de sorte que chaque bit dans un code représente une branche soit à gauche (0) ou à droite (1), avec des octets décodés (ou tout ce que vous avez des valeurs) dans les feuilles.

Décodage est alors juste un cas de lecture de bits du contenu codé, marchant l'arbre pour chaque bit. Lorsque vous atteignez une feuille, émettent cette valeur décodée, et continuez à lire jusqu'à ce que l'entrée soit épuisée.

Mise à jour: cette page décrit la technique, et a des graphiques de fantaisie.

Answer 4

Vous pouvez effectuer une sorte de recherche de lots sur la recherche dans l'arborescence habituelle Huffmann:

1. Choisir une profondeur de bit (appeler profondeur n ); c'est un compromis entre la vitesse, la mémoire et l'investissement de temps pour construire des tables;
2. Construire une table de consultation pour tous les 2 ^ n chaînes de bits de longueur n . Chaque entrée peut coder pour plusieurs jetons complets; il y aura souvent également quelques morceaux laissés qui ne sont un préfixe de codes de Huffman: pour chacun d'entre eux, faire un lien vers une autre table de consultation pour ce code;
3. Construire les autres tables de recherche. Le nombre total de tables est au plus un de moins que le nombre d'entrées codées dans l'arbre Huffmann.

Le choix d'une profondeur qui est un multiple de quatre, par exemple, de la profondeur 8, est un bon choix pour les opérations de décalage de bits.

Postscript Ceci diffère de l'idée dans le commentaire de potatoswatter sur la réponse de déroulage et de la réponse de Steve314 à l'aide de tables multiples: cela signifie que tous les n -bit recherche est mis à utiliser, devrait donc être plus rapide, mais rend la construction de table et recherche de manière significative plus délicate, et consommera beaucoup plus d'espace pour une profondeur donnée.

Answer 5

Pourquoi ne pas utiliser l'algorithme de décompression dans le même module source? Il semble être un algorithme décent.