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



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
141
142
 
# File 'lib/omnizip/algorithms/bzip2/bwt.rb', line 110

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



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

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. The first column
  # is the sorted last column — sort ONCE (the previous code
  # re-sorted inside the loop, making decode O(n^2 log n)).
  first_column = data.bytes.sort
  result = []
  idx = primary_index

  data.length.times do
    result << first_column[idx]
    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
71
72
73
 
# File 'lib/omnizip/algorithms/bzip2/bwt.rb', line 46

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

  n = data.length
  bytes = data.bytes

  # Doubled bytes: rotation a's byte at offset o is
  # dbl[a + o] — indexing needs no modulo, and comparisons
  # can run 8 bytes at a time (modulo arithmetic in the
  # comparator dominated the encoder's profile).
  dbl = bytes * 2

  # Build suffix array without creating rotation strings
  suffix_array = (0...n).to_a
  suffix_array.sort! do |a, b|
    compare_rotations(dbl, 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|
    dbl[n + idx - 1]
  end.pack("C*").b

  [transformed, primary_index]
end