text compression and the greedy method in this sectionwe consider an important text-processing tasktext compression in this problemwe are given string defined over some alphabetsuch as the ascii or unicode character setsand we want to efficiently encode into small binary string (using only the characters and text compression is useful in any situation where we wish to reduce bandwidth for digital communicationsso as to minimize the time needed to transmit our text likewisetext compression is useful for storing large documents more efficientlyso as to allow 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 asciiuse fixed-length binary strings to encode characters (with or bits in the traditional or extended ascii systemsrespectivelythe unicode system was originally proposed as -bit fixedlength representationalthough common encodings reduce the space usage by allowing common groups of characterssuch as those from the ascii systemwith fewer bits the huffman code saves space over fixed-length encoding by using short code-word strings to encode high-frequency characters and long code-word strings to encode low-frequency characters furthermorethe huffman code uses variable-length encoding specifically optimized for given string over any alphabet 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 to encode the string we convert each character in to 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 be prefix of another code-word in our encoding such code is called prefix codeand it simplifies the decoding of to retrieve (see figure even with this restrictionthe savings produced by variable-length prefix code can be significantparticularly if there is wide variance in character frequencies (as is the case for natural language text in almost every written languagehuffman' algorithm for producing an optimal variable-length prefix code for is based on the construction of binary tree that represents the code each edge in represents bit in code-wordwith an edge to left child representing " and an edge to right child representing " each leaf is associated with specific characterand the code-word for that character is defined by the sequence of bits associated with the edges in the path from the root of to (see figure each leaf has frequencyf ( )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 leaves in the subtree rooted at