package main
import (
"fmt"
"unicode"
)
/*
=====================================================================
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 (Go):
------------------------------
• Uses map[string]int for O(1) average lookup.
• Uses []string for compact dictionary storage.
• Manual scanning avoids regex overhead.
• Uses efficient string building via byte slices.
• Clean, idiomatic, modern Go design.
=====================================================================
*/
// ---------------------------------------------------------------------
// Dictionary structure: slice + map
// ---------------------------------------------------------------------
type WordDictionary struct {
Words []string // index → word
IndexMap map[string]int // word → index
}
// ---------------------------------------------------------------------
// Create a new dictionary
// ---------------------------------------------------------------------
func NewDictionary() *WordDictionary {
return &WordDictionary{
Words: make([]string, 0, 64),
IndexMap: make(map[string]int),
}
}
// ---------------------------------------------------------------------
// Find or add a word to the dictionary (O(1) average)
// ---------------------------------------------------------------------
func FindOrAdd(dict *WordDictionary, word string) int {
if idx, ok := dict.IndexMap[word]; ok {
return idx
}
newIndex := len(dict.Words)
dict.Words = append(dict.Words, word)
dict.IndexMap[word] = newIndex
return newIndex
}
// ---------------------------------------------------------------------
// Compress text into @ID tokens
// ---------------------------------------------------------------------
func Compress(input string, dict *WordDictionary) string {
out := make([]byte, 0, len(input)*2)
i := 0
n := len(input)
for i < n {
c := rune(input[i])
// Pass punctuation/spaces directly
if !unicode.IsLetter(c) && !unicode.IsDigit(c) {
out = append(out, input[i])
i++
continue
}
// Extract word
start := i
for i < n && (unicode.IsLetter(rune(input[i])) || unicode.IsDigit(rune(input[i]))) {
i++
}
word := input[start:i]
// Get dictionary index
id := FindOrAdd(dict, word)
// Write token
out = append(out, '@')
out = append(out, []byte(fmt.Sprintf("%d", id))...)
}
return string(out)
}
// ---------------------------------------------------------------------
// Decompress @ID tokens back into original text
// ---------------------------------------------------------------------
func Decompress(compressed string, dict *WordDictionary) string {
out := make([]byte, 0, len(compressed)*2)
i := 0
n := len(compressed)
for i < n {
c := compressed[i]
// Token?
if c == '@' {
i++
id := 0
// Parse digits
for i < n && unicode.IsDigit(rune(compressed[i])) {
id = id*10 + int(compressed[i]-'0')
i++
}
if id >= 0 && id < len(dict.Words) {
out = append(out, dict.Words[id]...)
}
} else {
// Pass punctuation/spaces
out = append(out, c)
i++
}
}
return string(out)
}
// ---------------------------------------------------------------------
// Main
// ---------------------------------------------------------------------
func main() {
original := "this is is a test test compression string string test " +
"this is a test compression"
dict := NewDictionary()
compressed := Compress(original, dict)
decompressed := Decompress(compressed, dict)
fmt.Printf("Original: \"%s\"\n", original)
fmt.Printf("Compressed: \"%s\"\n", compressed)
fmt.Printf("Decompressed: \"%s\"\n\n", decompressed)
fmt.Println("Dictionary:")
for i, w := range dict.Words {
fmt.Printf(" @%d => %s\n", 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
*/
