处理霍夫曼中的额外字节 compression/decompression

Question

我有一个程序可以根据在文本输入文件中读取的 ASCII 字符频率生成哈夫曼树。霍夫曼编码存储在一个包含 256 个元素的字符串数组中，如果未读取该字符，则为空字符串。该程序还对输出文件进行编码和压缩，目前在解压缩和解码方面具有一些功能。

总而言之，我的程序采用输入文件压缩和编码输出文件，关闭输出文件并打开编码作为输入文件，然后采用一个新的输出文件，该文件的解码消息应该与原始文本输入文件。

我的问题是，在我的测试中运行压缩时我注意到我有 3 个额外的字节，反过来当我解压缩和解码我的编码文件时，这 3 个额外的字节被解码到我的输出文件.根据原始输入文件中的文本量，我的其他测试会输出这些额外的字节。

我的研究让我提出了一些建议，例如将编码输出文件的前 8 个字节设为 unsigned long long 的 64 位，给出文件中的字节数或使用伪 EOF 但我坚持我将如何处理它，考虑到我已经编写的代码，这两种方法中哪一种是处理它的聪明方法，或者是否是一种聪明的方法？

感谢任何对此问题的指导或解决方案。

(对于encodedOutput函数，fileName为输入文件参数，fileName2为输出文件参数)

(对于decodeOutput函数，fileName2为输入文件参数，fileName 3为输出文件参数)

code[256] 是这两个函数的参数，并保存原始输入文件中读取的每个唯一字符的霍夫曼代码，例如，输入文件中读取的字符 'H' 可能在将代码传递给函数时，将代码“111”存储在代码[72]的代码数组中。

freq[256] 保存每个 ascii 字符读取的频率，或者如果它不在原始输入文件中则保存 0。

void encodeOutput(const string & fileName, const string & fileName2, string code[256]) {
    ifstream ifile; //to read file
    ifile.open(fileName, ios::binary);
    if (!ifile)//to check if file is open or not
    {
        die("Can't read again"); // function that exits program if can't open
    }
    ofstream ofile;
    ofile.open(fileName2, ios::binary);
    if (!ofile) {
        die("Can't open encoding output file");
    }
    int read; 
    read = ifile.get(); //read one char from file and store it in int
    char buffer = 0, bit_count = 0;
    while (read != -1) {//run this loop until reached to end of file(-1)
        for (unsigned b = 0; b < code[read].size(); b++) { // loop through bits (code[read] outputs huffman code)
            buffer <<= 1;
            buffer |= code[read][b] != '0';
            bit_count++;
            if (bit_count == 8) {
                ofile << buffer;
                buffer = 0;
                bit_count = 0;
            }
        }
        read = ifile.get();
    }

    if (bit_count != 0)
        ofile << (buffer << (8 - bit_count));

    ifile.close();
    ofile.close();
}

void decodeOutput(const string & fileName2, const string & fileName3, string code[256], const unsigned long long freq[256]) {
    ifstream ifile;
    ifile.open(fileName2, ios::binary);
    if (!ifile)
    {
        die("Can't read again");
    }
    ofstream ofile;
    ofile.open(fileName3, ios::binary);
    if (!ofile) {
        die("Can't open encoding output file");
    }
    priority_queue < node > q;
    for (unsigned i = 0; i < 256; i++) {
        if (freq[i] == 0) {
            code[i] = "";
        }
    }

    for (unsigned i = 0; i < 256; i++)
        if (freq[i])
            q.push(node(unsigned(i), freq[i]));

    if (q.size() < 1) {
        die("no data");
    }

    while (q.size() > 1) {
        node *child0 = new node(q.top());
        q.pop();
        node *child1 = new node(q.top());
        q.pop();
        q.push(node(child0, child1));
    } // created the tree
    string answer = "";
    const node * temp = &q.top(); // root 
    for (int c; (c = ifile.get()) != EOF;) {
        for (unsigned p = 8; p--;) { //reading 8 bits at a time 
            if ((c >> p & 1) == '0') { // if bit is a 0
                temp = temp->child0; // go left
            }
            else { // if bit is a 1
                temp = temp->child1; // go right
            }
            if (temp->child0 == NULL && temp->child1 == NULL) // leaf node
            {
                answer += temp->value;
                temp = &q.top();
            }
        }
    }
  ofile << ans;
}

Answer 1

由于integral promotion规则，(buffer << (8 - bit_count))将是一个整数表达式，导致写入4个字节。要只写一个字节，您需要将其转换为一个字符。

ofile << char(buffer << (8 - bit_count));

处理霍夫曼中的额外字节 compression/decompression

Handling extra bytes in huffman compression/decompression

c++

huffman-code

data-structures

visual-studio-2017