Huffman压缩文件结构

作者: Herixth | 来源:发表于2018-12-05 11:41 被阅读0次

Huffman压缩文件结构
2020-01-30 前端性能优化
Image Compression Tech
[Python&DS]- Python实现Huffman
Python批量压缩图片
数据结构(十四) -- Huffman树
Word2Vec中的数学原理
05-树9 Huffman Codes （30 分）
huffman for python
linux压缩解压

文件结构

说明

该文件结构针对ASCII码设计，字符的种类数设为 $N$ ，由于ASCII码中可显示字符十进制编码范围是 $[32,126]$ , 共 $95$ 种，考虑进少量不可见字符则 $N_{max}=127$ ，又因为对于Huffman编码，如果 $N\leq2$ 则编码没有任何效果，所以可设置范围 $N \in [3,127]$ 。
设源文件大小不超过4GB( $2^{32}\text{ bytes}$ )，又因为 $N>2$ ，所以在平均情况下所有文本中的字符的频数都可以用32位整数表示为 $M_i$ 。
由于Huffman编码方式确定，源文件文本对应的Huffman编码不可变，则设Huffman编码的长度为 $HLen$ 。
用存储所有字符-频数键值对的方式间接表示原Huffman树结构，解压时先根据键值对构建Huffman树再进行解压操作以得到原文件。
Huffman编码中最后一个字节设为 $HuffLast$ ，由于 $HuffLast$ 中存在编码余位不足8而补位的情况，故设 $HuffLast[7:loc]$ 为编码，而 $HuffLast[loc-1,0]$ 为补位，其中 $loc\in [0,7]$ ，特别地，当 $loc=0$ 时表示 $HuffLast$ 中没有补位。
设每一个字符-频数对为 $(K_i, M_i)$ ，其中 $M_i$ 经过计算后可得到等价的 $V_i$ ，所以字符-频数对 $(K_i,M_i)$ 可转换成键值对 $(K_i,V_i)$ ，则 $Pair=\{(K_1, V_1),(K_2,V_2),\dots,(K_N,V_N)\}$ 。
在该文件结构下，文件大小为 $(2\cdot N + HLen / 8 - 1)$ bytes.

整体结构

名称(简称)	占用空间
所有键值对集合( $Pair$ )	$(2 \cdot N - 1)$ bytes
文本Huffman编码( $Huff$ )	$(HLen/8)$ bytes

$Pair$

$Pair$ 为所有字符-频数变形后的键值对的集合。集合大小 $N > 2$ 。

对于 $Pair$ 中的除 $(K_1,V_1)$ 外每一个元素 $Pair[i]=(K_i,V_i)$ ，分配2个字节。

第一个字节表示该字符即 $K_i$ 。
第二个字节表示该字符对应原文本中出现的频数 $M_i$ 的变形 $V_i$ 。

$(K_1,V_1)$ 只分配一个字节存 $K_1$ ，不存 $V_1$ 。

由于每个字符在原文本中出现的频数 $M_i$ 属于32位整数，占四个字节，但是结合Huffman树构建的原理可将频数压缩至只占一个字节的 $V_i$ 。

$Pair$ 的计算与存储

定义 $(K_i,M_i)<(K_j,M_j) \text{ : } M_i <M_j \text{ or } (M_i=M_j \text{ and } K_i<K_j)$ 。将字符-频数集合按升序排序后得到新的序列 $\{(K_1,M_1),(K_2,M_2),\dots,(K_N,M_N)\}$ 。
设函数 $f(M_i)$ :
$f(M_i) = \begin{cases} 1 && i = 1 \\[2ex] M_{i-1} / M_{i} && i\in[2,N] \end{cases}$

当 $i=1$ 时，设 $V_i=C\cdot f(M_i)=C\text{ 其中C为常数}$ 。

当 $i>1$ 时， $0<f(M_i) < 1$ ，设 $V_i$ 表示 $f(M_i)$ 小数点后前8位小数，精度为 $1/2^8 = 0.0039$ 。

综上可得到有序序列 $V=\{i\in[1,N]|V_i\}$ 。
由于 $K_i$ 表示字符种类，范围为ASCII码前127位，则 $Ki$ 最高位 $K_i[7]$ 不参与字符种类表示。由于键值对个数为 $N$ ，对 $K_i[7]$ 进行标记，使得以下关系成立：
$((i < N-1 \wedge \forall x\in[1,i])\to K_x[7]=0)\wedge K_{N-1}[7] = 1$
即对于前 $N-1$ 个键值对除了 $K_{N-1}[7]=1$ ，其余 $K$ 的最高为都为0。通过这种方法就可以判断出 $N$ 的大小。
对于 $K_N[7]$ 进行标记。

