Binary Huffman Coding
- Create an instance of a FileInputStream with the file name passed into constructor
- Pass the FileInputStream to the constructor of the BufferedInputStream
- Attempts to read b.length bytes into b
- Returns total number of bytes read or -1 if nothing was read
- Need to know size of file beforehand
- Useful in current assignment to read in first 4 bytes
- Reads the next byte from the stream
- Returns the byte value or -1 if the end of the stream has been reached
- Easiest to set up a while loop and continually byte for -1 (similar to BufferedReader example in lab, except we're now checking for -1 instead of null).
- Java handles bytes in odd ways, often times converting them to ints when you least expect it
- Make sure you cast all byte literals (i.e. 0xE8 -> (byte) 0xE8)
- Make sure that for all bit operations with bytes, BIT-AND each byte with 0xFF
byte b = ...
b = (b & 0xFF) >>> 8
- Java integers are 32 bits
- Each byte is 8 bits
- Therefore, 4 bytes exactly fit into 1 integer
- It's easy to concatenate 4 bytes into an integer
- Repeatedly shift the resulting integer to the left by 8 bits and AND with next byte
let result = 0
let byte[] be an array of bytes
for index 0 to 3:
shift result to left by 8 bits
result = result BIT-OR (byte[index] BIT-AND 0xFF)
return result
- ByteBuffer API
- [ByteBuffer.wrap(byte[] array)](http://docs.oracle.com/javase/7/docs/api/java/nio/ByteBuffer.html#wrap(byte[]\)) - Returns an instance of a ByteBuffer given an array of bytes
- [ByteBuffer.getInt()](http://docs.oracle.com/javase/7/docs/api/java/nio/ByteBuffer.html#getInt(\)) - Returns the integer value of an instance of a ByteBuffer
- Need an abstract way traverse bits from array of bytes
- Create a BitReader class which takes an array of bytes and provides methods for traversing of bits
- Easiest to read entire file into byte array and then extract individual bits from there
- To find any particular bit, need to know which byte it is contained in and which index in the byte the bit is
- For example, bit 19 is the 3rd bit in the 2nd byte, but how can we determine this?
- Index into array = bit index / 8 (i.e. 19 / 8 = 2)
- Index into byte = bit index % 8 (i.e. 19 % 8 = 3)
- I might recommend the method get(int bitIndex) which returns the bit value from the BitReader
- Or you could create an iterator which does the above behind the scenes, and iterates over bit values
- Often times we want to know the value of a specific bit
- To query a specific bit, we need the use of a bitmask
- A bitmask if a set of bits used with bitwise operations
- To find the value for a specific bit, we perform a bitwise AND with a string of bits and a mask
- If the result is 0, then the bit is 0, otherwise 1
- Each mask should have a single 1 bit where you wish to query
The following table lists all of the masks needed to query bits from a byte:
| Index into Byte | Hex Value | Binary |
|---|---|---|
| 0 | 0x80 | 10000000 |
| 1 | 0x40 | 01000000 |
| 2 | 0x20 | 00100000 |
| 3 | 0x10 | 00010000 |
| 4 | 0x08 | 00001000 |
| 5 | 0x04 | 00000100 |
| 6 | 0x02 | 00000010 |
| 7 | 0x01 | 00000001 |
Let byte b = 10010001
If we want to query the first bit, AND it with it's mask:
10010001
AND 10000000
--------
10000000
Since 10000000 is not equal to 0, then we know the first bit is a 1.
If we want to query the second bit, AND it with it's mask:
10010001
AND 01000000
--------
00000000
Since 00000000 is equal to 0, then we know the second bit is 0.
- Create an array of 8 bitmasks where the array index corresponds to the index into the byte
- Create a single bitmask 0x80, and shift it to the right for as many positions as you need for the index into the byte
let b be a byte of data
let m be a bitmask for b
let i be the index into the byte
(b BIT-AND 0xFF) BIT-AND ((m BIT-AND 0xFF) UNSIGNED-RIGHT-SHIFT i)
create a stack
read first 0 from stream
set root to a new empty internal node and push it onto stack
while stack is not empty:
read next bit from stream
if bit is 0:
create a new empty internal node
else on a 1:
read 8 more bits and create a new leaf node with the data
if stack.peek() does not have left child:
add the new node as left child of stack.peek()
else:
add the new node as right child of stack.peek()
pop the top of the stack (because now it has two children)
if the new node is an internal node:
push the new node onto stack
- Looking at only the bits that make up the tree we have:
- We see the first 0 and create an empty root node and push it to the stack
- We see a 1 bit, create a new node containing the data from the next 8 bits
- Peek at the TOS and add as left child
- We see a 0 bit, create an empty internal node
- Peek at TOS and add as right child
- Pop the stack since their are two children
- Push internal node to stack
- We see a 1 bit, create a new node containing the data from the next 8 bits
- Peek at the TOS and add as left child
- We see a 1 bit, create a new node containing the data from the next 8 bits
- Peek at the TOS and add as right child
- Pop the stack, since the stack is now empty, we are done
- Once the tree is reconstructed, can decode rest of message
- Reading in the rest of the bits, traverse the tree, recording a 0 on left subtree and 1 on right
- Stop once the original amount of bytes (saved from step 1) have been decoded
- It's possible to stop before the end of a byte boundary due to padding
- Looking only at the bits which make up the encoded message with have
- Using the tree from above we get
(11)010011000 => (A)010011000 [1 byte]
A(0)10011000 => A(B)10011000 [2 bytes]
AB(10)011000 => AB(C)011000 [3 bytes]
ABC(0)11000 => ABC(B)11000 [4 bytes]
ABCB(11)000 => ABCB(A)000 [5 bytes]
ABCBA
- Note that the last 2 zeroes are simply padding
- Use Zach's BitWriter class
- Pass into the constructor an instance of an output stream (i.e. FileOutputStream or BufferedOutputStream)
- Don't forget to call the flush() method