"""
=====================================================================
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 (Python):
----------------------------------
• Uses dict for O(1) average lookup.
• Uses list for compact dictionary storage.
• Manual scanning avoids regex overhead.
• Uses Python's efficient string slicing.
• Clean, idiomatic, modern Python 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
=====================================================================
"""
# ---------------------------------------------------------------------
# Dictionary structure: list + dict
# ---------------------------------------------------------------------
class WordDictionary:
def __init__(self):
self.words = [] # index → word
self.index_map = {} # word → index
# ---------------------------------------------------------------------
# Find or add a word to the dictionary (O(1) average)
# ---------------------------------------------------------------------
def find_or_add(dict_obj: WordDictionary, word: str) -> int:
if word in dict_obj.index_map:
return dict_obj.index_map[word]
new_index = len(dict_obj.words)
dict_obj.words.append(word)
dict_obj.index_map[word] = new_index
return new_index
# ---------------------------------------------------------------------
# Compress text into @ID tokens
# ---------------------------------------------------------------------
def compress(text: str, dict_obj: WordDictionary) -> str:
out = []
i = 0
n = len(text)
while i < n:
c = text[i]
# Pass punctuation/spaces directly
if not c.isalnum():
out.append(c)
i += 1
continue
# Extract word
start = i
while i < n and text[i].isalnum():
i += 1
word = text[start:i]
# Get dictionary index
idx = find_or_add(dict_obj, word)
# Write token
out.append(f"@{idx}")
return "".join(out)
# ---------------------------------------------------------------------
# Decompress @ID tokens back into original text
# ---------------------------------------------------------------------
def decompress(compressed: str, dict_obj: WordDictionary) -> str:
out = []
i = 0
n = len(compressed)
while i < n:
c = compressed[i]
# Token?
if c == "@":
i += 1
idx = 0
# Parse digits
while i < n and compressed[i].isdigit():
idx = idx * 10 + (ord(compressed[i]) - ord("0"))
i += 1
if 0 <= idx < len(dict_obj.words):
out.append(dict_obj.words[idx])
else:
# Pass punctuation/spaces
out.append(c)
i += 1
return "".join(out)
# ---------------------------------------------------------------------
# Main
# ---------------------------------------------------------------------
if __name__ == "__main__":
original = (
"this is is a test test compression string string test "
"this is a test compression"
)
dict_obj = WordDictionary()
compressed = compress(original, dict_obj)
decompressed = decompress(compressed, dict_obj)
print(f'Original: "{original}"')
print(f'Compressed: "{compressed}"')
print(f'Decompressed: "{decompressed}"\n')
print("Dictionary:")
for i, w in enumerate(dict_obj.words):
print(f" @{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
"""
