Class: Omnizip::Algorithms::Zstandard::HuffmanEncoder

Inherits:
Object
  • Object
show all
Includes:
Constants
Defined in:
lib/omnizip/algorithms/zstandard/huffman_encoder.rb

Overview

Huffman Encoder for Zstandard (RFC 8878 Section 4.2)

Encodes literals using Huffman coding with FSE-compressed weights.

Constant Summary

Constants included from Constants

Constants::BLOCK_HEADER_SIZE, Constants::BLOCK_MAX_SIZE, Constants::BLOCK_TYPE_COMPRESSED, Constants::BLOCK_TYPE_RAW, Constants::BLOCK_TYPE_RESERVED, Constants::BLOCK_TYPE_RLE, Constants::BUFFER_SIZE, Constants::DEFAULT_LEVEL, Constants::DEFAULT_REPEAT_OFFSETS, Constants::FSE_MAX_ACCURACY_LOG, Constants::FSE_MIN_ACCURACY_LOG, Constants::HUFFMAN_MAX_BITS, Constants::HUFFMAN_MAX_CODE_LENGTH, Constants::HUFFMAN_MAX_LOG, Constants::HUFFMAN_STANDARD_TABLE_SIZE, Constants::LITERALS_BLOCK_COMPRESSED, Constants::LITERALS_BLOCK_RAW, Constants::LITERALS_BLOCK_RLE, Constants::LITERALS_BLOCK_TREELESS, Constants::LITERALS_LENGTH_ACCURACY_LOG, Constants::LITERAL_LENGTH_TABLE, Constants::MAGIC_BYTES, Constants::MAGIC_NUMBER, Constants::MATCH_LENGTH_ACCURACY_LOG, Constants::MATCH_LENGTH_TABLE, Constants::MAX_LEVEL, Constants::MIN_LEVEL, Constants::MODE_FSE, Constants::MODE_PREDEFINED, Constants::MODE_REPEAT, Constants::MODE_RLE, Constants::OFFSET_ACCURACY_LOG, Constants::PREDEFINED_LL_DISTRIBUTION, Constants::PREDEFINED_ML_DISTRIBUTION, Constants::PREDEFINED_OFFSET_DISTRIBUTION, Constants::REPEAT_OFFSET_1, Constants::REPEAT_OFFSET_2, Constants::REPEAT_OFFSET_3, Constants::SKIPPABLE_MAGIC_BASE, Constants::SKIPPABLE_MAGIC_MASK, Constants::WINDOW_LOG_MAX, Constants::WINDOW_LOG_MIN

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(code_lengths, codes, max_bits) ⇒ HuffmanEncoder

Initialize Huffman encoder

Parameters:

  • code_lengths (Array<Integer>) —

    Code lengths

  • codes (Hash<Integer, Integer>) —

    Symbol to code mapping

  • max_bits (Integer) —

    Maximum code length



223
224
225
226
227
228
229
230
231
232
233
234
235
236
 
# File 'lib/omnizip/algorithms/zstandard/huffman_encoder.rb', line 223

def initialize(code_lengths, codes, max_bits)
  @code_lengths = code_lengths
  @codes = codes
  @max_bits = max_bits

  # Build reverse lookup for encoding
  @symbol_code = {}
  @symbol_length = {}

  codes.each do |symbol, code|
    @symbol_code[symbol] = code
    @symbol_length[symbol] = code_lengths[symbol]
  end
end

Instance Attribute Details

#code_lengths ⇒ Array<Integer> (readonly)

Returns Code lengths for each symbol.

Returns:

  • (Array<Integer>) —

    Code lengths for each symbol



33
34
35
 
# File 'lib/omnizip/algorithms/zstandard/huffman_encoder.rb', line 33

def code_lengths
  @code_lengths
end

#codes ⇒ Hash<Integer, Integer> (readonly)

Returns Symbol to code mapping.

Returns:

  • (Hash<Integer, Integer>) —

    Symbol to code mapping



36
37
38
 
# File 'lib/omnizip/algorithms/zstandard/huffman_encoder.rb', line 36

def codes
  @codes
end

#max_bits ⇒ Integer (readonly)

Returns Maximum code length.

Returns:

  • (Integer) —

    Maximum code length



39
40
41
 
