/*
=====================================================================
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 (Scala):
---------------------------------
• Uses mutable.HashMap[String, Int] for O(1) average lookup.
• Uses ArrayBuffer[String] for compact dictionary storage.
• Manual scanning avoids regex overhead.
• Uses StringBuilder for efficient string construction.
• Clean, idiomatic, modern Scala design.
=====================================================================
*/
import scala.collection.mutable
import scala.collection.mutable.ArrayBuffer
// ---------------------------------------------------------------------
// Dictionary structure: ArrayBuffer + HashMap
// ---------------------------------------------------------------------
final class WordDictionary {
val words: ArrayBuffer[String] = ArrayBuffer.empty[String] // index → word
val indexMap: mutable.HashMap[String, Int] = mutable.HashMap.empty // word → index
}
// ---------------------------------------------------------------------
// Find or add a word to the dictionary (O(1) average)
// ---------------------------------------------------------------------
def findOrAdd(dict: WordDictionary, word: String): Int = {
dict.indexMap.get(word) match {
case Some(idx) => idx
case None =>
val newIndex = dict.words.length
dict.words += word
dict.indexMap.put(word, newIndex)
newIndex
}
}
// ---------------------------------------------------------------------
// Compress text into @ID tokens
// ---------------------------------------------------------------------
def compress(input: String, dict: WordDictionary): String = {
val out = new StringBuilder(input.length * 2)
var i = 0
val n = input.length
while (i < n) {
val c = input.charAt(i)
// Pass punctuation/spaces directly
if (!c.isLetterOrDigit) {
out.append(c)
i += 1
} else {
// Extract word
val start = i
while (i < n && input.charAt(i).isLetterOrDigit) {
i += 1
}
val word = input.substring(start, i)
// Get dictionary index
val id = findOrAdd(dict, word)
// Write token
out.append('@').append(id)
}
}
out.toString()
}
// ---------------------------------------------------------------------
// Decompress @ID tokens back into original text
// ---------------------------------------------------------------------
def decompress(compressed: String, dict: WordDictionary): String = {
val out = new StringBuilder(compressed.length * 2)
var i = 0
val n = compressed.length
while (i < n) {
val c = compressed.charAt(i)
// Token?
if (c == '@') {
i += 1
var id = 0
// Parse digits
while (i < n && compressed.charAt(i).isDigit) {
id = id * 10 + (compressed.charAt(i) - '0')
i += 1
}
if (id >= 0 && id < dict.words.length)
out.append(dict.words(id))
} else {
// Pass punctuation/spaces
out.append(c)
i += 1
}
}
out.toString()
}
// ---------------------------------------------------------------------
// Main
// ---------------------------------------------------------------------
object WordDictionaryCompression {
def main(args: Array[String]): Unit = {
val original =
"this is is a test test compression string string test " +
"this is a test compression"
val dict = new WordDictionary
val compressed = compress(original, dict)
val decompressed = decompress(compressed, dict)
println(s"""Original: "$original"""")
println(s"""Compressed: "$compressed"""")
println(s"""Decompressed: "$decompressed"""")
println()
println("Dictionary:")
dict.words.zipWithIndex.foreach { case (w, i) =>
println(s" @$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
*/
