/*
=====================================================================
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 (JavaScript):
--------------------------------------
• Uses Map for O(1) average lookup.
• Uses Array for compact dictionary storage.
• Manual scanning avoids regex overhead.
• Uses efficient string concatenation via arrays + join().
• Clean, idiomatic, modern JavaScript 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: array + Map
// ---------------------------------------------------------------------
class WordDictionary {
constructor() {
this.words = []; // index → word
this.indexMap = new Map(); // word → index
}
}
// ---------------------------------------------------------------------
// Find or add a word to the dictionary (O(1) average)
// ---------------------------------------------------------------------
function findOrAdd(dict, word) {
if (dict.indexMap.has(word)) {
return dict.indexMap.get(word);
}
const newIndex = dict.words.length;
dict.words.push(word);
dict.indexMap.set(word, newIndex);
return newIndex;
}
// ---------------------------------------------------------------------
// Compress text into @ID tokens
// ---------------------------------------------------------------------
function compress(input, dict) {
const out = [];
let i = 0;
while (i < input.length) {
const c = input[i];
// Pass punctuation/spaces directly
if (!/[A-Za-z0-9]/.test(c)) {
out.push(c);
i++;
continue;
}
// Extract word
const start = i;
while (i < input.length && /[A-Za-z0-9]/.test(input[i])) {
i++;
}
const word = input.slice(start, i);
// Get dictionary index
const id = findOrAdd(dict, word);
// Write token
out.push(`@${id}`);
}
return out.join("");
}
// ---------------------------------------------------------------------
// Decompress @ID tokens back into original text
// ---------------------------------------------------------------------
function decompress(compressed, dict) {
const out = [];
let i = 0;
while (i < compressed.length) {
const c = compressed[i];
// Token?
if (c === "@") {
i++;
let id = 0;
// Parse digits
while (i < compressed.length && /[0-9]/.test(compressed[i])) {
id = id * 10 + (compressed.charCodeAt(i) - 48);
i++;
}
if (id >= 0 && id < dict.words.length) {
out.push(dict.words[id]);
}
} else {
// Pass punctuation/spaces
out.push(c);
i++;
}
}
return out.join("");
}
// ---------------------------------------------------------------------
// Main
// ---------------------------------------------------------------------
const original =
"this is is a test test compression string string test " +
"this is a test compression";
const dict = new WordDictionary();
const compressed = compress(original, dict);
const decompressed = decompress(compressed, dict);
console.log(`Original: "${original}"`);
console.log(`Compressed: "${compressed}"`);
console.log(`Decompressed: "${decompressed}"\n`);
console.log("Dictionary:");
dict.words.forEach((word, i) => {
console.log(` @${i} => ${word}`);
});
/*
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
*/
