Difference between revisions of "161-A2.2"
Adrian Vidal (talk | contribs) |
Adrian Vidal (talk | contribs) |
||
Line 87: | Line 87: | ||
| <code>Decoder({'00':'e','01':'h','10':'y', '11':' '})</code> | | <code>Decoder({'00':'e','01':'h','10':'y', '11':' '})</code> | ||
| <code>'0100101101001011010010'</code> | | <code>'0100101101001011010010'</code> | ||
− | | <code>hey hey hey</code> | + | | <code>'hey hey hey'</code> |
|- | |- | ||
| <code>Decoder({'0':'hey','1':' '})</code> | | <code>Decoder({'0':'hey','1':' '})</code> | ||
| <code>'01010'</code> | | <code>'01010'</code> | ||
− | | <code>hey hey hey</code> | + | | <code>'hey hey hey'</code> |
|- | |- | ||
|} | |} |
Revision as of 07:25, 15 March 2021
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 0
s and 1
s only. You may assume in that the binary string is guaranteed to be decodable using the supplied decoder.
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'
|