import java.util.ArrayList;
import java.util.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 (Java):
--------------------------------
• Uses HashMap for O(1) average lookup.
• Uses ArrayList for compact dictionary storage.
• Uses StringBuilder for efficient string construction.
• Manual scanning avoids regex overhead.
• Clean, idiomatic, modern Java 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
=====================================================================
*/
public class WordDictionaryCompression {
// -----------------------------------------------------------------
// Dictionary structure: ArrayList + HashMap
// -----------------------------------------------------------------
static class Dictionary {
ArrayList<String> words = new ArrayList<>(); // index → word
HashMap<String, Integer> indexMap = new HashMap<>(); // word → index
}
// -----------------------------------------------------------------
// Find or add a word to the dictionary (O(1) average)
// -----------------------------------------------------------------
static int findOrAdd(Dictionary dict, String word) {
Integer existing = dict.indexMap.get(word);
if (existing != null)
return existing;
int newIndex = dict.words.size();
dict.words.add(word);
dict.indexMap.put(word, newIndex);
return newIndex;
}
// -----------------------------------------------------------------
// Compress text into @ID tokens
// -----------------------------------------------------------------
static String compress(String input, Dictionary dict) {
StringBuilder out = new StringBuilder(input.length() * 2);
int i = 0;
while (i < input.length()) {
char c = input.charAt(i);
// Pass punctuation/spaces directly
if (!Character.isLetterOrDigit(c)) {
out.append(c);
i++;
continue;
}
// Extract word
int start = i;
while (i < input.length() && Character.isLetterOrDigit(input.charAt(i)))
i++;
String word = input.substring(start, i);
// Get dictionary index
int id = findOrAdd(dict, word);
// Write token
out.append('@').append(id);
}
return out.toString();
}
// -----------------------------------------------------------------
// Decompress @ID tokens back into original text
// -----------------------------------------------------------------
static String decompress(String compressed, Dictionary dict) {
StringBuilder out = new StringBuilder(compressed.length() * 2);
int i = 0;
while (i < compressed.length()) {
char c = compressed.charAt(i);
// Token?
if (c == '@') {
i++;
int id = 0;
// Parse digits
while (i < compressed.length() && Character.isDigit(compressed.charAt(i))) {
id = id * 10 + (compressed.charAt(i) - '0');
i++;
}
if (id >= 0 && id < dict.words.size())
out.append(dict.words.get(id));
}
else {
// Pass punctuation/spaces
out.append(c);
i++;
}
}
return out.toString();
}
// -----------------------------------------------------------------
// Main
// -----------------------------------------------------------------
public static void main(String[] args) {
String original =
"this is is a test test compression string string test " +
"this is a test compression";
Dictionary dict = new Dictionary();
String compressed = compress(original, dict);
String decompressed = decompress(compressed, dict);
System.out.println("Original: \"" + original + "\"");
System.out.println("Compressed: \"" + compressed + "\"");
System.out.println("Decompressed: \"" + decompressed + "\"\n");
System.out.println("Dictionary:");
for (int i = 0; i < dict.words.size(); i++)
System.out.println(" @" + i + " => " + dict.words.get(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
*/
