use std::collections::HashMap;
/*
=====================================================================
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 (Rust):
--------------------------------
• Uses HashMap<String, usize> for O(1) average lookup.
• Uses Vec<String> for compact dictionary storage.
• Manual scanning avoids regex overhead.
• Uses efficient String building via push_str().
• Clean, idiomatic, modern Rust design.
=====================================================================
*/
// ---------------------------------------------------------------------
// Dictionary structure: Vec + HashMap
// ---------------------------------------------------------------------
#[derive(Debug)]
struct WordDictionary {
words: Vec<String>, // index → word
index_map: HashMap<String, usize> // word → index
}
impl WordDictionary {
fn new() -> Self {
Self {
words: Vec::new(),
index_map: HashMap::new(),
}
}
}
// ---------------------------------------------------------------------
// Find or add a word to the dictionary (O(1) average)
// ---------------------------------------------------------------------
fn find_or_add(dict: &mut WordDictionary, word: &str) -> usize {
if let Some(&idx) = dict.index_map.get(word) {
return idx;
}
let new_index = dict.words.len();
dict.words.push(word.to_string());
dict.index_map.insert(word.to_string(), new_index);
new_index
}
// ---------------------------------------------------------------------
// Compress text into @ID tokens
// ---------------------------------------------------------------------
fn compress(input: &str, dict: &mut WordDictionary) -> String {
let mut out = String::with_capacity(input.len() * 2);
let chars: Vec<char> = input.chars().collect();
let mut i = 0;
while i < chars.len() {
let c = chars[i];
// Pass punctuation/spaces directly
if !c.is_ascii_alphanumeric() {
out.push(c);
i += 1;
continue;
}
// Extract word
let start = i;
while i < chars.len() && chars[i].is_ascii_alphanumeric() {
i += 1;
}
let word: String = chars[start..i].iter().collect();
// Get dictionary index
let id = find_or_add(dict, &word);
// Write token
out.push('@');
out.push_str(&id.to_string());
}
out
}
// ---------------------------------------------------------------------
// Decompress @ID tokens back into original text
// ---------------------------------------------------------------------
fn decompress(compressed: &str, dict: &WordDictionary) -> String {
let mut out = String::with_capacity(compressed.len() * 2);
let chars: Vec<char> = compressed.chars().collect();
let mut i = 0;
while i < chars.len() {
let c = chars[i];
// Token?
if c == '@' {
i += 1;
let mut id: usize = 0;
// Parse digits
while i < chars.len() && chars[i].is_ascii_digit() {
id = id * 10 + (chars[i] as usize - '0' as usize);
i += 1;
}
if id < dict.words.len() {
out.push_str(&dict.words[id]);
}
} else {
// Pass punctuation/spaces
out.push(c);
i += 1;
}
}
out
}
// ---------------------------------------------------------------------
// Main
// ---------------------------------------------------------------------
fn main() {
let original = "this is is a test test compression string string test \
this is a test compression";
let mut dict = WordDictionary::new();
let compressed = compress(original, &mut dict);
let decompressed = decompress(&compressed, &dict);
println!("Original: \"{}\"", original);
println!("Compressed: \"{}\"", compressed);
println!("Decompressed: \"{}\"\n", decompressed);
println!("Dictionary:");
for (i, w) in dict.words.iter().enumerate() {
println!(" @{} => {}", i, w);
}
}
/*
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
*/