# File 'lib/omnizip/algorithms/zstandard/huffman_encoder.rb', line 39

def max_bits
  @max_bits
end

Class Method Details

.assign_lengths(node, depth, code_lengths, max_bits) ⇒ Object

Recursively assign code lengths to symbols



129
130
131
132
133
134
135
136
137
138
139
140
141
142
 
# File 'lib/omnizip/algorithms/zstandard/huffman_encoder.rb', line 129

def self.assign_lengths(node, depth, code_lengths, max_bits)
  return unless node

  depth = [depth, max_bits].min

  if node[:symbol]
    # Leaf node
    code_lengths[node[:symbol]] = depth.positive? ? depth : 1
  else
    # Internal node
    assign_lengths(node[:left], depth + 1, code_lengths, max_bits)
    assign_lengths(node[:right], depth + 1, code_lengths, max_bits)
  end
end

.build_canonical_codes(code_lengths) ⇒ Hash<Integer, Integer>

Build canonical Huffman codes from lengths

Parameters:

  • code_lengths (Array<Integer>) —

    Code lengths for each symbol

Returns:

  • (Hash<Integer, Integer>) —

    Symbol to code mapping



186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
 
# File 'lib/omnizip/algorithms/zstandard/huffman_encoder.rb', line 186

def self.build_canonical_codes(code_lengths)
  codes = {}
  return codes if code_lengths.nil? || code_lengths.empty?

  max_length = code_lengths.compact.max || 0
  return codes if max_length.zero?

  # Count symbols at each length
  bl_count = Array.new(max_length + 1, 0)
  code_lengths.each do |length|
    bl_count[length] += 1 if length&.positive?
  end

  # Calculate starting code for each length
  code = 0
  next_code = Array.new(max_length + 1, 0)
  (1..max_length).each do |bits|
    code = ((code + bl_count[bits - 1]) << 1)
    next_code[bits] = code
  end

  # Assign codes to symbols
  code_lengths.each_with_index do |length, symbol|
    next if length.nil? || length.zero?

    codes[symbol] = next_code[length]
    next_code[length] += 1
  end

  codes
end

.build_from_frequencies(frequencies, max_bits = HUFFMAN_MAX_BITS) ⇒ HuffmanEncoder

Build Huffman encoder from symbol frequencies

Parameters:

  • frequencies (Array<Integer>) —

    Symbol frequencies

  • max_bits (Integer) (defaults to: HUFFMAN_MAX_BITS) —

    Maximum code length (default 11)

Returns:



46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
# File 'lib/omnizip/algorithms/zstandard/huffman_encoder.rb', line 46

def self.build_from_frequencies(frequencies,
max_bits = HUFFMAN_MAX_BITS)
  return nil if frequencies.nil? || frequencies.empty?

  # Build Huffman tree and get code lengths
  code_lengths = build_huffman_lengths(frequencies, max_bits)

  # Limit code lengths to max_bits
  code_lengths = limit_code_lengths(code_lengths, max_bits)

  # Build canonical codes
  codes = build_canonical_codes(code_lengths)

  new(code_lengths, codes, max_bits)
end

.build_huffman_lengths(frequencies, max_bits) ⇒ Array<Integer>

Build Huffman code lengths using package-merge algorithm

Parameters:

  • frequencies (Array<Integer>) —

    Symbol frequencies

  • max_bits (Integer) —

    Maximum code length

Returns:

  • (Array<Integer>) —

    Code lengths



67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
 
# File 'lib/omnizip/algorithms/zstandard/huffman_encoder.rb', line 67

def self.build_huffman_lengths(frequencies, max_bits)
  return [] if frequencies.nil? || frequencies.empty?

  # Create list of (frequency, symbol) pairs
  symbols_with_freq = frequencies.each_with_index
    .select { |freq, _| freq&.positive? }
    .map { |freq, sym| [freq, sym] }

  return Array.new(frequencies.length, 0) if symbols_with_freq.empty?

  # Sort by frequency
  symbols_with_freq.sort_by! { |freq, _| freq }

  # Build Huffman tree
  code_lengths = Array.new(frequencies.length, 0)

  # Simple Huffman tree building
  # Using a priority queue approach
  build_tree_lengths(symbols_with_freq, code_lengths, max_bits)

  code_lengths
end

