Module: RubyLabs::BitLab

Defined in:
lib/bitlab.rb

Overview

BitLab

The BitLab module has definitions of classes and methods used in the projects for Chapter 7 of Explorations in Computing. The module has methods used to experiment with binary codes, including fixed-width codes and Huffman codes. Methods create messages by encoding strings, decode messages back to the original text, and run experiments that introduce errors into messages and test for errors with simple parity checks.

The file bitlab.rb also adds a method to the PriorityQueue class, which is defined in the top level RubyLabs module. The methods that insert and remove items have a “hook” that can be called called when when the queue is being displayed on the canvas. The update method defined here will move nodes of a Huffman tree around on the screen when they are removed from or added to the queue.

Defined Under Namespace

Classes: Code, HexCode, Message, Node, NodeCoords, NodeView, QueueView

Constant Summary collapse

@@unit =

Options for drawing trees on the canvas:

24
@@queueViewOptions =

pixels per “tree unit”

{
  :width => 42 * @@unit,
  :height => 15 * @@unit,
  :qy => 50,
  :qx => 50,
}
@@bitsDirectory =

Data directory for BitLab:

File.join(File.dirname(__FILE__), '..', 'data', 'huffman')

Instance Method Summary collapse

Instance Method Details

#assign_codes(tree, code = {}, prefix = Code.new(0,0)) ⇒ Object

Traverse a Huffman tree to make a Code object for each leaf node, returning the codes in a Hash object. When users call this method, they should pass only one argument (tree). On recursive calls the other two arguments will be the set of codes defined so far and the binary prefix for the path to the current node.

Users normally pass a tree to encode, which will call this method to make the code. The same tree should also be passed to decode to decode the message.

Example:

>> t = build_tree(f)
=> ( 1.000 ( A: 0.450 ) ( ... ) )
>> assign_codes(t)
=> {"A"=>0, "O"=>111, "E"=>101, "I"=>110, "U"=>100}

– :begin :assign_codes



298
299
300
301
302
303
304
305
306
 
# File 'lib/bitlab.rb', line 298

def assign_codes(tree, code = {}, prefix = Code.new(0,0))
  if tree.char != nil
    code[tree.char] = prefix
  else
    assign_codes(tree.left,  code, prefix + 0)
    assign_codes(tree.right, code, prefix + 1)
  end
  return code
end

#build_tree(f) ⇒ Object

Build a Huffane tree using frequencies in hash f (typically created by calling read_frequencies). The return value is a Node object that represents the root of the tree.

Example:

>> f = read_frequencies( :hvfreq )
=> {"A"=>0.45, "O"=>0.18, "E"=>0.12, "I"=>0.15, "U"=>0.1}
>> build_tree(f)
=> ( 1.000 ( A: 0.450 ) ( ... ) )

– :begin :build_tree



248
249
250
251
252
253
254
255
256
257
258
 
# File 'lib/bitlab.rb', line 248

def build_tree(f)
  pq = init_queue(f)

  while pq.length > 1
    n1 = pq.shift
    n2 = pq.shift
    pq << Node.combine(n1, n2)
  end

  return pq[0]
end

#decode(m, scheme) ⇒ Object

Decode a sequence of bits (represented by Message object m) using the specified decoding scheme.

Note: if the decoding scheme is not the same as the one used to create the message the results are unpredictable.

See also Message#decode, which generates a string using the coding scheme specified when the message was created. Message#decode always gives the right result – the point of this stand-alone decode method is to show what happens if the decoding scheme does not match the encoding scheme.

Example:

>> msg = encode("aloha", :ascii)
=> 01100001 01101100 01101111 01101000 01100001
>> decode(msg, :ascii)
=> "aloha"
>> decode(msg, :parity)
=> "?67??"



162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
 
# File 'lib/bitlab.rb', line 162

def decode(m, scheme)
  raise "not a message" unless m.class == Message  
  res = ""
  if scheme.class == Node
    res = huffman_decode(m, scheme)
  elsif scheme.class == Hash
    raise "packed decode not implemented"
  elsif scheme == :ascii
    m.array.each do |x|
      res << x.value.chr
    end
  elsif scheme == :parity
    m.array.each do |x|
      if x.even_parity?
        res << (x.value >> 1).chr
      elsif $KCODE[0] == ?U
        res << "\xe2\x80\xa2"
      else
        res << "?"
      end
    end
  else
    raise "unknown scheme: #{scheme}"
  end
  return res
end

#draw_node(node, x, y) ⇒ Object

:nodoc:



417
418
419
420
421
422
423
424
425
426
 
# File 'lib/bitlab.rb', line 417

def draw_node(node, x, y)   # :nodoc:
  return nil unless @@drawing
  opts = @@drawing.options
  d = @@unit
  circ = Canvas::Circle.new( x, y, d / 2, :fill => opts[:nodefill] )
  text = Canvas::Text.new( node.char, x, y, :anchor => :center )
  ftext = Canvas::Text.new( node.freq.to_s, x, y-d, {:font => opts[:freqfont].name, :anchor => :center} )
  node.drawing = NodeView.new(circ, text, ftext, nil, nil)
  node.coords = NodeCoords.new(x, y, x, 0, x, 0)
