-
-
Save majedsiefalnasr/32cff52b01d764ee158f2c36e4e84d95 to your computer and use it in GitHub Desktop.
/********************************************************************* | |
LZ 77, 78, W Algorithms | |
------------------- | |
_ | |
___ ___ __| | ___ _____ ___ __ ___ | |
/ __/ _ \ / _` |/ _ \ / _ \ \/ / '_ \ / _ \ | |
| (_| (_) | (_| | __/ | __/> <| |_) | (_) | | |
\___\___/ \__,_|\___| \___/_/\_\ .__/ \___/ | |
|_| | |
Made with love in Code Expo lab | |
www.code-expo.com | |
created by : ENG, Majed Sief Al-Nasr | |
**********************************************************************/ | |
#include <iostream> | |
#include <string> | |
#include <vector> | |
#include <sstream> | |
#include "windows.h" | |
using namespace std; | |
struct Node{ | |
int index; | |
string data; | |
Node *next; | |
}; | |
void st_Node(Node *head, int index, string data){ | |
head->index = index; | |
head->data = data; | |
head->next = NULL; | |
} | |
void insert_Node(Node *head, int index, string data){ | |
Node *new_Node = new Node; | |
new_Node->index = index; | |
new_Node->data = data; | |
new_Node->next = NULL; | |
Node *curr = head; | |
while (curr != NULL) | |
{ | |
if (curr->next == NULL) | |
{ | |
curr->next = new_Node; | |
return; | |
} | |
curr = curr->next; | |
} | |
} | |
Node *search_Node(Node *head, string data) | |
{ | |
Node *curr = head; | |
while (curr != NULL) | |
{ | |
if (data.compare(curr->data) == 0) | |
return curr; | |
else | |
curr = curr->next; | |
} | |
return NULL; | |
} | |
Node *search_Node(Node *head, int index) | |
{ | |
Node *curr = head; | |
while (curr != NULL) | |
{ | |
if (index == curr->index) | |
return curr; | |
else | |
curr = curr->next; | |
} | |
return NULL; | |
} | |
bool delete_Node(Node *head, Node *to_delete){ | |
if (to_delete == NULL) | |
return false; | |
else if (to_delete == head) | |
{ | |
head = to_delete->next; | |
delete to_delete; | |
return true; | |
} | |
else{ | |
Node *curr = head; | |
while (curr) | |
{ | |
if (curr->next == to_delete) | |
{ | |
curr->next = to_delete->next; | |
delete to_delete; | |
return true; | |
} | |
curr = curr->next; | |
} | |
return false; | |
} | |
} | |
vector <string> split(string str, char delimiter) { | |
vector<string> internal; | |
stringstream ss(str); // Turn the string into a stream. | |
string tok; | |
while (getline(ss, tok, delimiter)) { | |
internal.push_back(tok); | |
} | |
return internal; | |
} | |
string LZ77(string input, int option); | |
string LZ78(string input, int option); | |
string LZW(string input, int option); | |
int main() | |
{ | |
string input, result, method_text; | |
int method, option, option2; | |
string intro = R"( | |
Hi I'm Alpha ^_^ , Code Expo's assistant, I'm here to help you. | |
)"; | |
cout << intro; | |
main_menu: | |
string main_menu = R"( | |
------------------------------------------------------------------------------- | |
This tool generate compression and decompression using LZ-77, LZ-78 and LZW methods : | |
1- LZ-77 | |
2- LZ-78 | |
3- LZW | |
Enter 1, 2 or 3 according to method. | |
> )"; cout << main_menu; | |
cin >> method; | |
if (method == 1) | |
method_text = "LZ-77"; | |
else if (method == 2) | |
method_text = "LZ-78"; | |
else if (method == 3) | |
method_text = "LZW"; | |
else | |
{ | |
system("cls"); | |
cout << intro; | |
goto main_menu; | |
} | |
method_menu: | |
system("cls"); | |
cout << intro; | |
string main_menu_2 = R"( | |
------------------------------------------------------------------------------- | |
This tool generate compression and decompression using )" + method_text + R"( method : | |
1- Compression | |
2- Decompression | |
0- Main menu | |
Enter 1, 2 or 0 according to method. | |
> )"; cout << main_menu_2; | |
cin >> option; | |
if (option == 1) | |
{ | |
system("cls"); | |
cout << intro; | |
string lz77_Compression = R"( | |
------------------------------------------------------------------------------- | |
)" + method_text + R"( > Compression :)"; | |
cout << lz77_Compression << endl; | |
cout << "\t Enter your phrases : "; | |
cin.ignore(); | |
getline(cin, input); | |
if (method == 1) | |
result = LZ77(input, 1); | |
else if (method == 2) | |
result = LZ78(input, 1); | |
else if (method == 3) | |
result = LZW(input, 1); | |
else | |
{ | |
system("cls"); | |
cout << intro; | |
goto main_menu; | |
} | |
cout << "\n\t Final result : " << result << endl; | |
back_1: | |
cout << "\n Enter 0 to back to Main menu or 1 to back to Method menu. \n > "; | |
cin >> option2; | |
if (option2 == 0) | |
{ | |
system("cls"); | |
cout << intro; | |
goto main_menu; | |
} | |
else if (option2 == 1) | |
goto method_menu; | |
else | |
goto back_1; | |
} | |
else if (option == 2) | |
{ | |
system("cls"); | |
cout << intro; | |
string lz77_Compression = R"( | |
------------------------------------------------------------------------------- | |
LZ-77 > Decompression :)"; | |
cout << lz77_Compression << endl; | |
//cout << "Note : Enter 0 for NULL characters\n\n"; | |
cout << "\t Enter your code : "; | |
cin.ignore(); | |
getline(cin, input); | |
if (method == 1) | |
result = LZ77(input, 2); | |
else if (method == 2) | |
result = LZ78(input, 2); | |
else if (method == 3) | |
result = LZW(input, 2); | |
else | |
main_menu; | |
cout << "\n\t Final result : " << result << endl; | |
back_2: | |
cout << "\n Enter 0 to back to Main menu or 1 to back to Method menu. \n > "; | |
cin >> option2; | |
if (option2 == 0) | |
{ | |
system("cls"); | |
cout << intro; | |
goto main_menu; | |
} | |
else if (option2 == 1) | |
goto method_menu; | |
else | |
goto back_2; | |
} | |
else if (option == 0) | |
{ | |
system("cls"); | |
cout << intro; | |
goto main_menu; | |
} | |
else | |
goto method_menu; | |
cin.get(); | |
cin.ignore(); | |
return 0; | |
} | |
string LZ77(string input, int option) | |
{ | |
// Initialized variables | |
string result; | |
int length, char_info_selc = 0; | |
if (option == 1) | |
{ | |
check_char: // Length checker pointer | |
length = (int)input.length(); // Calculate input string length | |
// Check input line length is less than 3 | |
if (length <= 2) | |
{ | |
cout << "enter at leaset 3 characters \n"; | |
getline(cin, input); // Read input string | |
goto check_char; | |
} | |
// Declare an arry for final result called 'result_ary' | |
int** result_ary = new int*[3]; | |
for (int i = 0; i < length; ++i) | |
result_ary[i] = new int[length]; | |
// Set result_ary elements value to 0 to prevent previous values | |
for (int i = 0; i < 3; i++) | |
{ | |
for (int j = 0; j < length; j++) | |
result_ary[i][j] = 0; | |
} | |
// Declare an arry to store every char info in input string called 'char_info' | |
int** char_info = new int*[3]; | |
for (int i = 0; i < length; ++i) | |
char_info[i] = new int[length]; | |
// Set char_info elements value to 0 to prevent previous values | |
for (int i = 0; i < 3; i++) | |
{ | |
for (int j = 0; j < length; j++) | |
char_info[i][j] = 0; | |
} | |
// Set first char info to (0,0,'<first char>') | |
result_ary[0][0] = 0; | |
result_ary[1][0] = 0; | |
result_ary[2][0] = input[0]; | |
// Set result counter | |
int result_count = 1; | |
// A loop to perform some operations in every char in input string | |
for (int i = 1; i < length; i++) | |
{ | |
// A loop to check input char in position i is equal to any of | |
// previous char in input and save this info in char_info array | |
for (int j = 0; j < i; j++) | |
{ | |
// Check position of previous view of element i | |
if (input[i] == input[j]) | |
{ | |
// Set position pointer | |
char_info[0][char_info_selc] = i - j; | |
// Increase char info array selector by 1 | |
char_info_selc++; | |
} | |
} | |
// A loop to check length for every char position | |
for (int j = 0; j < length; j++) | |
{ | |
// Check current char info array position is not equal to 0 | |
if (char_info[0][j] != 0) | |
{ | |
// Set start point | |
int start = i - char_info[0][j]; | |
// Set count to calculate length for this char position | |
int count = 1; | |
// A loop to check length for this char position | |
for (int k = 0; k < length; k++) | |
{ | |
// Check next element of start by next element of input | |
if (input[start + count] == input[i + count]) | |
count++; // Increase count by 1 | |
else | |
{ | |
char_info[1][j] = count; // Store count value in length | |
// Check if this input char is the last char | |
if (i != (length - 1)) | |
{ | |
// Store next char to char info | |
// Check this postion is equal to length | |
if (char_info[0][j] + count == length) | |
char_info[2][j] = 0; // Set 0 in next char field | |
else | |
char_info[2][j] = input[char_info[0][j] + count]; // Set the next char | |
} | |
else | |
char_info[2][j] = NULL; // Set NULL in next char field | |
break; // Stop loop | |
} | |
} | |
} | |
} | |
// Set large selector | |
int large = 0; // large selector equal 0 | |
// Loop to check the largest length for every char info | |
for (int k = 1; k < length; k++) | |
{ | |
// Check largest | |
if (char_info[1][large] == char_info[1][k]) | |
large = k; // Set largest | |
else if (char_info[1][large] < char_info[1][k]) | |
large = k; // Set largest | |
} | |
// Check largest length is equal to 0 | |
if (char_info[1][large] == 0) | |
char_info[2][large] = input[i]; // Set char info | |
else | |
{ | |
i += char_info[1][large]; // increase loop counter by length of the largest char info element | |
char_info[2][large] = input[i]; // Set char info | |
} | |
// Set final result info | |
result_ary[0][result_count] = char_info[0][large]; | |
result_ary[1][result_count] = char_info[1][large]; | |
result_ary[2][result_count] = char_info[2][large]; | |
// Increase result counter | |
result_count++; | |
// Prepare char info array for next char by set it to 0 | |
for (int z = 0; z < 2; z++) | |
{ | |
for (int j = 0; j < length; j++) | |
char_info[z][j] = 0; // Set every element in char info to 0 | |
} | |
// Prepare char info selector for next char by set it to 0 | |
char_info_selc = 0; | |
} | |
// Display final results | |
for (int j = 0; j < length; j++) | |
{ | |
if (result_ary[0][j] == 0 && result_ary[1][j] == 0) | |
{ | |
if (result_ary[2][j] != NULL || result_ary[2][j] != 0) | |
{ | |
char z = result_ary[2][j]; | |
result += to_string(result_ary[0][j]) + "," + to_string(result_ary[1][j]) + "," + z + " "; | |
} | |
} | |
else | |
{ | |
//char z = result_ary[2][j]; | |
result += to_string(result_ary[0][j]) + "," + to_string(result_ary[1][j]) + ",0 "; | |
} | |
} | |
// Clean up memory | |
//for (int i = 0; i < 3; ++i) { | |
// { | |
// delete[] result_ary[i]; delete[] char_info[i]; | |
// } | |
//} | |
//delete[] result_ary; | |
//delete[] char_info; | |
return result; | |
} | |
else if (option == 2) | |
{ | |
vector<string> s_input = split(input, ' '); | |
for (int i = 0; i < s_input.size(); ++i) | |
{ | |
vector<string> ss_input = split(s_input[i], ','); | |
int p = stoi(ss_input[0]), | |
l = stoi(ss_input[1]); | |
string ch; | |
if (ss_input[2][0] == '0') | |
ch = ' '; | |
else | |
ch = ss_input[2]; | |
if (p != 0) | |
{ | |
int result_len = (int)result.length(); | |
for (int x = 0; x < l; x++) | |
result += result[result_len - p + x]; | |
} | |
if (ch[0] != '0' || ch[0] != NULL) | |
result += ch; | |
} | |
return result; | |
} | |
} | |
string LZ78(string input, int option) | |
{ | |
if (option == 1) | |
{ | |
Node *dictionary = new Node; | |
string word, result; | |
int length, last_seen, index = 1; | |
length = (int)input.length(); | |
word = input[0]; | |
st_Node(dictionary, 1, word); | |
result += "0," + word; | |
for (int i = 1; i < length; i++) | |
{ | |
string data; | |
data = input[i]; | |
re_check: | |
Node *search = search_Node(dictionary, data); | |
if (search) | |
{ | |
i++; | |
data += input[i]; | |
last_seen = search->index; | |
goto re_check; | |
} | |
else | |
{ | |
char zero; | |
if (input[i] == ' ') | |
zero = '0'; | |
else | |
zero = input[i]; | |
if ((int)data.length() < 2) | |
result += " " + to_string(0) + "," + zero; | |
else | |
result += " " + to_string(last_seen) + "," + zero; | |
index++; | |
if (i != length) | |
insert_Node(dictionary, index, data); | |
} | |
} | |
return result; | |
} | |
if (option == 2) | |
{ | |
Node *dictionary = new Node; | |
string result; | |
vector <string> s_input = split(input, ' '); | |
int zz = 2; | |
for (int i = 0; i < s_input.size(); i++) | |
{ | |
vector <string> ss_input = split(s_input[i], ','); | |
if (i == 0) | |
{ | |
st_Node(dictionary, 1, ss_input[1]); | |
result += ss_input[1]; | |
} | |
else | |
{ | |
Node *serched; | |
string get_search = ss_input[1]; | |
serched = search_Node(dictionary, stoi(ss_input[0])); | |
if (serched) | |
{ | |
result += serched->data + get_search; | |
get_search = serched->data + split(s_input[i], ',')[1]; | |
insert_Node(dictionary, zz, get_search); | |
} | |
else | |
{ | |
if (stoi(ss_input[0]) == 0) | |
insert_Node(dictionary, zz, get_search); | |
else | |
insert_Node(dictionary, zz, get_search); | |
result += get_search; | |
} | |
zz++; | |
} | |
} | |
if (result[(int)result.length() - 1] == '0') | |
result = result.substr(0, result.size() - 1); | |
return result; | |
} | |
} | |
string LZW(string input, int option) | |
{ | |
if (option == 1) | |
{ | |
Node *dictionary = new Node; | |
string result; | |
int length, last_seen, index = 128; | |
st_Node(dictionary, 32, " "); | |
for (int i = 33; i < 128; i++) | |
{ | |
string data; | |
data = i; | |
insert_Node(dictionary, i, data); | |
} | |
length = (int)input.length(); | |
for (int i = 0; i < length; i++) | |
{ | |
Node *searched; | |
string search; | |
search = input[i]; | |
re_search: | |
searched = search_Node(dictionary, search); | |
if (searched) | |
{ | |
i++; | |
search += input[i]; | |
last_seen = searched->index; | |
if (i != length) | |
goto re_search; | |
else | |
goto print; | |
} | |
else | |
{ | |
insert_Node(dictionary, index, search); | |
index++; | |
print: | |
result += to_string(last_seen) + " "; | |
i--; | |
} | |
} | |
return result; | |
} | |
if (option == 2) | |
{ | |
Node *dictionary = new Node; | |
string result; | |
int index = 128; | |
st_Node(dictionary, 32, " "); | |
for (int i = 33; i < 128; i++) | |
{ | |
string data; | |
data = i; | |
insert_Node(dictionary, i, data); | |
} | |
vector <string> s_input = split(input, ' '); | |
for (int i = 0; i < s_input.size(); i++) | |
{ | |
Node *searched; | |
int search; | |
search = stoi(s_input[i]); | |
searched = search_Node(dictionary, search); | |
string cur, prev, data; | |
if (searched) | |
cur = search_Node(dictionary, stoi(s_input[i]))->data; | |
if (i != 0) | |
prev = search_Node(dictionary, stoi(s_input[i - 1]))->data; | |
else | |
prev = cur; | |
int show = 0; | |
if (searched) | |
{ | |
result += searched->data; | |
if (i != 0) | |
{ | |
data = prev + cur[0]; | |
if (show != 1) | |
{ | |
insert_Node(dictionary, index, data); | |
index++; | |
} | |
} | |
show = 0; | |
} | |
else | |
{ | |
data = prev + prev[0]; | |
insert_Node(dictionary, index, data); | |
index++; | |
show = 1; | |
result += data; | |
} | |
} | |
return result; | |
} | |
} |
Hi Majed,
I keep receiving segmentation fault for decompression:
Compression./lz_all Hi I'm Alpha ^_^ , Code Expo's assistant, I'm here to help you. ------------------------------------------------------------------------------- This tool generate compression and decompression using LZ-77, LZ-78 and LZW methods : 1- LZ-77 2- LZ-78 3- LZW Enter 1, 2 or 3 according to method. > 1 sh: 1: cls: not found Hi I'm Alpha ^_^ , Code Expo's assistant, I'm here to help you. ------------------------------------------------------------------------------- This tool generate compression and decompression using LZ-77 method : 1- Compression 2- Decompression 0- Main menu Enter 1, 2 or 0 according to method. > 1 sh: 1: cls: not found Hi I'm Alpha ^_^ , Code Expo's assistant, I'm here to help you. ------------------------------------------------------------------------------- LZ-77 > Compression : Enter your phrases : test jabuka Final result : 0,0,t 0,0,e 0,0,s 3,1, 0,0,j 0,0,a 0,0,b 0,0,u 0,0,k 4,1, Enter 0 to back to Main menu or 1 to back to Method menu.
Decompression
./lz_all Hi I'm Alpha ^_^ , Code Expo's assistant, I'm here to help you. ------------------------------------------------------------------------------- This tool generate compression and decompression using LZ-77, LZ-78 and LZW methods : 1- LZ-77 2- LZ-78 3- LZW Enter 1, 2 or 3 according to method. > 1 sh: 1: cls: not found Hi I'm Alpha ^_^ , Code Expo's assistant, I'm here to help you. ------------------------------------------------------------------------------- This tool generate compression and decompression using LZ-77 method : 1- Compression 2- Decompression 0- Main menu Enter 1, 2 or 0 according to method. > 2 sh: 1: cls: not found Hi I'm Alpha ^_^ , Code Expo's assistant, I'm here to help you. ------------------------------------------------------------------------------- LZ-77 > Decompression : Note : Enter 0 for NULL characters Enter your code : 0,0,t 0,0,e 0,0,s 3,1, 0,0,j 0,0,a 0,0,b 0,0,u 0,0,k 4,1 Segmentation fault (core dumped)
Can you provide some instructions for usage?
Thanks
#########################
Sorry for making you wait. I update code, it runs perfectly now.
#########################
Final result : 0,0,t 0,0,e 0,0,s 3,1,0 0,0,j 0,0,a 0,0,b 0,0,u 0,0,k 4,1,0
Enter 0 to back to Main menu or 1 to back to Method menu.
1
sh: 1: cls: not found
Hi I'm Alpha ^_^ , Code Expo's assistant, I'm here to help you.
This tool generate compression and decompression using LZ-77 method :
1- Compression
2- Decompression
0- Main menu
Enter 1, 2 or 0 according to method.
2
sh: 1: cls: not found
Hi I'm Alpha ^_^ , Code Expo's assistant, I'm here to help you.
LZ-77 > Decompression :
Enter your code : 0,0,t 0,0,e 0,0,s 3,1,0 0,0,j 0,0,a 0,0,b 0,0,u 0,0,k 4,1,0
Final result : test jabuka
Enter 0 to back to Main menu or 1 to back to Method menu.
Thank you soo much
for (int i = 0; i < length; ++i) 294 line must be for (int i = 0; i < 3; ++i)
same 305 for (int i = 0; i < length; ++i)
It simply does not work. segmentation fault without reason happens too common.
Hi Majed,
I keep receiving segmentation fault for decompression:
Compression
Decompression
Can you provide some instructions for usage?
Thanks