• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 209
  • Last Modified:

Storing bits and then writing them to a file

Hi again,

I am implementing the Huffman Compression algorithm. This requires the program to store an appendable length of bits. This length then has to be written to a file.

I have been looking for data structures to store lengths of bits, but without much success. Also for the best way to then write these to a file.

Any help would be much appreciated. Thank you in advance.

Andy
0
acrxx
Asked:
acrxx
  • 5
  • 4
  • 2
  • +1
3 Solutions
 
aozarovCommented:
Check: java.util.BitSet
You can call toString() and save it to file as a String. (or you can serialize the object if you don't care about the format).
0
 
aozarovCommented:
bitSet.set(int index, boolean value) will expand the bit set as much as needed.
You might want to take a look at http://www.hta-bi.bfh.ch/~hew/java/software/Huffman/ which also uses BitSet
0
 
CodingExpertsCommented:
// This routine sets bit n in b.
byte BitSet(byte b, int n)
{
      b|=1<<(n-1);
      return(b);
}

// Convert a dual number representation in String format to an array of bytes.
void String2Bytes(String s, byte[] barray)
{
      int i,j,l=s.length()/8;
      for (j=0;j<l;j++) {
            for (i=0;i<8;i++) {      
                  if (s.charAt(i+(j*8))=='1') barray[j]=BitSet(barray[j],8-i);
            }
      }
      l=s.length()%8;
      for (i=0;i<l;i++) {
              if (s.charAt(i+(j*8))=='1') barray[j]=BitSet(barray[j],8-i);
      }
}

-CE
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
WebstormCommented:
Hi acrxx,

you can use this :


int tmp=0, // store written bits until we get a whole byte
     nbit=8; // number of bits that can be stored in tmp

/*
    bits : contains your bit values (high bits first)
    nbits : number of bits to be written
*/
void writeBits(OutputStream out,int bits, int nbits)
{
    while (nbits>0)
    {
        int n=(nbits>nbit)?nbit:nbits;

        nbits-=n;
        nbit-=n;
        tmp|=(  (bits>>>nbits)&( (1<<n)-1 )  )<<nbit;

        if (nbit==0) // no more bits can be stored in tmp
        {
            out.write(tmp);
            tmp=0;
            nbit=8;
        }
    }
}

// call this method just before closing your output stream
void flushBits(OutputStream out)
{
        if (nbit<0) out.write(tmp);
}
0
 
WebstormCommented:
>>void flushBits(OutputStream out)
>>{
>>        if (nbit<0) out.write(tmp);

should be :

void flushBits(OutputStream out)
{
        if (nbit<8) out.write(tmp);
0
 
acrxxAuthor Commented:
Does this mean, I can store the bitstream in int form, and the equivalent is then written to the file in bit form?

when:
int bits = 10001111

is then stored in the file as 10001111 in bits

Is that correct?
0
 
aozarovCommented:
No, integer has 4 bytes and therfore can represent 4 * 8 bits.
You can display it in the form of 101.. (binary form) by doing Integer.toBinaryString(bits).
But again, you are limited to 32 bits and to manipulate it you will have to use the binary operations (|, <, > ~, &, ..)
BitSet doesn't have the size limitation.
0
 
WebstormCommented:
>> Is that correct?
You can use my code to put each code when you generate them.
One Huffman code never exceed 16 bits (or less).

0
 
WebstormCommented:
You can directly write the bits to a file (use a FileOutputStream for the "out" parameter)
Or, if you want to get a byte array, use a ByteArrayOutputStream.
0
 
aozarovCommented:
>> One Huffman code never exceed 16 bits
Why is that? I don't think there is a limit to the number of bits that can be used by Huffman code (that is very much depends on the amount of symbols you  are trying to encode).
0
 
acrxxAuthor Commented:
Thanks to all for relieving me of the headache I was having over this :)
0
 
WebstormCommented:
:-)
0

Featured Post

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

  • 5
  • 4
  • 2
  • +1
Tackle projects and never again get stuck behind a technical roadblock.
Join Now