CODEWITHSUNDEEP
c++cryptographycompression
Deepak
Deepak

Reputation: 49

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 (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.

Upvotes: 1

Views: 4449

Answers (1)

rwong
rwong

Reputation: 6162

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.

Upvotes: 3

Related Questions