如何存储霍夫曼变换后的二进制代码？编码实现求解

Hey there! Let's work through how to encode that binary string into a dynamically resizing byte array—you’ve already got a solid start with the initial allocation and expansion idea, so let’s fill in the missing encoding step and tie everything together.

First, let's recap the core problem: we need to take a string of binary digits (with spaces) and pack them into bytes, since we can't store individual bits directly. Here's a step-by-step implementation that follows your original plan, plus handles the encoding and dynamic resizing properly.

Step 1: Preprocess the Input String #

First, we’ll strip out any spaces from the input so we’re only working with 0s and 1s. This makes it easier to iterate through each bit without skipping over whitespace.

Step 2: Initialize Storage & Track Progress #

We’ll start with 3 bytes as you suggested, and keep track of how many bits we’ve already packed (since each byte holds 8 bits).

Step 3: Encode Bits into Bytes #

For each bit in the cleaned string:

• Calculate which byte it belongs to, and which position in that byte (we’ll pack bits from the high bit to low bit by default—you can adjust this if needed).
• Set the corresponding bit in the byte using bitwise operations.
• Check if we’re running out of space, and expand the array by 3 bytes if we are.

Full Code Implementation #

Here’s a complete C++ example that puts it all together:

#include <iostream>
#include <string>
#include <cstring>

// Define BYTE if it's not already available (common in Windows environments)
typedef unsigned char BYTE;

int main() {
    std::string binaryInput = "01100111 011011 011 0110011011 0111101 ";
    
    // Step 1: Clean the input—remove all spaces
    std::string cleanedBinary;
    for (char c : binaryInput) {
        if (c != ' ') cleanedBinary += c;
    }

    int totalBits = cleanedBinary.size();
    if (totalBits == 0) {
        std::cout << "No valid binary bits to process!\n";
        return 0;
    }

    // Step 2: Initialize storage (3 bytes, all set to 0)
    int currentByteCapacity = 3;
    BYTE* byteStore = new BYTE[currentByteCapacity](); // The () initializes all bytes to 0
    int usedBits = 0;

    // Step 3: Encode each bit into the byte array
    for (char bitChar : cleanedBinary) {
        // Check if we need to expand the storage
        int remainingSpace = currentByteCapacity * 8 - usedBits;
        if (remainingSpace <= 0) {
            // Expand by 3 bytes as per your plan
            int newCapacity = currentByteCapacity + 3;
            BYTE* newStore = new BYTE[newCapacity]();
            
            // Copy existing data to the new array
            memcpy(newStore, byteStore, currentByteCapacity);
            
            // Clean up old memory
            delete[] byteStore;
            byteStore = newStore;
            currentByteCapacity = newCapacity;

            std::cout << "Expanded storage to " << currentByteCapacity << " bytes.\n";
        }

        // Calculate which byte and bit position to use
        int targetByteIndex = usedBits / 8;
        int targetBitPosition = 7 - (usedBits % 8); // Pack from high bit to low bit

        // Set the bit (only need to act if it's a '1'—bytes are initialized to 0)
        if (bitChar == '1') {
            byteStore[targetByteIndex] |= (1 << targetBitPosition);
        } else if (bitChar != '0') {
            std::cout << "Skipping invalid character: " << bitChar << "\n";
            continue;
        }

        usedBits++;
    }

    // Optional: Verify the result by printing each byte as binary
    std::cout << "\nEncoded bytes (binary):\n";
    int totalBytesUsed = (usedBits + 7) / 8; // Round up to full bytes
    for (int i = 0; i < totalBytesUsed; i++) {
        BYTE currentByte = byteStore[i];
        for (int j = 7; j >= 0; j--) {
            std::cout << ((currentByte >> j) & 1);
        }
        std::cout << " ";
    }
    std::cout << "\n";

    // Don't forget to free the allocated memory!
    delete[] byteStore;

    return 0;
}

Key Notes #

• Bit Order: The code packs bits from the highest position (bit 7) to the lowest (bit 0) in each byte. If you need the opposite order (low bit first), just change targetBitPosition to usedBits % 8.
• Memory Safety: Manually managing memory with new/delete works, but for a safer approach, consider using std::vector<BYTE> instead—it handles resizing and cleanup automatically:

  std::vector<BYTE> byteStore(3, 0); // Initial 3 bytes, all 0
  // When expanding:
  byteStore.resize(currentByteCapacity + 3, 0);
  

• Resizing Strategy: Your plan to expand by 3 bytes each time works, but for better performance with large datasets, you might want to double the capacity instead (reduces the number of reallocations).

内容的提问来源于stack exchange，提问作者user9506206