Substitution Compression

Write a C program that implements the Substitution Compression Algorithm. File provided:

-IronHeel.txt to be used as base to calculate the frequency and determine the binary code for each alphabetical letter by using HUFFMAN's code provided.

PART I

I.Questions

I.Processing Level 1

1.Creates a first array "Letter" that records the 26 alphabetical letters including the space (from A to Z plus space)

Example:

• Letters "space", a, b, etc. will be stored in Letter at the positions zero, one, two, and so on, respectively.

Note:

• Any character different from the 26 alphabetical letters is ignored, except space, comma, colon, semi-colon that are stored as "space")

2.Creates a second array "ASCII" and stores corresponding ASCII values (for space, comma, colon, semi-colon, use the ASCII value of space)

3.Reads IronHeel.txt file character by character and incrementally stores the occurrence of each character in a third Array "Occurrence".

Example:

• Occurrence of letter "a" will be stored in array Occurrence at the position one (5 marks)

4.After reading the full text, the program calculates the frequency of each character and inputs it into a fourth Array "Frequency".

Note: The letter's frequency is the total of its occurrences divided by the sum of the letters in the text

5.Ranks the frequencies from the highest to the lowest and inputs them in a fifth array Ordered_Frequency

6.Builds the coding table by using the Huffman code provided (in next page) and records appropriate code for each single letters into the sixth array "Huffman_Code" by respecting the following rule

Rule:

• The most appeared letter will have short coding format (less digits)
• The less appeared letter will have long coding format (more digits)
• Since the coding chart start from the short to the long format, you will start coding from the most to the less appeared letter

II.Processing Level 2

7.Reads again IronHeel.txt file

• Builds and displays the ciphered text by converting each characters into its Huffman representation (created in Question 6)
• Calculates and displays the theoretical compression rate (CR) (please read explanation in next page).
• Displays the following menu, where each numbers (1 or 2) should return appropriate result)
  1 = Display all the 6 Arrays along with the Compression Rate
  2= Display the ciphered

8.After the displaying of the ciphered text, the program breaks and prompts the following statement:

• "Would you want to see the plain text (Decoding of the ciphered text)?
  Y. = Yes (the program will automatically read and decrypts the ciphered text and displays the original text in capital letter)
  N.= No (the program stops)

Letter frequency coding: see image.

Explanation Question 6

• In computer system, information are coded by using ASCII code (see next page)
• Here, we will be using 8 bits ASCII table.
• For the compression rate, we can use the following formulas:

Compression Rate = 100 - [(Size of Ciphered Text / Size of Clear Text) x 100]

• Size of Ciphered Text = Text after Encryption (sum of bits form Huffman Code)
• Size of Clear Text = Text before Encryption (sum of bits from ASCII Code = sum of letters x 8 bits)

Example:

• Let assume your program prompts you to enter a text, and you type the following:"sheridan college"
• This will be coded as:
  By using ASCII code (since each character is 8-bits coded)
  8 bits x ( 8 + 1 + 7 ) = 128 bits
  By using Huffman Code (since the length of character is variable in HUFFMAN's table)
  (4 + 4 + 4 + 4 + 4 + 5 + 4 + 4) + ( 3) + (5 + 4 + 5 + 5 + 4 + 6 + 4)
  =33 + 3 + 33
  =69 bits

• Compression Rate = 100 [ (69/128)*100] = 46.09 %

PART II

Perform the same project using Binary Search Tree