Class: Omnizip::Algorithms::BZip2::Bwt

Inherits:
Object
  • Object
show all
Defined in:
lib/omnizip/algorithms/bzip2/bwt.rb

Overview

Burrows-Wheeler Transform (BWT)

The BWT is a block-sorting compression algorithm that rearranges a character string into runs of similar characters. This transformation is reversible and forms the foundation of the BZip2 compression algorithm.

The transformation works by:

  1. Creating all rotations of the input string
  2. Sorting these rotations lexicographically
  3. Taking the last column of the sorted rotations
  4. Recording the row index of the original string

This groups similar characters together, making the data more compressible for subsequent stages (MTF, RLE, Huffman).

Instance Method Summary collapse

Instance Method Details

#build_lf_mapping(last_column) ⇒ Array<Integer>

Build LF (Last-to-First) mapping for BWT decode

For each position i in the sorted order (first column), LF tells us which position in the sorted order corresponds to the same character in the last column

Parameters:

  • last_column (String) —

    Last column (transformed data)

Returns:

  • (Array<Integer>) —

    LF mapping array



108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
 
# File 'lib/omnizip/algorithms/bzip2/bwt.rb', line 108

def build_lf_mapping(last_column)
  n = last_column.length

  # Count occurrences of each byte value
  counts = Array.new(256, 0)
  last_column.each_byte { |b| counts[b] += 1 }

  # Build cumulative counts (start position of each byte in sorted array)
  cumulative = Array.new(256, 0)
  sum = 0
  256.times do |i|
    cumulative[i] = sum
    sum += counts[i]
  end

  # Build the LF mapping
  # For each position in last column, find its position in first column
  lf = Array.new(n)
  occurrence = Array.new(256, 0) # Track which occurrence of each byte

  last_column.each_byte.with_index do |byte, i|
    # This byte's position in first column is:
    # cumulative[byte] + occurrence[byte]
    pos_in_first = cumulative[byte] + occurrence[byte]
    occurrence[byte] += 1

    # Now find which last column position corresponds to this first column position
    # We need the inverse: which last column index has this sorted position
    lf[pos_in_first] = i
  end

  lf
end

#decode(data, primary_index) ⇒ String

Decode data using reverse Burrows-Wheeler Transform

Parameters:

  • data (String) —

    Transformed data (last column)

  • primary_index (Integer) —

    Index of original string

Returns:

  • (String) —

    Original data



77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
 
# File 'lib/omnizip/algorithms/bzip2/bwt.rb', line 77

def decode(data, primary_index)
  return "".b if data.empty?

  # Build LF (Last-to-First) mapping
  # This maps each position in L to corresponding position in F
  lf = build_lf_mapping(data)

  # Reconstruct by following the LF chain
  result = []
  idx = primary_index

  data.length.times do
    # The first column is the sorted last column
    # Get the character at this position
    byte_val = data.bytes.sort[idx]
    result << byte_val
    # Follow LF mapping to next position
    idx = lf[idx]
  end

  result.pack("C*").b
end

#encode(data) ⇒ Array<String, Integer>

Encode data using Burrows-Wheeler Transform (optimized)

Parameters:

  • data (String) —

    Input data to transform

Returns:

  • (Array<String, Integer>) —

    Transformed data and primary idx



46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
# File 'lib/omnizip/algorithms/bzip2/bwt.rb', line 46

def encode(data)
  return ["".b, 0] if data.empty?

  n = data.length
  bytes = data.bytes

  # Build suffix array without creating rotation strings
  # Use direct byte comparison for efficiency
  suffix_array = (0...n).to_a

  # Sort using optimized comparison that avoids string allocation
  suffix_array.sort! do |a, b|
    compare_rotations(bytes, a, b, n)
  end

  # Find primary index (position where suffix starts at 0)
  primary_index = suffix_array.index(0)

  # Extract last column (character before each suffix)
  transformed = suffix_array.map do |idx|
    bytes[(idx - 1) % n]
  end.pack("C*").b

  [transformed, primary_index]
end