large documents more efficientlyso as to allow for fixed-capacity storage device to contain as many documents as possible the method for text compression explored in this section is the huffman code standard encoding schemessuch as the ascii and unicode systemsuse fixedlength binary strings to encode characters (with bits in the ascii system and in the unicode systema huffman codeon the other handuses variablelength encoding optimized for the string the optimization is based on the use of character frequencieswhere we havefor each character ca count (cof the number of times appears in the string the huffman code saves space over fixed-length encoding by using short code-word strings to encode high-frequency characters and long codeword strings to encode low-frequency characters to encode the string xwe convert each character in from its fixed-length code word to its variable-length code wordand we concatenate all these code words in order to produce the encoding for in order to avoid ambiguitieswe insist that no code word in our encoding is prefix of another code word in our encoding such code is called prefix codeand it simplifies the decoding of in order to get back (see figure even with this restrictionthe savings produced by variablelength prefix code can be significantparticularly if there is wide variance in character frequencies (as is the case for natural language text in almost every spoken languagehuffman' algorithm for producing an optimal variable-length prefix code for is based on the construction of binary tree that represents the code each node in texcept the rootrepresents bit in code wordwith each left child representing " and each right child representing " each external node is associated with specific characterand the code word for that character is defined by the sequence of bits associated with the nodes in the path from the root of to (see figure each external node has frequency ( )which is simply the frequency in of the character associated with in additionwe give each internal node in frequencyf( )that is the sum of the frequencies of all the external nodes in the subtree rooted at figure an illustration of an example huffman code for the input string " fast runner need never be afraid of the dark"(afrequency of each character of (bhuffman tree for string the code for character is obtained by tracing the path from the root of to the external node where is storedand associating left child with and right child with