161-A2.2

Prefix-free codes are codes in which no codeword is a prefix of another codeword. This restriction allows for instantaneous decoding. In this exercise, you will be using a decoder implementation using a binary tree as its internal representation. We highly encourage you to understand how the code works before writing the solution. This exercise will appear in your submission bin after passing Exercise 1.

Exercise 2.1. Prefix-free codes (5 points)

Task description

In this task, you will recover messages which were encoded using a prefix-free code. You are given an implementation of a Decoder object, which is constructed via a dictionary mapping binary strings to symbols. Internally, the Decoder is implemented as a binary tree where each "left turn" corresponds to 0 and each "right turn" corresponds to a 1. For thie exercise, you need to write a function prefix_free_decode which will take a Decoder object and a binary string consisting of 0s and 1s only. You may assume in that the binary string is guaranteed to be decodable using the supplied decoder.

Note that in the interest of conciseness and readability, the script below may not be the fastest way to implement prefix-free decoders.

Python test script for execution

Header	class Node: def __init__(self, symbol=None): self.left = None self.right = None self.data = symbol def __del__(self): if self.left is not None: del self.left if self.right is not None: del self.right del self.data def insert(self, bitstring, symbol): if bitstring == '': self.data = symbol elif bitstring[0] == '0': if self.left is None: self.left = Node() self.left.insert(bitstring[1:], symbol) elif bitstring[0] == '1': if self.right is None: self.right = Node() self.right.insert(bitstring[1:], symbol) class Decoder: def __init__(self, symbol_map): self.root = Node() for (bit_string, symbol) in symbol_map.items(): self.root.insert(bit_string, symbol) def __del__(self): del self.root
Student submission (function only)	def prefix_free_decode(decoder, bit_string): # your code.. # more code.. return ans }
Main test script	# Main test script goes here, and will not be visible to students. # The script will test if the submitted code does the prescribed functionality. # For successfully validated scripts, test results will be sent via email.

Sample input

Decoder argument	str argument	Return value
test_decoder	'0100101111000111101111101111001010111001001010011100110000'	'sugar and spice'
test_decoder	'111000101111100001011000001001001110101101111111001011011000111111000000'	'and everything nice'
Decoder({'00':'e','01':'h','10':'y', '11':' '})	'0100101101001011010010'	'hey hey hey'
Decoder({'0':'hey','1':' '})	'01010'	'hey hey hey'

In the table, define test_decoder as follows

key

'v'

'y'

't'

'a'

'u'

'i'

'e'

'n'

'c'

's'

'd'

'h'

'g'

'p'

'r'

' '

value

'10010'

'10011'

'10100'

'1110'

'10101'

'1111'

'000'

'001'

'0100'

'0101'

'0110'

'10110'

'0111'

'10111'

'1000'

'110'