end

#draw_root(node, left, right) ⇒ Object

:nodoc:



402
403
404
405
406
407
408
409
410
411
412
413
414
415
 
# File 'lib/bitlab.rb', line 402

def draw_root(node, left, right)  # :nodoc:
  opts = @@drawing.options
  x = (left.coords.x + right.coords.x) / 2
  y = left.coords.y - 2 * @@unit
  draw_node(node, x, y)
  node.drawing.lseg = Canvas::Line.new(x, y, left.coords.x, left.coords.y)
  node.drawing.rseg = Canvas::Line.new(x, y, right.coords.x, right.coords.y)
  node.drawing.lseg.lower
  node.drawing.rseg.lower
  # [left, right].each do |desc|
  #   desc.drawing.ftext.delete
  #   desc.drawing.ftext = nil
  # end
end

#encode(s, type, opt = nil) ⇒ Object

Make a Message object for the characters in string s. The second parameter determines the code to use. It can be :ascii, :parity, a hash object that has code mappings for letters, or a Huffman tree. If a hash or tree is passed, the message type is set to :packed, otherwise it’s :unpacked. The encoding type is saved so it can be used later in decoding.

Example:

>> encode("atg", :ascii)
=> 01100001 01110100 01100111

>> nt_code
=> {"a"=>00, "c"=>10, "g"=>11, "t"=>01}
>> encode("atg", nt_code)
=> 000111



122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
 
# File 'lib/bitlab.rb', line 122

def encode(s, type, opt = nil)
  if (type.class == Hash || type.class == Node)
    code = (type.class == Node) ? assign_codes(type) : type
    msg = Message.new(:packed)
    s.each_byte do |ch|
      msg << code[ch.chr]
      printf("%s: %s\n", ch.chr, code[ch.chr]) if opt == :trace
    end
  else
    msg = Message.new(:unpacked)
    s.each_byte do |ch|
      code = ch.code(8)
      code.add_parity_bit if type == :parity
      msg << code
      printf("%s: %s\n", ch.chr, code) if opt == :trace
    end
  end
  return msg  
end

#garbled(m, n) ⇒ Object

Simulate noisy transmission of a message represented by a Message object m. Returns a copy of m after making n calls to the flip method (which changes a random bit in the message).

Example:

>> msg = encode("hola", :ascii)
=> 01101000 01101111 01101100 01100001
>> recvd = garbled(msg, 3)
=> 01001000 01000111 01101100 01100001
>> decode(recvd, :ascii)
=> "HGla"



201
202
203
204
205
206
207
208
 
# File 'lib/bitlab.rb', line 201

def garbled(m, n)
  res = m.copy
  n.times do
    c = res.array[ rand(res.array.length) ]
    c.flip( rand(c.length) )
  end
  return res
end

#huffman_decode(m, tree) ⇒ Object

Helper method used by decode and Message#decode: decode the binary codes in message m, using tree as a guide.



312
313
314
315
316
317
318
319
320
321
322
323
324
 
# File 'lib/bitlab.rb', line 312

def huffman_decode(m, tree)
  res = ""
  path = tree
  m.each_bit do |bit|
    if path.leaf?
      res << path.char
      path = tree
    end
    path = (bit == 0) ? path.left : path.right
  end
  res << path.char if path.leaf?
  return res
end

#init_queue(a) ⇒ Object

Helper method for build_tree: initialize a priority queue with Node objects for each letter in hash a, returning the queue as the result of the call.

Example:

>> f
=> {"A"=>0.45, "O"=>0.18, "E"=>0.12, "I"=>0.15, "U"=>0.1}
>> init_queue(f)
=> [( U: 0.100 ), ( E: 0.120 ), ( I: 0.150 ), ( O: 0.180 ), ( A: 0.450 )]

– :begin :init_queue



272
273
274
275
276
277
278
 
# File 'lib/bitlab.rb', line 272

def init_queue(a)
  q = PriorityQueue.new
  a.each do |x,f|
    q << Node.new(x,f)
  end
  return q
end

#make_codes(a) ⇒ Object

Make a unique binary code for each item in array a, returning a Hash that associates each item with a unique Code object. The codes are fixed-size binary codes, with a number of bits that depends on the number of items in a.

Example – make a 2-bit encoding for each of the 4 objects in this array:

>> nt_code = make_codes( ["a", "t", "c", "g"] )
=> {"a"=>00, "c"=>10, "g"=>11, "t"=>01}
>> nt_code["c"]
=> 10



59
60
61
62
63
64
65
66
 
# File 'lib/bitlab.rb', line 59

def make_codes(a)
  n = log2(a.length).ceil
  res = Hash.new
  a.each_with_index do |x,i|
    res[x] = i.code(n)
  end
  return res
end

#move_tree(tree, dx, dy) ⇒ Object

:nodoc:



386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
 
# File 'lib/bitlab.rb', line 386

