Member Avatar for pi_lord12

Hey guys, I'm working on a project to use Huffman trees to compress a text file into binary. For instance, based on the frequency of the characters in a string like "aardvark",

a - 3
r - 2
d - 1
v - 1
k - 1,

compression using a Huffman tree could look something like 001011011100101111, assuming that the most frequent character (a) would be stored using the least number of bits (0), and one of the least frequently occurring characters (k) would be stored with the most number of bits (1111), and so forth. I am able to form the tree and get the encoded sequence well, but I would now like a way to write each character as one bit rather than the usual full byte used to write a char to a file. I've tried using FileWriter and OutputStream classes such as ByteArrayOutputStream and DataOutputStream, but all seem to use 8 bits per character. I've tried searching quite a bit through the API and on Google but have seen nothing so far that seems effective. Does anyone know of a class or technique that would allow this compressed writing? Thanks in advance.

  • 2 Contributors
  • 2 Replies
  • 241 Views
  • 2 Weeks Discussion Span
  • Latest Post Latest Post by pi_lord12

Dani AI

Generated

Quick recap: confirmed that ’s BitSet idea solved the immediate need. Below is a compact, portable pattern that is easier to control than object-serialization and avoids common pitfalls (padding, Java-char vs byte, and header metadata).

Basic file layout (recommended)

  • 4-byte integer: total number of encoded bits (so padding can be ignored on read).
  • serialized Huffman tree (bit-level pre-order: 0 = internal, 1 + 8-bit symbol = leaf).
  • encoded bit stream (the concatenation of codewords).

A small, reliable BitOutputStream implementation (big‑endian within each byte):

public class BitOutputStream implements Closeable {
    private final OutputStream out;
    private int current = 0;
    private int numBits = 0;
    public BitOutputStream(OutputStream out) { this.out = out; }

    public void writeBit(int bit) throws IOException {
        current = (current << 1) | (bit & 1);
        if (++numBits == 8) {
            out.write(current);
            numBits = 0;
            current = 0;
        }
    }

    public void writeBits(String bits) throws IOException {
        for (int i = 0; i < bits.length(); i++) writeBit(bits.charAt(i) == '1' ? 1 : 0);
    }

    public void writeByte(byte b) throws IOException {
        for (int i = 7; i >= 0; i--) writeBit((b >> i) & 1);
    }

    public void flush() throws IOException {
        if (numBits > 0) out.write(current << (8 - numBits));
        out.flush();
    }

    public void close() throws IOException { flush(); out.close(); }
}

Tree serialization (pre-order):

void writeTree(Node node, BitOutputStream out) throws IOException {
    if (node.isLeaf()) {
        out.writeBit(1);
        out.writeByte((byte) node.symbol);
    } else {
        out.writeBit(0);
        writeTree(node.left, out);
        writeTree(node.right, out);
    }
}

Usage notes and gotchas

  • Compute total encoded bits beforehand and write it as the first 4 bytes. The decoder reads that to ignore final padding.
  • Prefer compressing bytes (e.g., UTF-8 bytes) rather than Java char (16-bit) unless intentionally handling 16-bit symbols.
  • If mixing DataOutputStream for headers and the BitOutputStream for bit payload, flush the header wrapper before constructing/using the bit writer on the same BufferedOutputStream.
  • BitSet and Java object-serialization are convenient, but their byte ordering and serialized form are implementation-specific and less portable; explicit bit I/O gives a stable file format.
  • Test round-trip correctness (serialize tree, write bits, then decode) and include a small checksum if long-term integrity matters.

Recommended Answers

All 2 Replies

Member Avatar for JamesCherrill

Have a look at BitSet. It holds long strings of bits, fully packed at 64 bits per 8 bytes, and can be written/read to/from files as a single Object using Object input/output streams.

Member Avatar for pi_lord12

Yep, that did the trick. Thanks!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.