Wie Huffman-Code schnell zu entschlüsseln?

Question

Ich habe implementated ein einfacher Kompressor mit reinem huffman-Code unter Windows.But ich weiß nicht viel darüber, wie die komprimierte Datei schnell zu entschlüsseln, mein schlechter Algorithmus ist:

Aufzählen all der Huffman-Code in der Code-Tabelle dann vergleichen Sie es mit den Bits in dem komprimierten file.It stellt sich heraus, schreckliche Ergebnis:. Dekomprimieren 3MB Datei 6 Stunden benötigen würde

Könnten Sie einen viel effizienteren Algorithmus? Soll ich Hash oder so etwas?

Aktualisieren : Ich habe implementated der Decoder mit Statustabelle, basierend auf meinen Freund Lins advice.I denke, diese Methode besser sein sollte als travesal huffman-Baum, 3MB innerhalb 6s.

Dank.

Answer 1

Eine Möglichkeit, den Binärbaum-Ansatz zu optimieren, ist eine Lookup-Tabelle zu verwenden. Sie ordnen den Tisch, so dass Sie direkt ein bestimmtes codierten Bit-Muster sehen können, so dass für die maximal mögliche Bit-Breite von Code.

Da die meisten Codes nicht die volle maximale Breite verwenden, werden sie an mehreren Stellen in der Tabelle enthalten - ein Ort für jede Kombination der nicht verwendeten Bits. Die Tabelle gibt an, wie viele Bits von dem Eingang zu verwerfen sowie der decodierte Ausgabe.

Wenn der längste Code zu lang ist, so dass die Tabelle nicht praktikabel ist, ist ein Kompromiss, einen Baum von kleineren zu verwenden, mit festen Breite-Index-Lookups. Zum Beispiel können Sie eine 256-Postentabelle verwenden, um einen Byte zu behandeln. Wenn der Eingangscode mehr als 8 Bits ist, zeigt der Tabelleneintrag, Decodierung unvollständig ist und leitet sie zu einer Tabelle, die Griffe der nächste auf dem 8 Bit. Größere Tabellen handeln Speicher für Geschwindigkeit - 256 Artikel wahrscheinlich zu klein ist

.

Ich glaube, dass dieser allgemeine Ansatz wird als „Präfix-Tabellen“, und ist das, was BobMcGees zitierte Code tut. Ein wahrscheinlicher Unterschied besteht darin, dass einige Komprimierungsalgorithmen erfordern die Präfix-Tabelle während der Dekompression aktualisiert werden - dies ist nicht für einfachen Huffman benötigt wird. IIRC, ich zum ersten Mal sah es in einem Buch über Bitmap-Grafiken Dateiformate, die GIF enthalten, einige Zeit vor dem Patent Panik.

Es sollte einfach sein, entweder eine vollständige Lookup-Tabelle, eine Hash-Tabelle Äquivalent oder ein Baum-of-small-Tabellen von einem binären Baummodell vorauszuberechnen. Der binäre Baum ist immer noch der Schlüssel Darstellung des Codes -. Diese Lookup-Tabelle ist nur Optimierung

Answer 2

Warum nicht einen Blick auf, wie die GZIP Quelle es der Fall ist, speziell die Huffman-Code Dekompression in speziell unpack.c? Es ist genau das, was Sie sind, außer es es viel, viel schneller macht.

Von dem, was ich sagen kann, ist es mit einem Lookup-Array und Schalt- / maskieren Operationen auf ganze Worten Betrieb schneller zu laufen. Ziemlich dicht Code though.

EDIT: Hier ist die komplette Quelle

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

Der typische Weg, um einen Huffman-Code dekomprimieren wird mit einem binären Baum. Sie fügen Ihre Codes in dem Baum, so dass jedes Bit in einem Code, um einen Zweig steht entweder nach links (0) oder rechts (1), mit decodierten Bytes (oder was auch immer Werten, die Sie haben) in den Blättern.

Die Decodierung ist dann nur ein Fall von Bits aus dem codierten Inhalt zu lesen, für jedes Bit den Baum zu Fuß. Wenn Sie erreichen ein Blatt, emit dieser Wert decodiert und lesen Sie weiter, bis der Eingang erschöpft ist.

Update: diese Seite die Technik beschreibt, und hat phantastische Graphiken.

Answer 4

Sie können auf dem üblichen Huffmann-Baum-Lookup eine Art Batch-Lookup ausführen:

1. eine Bittiefe Wahl (nennen wir es Tiefe n ); dies ist ein Kompromiss zwischen Geschwindigkeit, Speicher und Zeitaufwand zu konstruieren Tabellen;
2. Erstellen Sie eine Lookup-Tabelle für alle 2 ^ n Bitstrings der Länge n . Jeder Eintrag kann mehrere vollständige Token codieren; es wird übrig bleiben häufig auch einige Bits sein, dass nur ein Präfix von Huffman-Codes sind: für jeden von ihnen, für diesen Code einen Link zu einer weiteren Lookup-Tabelle machen;
3. Erstellen Sie die weiteren Lookup-Tabellen. Die Gesamtzahl der Tabellen ist höchstens eine weniger als die Anzahl der in der Huffmann Baum codierten Einträge.

Auswählen einer Tiefe, die ein Vielfaches von vier ist, beispielsweise, Tiefe 8, ist ein guter Sitz für Bitverschiebung Operationen.

Postscript Dies unterscheidet sich von der Idee in potatoswatter Kommentar auf Abroller Antwort und von Steve314 Antwort in mehreren Tabellen verwenden: Dies bedeutet, dass alle die n -Bit-Lookup ist put Gebrauch, sollte schneller so sein, aber Tischkonstruktion und nachschlagen wesentlich heikler macht, und wird viel mehr Platz für eine gegebene Tiefe verbrauchen.

Answer 5

Warum verwenden Sie nicht den decompress Algorithmus in der gleichen Quelle-Modul? Es scheint ein anständiger Algorithmus zu sein.