5

C++ でハフマンのエンコーディング アルゴリズムを実装しようとしています。

私の質問は次のとおりです。各文字に相当するバイナリ文字列を取得した後、これらのゼロと 1 を文字列 0 または文字列 1 としてではなくファイルにバイナリとして書き込むにはどうすればよいですか?

前もって感謝します ...

4

3 に答える 3

1

異なるデータ構造で各文字のエンコーディングを個別に取得することは、結果のバイナリファイルで各文字のエンコーディングを並置する必要があるため、解決策としては壊れています。個別に格納すると、ビットのベクトルに連続して直接格納するのと同じくらい難しくなります。 。

この考慮事項はstd::vector<bool>、タスクを実行するためにaを使用することを示唆していますが、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

ビットだけでバイナリ ファイルに書き込むことはできません。書き込まれるデータの最小サイズは 1 バイト (したがって 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 に答える