Milestone two

LO$5$: EXPLAIN THE STRUCTURE, CORRECT USE OF AND

IMPLEMENTATION OF APPROPRIATE ADVANCED DATA STRUCTURES

AND ALGORITHMS FOR A RANGE OF SCENARIOS.

Knowledge and Understanding

Communication

Scenario

It is often possible to improve space requirements by sacrificing efficiency in running time.

This tradeoff between space requirement and running time can be desirable in many

situations. For example, a user may wish to compress a file that is not frequently used to

take up less space on the storage medium.

The standard ASCII coding scheme assigns a unique, $8-$bit value to each character to

represent each of the $128$ symbols in the ASCII character set uniquely. This is a fixed$-$

length code since all the codes have the same fixed length. If all the symbols in the character

set were used with the same frequency, then a fixed$-$length coding scheme would be the

most space$-$efficient. However, most applications do not use all characters with the same

frequency.

Variable$-$length codes, such as Huffman Coding, take advantage of some characters being

used more frequently than others. They assign shorter codes to more frequently used

characters to improve space efficiency. This concept is at the core of most compression

techniques used today. Huffman Coding assigns codes to characters such that the code

length depends on the frequency of the corresponding character. The Huffman code for

each character is obtained from a binary tree called the Huffman coding tree.

A node of a Huffman coding tree contains a symbol, the weight $($frequency of occurrence$),$

and references to two child nodes.

An internal node of a Huffman coding tree contains a symbol $($use the $\text{'}$ $ $\text{'}$ character to

denote an internal node$),$ a weight, and references to two child nodes. The weight of an

internal node is the sum of the weights of the two child nodes.

A leaf node of a Huffman coding tree corresponds to a symbol in the character set $($all the

unique characters in the text to be encoded$),$ and it contains the symbol itself and the weight

$($frequency of occurrence$)$ of that symbol. The references to the two child nodes of a leaf

node are set to NULL.