Huffman codes compress text by assigning the characters that occur at the highes

Question

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 100101 Now map them to their characters and return the string: 'anb. This will print as 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)...codesn-1] an array of character mappings encoded: an encoded string

Explanation / Answer

// Few notes :

// Inside the main function, i have not read input since this was not what was asked. I have taken

// sample variables 'codes' and 'encoded' just to check the sample output is printed in the desired  

// way as only the contents of the function "string decode(vector<string> codes,string encoded)" was

// asked.

// Student can copy paste the contents of the function 'decode' inside his editor and check it's validity.

#include <iostream>

#include <string>

#include <vector>

#include <map>

using namespace std;

/* Start of 'decode' function */

string decode(vector<string> codes, string encoded) {

// using map to store the characters as values and their encodings as keys

map <string,string> characterEncoding;

int codeSize = codes.size();

int i = 0;

for(int i = 0;i<codeSize;i++){

string elem = codes[i];

//assuming that the characters and their encodings are ' ' i.e tab separated

int pos = elem.find(" ");

string val = elem.substr(0,pos);

if(val.compare("[newline]") == 0){

characterEncoding.insert(pair<string,string>(elem.substr(pos+1,elem.size()-pos-1)," " ) );

}else{

characterEncoding.insert(pair<string,string>(elem.substr(pos+1,elem.size()-pos-1),val ) );

}

}

//decode the encoded string now

int encodedSize = encoded.size();

string key,decoded;

key.assign("");

decoded.assign("");

map<string,string>::iterator it;

for(i=0;i<encodedSize;i++){

it = characterEncoding.find(key);

if(it != characterEncoding.end()){

//print the character corresponding to that encoding

decoded += it->second;

//assign the value of 'key' string to empty string ''

key.assign("");

key += encoded[i];

}else{

//append the current character to the key string and try to find it in the next iteration

key += encoded[i];

}

}

it = characterEncoding.find(key);

if(it != characterEncoding.end())

decoded += it->second;

return decoded;

}

/* End of decode function */

int main() {

// your code goes here

vector<string> codes;

string encoded;

encoded.assign("100100111111100101110001100000");

// was not able to print ' ' in the in the chegg text editor so gave 8 spaces to simulate tab(' ')

codes.push_back("a 100100");

codes.push_back("b 100101");

codes.push_back("c 110001");

codes.push_back("d 100000");

codes.push_back("[newline] 111111");

string decoded = decode(codes,encoded);

cout << decoded;

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.