$K_N[7]=\begin{cases} 0 & loc=0 \\[2ex] 1 & loc > 0 \end{cases}$
即可以来表示 $HuffLast$ 中是否有补位。
综上所述可以得到 $Pair=\{i\in[1,N]|(K_i, V_i)\}$ ，在存储时由于 $V_1=C$ ， $C$ 可以任取，故存储时略过 $V_1$ 。可得到占用空间为 $2\cdot N-1$ bytes。

$Huff$

对于长度为 $HLen$ 的二进制编码，每8位为一个字节以unsigned char类型储存进文件，对于最后不足8位的编码，长度满足 $HLen \text{ mod } 8 = (8 - loc) \text{ mod } 8$ 。
由 $K_N[7]$ 可得 $loc$ 得两种状态， $loc=0$ 时 $HuffLast$ 全是编码不用特殊处理； $loc=1$ 时对补位 $HuffLast[loc-1, 0]$ 进行处理，使以下关系成立:
$((loc>1 \wedge \forall x\in[0,loc-2])\to HuffLast[x]=1) \wedge ((loc\geq1)\to HuffLast[loc-1]=0)$

即

$HuffLast[x]=\begin{cases} 1 && loc > 1 \text{ and } x\in[0,loc-2] \\[2ex] 0 && loc \geq 1 \text{ and } x = loc-1\end{cases}$

用这种方法可以仅用一个额外的bit( $K_N[7]$ )，配合补位的内容就可以把 $HuffLast$ 中补位的个数表示出来。

总结

用 $V_i$ 表示 $M_i$ 时由于二进制小数位数的限制会有精度的损失，故 $V_i$ 可能略小于 $M_{i-1}/M_{i}$ ，而且 $V_i$ 的值仅和 $M_{i-1}$ 有关，而还原时是进行 $M^{d}_i=M^{d}_{i-1}/V_i$ ，会对通过 $M^{d}_{i-1}$ 对 $V_i$ 精度的误差进行累积，这两点共同导致还原出的 $M^{d}_i$ 略大于 $M_i$ 。

但是由于Huffman编码过程并不需要准确的 $M_i$ ，仅仅需要保存 $\{i\in[1,N]|M_i\}$ 各有可能的不相交子集元素之和大小关系，故这种方式在大概率下不会导致所建Huffman树与原树不同，也就保证了解压后文本的正确性。

代码片段(Huff.h)

2018-12-06更新: 感谢室友的测试，已经更改了一些bug

修复了各种状态转移间的信息未清空的问题。

修复了二进制小数转化的部分的临界问题。

修复了如果huffman编码部分没有补位，文件末尾仍有一个空字符的问题。

通过测试采用initC = 2替换原来的4。

#pragma once

#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>
#include <string>
#include <cmath>
#include <map>


#define SHOW_DETAIL

#define COMPRESS   0x1
#define DECOMPRESS 0x2
#define EXIT       0x3

#define BITSIZE    0x8

const int maxN = 1e4 + 1;
const int initC = 2;
int timestamp;


inline unsigned char dbToCh(double);
inline double chToDb(unsigned char);

struct VarAndFrec {
    char var;
    int frec;
    bool operator < (const VarAndFrec &obj) const {
        return this->frec < obj.frec;
    }
    VarAndFrec(char v = '\0', int f = 0) :
        var(v), frec(f) { }
    ~VarAndFrec() { }
};

struct Node {
    int frec;
    bool isLeaf;
    char var;
    Node *left;
    Node *right;

    Node(int frec = 0, char var = '\0') :
        frec(frec), var(var), isLeaf(true), left(NULL), right(NULL) { }
    ~Node() { }
};


class HuffMan {
public:
    HuffMan() {
        root = new Node;
    }
    ~HuffMan() { removeAll(root); }

    void Operate();

private:
    Node *root;
    std::map<char, int> varToFrec;
    std::map<char, std::string> codeList;
    std::ifstream input;
    std::ofstream output;
    std::string texts;

    void removeAll(Node *);
    void coding(Node *, std::string);

    bool getFilestream();
    void buildTree(bool);
    void compress();
    void decompress();
};

void HuffMan::removeAll(Node *root) {
    if (root == NULL) return;

    removeAll(root->left);
    removeAll(root->right);

    delete root;
}

void HuffMan::coding(Node *root, std::string code) {
    if (root->isLeaf) {
        codeList[root->var] = code;
        return;
    }
    coding(root->left, code + "0");
    coding(root->right, code + "1");
}


