Question

2. Using Lempel ziv compression code the following text

KMMKABKAMKVVDAABCKMAA

10 marks

Answer 1

The below c ++ code will give following output for your string guven in question

#include <bits/stdc++.h> 
using namespace std; 
vector<int> encoding(string s1) 
{ 
        cout << "Encoding\n"; 
        unordered_map<string, int> table; 
        for (int i = 0; i <= 255; i++) { 
                string ch = ""; 
                ch += char(i); 
                table[ch] = i; 
        } 

        string p = "", c = ""; 
        p += s1[0]; 
        int code = 256; 
        vector<int> output_code; 
        cout << "String\tOutput_Code\tAddition\n"; 
        for (int i = 0; i < s1.length(); i++) { 
                if (i != s1.length() - 1) 
                        c += s1[i + 1]; 
                if (table.find(p + c) != table.end()) { 
                        p = p + c; 
                } 
                else { 
                        cout << p << "\t" << table[p] << "\t\t"
                                << p + c << "\t" << code << endl; 
                        output_code.push_back(table[p]); 
                        table[p + c] = code; 
                        code++; 
                        p = c; 
                } 
                c = ""; 
        } 
        cout << p << "\t" << table[p] << endl; 
        output_code.push_back(table[p]); 
        return output_code; 
} 

void decoding(vector<int> op) 
{ 
        cout << "\nDecoding\n"; 
        unordered_map<int, string> table; 
        for (int i = 0; i <= 255; i++) { 
                string ch = ""; 
                ch += char(i); 
                table[i] = ch; 
        } 
        int old = op[0], n; 
        string s = table[old]; 
        string c = ""; 
        c += s[0]; 
        cout << s; 
        int count = 256; 
        for (int i = 0; i < op.size() - 1; i++) { 
                n = op[i + 1]; 
                if (table.find(n) == table.end()) { 
                        s = table[old]; 
                        s = s + c; 
                } 
                else { 
                        s = table[n]; 
                } 
                cout << s; 
                c = ""; 
                c += s[0]; 
                table[count] = table[old] + c; 
                count++; 
                old = n; 
        } 
} 
int main() 
{ 

        string s = "KMMKABKAMKVVDAABCKMAA"; 
        vector<int> output_code = encoding(s); 
        cout << "Output Codes are: "; 
        for (int i = 0; i < output_code.size(); i++) { 
                cout << output_code[i] << " "; 
        } 
        cout << endl; 
        decoding(output_code); 
} 

output

Encoding
String  Output_Code     Addition
K       75              KM      256
M       77              MM      257
M       77              MK      258
K       75              KA      259
A       65              AB      260
B       66              BK      261
KA      259             KAM     262
MK      258             MKV     263
V       86              VV      264
V       86              VD      265
D       68              DA      266
A       65              AA      267
AB      260             ABC     268
C       67              CK      269
KM      256             KMA     270
AA      267
Output Codes are: 75 77 77 75 65 66 259 258 86 86 68 65 260 67 256 267 

Decoding
KMMKABKAMKVVDAABCKMAA