Декодирование файла Хаффмана из канонической формы

Вам не нужно создавать коды или дерево, чтобы декодировать канонические коды. Все, что вам нужно, это список символов по порядку и количество символов в каждой длине кода. Под «по порядку» я подразумеваю сортировку по длине кода от самой короткой до самой длинной, а в пределах каждой длины кода — по значению символа.

Поскольку канонические коды в пределах длины кода представляют собой последовательные двоичные целые числа, вы можете просто выполнить целочисленное сравнение, чтобы увидеть, попадают ли биты, которые у вас есть, в этот диапазон кода, и, если это так, целочисленное вычитание, чтобы определить, какой это символ.

Ниже приведен код из puff.c (с небольшими изменениями ), чтобы наглядно показать, как это делается. bits(s, 1) возвращает следующий бит из потока. (Это предполагает, что всегда есть следующий бит.) h->count[len] — это количество символов, закодированных кодами длины len, где len находится в 0..MAXBITS. Если вы сложите h->count[1], h->count[2], ..., h->count[MAXBITS], это будет общее количество закодированных символов и длина массива h->symbol[]. Первые h->count[1] символов в h->symbol[] имеют длину 1. Следующие h->count[2] символов в h->symbol[] имеют длину 2. И так далее.

Значения в массиве h->count[], если они правильные, ограничены, чтобы не превысить возможное количество кодов, которые могут быть закодированы в len битах. Он может быть дополнительно ограничен для представления полного кода, т. Е. Нет последовательности битов, которая остается неопределенной, и в этом случае decode() не может возвращать ошибку (-1). Чтобы код был полным и не было превышено количество подписок, сумма h->count[len] << (MAXBITS - len) по всем len должна равняться 1 << MAXBITS.

Простой пример: если мы кодируем e одним битом, t двумя битами, а a и o тремя битами, то h->count[] будет {0, 1, 1, 2} (первое значение, h->count[0] не используется), а h->symbol[] будет {'e','t','a','o'}. Тогда код e будет 0, код t будет 10, a будет 110, а o будет 111.

#define MAXBITS 15              /* maximum bits in a code */

struct huffman {
    short *count;       /* number of symbols of each length */
    short *symbol;      /* canonically ordered symbols */
};

int decode(struct state *s, const struct huffman *h)
{
    int len;            /* current number of bits in code */
    int code;           /* len bits being decoded */
    int first;          /* first code of length len */
    int count;          /* number of codes of length len */
    int index;          /* index of first code of length len in symbol table */

    code = first = index = 0;
    for (len = 1; len <= MAXBITS; len++) {
        code |= bits(s, 1);             /* get next bit */
        count = h->count[len];
        if (code - count < first)       /* if length len, return symbol */
            return h->symbol[index + (code - first)];
        index += count;                 /* else update for next length */
        first += count;
        first <<= 1;
        code <<= 1;
    }
    return -1;                          /* ran out of codes */
}

Ваша карта содержит соответствующую информацию, но она отображает символы в коды. Тем не менее, данные, которые вы пытаетесь декодировать, содержат коды. Таким образом, ваша карта не может использоваться для эффективного чтения символов, соответствующих кодам, поскольку метод поиска ожидает символ. Поиск кодов и получение соответствующего символа будет линейным поиском.

Вместо этого вы должны реконструировать дерево Хаффмана, которое вы построили для шага сжатия. Значения частоты внутренних узлов здесь не имеют значения, но вам понадобятся листовые узлы в правильных позициях. Вы можете создавать дерево на лету, когда читаете заголовок файла. Сначала создайте пустое дерево. Для каждого прочитанного сопоставления символа с кодом создайте соответствующие узлы в дереве. Например. если символ «D» был сопоставлен с кодом 101, то убедитесь, что в корне есть правый дочерний узел, у которого есть левый дочерний узел, у которого есть правый дочерний узел, который содержит символ «D», создавая узлы, если они отсутствовали.

Используя это дерево, вы можете затем декодировать поток следующим образом (псевдокод, предполагая, что получение правильного дочернего элемента соответствует добавлению 1 к коду):

// use a node variable to remember the position in the tree while reading bits
node n = tree.root
while(stream not fully read) {
    read next bit into boolean b
    if (b == true) {
        n = n.rightChild
    } else {
        n = n.leftChild
    }
    // check whether we are in a leaf node now
    if (n.leftChild == null && n.rightChild == null) {
        // n is a leaf node, thus we have read a complete code
        // add the corresponding symbol to the decoded output
        decoded.add(n.getSymbol())
        // reset the search
        n = tree.root
    }
}

Обратите внимание, что инвертирование вашей карты для получения правильного направления все равно приведет к субоптимальной производительности (по сравнению с обходом бинарного дерева), поскольку она не может использовать ограничение на меньшее пространство поиска, как это делает обход.