bool HuffMan::getFilestream() {
    std::string getin = "", getout = "";

    printf("Please input source file name(size less than 4GB)\n>> ");
    getline(std::cin, getin);
    printf("Please input code file name\n>> ");
    getline(std::cin, getout);
    printf("\n");

    input.open(getin.c_str(), std::ios::in | std::ios::binary);
    output.open(getout.c_str(), std::ios::out | std::ios::binary);

    return input.good();
}

void HuffMan::buildTree(bool sign = true) {
    // read text
    if (sign) {
        char alpha = '\0';
        varToFrec.clear();
        while (input.get(alpha)) {
            texts += alpha;
            varToFrec.find(alpha) != varToFrec.end() ?
                varToFrec[alpha] ++ : varToFrec[alpha] = 1;
        }
        if (varToFrec.size() < 3) {
            printf("File no need to be compressed!\n");
            return;
        }
    }
    //
#ifdef SHOW_DETAIL
    std::map<char, int>::iterator mpiter = varToFrec.begin();
    printf("char     frec\n");
    for (; mpiter != varToFrec.end(); mpiter++) {
        printf(" %c        %d\n", mpiter->first, mpiter->second);
    }
#endif // SHOWDETAIL

    // build queue
    removeAll(root);
    root = new Node;
    std::map<std::pair<int, int>, Node *> priQ;
    // init
    std::map<char, int>::iterator iter = varToFrec.begin();
    for (; iter != varToFrec.end(); iter++) {
        priQ[std::pair<int, int>(iter->second, timestamp++)] = new Node(iter->second, iter->first);
    }
    while (priQ.size() > 1) {
        Node *fir = priQ.begin()->second; priQ.erase(priQ.begin());
        Node *sec = priQ.begin()->second; priQ.erase(priQ.begin());

        Node *inter = new Node(fir->frec + sec->frec);
        inter->isLeaf = false;
        inter->left = fir->frec < sec->frec ? fir : sec;
        inter->right = fir->frec < sec->frec ? sec : fir;

        priQ[std::pair<int, int>(inter->frec, timestamp++)] = inter;
    }

    root = priQ.begin()->second; priQ.clear();
}

void HuffMan::compress() {
    codeList.clear();
    coding(root, "");

#ifdef SHOW_DETAIL
    std::map<char, std::string>::iterator iter = codeList.begin();
    for (; iter != codeList.end(); iter++) {
        printf(" %c     %s\n", iter->first, iter->second.c_str());
    }
#endif // SHOW_DETAIL

    std::string LastCode = "";
    for (std::string::iterator iter = texts.begin(); iter != texts.end(); iter++) {
        LastCode += codeList[*iter];
    }

    int recLen = LastCode.length();
    /************ Pair ****************/
    int PairNum = varToFrec.size();
    VarAndFrec FTV[maxN];
    std::map<char, int>::iterator iterC = varToFrec.begin();
    for (int inc = 0; iterC != varToFrec.end(); iterC++, inc++) {
        FTV[inc] = VarAndFrec(iterC->first, iterC->second);
    }
    std::sort(FTV, FTV + PairNum);

    for (int idx = 0; idx < PairNum; idx++) {
        unsigned char K_i = FTV[idx].var, V_i = '\0';
        if (idx == PairNum - 1) {
            K_i |= (recLen % BITSIZE != 0) << (BITSIZE - 1);
        }
        else {
            K_i |= (idx == PairNum - 2) ? 0x80 : 0x00;
        }

        output << K_i;
        if (idx) {
            V_i = dbToCh(1.0 * FTV[idx - 1].frec / FTV[idx].frec);
            output << V_i;
        }
    }
    /************ Pair ****************/

    int len = recLen / BITSIZE;
    for (int inc = 0; inc < len; inc++) {
        unsigned char Tm = '\0';
        for (int snc = 0; snc < BITSIZE; snc++) {
            Tm |= (int(*(LastCode.begin() + inc * BITSIZE + snc) - '0') << snc);
        }
        output << Tm;
    }

    int Modlen = LastCode.length() % BITSIZE;
    unsigned char Ch = '\0';
    for (int inc = 0; inc < BITSIZE; inc++) {
        if (inc < Modlen)
            Ch |= (int(*(LastCode.begin() + len * BITSIZE + inc) - '0') << inc);
        else if (inc > Modlen)
            Ch |= (0x1 << inc);
    }

    if (Modlen)
        output << Ch;

    printf("Compress succeed!\n");

    input.close();
    output.close();
}


