/*
=====================================================================
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 (Swift):
---------------------------------
• Uses [String:Int] Dictionary for O(1) average lookup.
• Uses [String] Array for compact dictionary storage.
• Manual scanning avoids regex overhead.
• Uses StringBuilder‑style building via String.append.
• Clean, idiomatic, modern Swift design.
=====================================================================
*/
import Foundation
// ---------------------------------------------------------------------
// Dictionary structure: Array + Dictionary
// ---------------------------------------------------------------------
struct WordDictionary {
var words: [String] = [] // index → word
var indexMap: [String: Int] = [:] // word → index
}
// ---------------------------------------------------------------------
// Find or add a word to the dictionary (O(1) average)
// ---------------------------------------------------------------------
func findOrAdd(dict: inout WordDictionary, word: String) -> Int {
if let existing = dict.indexMap[word] {
return existing
}
let newIndex = dict.words.count
dict.words.append(word)
dict.indexMap[word] = newIndex
return newIndex
}
// ---------------------------------------------------------------------
// Compress text into @ID tokens
// ---------------------------------------------------------------------
func compress(_ input: String, dict: inout WordDictionary) -> String {
var out = ""
let chars = Array(input)
var i = 0
while i < chars.count {
let c = chars[i]
// Pass punctuation/spaces directly
if !c.isLetter && !c.isNumber {
out.append(c)
i += 1
continue
}
// Extract word
let start = i
while i < chars.count && (chars[i].isLetter || chars[i].isNumber) {
i += 1
}
let word = String(chars[start..<i])
// Get dictionary index
let id = findOrAdd(dict: &dict, word: word)
// Write token
out.append("@\(id)")
}
return out
}
// ---------------------------------------------------------------------
// Decompress @ID tokens back into original text
// ---------------------------------------------------------------------
func decompress(_ compressed: String, dict: WordDictionary) -> String {
var out = ""
let chars = Array(compressed)
var i = 0
while i < chars.count {
let c = chars[i]
// Token?
if c == "@" {
i += 1
var id = 0
// Parse digits
while i < chars.count, let digit = chars[i].wholeNumberValue {
id = id * 10 + digit
i += 1
}
if id >= 0 && id < dict.words.count {
out.append(dict.words[id])
}
} else {
// Pass punctuation/spaces
out.append(c)
i += 1
}
}
return out
}
// ---------------------------------------------------------------------
// Main
// ---------------------------------------------------------------------
let original =
"this is is a test test compression string string test " +
"this is a test compression"
var dict = WordDictionary()
let compressed = compress(original, dict: &dict)
let decompressed = decompress(compressed, dict: dict)
print("Original: \"\(original)\"")
print("Compressed: \"\(compressed)\"")
print("Decompressed: \"\(decompressed)\"\n")
print("Dictionary:")
for (i, w) in dict.words.enumerated() {
print(" @\(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
*/
