Class: Omnizip::Algorithms::BZip2::Huffman

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

Overview

Huffman Coding for BZip2

Implements canonical Huffman coding for the final compression stage of BZip2. Huffman coding assigns variable-length codes to symbols based on their frequencies, with more frequent symbols getting shorter codes.

This implementation:

  1. Builds a Huffman tree from symbol frequencies
  2. Generates canonical codes for efficient decoding
  3. Encodes data as a bit stream
  4. Decodes bit streams back to symbols

Defined Under Namespace

Classes: Node

Instance Method Summary collapse

Instance Method Details

#build_tree(frequencies) ⇒ Node?

Build Huffman tree from frequency table

Parameters:

  • frequencies (Hash<Integer, Integer>) —

    Symbol => frequency

Returns:

  • (Node, nil) —

    Root node of Huffman tree



66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
 
# File 'lib/omnizip/algorithms/bzip2/huffman.rb', line 66

def build_tree(frequencies)
  return nil if frequencies.empty?

  # Create leaf nodes
  nodes = frequencies.map do |symbol, freq|
    Node.new(symbol, freq)
  end

  # Build tree bottom-up
  while nodes.length > 1
    # Sort by frequency
    nodes.sort_by!(&:frequency)

    # Take two lowest frequency nodes
    left = nodes.shift
    right = nodes.shift

    # Create parent node
    parent = Node.new(nil, left.frequency + right.frequency)
    parent.left = left
    parent.right = right

    # Add back to nodes
    nodes << parent
  end

  nodes.first
end

#decode(bits, root, length) ⇒ String

Decode bit stream using Huffman tree

Parameters:

  • bits (String) —

    Encoded bit stream

  • root (Node) —

    Root of Huffman tree

  • length (Integer) —

    Expected output length

Returns:

  • (String) —

    Decoded data



133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
 
# File 'lib/omnizip/algorithms/bzip2/huffman.rb', line 133

def decode(bits, root, length)
  return "".b if bits.empty? || root.nil?

  result = []
  current = root
  bit_string = bytes_to_bits(bits)
  bit_index = 0

  while result.length < length && bit_index < bit_string.length
    bit = bit_string[bit_index]
    bit_index += 1

    # Navigate tree
    current = (bit == "0" ? current.left : current.right)

    # Check if we reached a leaf
    if current.leaf?
      result << current.symbol
      current = root
    end
  end

  result.pack("C*")
end

#encode(data, codes) ⇒ String

Encode data using Huffman codes

Parameters:

  • data (String) —

    Input data to encode

  • codes (Hash<Integer, String>) —

    Symbol => binary code

Returns:

  • (String) —

    Encoded bit stream (as binary string)



112
113
114
115
116
117
118
119
120
121
122
123
124
125
 
# File 'lib/omnizip/algorithms/bzip2/huffman.rb', line 112

def encode(data, codes)
  return "".b if data.empty?

  bits = []

  data.each_byte do |byte|
    code = codes[byte]
    raise "No code for byte #{byte}" unless code

    bits << code
  end

  bits_to_bytes(bits.join)
end

#generate_codes(root) ⇒ Hash<Integer, String>

Generate code table from Huffman tree

Parameters:

  • root (Node) —

    Root of Huffman tree

Returns:

  • (Hash<Integer, String>) —

    Symbol => binary code



99
100
101
102
103
104
105
 
# File 'lib/omnizip/algorithms/bzip2/huffman.rb', line 99

def generate_codes(root)
  return {} if root.nil?

  codes = {}
  generate_codes_recursive(root, "", codes)
  codes
end