.build_tree_lengths(symbols_with_freq, code_lengths, max_bits) ⇒ Object

Build code lengths using tree approach



91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
 
# File 'lib/omnizip/algorithms/zstandard/huffman_encoder.rb', line 91

def self.build_tree_lengths(symbols_with_freq, code_lengths, max_bits)
  return if symbols_with_freq.empty?

  # Create leaf nodes
  nodes = symbols_with_freq.map do |freq, sym|
    { freq: freq, symbol: sym, left: nil, right: nil, depth: 0 }
  end

  # Build tree by combining nodes
  while nodes.length > 1
    # Sort by frequency
    nodes.sort_by! { |n| n[:freq] }

    # Combine two smallest
    left = nodes.shift
    right = nodes.shift

    combined = {
      freq: left[:freq] + right[:freq],
      symbol: nil,
      left: left,
      right: right,
      depth: [left[:depth], right[:depth]].max + 1,
    }

    nodes << combined
  end

  # Extract code lengths from tree
  if nodes.length == 1
    assign_lengths(nodes[0], 0, code_lengths, max_bits)
  elsif symbols_with_freq.length == 1
    # Single symbol
    code_lengths[symbols_with_freq[0][1]] = 1
  end
end

.limit_code_lengths(code_lengths, max_bits) ⇒ Array<Integer>

Limit code lengths to maximum

Uses the package-merge algorithm concept to limit lengths.

Parameters:

  • code_lengths (Array<Integer>) —

    Original code lengths

  • max_bits (Integer) —

    Maximum code length

Returns:

  • (Array<Integer>) —

    Limited code lengths



151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
 
# File 'lib/omnizip/algorithms/zstandard/huffman_encoder.rb', line 151

def self.limit_code_lengths(code_lengths, max_bits)
  return code_lengths if code_lengths.nil? || code_lengths.empty?

  # Check if any length exceeds max
  max_length = code_lengths.max || 0
  return code_lengths if max_length <= max_bits

  # Limit using a simple approach: cap at max_bits and adjust
  # This is a simplified implementation
  lengths = code_lengths.map { |l| [l, max_bits].min }

  # Ensure Kraft inequality is satisfied
  # Sum of 2^(-length) must be <= 1
  kraft_sum = lengths.sum { |l| l.positive? ? 1 << (max_bits - l) : 0 }
  max_kraft = 1 << max_bits

  if kraft_sum > max_kraft
    # Need to increase some lengths
    # This is simplified - a proper implementation would use package-merge
    lengths = redistribute_lengths(lengths, max_bits)
  end

  lengths
end

.redistribute_lengths(lengths, max_bits) ⇒ Object

Redistribute lengths to satisfy Kraft inequality



177
178
179
180
 
# File 'lib/omnizip/algorithms/zstandard/huffman_encoder.rb', line 177

def self.redistribute_lengths(lengths, max_bits)
  # Simplified: just cap at max_bits
  lengths.map { |l| [l, max_bits].min }
end

Instance Method Details

#encode(data) ⇒ String

Encode data using Huffman codes

Parameters:

  • data (String) —

    Data to encode

Returns:

  • (String) —

    Encoded bitstream



242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
 
# File 'lib/omnizip/algorithms/zstandard/huffman_encoder.rb', line 242

def encode(data)
  return "" if data.nil? || data.empty?

  bits = []

  data.each_byte do |byte|
    code = @symbol_code[byte]
    length = @symbol_length[byte]

    next unless code && length

    # Write bits MSB first
    length.times do |i|
      bit = (code >> (length - 1 - i)) & 1
      bits << bit
    end
  end

  # Convert bit array to bytes
  bits_to_bytes(bits)
end

#encode_table_description ⇒ String

Encode Huffman table description for Zstandard

Zstandard compresses Huffman weights using FSE.

Returns:

  • (String) —

    Encoded Huffman table description



269
270
271
272
273
274
275
276
277
278
279
 
# File 'lib/omnizip/algorithms/zstandard/huffman_encoder.rb', line 269

def encode_table_description
  # Convert code lengths to weights
  # Weight = max_bits - code_length + 1 (for non-zero lengths)
  weights = @code_lengths.map do |length|
    next 0 if length.nil? || length.zero?

    @max_bits - length + 1
  end

  encode_weights_fse(weights)
end