algorithm design techniques character code frequency total bits space newline total figure using standard coding scheme the case where we are transmitting it over slow phone line alsosince on virtually every machinedisk space is preciousone might wonder if it would be possible to provide better code and reduce the total number of bits required the answer is that this is possibleand simple strategy achieves percent savings on typical large files and as much as to percent savings on many large data files the general strategy is to allow the code length to vary from character to character and to ensure that the frequently occurring characters have short codes notice that if all the characters occur with the same frequencythen there are not likely to be any savings the binary code that represents the alphabet can be represented by the binary tree shown in figure the tree in figure has data only at the leaves the representation of each character can be found by starting at the root and recording the pathusing to indicate the left branch and to indicate the right branch for instances is reached by going leftthen rightand finally right this is encoded as this data structure is sometimes referred to as trie if character ci is at depth di and occurs fi timesthen the cost of the code is equal to di fi better code than the one given in figure can be obtained by noticing that the newline is an only child by placing the newline symbol one level higher at its parentwe obtain the new tree in figure this new tree has cost of but is still far from optimal figure representation of the original code in tree sp nl