Comment décoder le code de Huffman rapidement?

J’ai implémenté un compresseur simple en utilisant du code pur huffman sous Windows.Mais je ne sais pas trop comment décoder rapidement le fichier compressé, mon mauvais algorithme est:

Énumérez tout le code de Huffman dans la table de codes puis comparez-le avec les bits du fichier compressé. Le résultat est horrible: décompresser un fichier de 3 Mo nécessiterait 6 heures.

Pourriez-vous fournir un algorithme beaucoup plus efficace? Devrais-je utiliser Hash ou quelque chose?

Mise à jour : J’ai implémenté le décodeur avec la table d’état, basé sur les conseils de mon ami Lin. Je pense que cette méthode devrait être meilleure que l’arbre travesal huffman, 3 Mo dans les 6 secondes.

Merci.

Une façon d’optimiser l’approche de l’arborescence binary consiste à utiliser une table de recherche. Vous organisez la table de manière à pouvoir rechercher directement un motif de bits codé particulier, ce qui permet d’obtenir la largeur de bits maximale possible pour tout code.

Étant donné que la plupart des codes n’utilisent pas la largeur maximale complète, ils sont inclus à plusieurs emplacements dans le tableau – un emplacement pour chaque combinaison de bits inutilisés. Le tableau indique le nombre de bits à supprimer de l’entrée ainsi que de la sortie décodée.

Si le code le plus long est trop long et que la table est impraticable, un compromis consiste à utiliser un arbre contenant des recherches plus petites à indice de largeur fixe. Par exemple, vous pouvez utiliser un tableau de 256 éléments pour gérer un octet. Si le code d’entrée est supérieur à 8 bits, l’entrée de table indique que le décodage est incomplet et vous dirige vers une table qui gère les 8 bits suivants. Les tables plus grandes échangent de la mémoire pour la vitesse – 256 éléments est probablement trop petit.

Je crois que cette approche générale s’appelle “tables de préfixes” et c’est ce que fait le code cité par BobMcGees. Une différence probable est que certains algorithmes de compression nécessitent la mise à jour de la table de préfixes lors de la décompression – cela n’est pas nécessaire pour Huffman simple. IIRC, je l’ai d’abord vu dans un livre sur les formats de fichiers graphiques bitmap incluant du GIF, quelque temps avant la panique des brevets.

Il devrait être facile de précalculer une table de recherche complète, un équivalent de table de hachage ou une arborescence de petites tables à partir d’un modèle d’arbre binary. L’arbre binary est toujours la représentation clé du code – cette table de recherche est simplement une optimisation.

Pourquoi ne pas regarder comment la source GZIP fonctionne, en particulier le code de décompression Huffman dans spécifiquement unpack.c? Il fait exactement ce que vous êtes, sauf qu’il le fait beaucoup, beaucoup plus rapidement.

D’après ce que je peux dire, il utilise un tableau de recherche et des opérations de décalage / masque opérant sur des mots entiers pour s’exécuter plus rapidement. 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 redissortingbute 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< 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<> (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< 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< 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; } 

Le moyen typique de décompresser un code de Huffman consiste à utiliser un arbre binary. Vous insérez vos codes dans l’arborescence, de sorte que chaque bit d’un code représente une twig située à gauche (0) ou à droite (1), avec octets décodés (ou les valeurs que vous avez) dans les feuilles.

Le décodage consiste alors simplement à lire des bits à partir du contenu codé, en parcourant l’arbre pour chaque bit. Lorsque vous atteignez une feuille, émettez 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 présente des graphismes sophistiqués.

Vous pouvez effectuer une sorte de recherche par lot sur la recherche habituelle dans l’arbre de Huffmann:

  1. Choisir une profondeur de bits (appelez-la profondeur n ); c’est un compromis entre la vitesse, la mémoire et l’investissement en temps pour construire des tables;
  2. Construisez une table de recherche pour toutes les chaînes de 2 ^ n bits de longueur n . Chaque entrée peut coder plusieurs jetons complets; il restra généralement aussi quelques bits qui ne sont qu’un préfixe des codes de Huffman: pour chacun d’eux, créez un lien vers une autre table de recherche pour ce code;
  3. Construisez les autres tables de recherche. Le nombre total de tables est au plus égal à un de moins que le nombre d’entrées codées dans l’arbre de Huffmann.

Choisir une profondeur qui est un multiple de quatre, par exemple la profondeur 8, convient parfaitement aux opérations de transfert de bits.

Postscript Ceci diffère de l’idée contenue dans le commentaire de potatoswatter sur la réponse de undind et de Steve314 qui utilise plusieurs tables: cela signifie que toute la recherche à n bits est utilisée, elle devrait donc être plus rapide, mais rend la construction et la recherche de table significativement plus difficiles. consum beaucoup plus d’espace pour une profondeur donnée.

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