void HuffMan::decompress() {
    std::string line;
    std::string text;
    bool needEnter = false;
    while (std::getline(input, line)) {
        if (needEnter) line = "\n" + line;
        text += line;
        needEnter = true;
    }

    int KVpairNum = 0, loc = 0;
    int nextStop = 0;
    // Read Pair
    varToFrec.clear();
    for (std::string::iterator iter = text.begin(); iter != text.end(); iter++) {
        if (iter != text.begin()) {
            varToFrec[(*iter) & 0x7F] = std::floor(varToFrec[(*(iter - 1 - (varToFrec.size() >= 2))) & 0x7F] / chToDb(*(iter + 1)));
            if (nextStop) {
                loc = ((*iter) >> (BITSIZE - 1)) & 0x01;
                break;
            }
            else {
                nextStop = ((*iter) >> (BITSIZE - 1)) & 0x01;
            }
            iter++;
        }
        else {
            nextStop = ((*iter) >> (BITSIZE - 1)) & 0x01;
            varToFrec[(*iter) & 0x7F] = initC;
        }
    }
    buildTree(false);
    unsigned char HFLast = *text.rbegin();
    if (loc) {
        loc = BITSIZE;
        while (HFLast & (1 << (--loc)));
    }
    else {
        loc = BITSIZE;
    }

    int PairSize = 2 * varToFrec.size() - 1;
    // Read Huffman Code
    Node *curr = root;
    for (std::string::iterator iter = text.begin() + PairSize; iter != text.end(); iter++) {
        unsigned char Tm = *iter;
        int Range = (iter + 1 == text.end() ? loc : BITSIZE);
        for (int inc = 0; inc < Range; inc++) {
            curr = ((Tm >> inc) & 0x1) ? curr->right : curr->left;
            if (curr->isLeaf) {
                output << curr->var;
                curr = root;
            }
        }
    }

    printf("Decompress succeed!\n");

    input.close();
    output.close();
}

void HuffMan::Operate() {
    bool quit = false;
    int  opeNum = 0;
    while (!quit) {
        printf("-------------------\n");
        printf("1. Compress   \n");
        printf("2. Decompress \n");
        printf("3. Exit       \n");
        printf("-------------------\n");
        printf(">> ");
        scanf("%d", &opeNum);
        getchar();

        if (opeNum == COMPRESS) {
            if (getFilestream()) {
                buildTree();
                compress();
            }
        }
        else if (opeNum == DECOMPRESS) {
            if (getFilestream()) {
                decompress();
            }
        }
        else if (opeNum == EXIT) {
            quit = true;
        }
    }
}

inline unsigned char dbToCh(double db) {
    unsigned char Ch = '\0';
    for (int mv = 0; mv < 8; mv++) {
        Ch |= (unsigned char)((db * 2 >= 1) << (7 - mv));
        db = 2 * db >= 1 ? 2 * db - 1 : 2 * db;
    }
    return Ch;
}

inline double chToDb(unsigned char Ch) {
    double db = 0;
    for (int mv = 0; mv < 8; mv++) {
        db += pow(2, mv - 8) * ((Ch >> mv) & 0x01);
    }
    return db;
}

Huffman压缩文件结构
文件结构说明该文件结构针对ASCII码设计，字符的种类数设为，由于ASCII码中可显示字符十进制编码范围是 ,...
2020-01-30 前端性能优化
减少资源体积 gzip gzip 使用了 LZ77 算法与 Huffman 编码来压缩文件，重复度越高的文件可压缩...
Image Compression Tech
Adaptive Huffman Coding As Adaptive Huffman Coding is gen...
[Python&DS]- Python实现Huffman
本文主要介绍Huffman编码、Huffman树、和如何借助Python实现Huffman编码树对文件进行压缩和解...
Python批量压缩图片
文件夹结构如下待压缩文件放到文件夹prepare.
数据结构(十四) -- Huffman树
本文将通过 Huffman 编码树的构造问题，介绍优先队列结构的具体应用。二进制编码通讯系统可以帮助人们将一段...
Word2Vec中的数学原理
一、旧版本的神经网络表示词向量二、huffman树及huffman编码 2.1 Huffman树的构造根据词典...
05-树9 Huffman Codes （30 分）
05-树9 Huffman Codes （30 分） In 1953, David A. Huffman publ...
huffman for python
项目地址：python-huffman (github) 2017.3.27 目前完成了 huffman tree...
linux压缩解压
zip压缩解压压缩文件压缩目录 unzip解压缩不重建文档的目录结构，把所有文件解压到同一目录下将压缩文件...