#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <cctype>
#include <sstream>
/*
=====================================================================
High‑Performance Reversible Text Compression Using a Word Dictionary
---------------------------------------------------------------------
This program compresses text by replacing repeated words with tokens
like @0, @1, @2... and stores each unique word in a dictionary.
The compressed text is fully reversible.
WHY THIS VERSION IS FAST (C++17):
---------------------------------
• Uses std::unordered_map for O(1) average lookup.
• Uses std::vector for compact dictionary storage.
• Uses std::string_view for zero‑copy word extraction.
• Uses std::string with reserve() to avoid reallocations.
• Clean, idiomatic, modern C++ design.
OUTPUT EXAMPLE:
Original: this is is a test test compression string string test
Compressed: @0 @1 @1 @2 @3 @3 @4 @5 @5 @3
Decompressed: this is is a test test compression string string test
=====================================================================
*/
// ---------------------------------------------------------------------
// Dictionary structure: vector + hash table
// ---------------------------------------------------------------------
struct Dictionary {
std::vector<std::string> words; // index → word
std::unordered_map<std::string, int> indexMap; // word → index
};
// ---------------------------------------------------------------------
// Find or add a word to the dictionary (O(1) average)
// ---------------------------------------------------------------------
int findOrAdd(Dictionary &dict, std::string_view word) {
auto it = dict.indexMap.find(std::string(word));
if (it != dict.indexMap.end())
return it->second;
int newIndex = dict.words.size();
dict.words.emplace_back(word);
dict.indexMap[dict.words.back()] = newIndex;
return newIndex;
}
// ---------------------------------------------------------------------
// Compress text into @ID tokens
// ---------------------------------------------------------------------
std::string compress(const std::string &input, Dictionary &dict) {
std::string output;
output.reserve(input.size() * 2); // avoid reallocations
size_t i = 0;
while (i < input.size()) {
// Pass punctuation/spaces directly
if (!std::isalnum(static_cast<unsigned char>(input[i]))) {
output.push_back(input[i]);
i++;
continue;
}
// Extract word
size_t start = i;
while (i < input.size() && std::isalnum(static_cast<unsigned char>(input[i])))
i++;
std::string_view word(&input[start], i - start);
// Get dictionary index
int id = findOrAdd(dict, word);
// Write token
output += '@';
output += std::to_string(id);
}
return output;
}
// ---------------------------------------------------------------------
// Decompress @ID tokens back into original text
// ---------------------------------------------------------------------
std::string decompress(const std::string &compressed, const Dictionary &dict) {
std::string output;
output.reserve(compressed.size() * 2);
size_t i = 0;
while (i < compressed.size()) {
// Token?
if (compressed[i] == '@') {
i++;
int id = 0;
while (i < compressed.size() && std::isdigit(static_cast<unsigned char>(compressed[i]))) {
id = id * 10 + (compressed[i] - '0');
i++;
}
if (id >= 0 && id < static_cast<int>(dict.words.size())) {
output += dict.words[id];
}
}
else {
// Pass punctuation/spaces
output.push_back(compressed[i]);
i++;
}
}
return output;
}
// ---------------------------------------------------------------------
// Main
// ---------------------------------------------------------------------
int main() {
std::string original =
"this is is a test test compression string string test this is a test compression";
Dictionary dict;
std::string compressed = compress(original, dict);
std::string decompressed = decompress(compressed, dict);
std::cout << "Original: \"" << original << "\"\n";
std::cout << "Compressed: \"" << compressed << "\"\n";
std::cout << "Decompressed: \"" << decompressed << "\"\n\n";
std::cout << "Dictionary:\n";
for (size_t i = 0; i < dict.words.size(); i++)
std::cout << " @" << i << " => " << dict.words[i] << "\n";
}
/*
run:
Original: "this is is a test test compression string string test this is a test compression"
Compressed: "@0 @1 @1 @2 @3 @3 @4 @5 @5 @3 @0 @1 @2 @3 @4"
Decompressed: "this is is a test test compression string string test this is a test compression"
Dictionary:
@0 => this
@1 => is
@2 => a
@3 => test
@4 => compression
@5 => string
*/
