Class: Omnizip::Formats::Rar::Compression::LZ77Huffman::HuffmanBuilder

Inherits:
Object
  • Object
show all
Defined in:
lib/omnizip/formats/rar/compression/lz77_huffman/huffman_builder.rb

Overview

Huffman tree builder for dynamic compression

Builds canonical Huffman trees from symbol frequencies. Uses priority queue (heap) algorithm to construct optimal trees.

Responsibilities:

  • ONE responsibility: Build Huffman trees and generate codes
  • Collect symbol frequencies
  • Build optimal Huffman tree
  • Generate canonical Huffman codes
  • Calculate code lengths

Defined Under Namespace

Classes: Node

Constant Summary collapse

MAX_CODE_LENGTH = 
15

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ HuffmanBuilder

Returns a new instance of HuffmanBuilder.



40
41
42
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/huffman_builder.rb', line 40

def initialize
  @frequencies = Hash.new(0)
end

Instance Attribute Details

#frequencies ⇒ Object (readonly)

Returns the value of attribute frequencies.



38
39
40
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/huffman_builder.rb', line 38

def frequencies
  @frequencies
end

Instance Method Details

#add_symbol(symbol, count = 1) ⇒ void

This method returns an undefined value.

Add symbol occurrence(s)

Parameters:

  • symbol (Integer) —

    Symbol value

  • count (Integer) (defaults to: 1) —

    Number of occurrences



49
50
51
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/huffman_builder.rb', line 49

def add_symbol(symbol, count = 1)
  @frequencies[symbol] += count
end

#build_tree ⇒ Node?

Build Huffman tree from frequencies

Uses priority queue algorithm to build optimal tree. Returns root node of the tree.

Returns:

  • (Node, nil) —

    Root node or nil if empty



59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/huffman_builder.rb', line 59

def build_tree
  return nil if @frequencies.empty?

  if @frequencies.size == 1
    return Node.new(@frequencies.keys.first,
                    @frequencies.values.first)
  end

  # Create leaf nodes
  heap = @frequencies.map { |symbol, freq| Node.new(symbol, freq) }
  heap.sort_by!(&:frequency)

  # Build tree bottom-up
  while heap.size > 1
    left = heap.shift
    right = heap.shift

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

    # Insert maintaining heap property
    insert_into_heap(heap, parent)
  end

  heap.first
end

#code_lengths ⇒ Hash<Integer, Integer>

Get code lengths only (for header transmission)

Returns:

  • (Hash<Integer, Integer>) —

    symbol => length



113
114
115
116
117
118
119
120
121
122
123
124
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/huffman_builder.rb', line 113

def code_lengths
  root = build_tree
  return {} if root.nil?

  if root.leaf?
    return { root.symbol => 1 }
  end

  lengths = {}
  calculate_code_lengths(root, 0, lengths)
  lengths
end

#empty? ⇒ Boolean

Check if empty

Returns:

  • (Boolean) 


136
137
138
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/huffman_builder.rb', line 136

def empty?
  @frequencies.empty?
end

#generate_codes ⇒ Hash<Integer, Array(Integer, Integer)>

Generate canonical Huffman codes

Returns hash mapping symbols to [code, length] pairs. Codes are canonical (same-length codes are sequential).

Returns:

  • (Hash<Integer, Array(Integer, Integer)>) —

    symbol => [code, length]



93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/huffman_builder.rb', line 93

def generate_codes
  root = build_tree
  return {} if root.nil?

  # Handle single symbol case
  if root.leaf?
    return { root.symbol => [0, 1] }
  end

  # Calculate code lengths for each symbol
  code_lengths = {}
  calculate_code_lengths(root, 0, code_lengths)

  # Generate canonical codes from lengths
  generate_canonical_codes(code_lengths)
end

#reset ⇒ void

This method returns an undefined value.

Reset builder



129
130
131
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/huffman_builder.rb', line 129

def reset
  @frequencies.clear
end

#symbol_count ⇒ Integer

Get number of symbols

Returns:

  • (Integer) 


143
144
145
 
# File 'lib/omnizip/formats/rar/compression/lz77_huffman/huffman_builder.rb', line 143

def symbol_count
  @frequencies.size
end