Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
764 lines (638 sloc) 24.9 KB
"""
Code for compressing and decompressing using Huffman compression.
"""
from nodes import HuffmanNode, ReadNode
# ====================
# Helper functions for manipulating bytes
def get_bit(byte, bit_num):
""" Return bit number bit_num from right in byte.
@param int byte: a given byte
@param int bit_num: a specific bit number within the byte
@rtype: int
>>> get_bit(0b00000101, 2)
1
>>> get_bit(0b00000101, 1)
0
"""
return (byte & (1 << bit_num)) >> bit_num
def byte_to_bits(byte):
""" Return the representation of a byte as a string of bits.
@param int byte: a given byte
@rtype: str
>>> byte_to_bits(14)
'00001110'
"""
return "".join([str(get_bit(byte, bit_num))
for bit_num in range(7, -1, -1)])
def bits_to_byte(bits):
""" Return int represented by bits, padded on right.
@param str bits: a string representation of some bits
@rtype: int
>>> bits_to_byte("00000101")
5
>>> bits_to_byte("101") == 0b10100000
True
"""
return sum([int(bits[pos]) << (7 - pos)
for pos in range(len(bits))])
# ====================
# Functions for compression
def make_freq_dict(text):
""" Return a dictionary that maps each byte in text to its frequency.
@param bytes text: a bytes object
@rtype: dict{int,int}
>>> d = make_freq_dict(bytes([65, 66, 67, 66]))
>>> d == {65: 1, 66: 2, 67: 1}
True
>>> d = make_freq_dict(bytes([1, 1, 1]))
>>> d == {1: 3}
True
>>> d = make_freq_dict(bytes([1]))
>>> d == {1: 1}
True
"""
# Learned about bytes from http://saqif.me/a2_bytes
bytes_list = list(text)
freq_dict = {}
for i in bytes_list:
if i not in freq_dict:
freq_dict[i] = bytes_list.count(i)
return freq_dict
def huffman_tree(freq_dict):
""" Return the root HuffmanNode of a Huffman tree corresponding
to frequency dictionary freq_dict
@param dict(int,int) freq_dict: a frequency dictionary
@rtype: HuffmanNode
SOURCES
======
Read about priority queue implementation at https://saqif.me/a2_link1
Learned about Huffman Algorithm at http://saqif.me/a2_link2
>>> freq = {2: 6, 3: 4}
>>> t = huffman_tree(freq)
>>> result1 = HuffmanNode(None, HuffmanNode(3), HuffmanNode(2))
>>> result2 = HuffmanNode(None, HuffmanNode(2), HuffmanNode(3))
>>> t == result1 or t == result2
True
>>> freq = {1: 11}
>>> t = huffman_tree(freq)
>>> t == HuffmanNode(1)
True
>>> t = huffman_tree({})
>>> t == HuffmanNode()
True
>>> freq_dict = {'A':10, 'E': 15, 'I': 12, 'S': 3, 'T': 4, 'P': 13, 'G': 1}
>>> t = huffman_tree(freq_dict)
>>> result1 = HuffmanNode(None, HuffmanNode(None, \
HuffmanNode('I', None, None), HuffmanNode('P', None, None)), \
HuffmanNode(None, HuffmanNode('E', None, None), HuffmanNode(None, \
HuffmanNode(None, HuffmanNode('T', None, None), HuffmanNode(None, \
HuffmanNode('G', None, None), HuffmanNode('S', None, None))), \
HuffmanNode('A', None, None))))
>>> t == result1
True
"""
nodes = get_sorted_symbols(freq_dict)
while len(nodes) > 1:
node_1, node_2 = nodes.pop(), nodes.pop()
# new_node = tuple: (combined_frequency, new_HuffmanNode)
new_node = (node_1[0] + node_2[0],
HuffmanNode(None, node_1[1], node_2[1]))
nodes.append(new_node)
nodes.sort()
nodes = nodes[::-1]
# if len(nodes) != 0 and new_node[0] > nodes[-1][0]:
# nodes.insert(0, new_node)
# else:
# nodes.append(new_node)
return nodes[0][1] if len(nodes) > 0 else HuffmanNode()
def get_sorted_symbols(freq_d):
""" Return a list of tuples (frequency, HuffmanNode(symbol) for each
symbol in freq_d and sorted in descending order.
:param dict freq_d: Frequency dictionary
:return list:
>>> d = {'a':2, 'b':5, 'c':7}
>>> d = get_sorted_symbols(d)
>>> result = [(7, HuffmanNode('c', None, None)), \
(5, HuffmanNode('b', None, None)), (2, HuffmanNode('a', None, None))]
>>> d == result
True
>>> d = {'a':2, 'b':5, 'c':7}
>>> d = get_sorted_symbols(d)
>>> result = [(7, HuffmanNode('c', None, None)), \
(5, HuffmanNode('b', None, None)), (2, HuffmanNode('a', None, None))]
>>> d == result
True
"""
sorted_nodes = []
for key, val in freq_d.items():
sorted_nodes.append((val, HuffmanNode(key)))
sorted_nodes.sort()
# Return list of tuples, sorted with highest frequencies first.
return sorted_nodes[::-1]
def get_codes(tree):
""" Return a dict mapping symbols from tree rooted at HuffmanNode to codes.
@param HuffmanNode tree: a Huffman tree rooted at node 'tree'
@rtype: dict(int,str)
>>> tree = HuffmanNode(None, HuffmanNode(3), HuffmanNode(2))
>>> d = get_codes(tree)
>>> d == {3: "0", 2: "1"}
True
>>> tree = HuffmanNode(2)
>>> get_codes(tree)
{2: '1'}
>>> tree = huffman_tree({})
>>> get_codes(tree)
{}
>>> tree = huffman_tree({"a":5, "b":6, "c":4, "d":3, "e":4})
>>> d = get_codes(tree)
>>> d == {'e':'00', 'a':'01', 'b':'10', 'd':'110', 'c':'111'} or \
d == {'a':'01', 'c':'00', 'e':'111', 'b':'10', 'd':'110'}
True
>>> freq_dict = {'A':10, 'E': 15, 'I': 12, 'S': 3, 'T': 4, 'P': 13, 'G': 1}
>>> tree = huffman_tree(freq_dict)
>>> d = get_codes(tree)
>>> d == {'I': '00', 'P': '01', 'E': '10', 'A': '111', 'T': '1100', 'G': \
'11010', 'S': '11011'}
True
>>> tree = huffman_tree({0: 1, 1: 1})
>>> d = get_codes(tree)
>>> d == {0: '0', 1: '1'}
True
"""
def _generate_code_dict(root, prefix='', code_map=None):
# Private function.
# Function to traverse tree, and keep track of mutating code map.
code_map = {} if code_map is None else code_map
if root is None:
# Huffman Node is empty
return {}
elif root.symbol is None:
# Internal Node
_generate_code_dict(root.left, prefix + '0', code_map)
_generate_code_dict(root.right, prefix + '1', code_map)
elif root.symbol is not None:
# Symbol
prefix = prefix if prefix != '' else '1'
code_map.update({root.symbol: prefix})
else:
pass
return code_map
return _generate_code_dict(tree)
def number_nodes(tree):
""" Number internal nodes in tree according to postorder traversal;
start numbering at 0.
@param HuffmanNode tree: a Huffman tree rooted at node 'tree'
@rtype: NoneType
>>> left = HuffmanNode(None, HuffmanNode(3), HuffmanNode(2))
>>> right = HuffmanNode(None, HuffmanNode(9), HuffmanNode(10))
>>> tree = HuffmanNode(None, left, right)
>>> number_nodes(tree)
>>> tree.left.number
0
>>> tree.right.number
1
>>> tree.number
2
>>> freq_dict = {'A':10, 'E': 15, 'I': 12, 'S': 3, 'T': 4, 'P': 13, 'G': 1}
>>> tree = huffman_tree(freq_dict)
>>> number_nodes(tree)
>>> tree.left.number, tree.right.right.left.right.number, \
tree.right.right.left.number, tree.right.right.number, tree.right.number, \
tree.number
(0, 1, 2, 3, 4, 5)
>>> tree = huffman_tree({'a':5})
>>> number_nodes(tree)
>>> tree.number
0
>>> tree = huffman_tree({})
>>> number_nodes(tree)
>>> tree.number
0
"""
def _set_node_num(node, num=0):
# Traverse node post-order, and assign number property to internal nodes
# Start at num. Returns the number value of the last visited node + 1
if node is None:
pass
elif node.symbol is None:
# Internal Node
num = _set_node_num(node.left, num) - 1
num = _set_node_num(node.right, num)
node.number = num
else:
# Leaf. Possibly Tree with one symbol
pass
return num + 1
left_nodes = _set_node_num(tree.left, -1)
right_nodes = _set_node_num(tree.right, left_nodes - 1)
tree.number = right_nodes
def avg_length(tree, freq_dict):
""" Return the number of bits per symbol required to compress text
made of the symbols and frequencies in freq_dict, using the Huffman tree.
@param HuffmanNode tree: a Huffman tree rooted at node 'tree'
@param dict(int,int) freq_dict: frequency dictionary
@rtype: float
>>> freq = {3: 2, 2: 7, 9: 1}
>>> left = HuffmanNode(None, HuffmanNode(3), HuffmanNode(2))
>>> right = HuffmanNode(9)
>>> tree = HuffmanNode(None, left, right)
>>> avg_length(tree, freq)
1.9
"""
bits_needed, codes_dict = [], get_codes(tree)
for symbol in codes_dict:
bits_needed.append(len(codes_dict[symbol]) * freq_dict[symbol])
# Return sum of bits_needed / sum of frequencies
return sum(bits_needed) / sum([i for i in list(freq_dict.values())])
def generate_compressed(text, codes):
""" Return compressed form of text, using mapping in codes for each symbol.
@param bytes text: a bytes object
@param dict(int,str) codes: mappings from symbols to codes
@rtype: bytes
>>> d = {0: "0", 1: "10", 2: "11"}
>>> text = bytes([1, 2, 1, 0])
>>> result = generate_compressed(text, d)
>>> [byte_to_bits(byte) for byte in result]
['10111000']
>>> text = bytes([1, 2, 1, 0, 2])
>>> result = generate_compressed(text, d)
>>> [byte_to_bits(byte) for byte in result]
['10111001', '10000000']
>>> text = bytes([0, 0, 0, 2, 1, 1])
>>> codes = {2: '00', 1: '01', 0: '1'}
>>> result = generate_compressed(text, codes)
>>> [byte_to_bits(byte) for byte in result]
['11100010', '10000000']
"""
text_list, bits_builder, bits, cursor = list(text), '', [], 0
for i in text_list:
bits_builder += codes[i]
# Append every 8 characters to bits list.
# Learned chunking technique from http://saqif.me/a2_link5
while cursor < len(bits_builder):
bits.append(bits_builder[cursor: cursor + 8])
cursor += 8
return bytes([bits_to_byte(i) for i in bits])
def tree_to_bytes(tree):
""" Return a bytes representation of the tree rooted at tree.
@param HuffmanNode tree: a Huffman tree rooted at node 'tree'
@rtype: bytes
The representation should be based on the postorder traversal of tree
internal nodes, starting from 0.
Precondition: tree has its nodes numbered.
>>> tree = HuffmanNode(None, HuffmanNode(3), HuffmanNode(2))
>>> number_nodes(tree)
>>> list(tree_to_bytes(tree))
[0, 3, 0, 2]
>>> left = HuffmanNode(None, HuffmanNode(3), HuffmanNode(2))
>>> right = HuffmanNode(5)
>>> tree = HuffmanNode(None, left, right)
>>> number_nodes(tree)
>>> list(tree_to_bytes(tree))
[0, 3, 0, 2, 1, 0, 0, 5]
"""
result = b""
if not tree.left.is_leaf():
result += tree_to_bytes(tree.left)
if not tree.right.is_leaf():
result += tree_to_bytes(tree.right)
if tree.left.is_leaf():
result += bytes([0, tree.left.symbol])
else:
result += bytes([1, tree.left.number])
if tree.right.is_leaf():
result += bytes([0, tree.right.symbol])
else:
result += bytes([1, tree.right.number])
return result
def size_to_bytes(size):
""" Return the size as a bytes object.
@param int size: a 32-bit integer that we want to convert to bytes
@rtype: bytes
>>> list(size_to_bytes(300))
[44, 1, 0, 0]
"""
# little-endian representation of 32-bit (4-byte)
# int size
return size.to_bytes(4, "little")
def compress(in_file, out_file):
""" Compress contents of in_file and store results in out_file.
@param str in_file: input file whose contents we want to compress
@param str out_file: output file, where we store our compressed result
@rtype: NoneType
"""
with open(in_file, "rb") as f1:
text = f1.read()
freq = make_freq_dict(text)
tree = huffman_tree(freq)
codes = get_codes(tree)
number_nodes(tree)
print("Bits per symbol:", avg_length(tree, freq))
result = (num_nodes_to_bytes(tree) + tree_to_bytes(tree) +
size_to_bytes(len(text)))
result += generate_compressed(text, codes)
with open(out_file, "wb") as f2:
f2.write(result)
def num_nodes_to_bytes(tree):
""" Return number of nodes required to represent tree (the root of a
numbered Huffman tree).
@param HuffmanNode tree: a Huffman tree rooted at node 'tree'
@rtype: bytes
"""
return bytes([tree.number + 1])
# ====================
# Functions for decompression
def generate_tree_general(node_lst, root_index):
""" Return the root of the Huffman tree corresponding
to node_lst[root_index].
The function assumes nothing about the order of the nodes in the list.
@param list[ReadNode] node_lst: a list of ReadNode objects
@param int root_index: index in the node list
@rtype: HuffmanNode
>>> lst = [ReadNode(0, 5, 0, 7), ReadNode(0, 10, 0, 12), \
ReadNode(1, 1, 1, 0)]
>>> generate_tree_general(lst, 2)
HuffmanNode(None, HuffmanNode(None, HuffmanNode(10, None, None), \
HuffmanNode(12, None, None)), \
HuffmanNode(None, HuffmanNode(5, None, None), HuffmanNode(7, None, None)))
>>> lst = [ReadNode(0, 1, 0, 2), ReadNode(0, 3, 0, 6), \
ReadNode(0, 4, 0, 5), ReadNode(1, 0, 1, 1), ReadNode(1, 2, 1, 3)]
>>> generate_tree_general(lst, 4)
HuffmanNode(None, HuffmanNode(None, HuffmanNode(4, None, None), \
HuffmanNode(5, None, None)), HuffmanNode(None, HuffmanNode(None, \
HuffmanNode(1, None, None), HuffmanNode(2, None, None)), \
HuffmanNode(None, HuffmanNode(3, None, None), HuffmanNode(6, None, None))))
"""
root_node = node_lst[root_index]
# Set left and right nodes, so else statements won't be needed.
left, right = HuffmanNode(root_node.l_data), HuffmanNode(root_node.r_data)
if root_node.l_type == 1:
# Branch
left = generate_tree_general(node_lst, root_node.l_data)
if root_node.r_type == 1:
# Branch
right = generate_tree_general(node_lst, root_node.r_data)
return HuffmanNode(None, left, right)
def generate_uncompressed(tree, text, size):
""" Use Huffman tree to decompress size bytes from text.
@param HuffmanNode tree: a HuffmanNode tree rooted at 'tree'
@param bytes text: text to decompress
@param int size: how many bytes to decompress from text.
@rtype: bytes
"""
def _symbols_dict(codes_dict):
d = {}
for code in codes_dict:
d[codes_dict[code]] = code
return d
all_codes, symbols_dict, i, remaining = get_codes(tree), {}, 0, ""
symbols_dict, result = _symbols_dict(all_codes), []
for x in range(size):
for y in symbols_dict:
if len(y) > len(remaining) and i < len(text):
remaining += byte_to_bits(text[i])
i += 1
if remaining[:len(y)] == y:
result.append(symbols_dict[y])
remaining = remaining[len(y):]
break
return bytes(result)
# def generate_uncompressed(tree, text, size):
# """ Use Huffman tree to decompress size bytes from text.
#
# @param HuffmanNode tree: a HuffmanNode tree rooted at 'tree'
# @param bytes text: text to decompress
# @param int size: how many bytes to decompress from text.
# @rtype: bytes
#
# >>> t = HuffmanNode(None, HuffmanNode(None, HuffmanNode(3), \
# HuffmanNode(None, HuffmanNode(1), HuffmanNode(4))), HuffmanNode(None,\
# HuffmanNode(2), HuffmanNode(5)))
# >>> text = bytes([216, 0])
# >>> size = 4
# >>> b = generate_uncompressed(t, text, size)
# >>> list(b) == [5, 4, 3, 3]
# True
# >>> t = HuffmanNode(None, HuffmanNode(None, HuffmanNode(1), \
# HuffmanNode(None, HuffmanNode(2), HuffmanNode(3))), HuffmanNode(None, \
# HuffmanNode(4), HuffmanNode(5)))
# >>> text = bytes([216, 0])
# >>> size = 4
# >>> result = generate_uncompressed(t, text, size)
# >>> result == bytes([5, 3, 1, 1])
# True
# """
# if size < 1500000:
# # More efficient to handle this without recursion.
# return _generate_uncompressed_small(tree, text, size)
# else:
# bits, prcsd, symbol_list = '', {}, []
# for byte in text:
# bits += byte_to_bits(byte)
# bit_list, prev, dead_end = list(bits), [], False
# while len(symbol_list) < size and len(bit_list) > 0 \
# and not dead_end:
# traverse_tree(tree, bit_list, symbol_list, prev, prcsd)
# if symbol_list[-1] is None:
# # bits have lead to an internal node. Another set of
# # bits are required to move further. Flag a dead end.
# symbol_list.pop()
# bits = ''.join(prev)
# dead_end = True
# else:
# # Reset bits and prev lists
# bits = ''
# del prev[:]
# return bytes(symbol_list)
def _generate_uncompressed_small(tree, text, size):
# Does the same thing as generate_uncompressed, but without recursion.
# More efficient for smaller sizes.
bits, symbol_list, not_in_lst = '', [], []
beg, end, codes = 0, 0, get_codes(tree)
rev_d = reverse_dict(codes)
seen = {}
# Gather all bytes in string form
for byte in text:
bits += byte_to_bits(byte)
# Starting at the beginning, walk through string and find symbols.
while len(symbol_list) < size:
bit_part = bits[beg:end + 1]
if bit_part in seen or bit_part not in not_in_lst and bit_part in rev_d:
seen[bit_part] = rev_d[bit_part]
symbol_list.append(rev_d[bit_part])
beg += len(bit_part)
end = beg
else:
# Keep track of the codes that were not found, so they aren't
# searched for again.
not_in_lst.append(bit_part)
end += 1
return bytes(symbol_list)
def traverse_tree(tree, bit_list, symbol_list, prev, processed):
""" Traverse tree using bits, and add the symbols found, to symbol_list.
:param HuffmanNode tree:
:param list bit_list: Bits for traversal
:param list symbol_list: List to hold symbols.
:param list prev: The previous bit/s that was traversed
:param dict processed: Dict of previously processed symbols
:return None:
>>> bit_list, symbol_list, prev, prcsd = ['0'], [], [], {}
>>> tree = HuffmanNode(None, HuffmanNode(2), HuffmanNode(3))
>>> traverse_tree(tree, bit_list, symbol_list, prev, prcsd)
>>> symbol_list
[2]
>>> bit_list, symbol_list, prev, prscd = ['0', '0'], [], [], {}
>>> tree = HuffmanNode(None, HuffmanNode(None, HuffmanNode(4, None, None), \
HuffmanNode(5, None, None)), HuffmanNode(None, HuffmanNode(None, \
HuffmanNode(1, None, None), HuffmanNode(2, None, None)), \
HuffmanNode(None, HuffmanNode(3, None, None), HuffmanNode(6, None, None))))
>>> traverse_tree(tree, bit_list, symbol_list, prev, prscd)
>>> symbol_list
[4]
>>> bit_list, symbol_list, prev, prcsd = ['1', '1', '0'], [], [], {}
>>> traverse_tree(tree, bit_list, symbol_list, prev, prcsd)
>>> symbol_list
[3]
>>> bit_list, symbol_list, prev, prscd = ['1', '0', '1', '0'], [], [], {}
>>> traverse_tree(tree, bit_list, symbol_list, prev, prscd)
>>> symbol_list
[2]
"""
bit = bit_list[0] if bit_list else ''
path = ''.join(prev)
if tree.symbol is not None:
# Return symbol and leftover bits
symbol_list.append(tree.symbol)
processed[path] = tree.symbol
elif bit == '1':
next_move = bit_list.pop(0)
# Go right
prev.append(next_move)
path += next_move
# try/except blocks less costly than if/else
try:
symbol_list.append(processed[path])
except KeyError:
traverse_tree(tree.right, bit_list, symbol_list, prev, processed)
elif bit == '0':
next_move = bit_list.pop(0)
# Go left
prev.append(next_move)
path += next_move
try:
symbol_list.append(processed[path])
except KeyError:
traverse_tree(tree.left, bit_list, symbol_list, prev, processed)
elif bit == '':
symbol_list.append(None)
else:
pass
def reverse_dict(dict_):
""" Return a dictionary of values to keys from dict_.
Precondition: No two keys in dict_ should map to the same value!
Otherwise, occurances after the first will be ignored!
:param dict dict_: Dictionary to reverse
:return dict:
>>> d = {'a': 1, 'b': 2, 'c': 3}
>>> reverse_dict(d)
{1: 'a', 2: 'b', 3: 'c'}
>>> d = {'a': 1, 'b': 2, 'c': 1}
>>> reverse_dict(d)
{1: 'c', 2: 'b'}
"""
return {value: key for key, value in dict_.items()}
def bytes_to_nodes(buf):
""" Return a list of ReadNodes corresponding to the bytes in buf.
@param bytes buf: a bytes object
@rtype: list[ReadNode]
>>> bytes_to_nodes(bytes([0, 1, 0, 2]))
[ReadNode(0, 1, 0, 2)]
"""
lst = []
for i in range(0, len(buf), 4):
l_type = buf[i]
l_data = buf[i + 1]
r_type = buf[i + 2]
r_data = buf[i + 3]
lst.append(ReadNode(l_type, l_data, r_type, r_data))
return lst
def bytes_to_size(buf):
""" Return the size corresponding to the
given 4-byte little-endian representation.
@param bytes buf: a bytes object
@rtype: int
>>> bytes_to_size(bytes([44, 1, 0, 0]))
300
"""
return int.from_bytes(buf, "little")
def uncompress(in_file, out_file):
""" Uncompress contents of in_file and store results in out_file.
@param str in_file: input file to uncompress
@param str out_file: output file that will hold the uncompressed results
@rtype: NoneType
"""
with open(in_file, "rb") as f:
num_nodes = f.read(1)[0]
buf = f.read(num_nodes * 4)
node_lst = bytes_to_nodes(buf)
# use generate_tree_general or generate_tree_postorder here
tree = generate_tree_general(node_lst, num_nodes - 1)
size = bytes_to_size(f.read(4))
with open(out_file, "wb") as g:
text = f.read()
g.write(generate_uncompressed(tree, text, size))
# ====================
# Other functions
def improve_tree(tree, freq_dict):
""" Improve the tree as much as possible, without changing its shape,
by swapping nodes. The improvements are with respect to freq_dict.
@param HuffmanNode tree: Huffman tree rooted at 'tree'
@param dict(int,int) freq_dict: frequency dictionary
@rtype: NoneType
>>> left = HuffmanNode(None, HuffmanNode(99), HuffmanNode(100))
>>> right = HuffmanNode(None, HuffmanNode(101), \
HuffmanNode(None, HuffmanNode(97), HuffmanNode(98)))
>>> tree = HuffmanNode(None, left, right)
>>> freq = {97: 26, 98: 23, 99: 20, 100: 16, 101: 15}
>>> improve_tree(tree, freq)
>>> avg_length(tree, freq)
2.31
"""
# Create a list of symbols, sorted by their frequency in ascending order.
symbol_sort = get_sorted_symbols(freq_dict)
symbol_sort = [(i[0], i[1].symbol) for i in symbol_sort]
symbol_sort.sort()
inorder_replace(tree, symbol_sort)
def inorder_replace(tree, symbol_sort):
""" Traverse tree inorder, and each symbol with the last symbol in
symbol_sort.
:param HuffmanNode tree: Root of tree to traverse
:param list symbol_sort:
list of tuples (frequency, symbol). Sorted in decending order.
:return:
"""
if tree.symbol is not None:
# Internal node!
tree.symbol = symbol_sort.pop()[1]
else:
inorder_replace(tree.left, symbol_sort)
inorder_replace(tree.right, symbol_sort)
if __name__ == "__main__":
import python_ta
python_ta.check_all(config="huffman_pyta.txt")
import doctest
doctest.testmod()
import time
mode = input("Press c to compress or u to uncompress: ")
if mode == "c":
fname = input("File to compress: ")
start = time.time()
compress(fname, fname + ".huf")
print("compressed {} in {} seconds."
.format(fname, time.time() - start))
elif mode == "u":
fname = input("File to uncompress: ")
start = time.time()
uncompress(fname, fname + ".orig")
print("uncompressed {} in {} seconds."
.format(fname, time.time() - start))