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