#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define INITIAL_CAPACITY 16
/**
* Structure representing a Dictionary that maps unique words to integer indices.
*/
typedef struct {
char **words; // Array of dynamically allocated word strings
size_t count; // Current number of unique words stored
size_t capacity; // Allocated capacity of the dictionary array
} Dictionary;
/* Function prototypes */
Dictionary *dict_create(void);
int dict_find_or_add(Dictionary *dict, const char *word);
void dict_free(Dictionary *dict);
char *compress_string(const char *input, Dictionary *dict);
char *decompress_string(const char *compressed, const Dictionary *dict);
/**
* Creates and initializes a new empty Dictionary.
*/
Dictionary *dict_create(void) {
Dictionary *dict = malloc(sizeof(Dictionary));
if (!dict) return NULL;
dict->capacity = INITIAL_CAPACITY;
dict->count = 0;
dict->words = malloc(dict->capacity * sizeof(char *));
if (!dict->words) {
free(dict);
return NULL;
}
return dict;
}
/**
* Searches for a word in the dictionary.
* If found, returns its existing index.
* If not found, adds the word to the dictionary and returns the new index.
*/
int dict_find_or_add(Dictionary *dict, const char *word) {
for (size_t i = 0; i < dict->count; i++) {
if (strcmp(dict->words[i], word) == 0) {
return (int)i;
}
}
if (dict->count >= dict->capacity) {
size_t new_cap = dict->capacity * 2;
char **new_words = realloc(dict->words, new_cap * sizeof(char *));
if (!new_words) return -1;
dict->words = new_words;
dict->capacity = new_cap;
}
dict->words[dict->count] = strdup(word);
if (!dict->words[dict->count]) return -1;
return (int)(dict->count++);
}
/**
* Frees all memory allocated for the dictionary and its contained words.
*/
void dict_free(Dictionary *dict) {
if (!dict) return;
for (size_t i = 0; i < dict->count; i++) {
free(dict->words[i]);
}
free(dict->words);
free(dict);
}
/**
* Compresses a string by replacing unique words with dictionary tokens (e.g., @0, @1).
* Preserves non-alphanumeric punctuation and spacing intact.
*/
char *compress_string(const char *input, Dictionary *dict) {
if (!input || !dict) return NULL;
size_t out_capacity = strlen(input) + 64;
size_t out_len = 0;
char *output = malloc(out_capacity);
if (!output) return NULL;
output[0] = '\0';
const char *ptr = input;
while (*ptr != '\0') {
if (!isalnum((unsigned char)*ptr)) {
if (out_len + 2 >= out_capacity) {
out_capacity *= 2;
output = realloc(output, out_capacity);
}
output[out_len++] = *ptr++;
output[out_len] = '\0';
continue;
}
const char *word_start = ptr;
while (*ptr != '\0' && isalnum((unsigned char)*ptr)) {
ptr++;
}
size_t word_len = (size_t)(ptr - word_start);
char temp_word[128] = "";
if (word_len >= sizeof(temp_word)) word_len = sizeof(temp_word) - 1;
memcpy(temp_word, word_start, word_len);
temp_word[word_len] = '\0';
int word_id = dict_find_or_add(dict, temp_word);
char token[32] = "";
int token_len = snprintf(token, sizeof(token), "@%d", word_id);
if (out_len + (size_t)token_len >= out_capacity) {
out_capacity = (out_len + (size_t)token_len) * 2;
output = realloc(output, out_capacity);
}
memcpy(output + out_len, token, (size_t)token_len);
out_len += (size_t)token_len;
output[out_len] = '\0';
}
return output;
}
/**
* Decompresses a tokenized string (@0, @1, ...) using the provided Dictionary.
* Reconstructs the original text by substituting tokens back into words.
*/
char *decompress_string(const char *compressed, const Dictionary *dict) {
if (!compressed || !dict) return NULL;
size_t out_capacity = strlen(compressed) * 2 + 64;
size_t out_len = 0;
char *decompressed = malloc(out_capacity);
if (!decompressed) return NULL;
decompressed[0] = '\0';
const char *ptr = compressed;
while (*ptr != '\0') {
// Step 1: Detect token start indicator '@' followed by digits
if (*ptr == '@' && isdigit((unsigned char)*(ptr + 1))) {
ptr++; // Skip '@'
// Parse token index
int index = 0;
while (isdigit((unsigned char)*ptr)) {
index = index * 10 + (*ptr - '0');
ptr++;
}
// Look up corresponding word from dictionary
if (index >= 0 && (size_t)index < dict->count) {
const char *word = dict->words[index];
size_t word_len = strlen(word);
// Resize buffer if word exceeds current allocation
if (out_len + word_len >= out_capacity) {
out_capacity = (out_len + word_len) * 2;
decompressed = realloc(decompressed, out_capacity);
}
memcpy(decompressed + out_len, word, word_len);
out_len += word_len;
decompressed[out_len] = '\0';
}
} else {
// Step 2: Pass non-token characters (spaces, punctuation) through directly
if (out_len + 2 >= out_capacity) {
out_capacity *= 2;
decompressed = realloc(decompressed, out_capacity);
}
decompressed[out_len++] = *ptr++;
decompressed[out_len] = '\0';
}
}
return decompressed;
}
int main(void) {
const char *original = "this is is a test test compression string string test this is a test compression";
Dictionary *dict = dict_create();
if (!dict) {
fprintf(stderr, "Failed to initialize dictionary.\n");
return EXIT_FAILURE;
}
char *compressed = compress_string(original, dict);
if (compressed) {
size_t orig_size = strlen(original);
size_t comp_size = strlen(compressed);
printf("Original String : \"%s\"\n", original);
printf("Original Size : %zu bytes\n\n", orig_size);
printf("Dictionary Mapping:\n");
for (size_t i = 0; i < dict->count; i++) {
printf(" [@%zu] => %s\n", i, dict->words[i]);
}
printf("\nCompressed String: \"%s\"\n", compressed);
printf("Compressed Size : %zu bytes\n", comp_size);
printf("Space Reduction : %.2f%%\n\n",
(1.0 - ((double)comp_size / (double)orig_size)) * 100.0);
// Print original text decompressed from the token stream
char *decompressed = decompress_string(compressed, dict);
if (decompressed) {
printf("Decompressed Text: \"%s\"\n", decompressed);
free(decompressed);
}
free(compressed);
}
dict_free(dict);
return EXIT_SUCCESS;
}
/*
run:
Original String : "this is is a test test compression string string test this is a test compression"
Original Size : 80 bytes
Dictionary Mapping:
[@0] => this
[@1] => is
[@2] => a
[@3] => test
[@4] => compression
[@5] => string
Compressed String: "@0 @1 @1 @2 @3 @3 @4 @5 @5 @3 @0 @1 @2 @3 @4"
Compressed Size : 44 bytes
Space Reduction : 45.00%
Decompressed Text: "this is is a test test compression string string test this is a test compression"
*/
