自适应 Huffman 编码的实现代码

由于项目已经中止，而且这些代码不牵涉到自适应 Huffman 编码以外的内容或改进，所以现在给出实现的代码。

较早的记录：http://blog.chinaunix.net/u/24581/showart_198631.html

注：压缩数据的“长度”是以 bit 计的，而原始数据的长度是以 byte 计算的。

头文件：DynamicHuffman.h

#pragma once

#include <list>
using namespace std;

class CDynamicHuffman
{
    struct Node;
    typedef Node *Iterator;

    struct Node
    {
        Iterator Left, Right, Parent;
        int Weight;
        int Symbol;

        void Set(Iterator left, Iterator right, Iterator parent, int weight, int symbol)
        {
            Left = left;
            Right = right;
            Parent = parent;
            Weight = weight;
            Symbol = symbol;
        }
    };

    static int const NYT = 256;

    Node Tree[511];
    int TreeSize;
    Iterator Symbols[257];
    int CharNumber;
public:
    CDynamicHuffman();
    ~CDynamicHuffman();
public:
    bool Compress(char* dest, int& destLen, const char* src, int srcLen);
    bool Decompress(char* dest, int& destLen, const char* src, int srcLen);

private:
    void Clear();
    void Initialize();

    void CharToBit(unsigned char ch, unsigned int& bit, int& len);
    void BitToChar(unsigned int bit, int& len, unsigned char& ch);

    void GetNYTCode(unsigned int& bit, int& len);

    void PushChar(unsigned char ch);

    void SwapNode(Iterator a, Iterator b);

    void BlockJump(Iterator& node);
private:
    void PushBit(unsigned char* dest, int& len, unsigned int bit, int bitLen);
    void PopBit(const unsigned char* src, int len, int& pos, unsigned int& bit, int& bitLen);
};


库文件：DynamicHuffman.cpp

#include ".\dynamichuffman.h"

#include <vector>
using namespace std;

CDynamicHuffman::CDynamicHuffman()
{
}

CDynamicHuffman::~CDynamicHuffman()
{
}

void CDynamicHuffman::Clear()
{
    TreeSize = 0;
    for (int i = 0; i <= NYT; ++i)
        Symbols[i] = NULL;
    CharNumber = 0;
}

bool CDynamicHuffman::Compress(char* _dest, int& destLen, const char* _src, int srcLen)
{
    unsigned char* dest = (unsigned char*)_dest;
    const unsigned char* src = (const unsigned char*)_src;

    Initialize();
    int len = 0;
    for (const unsigned char *p = src, *pend = src + srcLen; p != pend; ++p)
    {
        unsigned int bit;
        int bitLen;
        CharToBit(*p, bit, bitLen);
        PushChar(*p);

        if (len + bitLen > destLen)
            return false;

        PushBit(dest, len, bit, bitLen);
    }
    destLen = len;
    return true;
}

bool CDynamicHuffman::Decompress(char* _dest, int& destLen, const char* _src, int srcLen)
{
    unsigned char* dest = (unsigned char*)_dest;
    const unsigned char* src = (const unsigned char*)_src;

    Initialize();
    int len = 0, pos = 0;
    unsigned int bit = 0;
    int bitLen = 0;
    while ((pos < srcLen) || (bitLen > 0))
    {
        unsigned char ch;
        PopBit(src, srcLen, pos, bit, bitLen);
        BitToChar(bit, bitLen, ch);

        if (++len > destLen)
            return false;

        PushChar(ch);

        *dest++ = ch;
    }
    destLen = len;
    return true;
}

void CDynamicHuffman::Initialize()
{
    Clear();

    Tree[TreeSize++].Set(NULL, NULL, NULL, 0, NYT);

    Symbols[NYT] = Tree;

    CharNumber = 0;
}

void CDynamicHuffman::CharToBit(unsigned char ch, unsigned int& bit, int& len)
{
    int c = ch;
    if (Symbols[c] == NULL)
        c = NYT;

    Iterator n = Symbols[c];
    bit = 0;
    len = 0;
    while (n != Tree)
    {
        Iterator p = n->Parent;
        bit |= (p->Right == n) << len++;
        n = p;
    }
    if (c == NYT)
    {
        bit = (bit << 8) | ch;
        len += 8;
    }
}

