Created
April 21, 2023 14:57
-
-
Save sor4chi/bf78cb5867f72d7620d672eba2508765 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <stdio.h> | |
| // Define a struct to represent an LZ77 code | |
| struct LZ77 { | |
| int pos; // position of the longest match in the input string | |
| int len; // length of the match | |
| char next; // next character in the input string after the match | |
| }; | |
| // Encode the input string using the LZ77 algorithm | |
| // and store the resulting codes in the lz77 array | |
| // Return the number of codes generated | |
| int lz77_encode(char *str, struct LZ77 *lz77) { | |
| int i, j, k, l, m, n; | |
| int max_len, max_pos; | |
| int len, pos; | |
| int count = 0; | |
| // Loop through each character in the input string | |
| for (i = 0; str[i] != '\0'; i++) { | |
| max_len = 0; | |
| max_pos = 0; | |
| // Search for the longest match in the input string | |
| // that occurs before the current character | |
| for (j = 0; j < i; j++) { | |
| len = 0; | |
| pos = i - j; | |
| for (k = 0; k < 18; k++) { | |
| if (str[i + k] == str[j + k]) { | |
| len++; | |
| } else { | |
| break; | |
| } | |
| } | |
| // If the length of the match is greater than 2, | |
| // generate a new LZ77 code and store it in the lz77 array | |
| if (len > max_len) { | |
| max_len = len; | |
| max_pos = pos; | |
| } | |
| } | |
| if (max_len > 2) { | |
| lz77[count].pos = max_pos; | |
| lz77[count].len = max_len; | |
| lz77[count].next = str[i + max_len]; | |
| i += max_len - 1; | |
| count++; | |
| } else { | |
| // Otherwise, generate a special LZ77 code that represents a literal character | |
| lz77[count].pos = 0; | |
| lz77[count].len = 0; | |
| lz77[count].next = str[i]; | |
| count++; | |
| } | |
| } | |
| return count; | |
| } | |
| // Decode the LZ77 codes and store the resulting string in the str array | |
| // Return the length of the resulting string | |
| int lz77_decode(struct LZ77 *lz77, int count, char *str) { | |
| int i, j, k; | |
| int pos, len; | |
| int index = 0; | |
| // Loop through each LZ77 code in the lz77 array | |
| for (i = 0; i < count; i++) { | |
| pos = lz77[i].pos; | |
| len = lz77[i].len; | |
| // If the code represents a literal character, copy it to the output string | |
| if (pos == 0) { | |
| str[index] = lz77[i].next; | |
| index++; | |
| } else { | |
| // Otherwise, copy a sequence of characters from the output string | |
| // that corresponds to the longest match in the input string | |
| for (j = 0; j < len; j++) { | |
| str[index] = str[index - pos]; | |
| index++; | |
| } | |
| // Then copy the next character in the input string | |
| str[index] = lz77[i].next; | |
| index++; | |
| } | |
| } | |
| // Add a null terminator to the output string | |
| str[index] = '\0'; | |
| return index; | |
| } | |
| int main() { | |
| char str[100] = "abracadabraabracadabraabracadabraabracadabraabracadabraabracadabra"; | |
| struct LZ77 lz77[100]; | |
| int count; | |
| int i; | |
| // Encode the input string and print out the resulting codes | |
| count = lz77_encode(str, lz77); | |
| for (i = 0; i < count; i++) { | |
| printf("%d %d %c\n", lz77[i].pos, lz77[i].len, lz77[i].next); | |
| } | |
| printf("\n"); | |
| // Decode the codes and print out the resulting string | |
| lz77_decode(lz77, count, str); | |
| printf("%s\n", str); | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment