5

我正在尝试在 C++ 中实现霍夫曼的编码算法。

我的问题是：在我得到每个字符的等效二进制字符串之后，我怎样才能将这些零和一作为二进制文件写入文件而不是字符串 0 或字符串 1？

提前致谢 ...

4

3 回答 3

1

在不同的数据结构中单独获取每个字符的编码是一个失败的解决方案，因为您需要将生成的二进制文件中的每个字符的编码并列：单独存储它们使得这与直接将它们连续存储在位向量中一样困难.

这种考虑建议使用 astd::vector<bool>来执行您的任务，但它是一个损坏的解决方案，因为它不能被视为 c 样式的数组，并且您在输出时确实需要它。

这个问题准确地询问了哪些是 的有效替代品std::vector<bool>，所以我认为该问题的答案非常适合您的问题。

顺便说一句，我要做的就是std::vector<uint8_t>在一个适合你需要的类下包装一个，就像附加的代码一样：

#include <iostream>
#include <vector>
#include <cstdint>
#include <algorithm>
class bitstream {
private:
    std::vector<std::uint8_t> storage;
    unsigned int bits_used:3;
    void alloc_space();
public:
    bitstream() : bits_used(0) { }

    void push_bit(bool bit);

    template <typename T>
    void push(T t);

    std::uint8_t *get_array();

    size_t size() const;

    // beware: no reference!
    bool operator[](size_t pos) const;
};

void bitstream::alloc_space()
{
    if (bits_used == 0) {
        std::uint8_t push = 0;
        storage.push_back(push);
    }
}

void bitstream::push_bit(bool bit)
{
    alloc_space();
    storage.back() |= bit << 7 - bits_used++;
}

template <typename T>
void bitstream::push(T t)
{
    std::uint8_t *t_byte = reinterpret_cast<std::uint8_t*>(&t);
    for (size_t i = 0; i < sizeof(t); i++) {
        uint8_t byte = t_byte[i];
        if (bits_used > 0) {
            storage.back() |= byte >> bits_used;
            std::uint8_t to_push = (byte & ((1 << (8 - bits_used)) - 1)) << bits_used;
            storage.push_back(to_push);
        } else {
            storage.push_back(byte);
        }
    }
}

std::uint8_t *bitstream::get_array()
{
    return &storage.front();
}

size_t bitstream::size() const
{
    const unsigned int m = 0;
    return std::max(m, (storage.size() - 1) * 8 + bits_used);
}

bool bitstream::operator[](size_t size) const
{
    // No range checking
    return static_cast<bool>((storage[size / 8] >> 7 - (size % 8)) & 0x1);
}

int main(int argc, char **argv)
{
    bitstream bs;
    bs.push_bit(true);
    std::cout << bs[0] << std::endl;
    bs.push_bit(false);
    std::cout << bs[0] << "," << bs[1] << std::endl;
    bs.push_bit(true);
    bs.push_bit(true);
    std::uint8_t to_push = 0xF0;
    bs.push_byte(to_push);
    for (size_t i = 0; i < bs.size(); i++)
        std::cout << bs[i] << ",";
    std::cout << std::endl;
}
于 2012-06-24T10:35:43.203 回答
1

我希望这段代码可以帮助你。

  • 您从表示输入文件的每个字符的连续编码的字节序列（1 和 0）开始。
  • 您获取序列的每个字节并在临时字节中添加一个位 ( char byte)
  • 每次填充一个字节时，都会将其写入文件（为了提高效率，您也可以等待获得更大的数据）
  • 最后，您将剩余的位写入文件，用尾随零填充，例如
  • 正如 akappa 正确指出的那样，如果在每次文件写入操作之后（或者更一般地说，每次它被完全填充并刷新到其他地方），else分支可以被删除，所以只必须写入。byte01s
void writeBinary(char *huffmanEncoding, int sequenceLength)
{
    char byte = 0;
    // For each bit of the sequence
    for (int i = 0; i  < sequenceLength; i++) {
        char bit = huffmanEncoding[i];

        // Add a single bit to byte
        if (bit == 1) {
            // MSB of the sequence to msb of the file
            byte |= (1 << (7 - (i % 8)));
            // equivalent form: byte |= (1 << (-(i + 1) % 8);
        }
        else {
            // MSB of the sequence to msb of the file
            byte &= ~(1 << (7 - (i % 8)));
            // equivalent form: byte &= ~(1 << (-(i + 1) % 8);
        }

        if ((i % 8) == 0 && i > 0) {
            //writeByteToFile(byte);
        }
    }

    // Fill the last incomplete byte, if any, and write to file
}
于 2012-06-24T10:38:18.883 回答
0

您不能写入只有位的二进制文件；写入的最小数据大小是一个字节（因此是 8 位）。

所以你应该做的是创建一个缓冲区（任何大小）。

char BitBuffer;

写入缓冲区：

int Location;
bool Value;

if (Value)
    BitBuffer |= (1 << Location);
else
    BitBuffer &= ~(1 << Location)

代码(1 << Location)生成一个除指定位置外全为 0 的数字Location。然后，如果Value设置为 true，则将 Buffer 中的相应位设置为 1，否则设置为 0。使用的二进制操作相当简单，如果你不理解它们，它应该在任何好的 C++ 书籍/教程中。

位置应该是 <0, sizeof(Buffer)-1> 范围内的数字，因此在这种情况下为 <0,7>。

使用 fstream 时，将缓冲区写入文件相对简单。只要记住以二进制文件的形式打开它。

ofstream File;
File.open("file.txt", ios::out | ios::binary);
File.write(BitBuffer, sizeof(char))

编辑：注意到一个错误并修复它。

EDIT2：您不能<<在二进制模式下使用运算符，我忘记了。

替代解决方案：使用std::vector<bool>或std::bitset作为缓冲液。

这应该更简单，但我想我可以帮助你更多一点。

void WriteData (std::vector<bool> const& data, std::ofstream& str)
{
    char Buffer;
    for (unsigned int i = 0; i < data.size(); ++i)
    {
       if (i % 8 == 0 && i != 0)
           str.write(Buffer, 1);
       else
           // Paste buffer setting code here
           // Location = i/8;
           // Value = data[i];
    }
    // It might happen that data.size() % 8 != 0. You should fill the buffer
    // with trailing zeros and write it individually.
}
于 2012-06-24T09:55:15.960 回答