void CDynamicHuffman::BitToChar(unsigned int bit, int& len, unsigned char& ch)
{
    unsigned int mask = 1 << (len - 1);
    Iterator node = Tree;
    while (node->Symbol == -1)
    {
        if (bit & mask)
            node = node->Right;
        else
            node = node->Left;
        --len;
        mask >>= 1;
    }

    if (node->Symbol == NYT)
    {
        len -= 8;
        ch = (bit >> len) & 0xFF;
    }
    else
    {
        ch = node->Symbol;
    }
}

void CDynamicHuffman::GetNYTCode(unsigned int& bit, int& len)
{
    Iterator n = Symbols[NYT];
    bit = 0;
    len = 0;
    while (n != Tree)
    {
        bit |= (n->Left != NULL) << len++;
        n = n->Parent;
    }
}

void CDynamicHuffman::PushChar(unsigned char ch)
{
    int c = (unsigned char)ch;
    Iterator cur;
    if (Symbols[c] == NULL)
    {
        ++CharNumber;
        cur = Symbols[NYT];
        if (CharNumber == 256)
        {
            cur->Symbol = c;
            cur->Weight = 1;

            Symbols[c] = cur;

            Symbols[NYT] = NULL;
        }
        else
        {
            cur->Symbol = -1;
            cur->Weight = 1;

            Tree[TreeSize].Set(NULL, NULL, cur, 1, c);
            Iterator node = Tree + TreeSize++;
            Symbols[c] = node;

            Tree[TreeSize].Set(NULL, NULL, cur, 0, NYT);
            Iterator nyt = Tree + TreeSize++;
            Symbols[NYT] = nyt;

            cur->Left = nyt;
            cur->Right = node;
        }
    }
    else
    {
        cur = Symbols[c];
        BlockJump(cur);
        ++(cur->Weight);
    }

    while (cur != Tree)
    {
        cur = cur->Parent;

        BlockJump(cur);
        ++(cur->Weight);
    }
}

void CDynamicHuffman::SwapNode(CDynamicHuffman::Iterator a, CDynamicHuffman::Iterator b)
{
    if (a->Left != NULL)
        a->Left->Parent = b;
    if (a->Right != NULL)
        a->Right->Parent = b;

    if (b->Left != NULL)
        b->Left->Parent = a;
    if (b->Right != NULL)
        b->Right->Parent = a;

    swap(*a, *b);
    swap(a->Parent, b->Parent);
    if (a->Symbol != -1)
        Symbols[a->Symbol] = a;
    if (b->Symbol != -1)
        Symbols[b->Symbol] = b;
}

void CDynamicHuffman::BlockJump(CDynamicHuffman::Iterator &node)
{
    Iterator head = node;
    for (; head != Tree; --head)
    {
        Iterator prev = head;
        --prev;
        if (prev->Weight != node->Weight)
            break;
    }

    if ((head != node) && (node->Parent != head))
    {
        SwapNode(head, node);
        node = head;
    }
}

void CDynamicHuffman::PushBit(unsigned char* dest, int& len, unsigned int bit, int bitLen)
{
    while (bitLen > 0)
    {
        unsigned char* byte = dest + len / 8;
        int bitLeft = 8 - len % 8;

        *byte = (*byte & (0xFF << bitLeft)) | ((bit >> (bitLen - 1)) & 0x1) << (bitLeft - 1);
        ++len;
        --bitLen;
    }
}

void CDynamicHuffman::PopBit(const unsigned char* src, int len, int& pos, unsigned int& bit, int& bitLen)
{
    while ((pos < len) && (bitLen < 32))
    {
        const unsigned char* byte = src + pos / 8;
        int bitLeft = 8 - pos % 8;

        bit = (bit << 1) | ((*byte >> (bitLeft - 1)) & 0x1);
        ++bitLen;
        ++pos;
    }
}