Decoding of codes generated from shannon fano encoding algorithm

I have generated the codes for different symbol in a file using shannon fano algorithm. Now my problem is that how i will store these codes into file 开发者_如何学JAVA(as file is in byte) so that while reading, reader can assure that at some point, it is the end of code for a particular symbol. So that extra code will not be read.

First, you can use bitwise operations to read a variable number of bits (not multiple of 8) from a byte array.

Second, if the code is a valid Prefix code, which satisfies

there is no valid code word in the system that is a prefix (start) of any other valid code word in the set

then you can determine where the code ends by comparing the prefix with a table.

Usually, this is done in the following manner:

• Suppose the code length is anywhere from 1 to 16 bits.
• Load the next 16 bits from the file to the variable.
• Compare the 16-bit variable with a table which contain the following values. Binary search or radix search can be used.
  • Key: the Shannon-Fano or Huffman code, shifted so that the top bit is at the most-significant bit.
  • KeyLength: the actual number of bits in the Shannon-Fano or Huffman code. This allows us to subtract the number of decoded bits from the variable.
  • Value: the value that the code will decode to.
• Subtract (remove) the decoded bits from the variable depending on the code. For example, if the code has 9 bits, we will remove 9 bits from the MSB and keep the remaining 7 bits.
• Read the next 9 bits from the file, concatenating with the undecoded 7 bits.
• Repeat the process.