Huffman codes compress text by assigning the characters that occur at the highest frequency the shortest...

 

 

 

 

Transcribed Image Text:

Huffman codes compress text by assigning the characters that occur at the highest frequency the shortest possible codes. In this encoding scheme, no code can be a prefix of another. For example, if the code for a is 01, then the code for b cannot be 011. Given an array of Huffman code mappings and a Huffman-encoded string, find the decoded string. Each mapping will be a string consisting of a tab-separated character and its encoded value: 'c encoded value' where the whitespace is a tab character. The newline character is represented as the character (newline] in the codes list, but should translate to n when decoded. For example, given codes = ('a 100100, 'b 100101' Inewline] 111111') and the string encoded = 100100111111100101 we do the following. Break encoded into its constituent encodings. 100100 111111 100101 Now map them to their characters and return the string: 'anb'. This will print as: b Function Description Complete the function decode in the editor below. The function must return the decoded string. decode has the following parameter(s): codes(codes(0).codes[n-1]]: an array of character mappings encoded: an encoded string Constraints • 1sns 100 • 1 s Jencoded s 7000 • All characters of encoded are either '0' or '1' • All inputs will represent a valid Huffman encoded string v Sample Case 0 Sample Input a 100100 100101 110001 d 100000 [newline] 111111 111110 000001 111110000001100100111111100101110001111110 Sample Output pga bcp Explanation encoded: Character Code 11111080000110010011111110010111000111111O a 100100 b 100101 110001 111110 000001 180100 111111 180101 110001 111110 100000 a \n [newline] 111111 111110 decoded: 000001 pqa\nbcp This diagram depicts the conversion from 111110000001100100111111100101110001111110 to pqavnbcp. v Sample Case 1 Sample Input a 100100 b. 100101 110001 d. (newline] 100000 111111 100100111111100101110001100000 Sample Output a bcd Explanation encoded: 100100111111100101110001100000 Character Code a 100100 b 100101 100100 111111 100101 110001 108000 110001 a \n 100000 Inewline] 111111 decoded: a\nbcd This diagram depicts the conversion from 100100111111100101110001100000 to a\nbcd. string decode (vector<string> codes, string encoded) { Huffman codes compress text by assigning the characters that occur at the highest frequency the shortest possible codes. In this encoding scheme, no code can be a prefix of another. For example, if the code for a is 01, then the code for b cannot be 011. Given an array of Huffman code mappings and a Huffman-encoded string, find the decoded string. Each mapping will be a string consisting of a tab-separated character and its encoded value: 'c encoded value' where the whitespace is a tab character. The newline character is represented as the character (newline] in the codes list, but should translate to n when decoded. For example, given codes = ('a 100100, 'b 100101' Inewline] 111111') and the string encoded = 100100111111100101 we do the following. Break encoded into its constituent encodings. 100100 111111 100101 Now map them to their characters and return the string: 'anb'. This will print as: b Function Description Complete the function decode in the editor below. The function must return the decoded string. decode has the following parameter(s): codes(codes(0).codes[n-1]]: an array of character mappings encoded: an encoded string Constraints • 1sns 100 • 1 s Jencoded s 7000 • All characters of encoded are either '0' or '1' • All inputs will represent a valid Huffman encoded string v Sample Case 0 Sample Input a 100100 100101 110001 d 100000 [newline] 111111 111110 000001 111110000001100100111111100101110001111110 Sample Output pga bcp Explanation encoded: Character Code 11111080000110010011111110010111000111111O a 100100 b 100101 110001 111110 000001 180100 111111 180101 110001 111110 100000 a \n [newline] 111111 111110 decoded: 000001 pqa\nbcp This diagram depicts the conversion from 111110000001100100111111100101110001111110 to pqavnbcp. v Sample Case 1 Sample Input a 100100 b. 100101 110001 d. (newline] 100000 111111 100100111111100101110001100000 Sample Output a bcd Explanation encoded: 100100111111100101110001100000 Character Code a 100100 b 100101 100100 111111 100101 110001 108000 110001 a \n 100000 Inewline] 111111 decoded: a\nbcd This diagram depicts the conversion from 100100111111100101110001100000 to a\nbcd. string decode (vector<string> codes, string encoded) {