Question

How to perform high‑performance reversible text compression using a word dictionary in Ruby

Answer 1

#
# =====================================================================
# 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 (Ruby):
# --------------------------------
# • Uses Hash for O(1) average lookup.
# • Uses Array for compact dictionary storage.
# • Manual scanning avoids regex overhead.
# • Uses efficient string building via << operator.
# • Clean, idiomatic, modern Ruby design.
# =====================================================================
#

# ---------------------------------------------------------------------
# Dictionary structure: Array + Hash
# ---------------------------------------------------------------------
class WordDictionary
  attr_reader :words, :index_map

  def initialize
    @words = []            # index → word
    @index_map = {}        # word → index
  end
end

# ---------------------------------------------------------------------
# Find or add a word to the dictionary (O(1) average)
# ---------------------------------------------------------------------
def find_or_add(dict, word)
  if dict.index_map.key?(word)
    return dict.index_map[word]
  end

  new_index = dict.words.length
  dict.words << word
  dict.index_map[word] = new_index
  new_index
end

# ---------------------------------------------------------------------
# Compress text into @ID tokens
# ---------------------------------------------------------------------
def compress(input, dict)
  out = +""
  i = 0
  n = input.length

  while i < n
    c = input[i]

    # Pass punctuation/spaces directly
    unless c =~ /[A-Za-z0-9]/
      out << c
      i += 1
      next
    end

    # Extract word
    start = i
    i += 1 while i < n && input[i] =~ /[A-Za-z0-9]/
    word = input[start...i]

    # Get dictionary index
    id = find_or_add(dict, word)

    # Write token
    out << "@#{id}"
  end

  out
end

# ---------------------------------------------------------------------
# Decompress @ID tokens back into original text
# ---------------------------------------------------------------------
def decompress(compressed, dict)
  out = +""
  i = 0
  n = compressed.length

  while i < n
    c = compressed[i]

    # Token?
    if c == "@"
      i += 1
      id = 0

      # Parse digits
      while i < n && compressed[i] =~ /[0-9]/
        id = id * 10 + (compressed[i].ord - "0".ord)
        i += 1
      end

      out << dict.words[id] if id < dict.words.length
    else
      # Pass punctuation/spaces
      out << c
      i += 1
    end
  end

  out
end

# ---------------------------------------------------------------------
# Main
# ---------------------------------------------------------------------
original =
  "this is is a test test compression string string test " \
  "this is a test compression"

dict = WordDictionary.new

compressed   = compress(original, dict)
decompressed = decompress(compressed, dict)

puts "Original:      \"#{original}\""
puts "Compressed:    \"#{compressed}\""
puts "Decompressed:  \"#{decompressed}\"\n\n"

puts "Dictionary:"
dict.words.each_with_index do |word, i|
  puts "  @#{i} => #{word}"
end



#
# 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
#

 

70+ SQL courses for beginners and professionals