Please use the appropriate notations and please explain thoroughly,i really have
ID: 3665411 • Letter: P
Question
Please use the appropriate notations and please explain thoroughly,i really have a problem with understanding these(just dont answer if you dont want to explain)
also please make it readable
your help is very much appreciated
16.3-6 Suppose we have an optimal prefix code on a set C = {0, l, . . . , n-1) of charac- ters and we wish to transmit this code using as few bits as possible. Show how to represent any optimal prefix code on C using only 2n-1 + nIgn1 bits. (Hint: Use 2n 1 bits to specify the structure of the tree, as discovered by a walk of the tree.)Explanation / Answer
An ideal prex-free code on a set C= {0, 1,…, n1} of characters worked by creating a binary tree of nodes. A binary tree can stored in a regular array and the size depends on the number of symbols n. These nodes are leaf node or an internal node. Consider as with n trees, all nodes are leaf nodes each consists of a single node corresponding to one message word and the weight (frequency of appearance) .So, here 2n-1 indicates the tree structure where leaf node or Internal nodes contain symbol weight. This having two child nodes and it linked to a parent node. Bit '0' represents the left child and the other bit i.e. '1' represents the right child with nlog (n) is a sequence of letters where length of each letter be binary encoding for log (n) and taking as total n log (n ) bit.
Let it be an easy understands by sum up the above that the tree finished has up to n leaf nodes and internal nodes by a sequence of 2n1 bits found of the tree with the preorder traversal . It has the n members of C with the n leaf of the tree followed by preorder traversal which can be done by listing them in the order. So, log n is enough to represent the n members of C without any need of delimiters Hence, a total of 2n1+nlogn2n1+nlognbits.