161-A2.2

From Microlab Classes
Jump to navigation Jump to search

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'