using System;
using System.Collections.Generic;
using System.Text;
/*
=====================================================================
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#):
------------------------------
• Uses Dictionary<string,int> for O(1) average lookup.
• Uses List<string> for compact dictionary storage.
• Uses StringBuilder for efficient string construction.
• Manual scanning avoids regex overhead.
• 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
=====================================================================
*/
class WordDictionary
{
public List<string> Words = new List<string>(); // index → word
public Dictionary<string, int> IndexMap = new Dictionary<string, int>(); // word → index
}
class Program
{
// -----------------------------------------------------------------
// Find or add a word to the dictionary (O(1) average)
// -----------------------------------------------------------------
static int FindOrAdd(WordDictionary dict, string word)
{
if (dict.IndexMap.TryGetValue(word, out int existing))
return existing;
int newIndex = dict.Words.Count;
dict.Words.Add(word);
dict.IndexMap[word] = newIndex;
return newIndex;
}
// -----------------------------------------------------------------
// Compress text into @ID tokens
// -----------------------------------------------------------------
static string Compress(string input, WordDictionary dict)
{
StringBuilder outText = new StringBuilder(input.Length * 2);
int i = 0;
while (i < input.Length)
{
char c = input[i];
// Pass punctuation/spaces directly
if (!char.IsLetterOrDigit(c)) {
outText.Append(c);
i++;
continue;
}
// Extract word
int start = i;
while (i < input.Length && char.IsLetterOrDigit(input[i]))
i++;
string word = input.Substring(start, i - start);
// Get dictionary index
int id = FindOrAdd(dict, word);
// Write token
outText.Append('@').Append(id);
}
return outText.ToString();
}
// -----------------------------------------------------------------
// Decompress @ID tokens back into original text
// -----------------------------------------------------------------
static string Decompress(string compressed, WordDictionary dict)
{
StringBuilder outText = new StringBuilder(compressed.Length * 2);
int i = 0;
while (i < compressed.Length)
{
char c = compressed[i];
// Token?
if (c == '@')
{
i++;
int id = 0;
// Parse digits
while (i < compressed.Length && char.IsDigit(compressed[i])) {
id = id * 10 + (compressed[i] - '0');
i++;
}
if (id >= 0 && id < dict.Words.Count)
outText.Append(dict.Words[id]);
}
else {
// Pass punctuation/spaces
outText.Append(c);
i++;
}
}
return outText.ToString();
}
// -----------------------------------------------------------------
// Main
// -----------------------------------------------------------------
static void Main()
{
string original =
"this is is a test test compression string string test " +
"this is a test compression";
WordDictionary dict = new WordDictionary();
string compressed = Compress(original, dict);
string decompressed = Decompress(compressed, dict);
Console.WriteLine($"Original: \"{original}\"");
Console.WriteLine($"Compressed: \"{compressed}\"");
Console.WriteLine($"Decompressed: \"{decompressed}\"\n");
Console.WriteLine("Dictionary:");
for (int i = 0; i < dict.Words.Count; i++)
Console.WriteLine($" @{i} => {dict.Words[i]}");
}
}
/*
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
*/