def move_tree(tree, dx, dy)   # :nodoc:
  tree.coords.x += dx
  tree.coords.y += dy
  Canvas.move(tree.drawing.circle, dx, dy)
  Canvas.move(tree.drawing.text, dx, dy)
  Canvas.move(tree.drawing.ftext, dx, dy) if tree.drawing.ftext
  if tree.left
    Canvas.move(tree.drawing.lseg, dx, dy)
    move_tree(tree.left, dx, dy) 
  end
  if tree.right
    Canvas.move(tree.drawing.rseg, dx, dy)
    move_tree(tree.right, dx, dy)
  end
end

#print_codes(a, mode = :by_code) ⇒ Object

Print the codes in a, which should be an associative array made by make_codes or assign_codes, the method that creates binary codes for a Huffman tree.

An option specifies how to order the output, either :by_code (the default) or :by_name.

Example:

>> nt_code
=> {"a"=>00, "c"=>10, "g"=>11, "t"=>01}

>> print_codes(nt_code)
00  a
01  t
10  c
11  g
=> true

>> print_codes(nt_code, :by_name)
a  00
c  10
g  11
t  01
=> true



91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
 
# File 'lib/bitlab.rb', line 91

def print_codes(a, mode = :by_code)
  if mode == :by_code
    a.sort { |x,y| x[1] <=> y[1] }.each do |sym, code|
      printf "%s  %s\n", code, sym
    end
  elsif mode == :by_name
    width = a.keys.map{ |x| x.to_s.length }.max
    a.keys.sort { |x,y| x.to_s <=> y.to_s }.each do |x|
      printf "%-#{width}s  %s\n", x, a[x]
    end
  else
    raise "print_codes: mode must be :by_code or :by_name"
  end
  return true
end

#read_codes ⇒ Object

The data directory BitLabs has a file named “testcodes.txt” that contains a set of binary encodings of Hawaiian words. Call this method to read the encodings and return and an array of Message objects, one for each encoding. Users can try decoding the messages by hand before verifying their answer by passing them to decode. The messages are ordered from shortest to longest.

Example (assuming t is the Huffman tree for the full Hawaiian alphabet):

>> msgs = read_codes
=> [011010, ... 000101101100001100001011011000011011100110001011011100110001011010110011011010011110]
>> decode(msgs[-1], t)
=> "HUMUHUMUNUKUNUKUAPUA'A"



338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
 
# File 'lib/bitlab.rb', line 338

def read_codes
  codes = Array.new
  fn = File.join(@@bitsDirectory, "testcodes.txt")
  File.open(fn).each do |line|
    line.chomp!
    code = Code.new(0,0)
    line.each_byte do |byte|
      code << byte[0]                # add least significant digit of ASCII "0" or "1"
    end
    msg = Message.new(:packed)
    msg << code
    codes << msg
  end
  return codes
end

#read_frequencies(fn) ⇒ Object

Read letters and frequencies from file fn, save them in a hash indexed by letter name. The hash can be passed to build_tree, the method that creates a Huffman tree from a set of letter frequencies. If fn is a symbol it should be the name of one of the letter frequency files included with RubyLabs; if it’s a string is should be the name of a file in the current working directory.

Example:

>> read_frequencies( :hvfreq )
=> {"A"=>0.45, "O"=>0.18, "E"=>0.12, "I"=>0.15, "U"=>0.1}



220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
 
# File 'lib/bitlab.rb', line 220

def read_frequencies(fn)
  a = Hash.new
  if fn.class == Symbol
    fn = File.join(@@bitsDirectory, fn.to_s + ".txt")
  end
  File.open(fn).each do |line|
    line.chomp!
    next if line.length == 0
    next if line[0] == ?#
    x = line[/^./]
    f = line[/\d+\.\d+/].to_f
    a[x] = f
  end
  return a
end

#read_words ⇒ Object

The data directory for BitLabs has a file named “testwords.txt” with a few Hawaiian words. Call this method to read the file and return a list of strings for experiments with encoding Hawaiian words with a Huffman code.



358
359
360
361
362
 
# File 'lib/bitlab.rb', line 358

def read_words
  fn = File.join(@@bitsDirectory, "testwords.txt")
  words = File.open(fn).readlines
  return words.map { |x| x.chomp }
end

#view_queue(pq, userOptions = {}) ⇒ Object

Initialize the RubyLabs Canvas and draw a picture of priority queue pq. Future calls to the queue’s << and shift methods will update the drawing.



371
372
373
374
375
376
377
378
379
380
381
382
383
384
 
# File 'lib/bitlab.rb', line 371

def view_queue(pq, userOptions = {} )
  options = @@queueViewOptions.merge(userOptions)
  Canvas.init(options[:width], options[:height], "BitLab")
  @@drawing = QueueView.new(pq, options)
  options[:nodefill] = "lightgray"
  options[:freqfont] = Canvas::Font.new('freqfont', :family => 'Helvetica', :size => 10)
  pq.on_canvas = true
  x = options[:qx]
  pq.each_with_index do |node, i|
    draw_node(node, x, options[:qy])
    x += 3 * @@unit
  end
  return true    
end